Proof-Number Search and Transpositions
M. Schijf, L.V. Allis, JOS W. H. M. UITERWIJK · ICGA Journal · 1994
Proof-number search (pn-search) has been successfully applied to games such as connect-four, qubic and go-moku. Although pn-search is a game-tree search algorithm, minor modifications allow its application to the acyclic-graph representation of these games. To apply pn-search to cyclic-graph repres entations, e.g., of chess, several obstacles must be overcome, which have been the subject of our investigations. This article describes the application of pn-search to trees, acyclic graphs and cyclic graphs. Experiments on chess, using four different pn-search variants, indicate the suitability of pn-search for solving checkmate problems. The results show that pn-search adapted for cyclic-graph representations outperforms its tree and acyclic-graph counterparts.