将棋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に興味のある方は、是非取り組んでみていただきたい。
詰将棋専用ソフトは実戦で読むときも何百手も読んでいるのでしょうか？もしそうならfloodgateで見つかった最長手数の詰みは約７０手くらいなのでそれくらいで打ち切りにしたら
さらに効率的になるってことはないのですか？
https://tadaoyamaoka.hatenablog.com/entry/2023/07/22/164719
今回のやねこま王ではdf-pnは1局面あたり探索ノード(局面)数100万で打ち切りですね。(40手詰めぐらいまでの詰将棋がこのノード数でだいたい解ける)
ですので、それで見つからない詰みは知らんということです。
でも、PV lineなら、その2 * n手後の局面でまたdf-pn呼ぶので、それで詰みが発見できる場合もありますし..
ゲーム計算メカニズム読みたい人は、最寄りの図書館に行って「図書館間相互貸借でゲーム計算メカニズム読みたいです」と図書館の人に尋ねるのが吉と占いに出ました
それが良さげですなー。出版社が再販してくれると良いのですが…。
> それで、先日のWCSC34で、私は技巧の出村さんに詰将棋ルーチンについて詳しく教えていただいた。
事情を知らないのですが、なにが「それで」なのですか？出村さんが突然出てきたような気がして。
「出村さんはGPS将棋の金子先生の研究室なのか(詳しくは聞いていない)、df-pnも相当詳しく研究されているので、df-pnが現在のように何をアルゴリズムのベースにして実装して良いかわからない閉塞的状況において、教えを請うのに適任であるから」と言いたかったです。
やねうらおさんの記事に触発され、df-pnの解説記事や論文をいくつか読んでみました。それを踏まえた個人的な疑問と感想についてです。
df-pn(+)は詰むか詰まないかの判定が速いアルゴリズムなようですが、一方で無駄合を判定しつつ正当性の高い短い手順を返すという「詰将棋のルール」に適合させるには最適なアルゴリズムと言えるかは分からないと感じています。短い手順を返せないプログラムは、玉方の対応を随所で誤るということになってしまいます。
（KomoringHeightsは詰将棋ソルバーの中では恐らく最も高速で素晴らしいソフトですが、現状は無駄合判定ができず、精度が低い変な手順を返しがちです。）
N手で詰んだら、N-2手以内で詰む手順があるか探索しなおすことを繰り返して精度を上げる的実装はあるようですが、それも時間がかかるケースはあるでしょうし、「遅いけどより詰将棋のルールに適合しやすい別のアルゴリズム」に速度負けする可能性もなくはないなと感じています。そこで、個人的な疑問点としては、柿木の無駄合判定アルゴリズムは上手くdf-pnに組み込めるのか？また、少ない計算量でdf-pnが返す手順の精度を圧倒的に上げる方法はあるのか？やねうらおさんはこのあたりをどう思いますか？
まあ、速度を求めるか精度を求めるかは目的の問題になるのでしょうが…詰むか詰まないかの判定が速く、且つ返す答えの精度も高いという夢のプログラムがもしあれば、値段が高くても是非欲しいし、周りの人にも布教したいと個人的には思っているのです。
df-pnである局面から詰みまでの手数を正確に求めることはできるのですが(つまりは、「柿木の無駄合判定アルゴリズムにdf-pnを組み込む」ことはできる)、いまよりはるかに展開する枝が増えて致命的に探索効率が落ちるので、df-pnの良さは失われてしまいますね…。
岡部文洋さんが経路分岐数を用いたアルゴリズム(Branch Number Search)を論文で発表していて、ググってアクセス可能でしかも多分優秀なアルゴリズムなんですけど、実装例を知りません。これはdf-pn以上のロストテクノロジーかもしれないです
BNSを誰もやらない理由って何かあるのかなーと不思議に思ってます
効率がわずかにしか改善しないのに実装が複雑になる(置換表に登録すべき項目がわりと増える)のが嫌なのかも？
やねうらおさん、教えていただきありがとうございます
証明数の二重カウントみたいな問題が起こらないということなので、実装は楽になるんじゃないかと思ったんですけど、やってみないと分からないかもしれません
追加質問で申し訳ないのですが、置換表に登録すべき項目が増えるとは具体的に何が増えるのでしょうか
> 置換表に登録すべき項目が増えるとは具体的に何が増えるのでしょうか
1. メモリアクセスが増えるのでメモリ帯域が限られているとそこがボトルネックになってNPSが下がります。
2. 局面あたりの使用するメモリ量が増えるので、ある問題を解く時にメモリがちょうど足りなくなる可能性が出てきます。
3. 2.の場合、GC(Garbage Collector)を実装しないといけなくなって実装がいたずらに複雑になります。
4. 3.のようにGCを実装した場合、今度はGCで探索した情報が掃除されてしまったがために解けなくなる問題が出てきます。
そんなわけで、本当にプラスになるかはなかなか判断が難しいところですね。両方実装して比較するのが良いのでしょうけども、バグなしに実装するのはわりと大変そう…。