必至問題を解くプログラムとその評価

概要

論文の詳細を見る
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.
人工知能学会の論文
2001-11-01

必至問題を解くプログラムとその評価

スポンサーリンク

概要

著者

関連論文

スポンサーリンク