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.