Proof-Number Search and Transpositions

Article type: Research Article

Authors: Schijf, M. | Allis, L.V.^{; *} | Uiterwijk, J.W.H.M.

Affiliations: Department of Computer Science, University of Limburg, Maastricht, The Netherlands

Note: [*] At present with the Artificial Intelligence Group of the Department of Computer Science, Vrije Universiteit, Amsterdam, The Netherlands.

Abstract: 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 representations, 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.

DOI: 10.3233/ICG-1994-17203

Journal: ICGA Journal, vol. 17, no. 2, pp. 63-74, 1994