出版社：The Japanese Society for Artificial Intelligence
摘要：Brinkmate (hisshi in Japanese) is an important notion of accessing to the opponent’s King in shogi. This is essentially the same as conventional chess mating problems, where all moves are considered. However, in shogi the problem is much more difficult, as the possibilities for delivering check or threatmate, and the number of defenses are much greater.The defending side may have 200 or 300 possible defensive moves to consider. Brinkmate search is resolved into an AND/OR-tree search based on the concept of threat sequence proposedby Iida. The cost of brinkmate search is by far more expensive than mating (tsumeshogi) to find a solution. Since not much is known about brinkmate itself or brinkmate search, we first explain it by giving the definition of brinkmate. In an AND/OR tree of brinkmate search, to determine effective branches (i.e., legal moves) at any internal node is often a time-consuming task. This paper proposes a new search algorithm, denoted by SPH, for an AND/OR-tree search. The algorithm is implemented in a shogi-hisshi (Japanese-chess brinkmate-problem) program, and evaluated by testing it on difficult hisshi problems. Moreover, it is enhanced by several methods including a new idea, denoted by TDSS. The experimental results are compared with those of other programs. The program with TDSS shows the best results for solving short-step problems, while the SPH program in general outperforms the other programs in solving long-step problems.
