「df-pnアルゴリズムの詰将棋を解くプログラムへの応用」（Vol.43，No.6）

［論文概要］
　詰将棋を解くプログラムの研究は近年大きく進歩した．その原動力となったのは，証明数や反証数という概念の導入である．詰将棋に適用すると，証明数は玉の逃げ方の総数，反証数は攻め方の王手の総数を表す．証明数・反証数を対等に扱った，最もナイーブなアルゴリズムは，pn-searchという最良優先探索法である．本論文では，我々の提案している，df-pnアルゴリズムという，pn-searchと同等の振る舞いをする深さ優先探索法をベースに，様々な技法を導入したプログラムを作成した．我々のプログラムでは300手以上の詰将棋のすべてを解くことに初めて成功するなどの成果を挙げることができた．

［推薦理由］
　詰将棋を解くためのアルゴリズムとその評価に関する論文である．著者らがすでに提案した，証明数と反証数ベースのdp-fnアルゴリズムに，さらに，ハッシュの効率的な利用，局面間の優越関係の利用，Graph History Interaction問題対策，等の5手法を追加した．これをプログラム化し，複数の詰将棋問題に対して適用，評価した．その結果，初めて300手以上の詰将棋をすべて，江戸時代の詰将棋作品集「将棋図巧」99題，「将棋無双」94題をすべて，江戸時代から昭和までの名作詰将棋「続詰むや詰まざるや」から195題，「将棋墨酔」の103題中95題を解いた．対象を詰将棋に集中した研究であるが，さまざまな手法を組み合わせて，従来の最強詰将棋プログラムを大きく超える成果を達成したことは論文賞に値する．