Abstract
The note describes the development of AND/OR-tree search algorithms in the mating search of shogi. Originally depth-first algorithms are successfully transformed in best-first algorithms, such as PN*, PDS, and df-pn. Each of these algorithms aims at solving hard tsume-shogi problems. The algorithms can be characterized as variants of proof-number search. We note that PN* only uses proof numbers, while PDS and df-pn uses both proof numbers and disproof numbers. The df-pn search behaviour is similar to proof-number search’s behaviour. Recently, the strong shogi programs have come to apply these algorithms in their tournament versions and are now able to find relatively long-step mating sequences in a short time.
Get full access to this article
View all access options for this article.