Proof-number search
Encyclopedia
Proof-number search is a game tree
search algorithm
invented by Victor Allis
, with applications mostly in endgame solvers, but also for sub-goals during games.
Using a binary goal (e.g. first player wins the game), game trees of two-person perfect-information games can be mapped to an and–or tree. Maximizing nodes become OR-nodes, minimizing nodes are mapped to AND-nodes. For all nodes proof and disproof numbers are stored, and updated during the search.
The proof and disproof numbers represent lower bounds on the number of nodes to be evaluated to prove (or disprove) certain nodes. By always selecting the most proving (disproving) node to expand, an efficient search is generated.
Some variants of the like PN2, PDS-PN have been developed to address the quite big memory
requirements of the algorithm.
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
invented by Victor Allis
Victor Allis
Louis Victor Allis is a Dutch computer scientist working in the artificial intelligence field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game search techniques: proof-number search and dependency-based search...
, with applications mostly in endgame solvers, but also for sub-goals during games.
Using a binary goal (e.g. first player wins the game), game trees of two-person perfect-information games can be mapped to an and–or tree. Maximizing nodes become OR-nodes, minimizing nodes are mapped to AND-nodes. For all nodes proof and disproof numbers are stored, and updated during the search.
The proof and disproof numbers represent lower bounds on the number of nodes to be evaluated to prove (or disprove) certain nodes. By always selecting the most proving (disproving) node to expand, an efficient search is generated.
Some variants of the like PN2, PDS-PN have been developed to address the quite big memory
requirements of the algorithm.