PROOF-NUMBER SEARCH

Proof-number search (pn-search) is designed for finding the game-theoretical value in game trees. It is based on ideas derived from conspiracy-number search and its variants, such as applied cn-search and alphabeta-cn search. While in cn-search the purpose is to continue searching until it is unlikely that the minimax value of the root will change, pn-search aims at proving the true value of the root. Therefore, pn-search does not consider interim minimax values. Pn-search selects the next node to be expanded using two criteria: the potential range of subtree values and the number of nodes which must conspire to prove or disprove that range of potential values. These two criteria enable pn-search to treat efficiently game trees with a non-uniform branching factor. It is shown that in non-uniform trees pn-search outperforms other types of search, such as alpha-beta iterative-deepening search, even when enhanced with transposition tables, move ordering for the full principal variation, etc. Pn-search has been used to establish the game-theoretical values of Connect-Four, Qubic, and Go-Moku. There pn-search was able to find a forced win for the player to move first. The experiments described here are in the domain of Awari, a game which has not yet been solved. The experiments are repeatable for other games with a non-uniform branching factor. This article describes the underlying principles of pn-search, presents an appropriate implementation, and provides an analysis of its strengths and weaknesses.