Note: [1] This note is an edited and extended version of the second author’s invited lecture “Advances of AND/OR-tree Search Algorithms in Shogi Mating Search”, presented at the Computer Game-Playing Workshop 2001, held in Maastricht, The Netherlands, on August 20-23, 2001, in the framework of the CMG 6th Computer Olympiad in Maastricht, August 19-23, 2001.
Note: [2] Department of Computer Science, Shizuoka University, 3-5-1 Johoku, Hamamatsu, 432-8011 Japan. E-mail: {sakuta, iida}@cs.inf.shizuoka.ac.jp}
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.
DOI: 10.3233/ICG-2001-24405
Journal: ICGA Journal, vol. 24, no. 4, pp. 231-235, 2001
