The PN*-search algorithm: Application to tsume-shogi

This paper proposes a new search algorithm, denoted PN*, for AND/OR tree st arch. The algorithm is based on proof-number (PN) search, a best-first sear ch algorithm, proposed by Allis et al. [Artificial Intelligence 66 (1) (199 4) 91-124], and on Korf's RBFS algorithm [Artificial Intelligence 62 (1) (1 993) 41-78]. PN* combines several existing ideas. It transforms a best-firs t PN-search algorithm into an iterative-deepening depth-first approach. Mor eover, it is enhanced by methods such as recursive iterative deepening, dyn amic evaluation, efficient successor ordering, and pruning by dependency re lations. The resulting algorithm turns out to be highly efficient as witnes sed by the experimental results. The PN* algorithm is implemented in a tsume-shogi (Japanese-chess mating-pr oblem) program, and evaluated by testing it on 295 notoriously difficult ts ume-shogi problems tone problem has a depth of search of over 1500 plies). The experimental results are compared with those of other programs. The PN* program shows by far the best results, solving all problems but one. Needl ess to say, it outperforms the best human tsume-shogi problem solvers by fa r. (C) 2001 Elsevier Science B.V. All rights reserved.