Proof-number search

Proof-number search (short: PN search) is a game tree search algorithm invented by Victor Allis,[1] 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 proof number search like dfPN, PN2, PDS-PN[2] have been developed to address the quite big memory requirements of the algorithm.

References

  1. ↑ Allis, L Victor. Searching for Solutions in Games and Artificial Intelligence. PhD Thesis. ISBN 90-9007488-0. Retrieved 24 Oct 2014.
  2. ↑ Mark H.M. Winands, Jos W.H.M. Uiterwijk, and H. Jaap van den Herik (2003). "PDS-PN: A New Proof-Number Search Algorithm" (PDF). Lecture Notes in Computer Science.