17/05/01 23:21:41.92 nB6uL1P/.net
>>411
関連
URLﾘﾝｸ(ipsj.ixsq.nii.ac.jp)
URLﾘﾝｸ(ipsj.ixsq.nii.ac.jp)
df-pnアルゴリズムの詰将棋を解くプログラムへの応用（論文賞受賞） 長井 歩 今井 浩 東京大学 情報処理学会論文誌 2002
詰将棋を解くプログラムの研究はこの10年の間に大きく進歩した．その原動力となったのは，証明数や反証数という概念の導入である．
詰将棋に適用すると，直感的にいうと，証明数は玉の逃げ方の総数を，反証数は攻め方の王手の総数を表す．前者は攻め方にとって，後者は玉方にとって非常に重要な値である．証明数・反証数を対等に扱った，最もナイーブなアルゴリズムは，Allisによるpn-searchという最良優先探索法である．
我々は近年，df-pnアルゴリズムという，pn-searchと同等の振舞いをする深さ優先探索法を提案している．この論文では，df-pnアルゴリズムを用いて詰将棋を解く強力なプログラムを作成し，その過程で導入した様々な技法を提案する．
これらの技法をdf-pnの上に実装することにより，我々のプログラムでは300手以上の詰将棋のすべてを解くことに初めて成功した．
しかもそれは，シングルプロセッサのワークステーションで解くなど，解答能力と解答時間の両面で優れた結果を出すことができた．