将棋AIで用いている詰将棋ルーチンにdf-pnというアルゴリズムがある。

これは、proof number(証明数)、disproof number(非証明数)を用いて効率的に探索を行い、その局面が詰むか、詰まないかを判定できるとても強力なアルゴリズムである。

将棋ファンなら『脊尾詰』と言う「ミクロコスモス」(1525手詰)を解く詰将棋専用ソフトについて一度ぐらいは聞いたことぐらいあるだろう。これは、脊尾さんが大学時代に作成されたプログラムである。そこに使われていたのが脊尾さんが考案されたdf-pnというアルゴリズムである。

df-pnに関しては、脊尾さん自身の論文(1998年)があるものの、要点しか書かれておらず、いまのようにGitHubにソースコードがあるわけでもなく、その詳細については長らく謎に包まれたままであった。(この脊尾さんの論文では、証明数のみを用いており、非証明数は陽には出てこなかった。だから、正確には、これはdf-pnの前身とでも言うべきだが、そこは話の本筋ではないので割愛する。)

歴史的なことを言うと、10年ぐらい前にGPS将棋にdf-pnが実装されることになる。GPS将棋のdf-pnはガーベジコレクション(不要になったエントリーを掃除してメモリを節約する技術)も搭載されており、完璧な実装ではあるのだが、ソースコードが非常に読みづらい。C++ templateを多用してあることやコメントがほとんど書かれていないことなどもあって、これを解読するのはほとんど不可能である。

その後、5,6年前にたぬきさん(nodchip)が、やねうら王のmate solverとしてdf-pnを実装したが、いくつか解けない問題があった。簡単に言えばバグっているのである。dlshogiのdf-pnの実装も、このたぬきさんのコードを参考に実装してあるので、解ける問題については推して知るべしである。

そんななか、KomoringHeightsという、やねうら王ベースの実装が公開された。これが、かなり完璧なコードで、ほとんどの詰将棋は解けるのではないかと言われている。いまdf-pnの参考実装を探しているなら、真っ先に読むべきコードである。

KomoringHeights(GitHub) : https://github.com/komori-n/KomoringHeights

ともかく、df-pnは、論文を読んだだけでは完璧にはほど遠い実装しかできず、大変困った状況が長らく続いていたのである。脊尾さんの論文に対しては、「読むだけで実装できるように論文を書いておけよ」と不満を漏らす開発者も多かった。もしかすると、脊尾さんの時代はミクロコスモスが解ける詰将棋ソフトは十分な魅力があったので、アルゴリズムの詳細まで書いてしまうとコピー商品のようなものが発売されてしまうから、それを避けたのかも知れないが。(当時、「脊尾詰」は単独では使えず「励棋」と言う将棋ソフトと組み合わせて使う必要があった。ソフトにはいくつものバリエーションがあり、一番高い組み合わせだと7万円ぐらいした。)

それで、先日のWCSC34で、私は技巧の出村さんに詰将棋ルーチンについて詳しく教えていただいた。出村さんは私が以前お会いしたあと、北海道で弁護士をされていたのだが、また将棋AIの開発がしたくなった(?)そうで、いまは東京大学の大学院でAIの研究をされているそうである。

df-pnという技術がロストテクノロジーになる前に、ここでそのことを詳らかにしておく必要があると感じ、教えてもらったことを余すことなく、以下の書き記す次第である。

出村さんが言うには、

１．進歩本
２．ゲーム計算アルゴリズム
３．金子さんの論文

この3つを揃えてやっと完璧(なアルゴリズムの説明)になるのだそうだ。『ダ・ヴィンチ・コード』(映画)みたいだな、と思った。

それで、1.とは、以下の3冊である。

『コンピュータ将棋の進歩2』 第1章 共謀数を用いた詰将棋の解法（脊尾昌宏）
https://www.amazon.co.jp/exec/obidos/ASIN/4320028929/aaaaab0c-22/ref=nosim/

『コンピュータ将棋の進歩4』 第5章 df-pnアルゴリズムと詰将棋を解くプログラムへの応用（長井歩）
https://www.amazon.co.jp/exec/obidos/ASIN/4320120744/aaaaab0c-22/ref=nosim/

『コンピュータ将棋の進歩6』 第6章 難問詰将棋をコンピュータで解く （岸本章宏）
https://www.amazon.co.jp/exec/obidos/ASIN/4320123212/aaaaab0c-22/ref=nosim/

2.は、次の本なのだが、絶版なのである。どこもかしこも絶版。

『ゲーム計算メカニズム (コンピュータ数学シリーズ 7)』
https://www.amazon.co.jp/exec/obidos/ASIN/4339025402/aaaaab0c-22/ref=nosim/

この本、入手できないものかと、私は昨日一日あちこちに問い合わせしまくっていたのだが、徒労に終わり、溜息混じりに自分の書庫を見たら、なんとこの本があった。

しかもゲーム開発の書庫にあった。ゲーム開発じゃねぇんだけど。(昔の自分、たぶんこの本をゲーム開発本だと思って購入してる。)

目次は、こんな感じになっている。将棋AI開発者なら目次を見ただけでよだれが出てくる(?)だろう。垂涎ものである。

ともかく、df-pnをやろうという開発者の方には、古本屋などをウォッチして何とか入手していただきたい。

この本が絶版になっているのが私には許せないのだが、『ゲーム計算メカニズム』みたいなわけのわからんタイトルをつけたら絶版になるのもやむなしである。「脊尾詰を超える最強の詰将棋AIが作れる本」とかだったら、もっと売れてた気がする。

まあそれはさておき、3.は、次の論文である。これはボタンぽちっと押すだけで入手できる。

これは、GPS将棋の主要開発者である金子 知適先生の論文である。df-pnを並列探索にする手法について書かれており、lockする箇所を最小限にしながら探索の正確性を担保してくれる。(らしい)

論文 : Parallel Depth First Proof Number Search(金子 知適)
https://ojs.aaai.org/index.php/AAAI/article/view/7551

あと、冒頭で挙げたKomoringHeightsの作者が、その実装のために参考にした文献を挙げている。2.が入手できない人は、こちらもあたってみられることをお勧めする。

KomoringHeights References : https://github.com/komori-n/KomoringHeights/blob/main/source/engine/user-engine/docs/refs.md

そんなわけで、もはやロストテクノロジーとなりかけているdf-pnだが、非常に興味深い技術なので、将棋AIに興味のある方は、是非取り組んでみていただきたい。