PROOF-NUMBER SEARCH

Proof-number search (pn-search) is designed for finding the game-theor etical value in game trees. It is based on ideas derived from conspira cy-number search and its variants, such as applied cn-search and alpha beta-cn search. While in cn-search the purpose is to continue searchin g 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-s earch does not consider interim minimax values. Pn-search selects the next node to be expanded using two criteria: the potential range of su btree values and the number of nodes which must conspire to prove or d isprove that range of potential values. These two criteria enable pn-s earch to treat efficiently game trees with a non-uniform branching fac tor. 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 pr incipal variation, etc. Pn-search has been used to establish the game- theoretical values of Connect-Four, Qubic, and Go-Moku. There pn-searc h was able to find a forced win for the player to move first. The expe riments described here are in the domain of Awari, a game which has no t 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.