連載やねうら王miniを強くしよう!7日目

今回は、長編(1000手~)の協力詰めが解けるsolverにします。

工夫その1 . 不詰めの証明

よく考えてみると、5手先まで読んだときにそれ以上王手が続かない局面は100手先まで読んだところで詰みません。

そこで、TTEntryに残り探索depthを入れるのと、詰まないことが確定しているならその旨も保存しておくべきです。

具体的には、王手が続かなくなった局面について保存するときにdepthを無限大としてTTEntryに格納しておきます。王手が続かない以上、いくら残り探索深さがあったところで詰みませんので。

この「無限大」を表現するのは、最大探索深さ(MAX_PLY)で良いでしょう。これ以上深くなることは想定していないので…。

次に、あるnodeの子(あるnodeから1手進めた局面)が全部depthが無限大で詰まないことがわかっているなら、そのnodeも詰まないはずです。

そこでそのようにプログラムを修正すればもっと効率的に探索できるはずです。

詰まないことに対する定式化

上の事実は、もう少し別の書き方をすると、あるnodeの子が3つしかないとして(ある局面で指し手が3つあったとして)、それぞれ3手で詰まない、5手で詰まない、無限大で詰まない、ということがわかっている場合、このnodeは、3 + 1 = 4手では詰まない(もっと深さがあれば詰むかも知れない)ということがわかります。

すなわち、あるnodeのTTEntryに書き込むべきdepthの値は、子のnodeが置換表に書いたdepth (これは子のnodeの数だけある)の最小値 + 1 ということがわかります。実際には、no_mate_depthが無限大(MAX_PLY)のときは無限大に1を足すのは少し気持ち悪いので、

no_mate_depth = min(child_no_mate_depth +1, no_mate_depth);

のようにしておくといいと思います。

工夫その2. 置換表に指し手を格納することによる高速化

いま、詰まないことがわかっている局面(no_mate_depth == MAX_PLYである局面)のことを、確定局面と呼ぶことにします。

あるnodeの子nodeが1つを除いて確定局面である場合、この確定局面ではない子nodeだけ調べれば良いです。この局面では1手しか応手がないので、これをone replyと呼ぶことにします。

この子nodeに進むための指し手を置換表に登録しておけば、このnodeの指し手生成を省略できますし、また、確定局面だと判明している子nodeに進んで置換表をprobe()する手間が省けます。

工夫その3. 置換表にClusterを導入する

Clusterについてはすでに説明しました。

工夫その4. 置換表に世代を導入する

すべての子が確定局面であるなら、そのnodeは確定局面です。
このように確定局面は親方向に伝播していきます。

反復深化をしていくときに探索開始局面から最初に辿りつくのは、末端の確定局面ではなく、その親や、その親の親、…、と言った、親nodeです。ということは、確定局面の親を持つなら、その子の情報は置換表上には要らないのです。(別の手順でこの子nodeに到達することもありますが、それはいま考えないことにします。)

ということで、置換表からは、一番親の確定局面だけを残して、その子の情報は捨てたいのです。

従来、こういう目的では置換表用のGC(garbage collection)が実装されてきました。過去の長編詰将棋を解く論文を見ているとGCを実装しているものがよくあります。

現代的な視点では、これらはGCでやるべきではないと思います。
もう少し簡単に実装できるからです。

それが世代という概念です。置換表に世代という16bitの整数カウンターがあるとします。

協力詰めでは反復深化のごとにこのカウンターを1足します。

また、TTEntryにも世代を持たせて、TTEntry::save()のときに、この置換表(TranspositionTable)の世代を書き込んでおきます。probe()に成功したときもTTEntryの世代を置換表の世代にします。(これを世代のrefreshと呼びます。)

こうしておいて、置換表が衝突してCluster内でrehashするときに、世代の近いTTEntryのほうを優先して残すのです。世代が離れているということは前回の反復深化でrefreshされていない、すなわち、使われていなかったことを意味するので、そのnodeの親は確定局面である可能性が高いからです。

このように置換表に世代という概念を導入することで、GCは不要になります。(GCの動作に近い動作になります。)

工夫まとめ

工夫その1.で確定局面が親に伝播(子がすべて確定局面なら親も確定局面)するようになりました。

工夫その2.で、子が1つだけ非確定局面であるnodeでは、他の子(確定局面の子)を辿らないようになりました。

辿らないということはprobeされないということで、工夫その4.により、refreshもされなくて、置換表の世代とTTEntryの世代とがかけ離れていくのでこれらは、工夫その3.のClusterを導入したときに、rehash処理のときに捨て去られる対象となります。

このように、以上の工夫1.~4.は相互に絡み合って効果を発揮するようになっています。

工夫その5.反復深化は2手ずつ

何手で詰むかわからないので1手ずつ深くしていきながら詰むかどうかを調べています。1手ずつ深くしていきながら探索することを反復深化(iterative deeping)と呼びます。この頭文字を取って、id(id_loop)と書いてあります。Stockfishもそんな関数名になっていたと思います。

この反復深化、2手ずつ進めたほうが全体的には高速であるようです。

探索の色んな問題が絡むので2手ずつ進めたほうがいいかどうかは一般的には言えませんが、とりあえず協力詰めでは2手ずつ進めて問題なさげでかつ速くなるというのが結論のようです。

工夫その6.循環局面の検出

協力詰めにおいては連続王手の千日手と劣等局面の判定については難しいところがあるようです。

劣等局面のほうが優れているケース
協力詰めsolverを並列化するとGHI問題に行き当たる件

上記の話題はまだ調査中で結論が出ていないので、とりあえず保留しておきます。

長編は解けるようになったのですか?

協力詰めsolverを公開します

協力詰めの最長編である『寿限無3』(49909手) が解けました。
序盤で変化の多い一部の長編を除き、すべて解けるようです。

上の協力詰めsolverをダウンロードすると、なかにソースコードが入っています。
(開発中のやねうら王miniのソースコードを流用しています。)

やねうら王miniのソースコードの公開を待ちきれないという人は、上の協力詰めのソースコードをいじってみると良いのではないでしょうか。

協力詰めの論文

協力詰めの論文としては以下の論文ぐらいしかありません。

反復深化探索に基く協力詰将棋の解法
http://mm.cs.uec.ac.jp/doc/ipsj2002.pdf

この論文に気づいたのは私が協力詰めsolverをある程度書き上げてからだったのですが、比較的よく出来た論文だと思います。(上から目線でスマソ)

one replyのアイデアは上記の論文からもらいました。

ただ、上記の論文は現代的な観点で見ると、置換表のGCを実装していたりして実装が複雑だなと思いました。

あと、確定局面に関しては、上の「詰まないことに対する定式化」で書いたような方法で親nodeに伝播させていくほうがシンプルで、かつ枝刈り性能がいいはず。

ここまでのまとめ

長編協力詰めが解ける協力詰めsolverが完成しました。これで終盤の探索についての理解が深まったかと思います。

次回からは新連載、「やねうら王miniを強くしよう2」が始まります。お楽しみに!

今回のソースコード

おまけとして、以下に今回の協力詰めのソースコード(シングルスレッド版)を貼り付けておきます。

あと、置換表の使用率(hashfull)を計算する関数については本連載中には解説していませんでしたが、USIプロトコルでは千分率で返すことになっているのでTTEntryの先頭1000個、サンプリングしてそのTTEntryの世代を調べることで置換表使用率を計算できるという仕組みになっています。(以下のソースコードを参照のこと。)

置換表使用率の出力を実装していないソフトも結構あるとは思いますが、これを実装することにより、置換表にどれくらいのメモリを割り当てるのが適切なのかがわかるようになるので、是非実装されることをお勧めします。

 

連載やねうら王miniを強くしよう!7日目」への6件のフィードバック

  1. とりあえずいつもの誤字さがし・・・

    >従来、こういう目的では置換表用のGC(garbage collection)を実装されてきました。

    GC(garbage collection)をーー>GC(garbage collection)が・・・かな。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です