Proof-number search
Proof Number search ( short: PN- search) or proof number search is a game tree search algorithm, which was invented by Victor Allis, originally to solve the Games four wins and Qubic. Applications are mainly the final solution and sub-goals during the game.
For the application of the algorithm is a binary target is defined (for example, players at the train wins ) and the game tree in an and-or tree transformed. This is easily possible by maximizing nodes are considered as an OR node and minimizing node as an AND node (See minimax algorithm).
Numbers for the proof ( proof numbers) and rebuttal ( Widerlegzahlen ) of nodes ( proof and disproof numbers ) are routed to the node and updated during the search. They are defined as the lower bound of the still -expanding nodes in order to achieve a proof or disproof.
By selecting the most demonstrative and most irrefutable node for the next expansion an efficient search is generated.
Because of the high number of nodes generated the PN search is limited by the available memory. However, there are variations that can loosen this limitation and to assess much more positions, eg PN ^ 2, PDS - PN.