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

摘要

This paper proposes a new search algorithm, denoted PN∗, for AND/OR tree search. The algorithm is based on proof-number (PN) search, a best-first search algorithm, proposed by Allis et al. [Artificial Intelligence 66 (1) (1994) 91–124], and on Korf's RBFS algorithm [Artificial Intelligence 62 (1) (1993) 41–78]. PN∗ combines several existing ideas. It transforms a best-first PN-search algorithm into an iterative-deepening depth-first approach. Moreover, it is enhanced by methods such as recursive iterative deepening, dynamic evaluation, efficient successor ordering, and pruning by dependency relations. The resulting algorithm turns out to be highly efficient as witnessed by the experimental results.