Probability based Proof Number Search
Zhang Song, Hiroyuki Iida, H. van den Herik · 2019
Probability based proof number search (PPN-search) is a game tree search algorithm improved from proof number search (PN-search) (Allis et al., 1994), with applications in solving games or endgame positions. PPN-search uses one indicator named “probability based proof number” (PPN) to indicate the “probability” of proving a node. The PPN of a leaf node is derived from Monte-Carlo evaluations. The PPN of an internal node is backpropagated from its children following AND/OR probability rules. For each iteration, PPN-search selects the child with the maximum PPN at OR nodes and minimum PPN at AND nodes. This holds from the root to a leaf. The resultant node is considered to be the most proving node for expansion. In this paper, we investigate the performance of PPN-search on P-game trees (Kocsis and Szepesvari, 2006) and compare our results with those from other game solvers such as MCPN-search (Saito et al., 2006), PN-search, the UCT solver (Winands et al., 2008), and the pure MCTS solver (Winands et al., 2008). The experimental results show that (1) PPN-search takes less time and fewer iterations to solve a P-game tree on average, and (2) the error rate of selecting a correct solution decreases faster and more smoothly as the iteration number increases.