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

今回は、中編(100手以上~1000手未満)の協力詰めが解けるsolverを作ります。

MovePickerの設計

ここまで、LEGALで合法手のみを生成しているのですが、これはいったんすべての指し手を生成して、合法かどうかをひとつずつテストしているので無駄が多いというのは以前書きました。

また、先手は王手のみと限定できるならLEGALではなくCHECKS(王手)の指し手を生成したほうが生成の時間が短くて済みます。

やねうら王miniには高速なCHECKSの指し手の生成ルーチンがあります。おそらく、Bitboardを用いた高速なCHECKSの指し手の生成ルーチンが公開されるのはこれが始めてでしょう。書くのにずいぶん苦労しましたが、うまく動いているようですのでこれを使って書き換えてみましょう。

指し手生成を高速化した協力詰めsolver

No.90に再挑戦

置換表も出来たことですし、再度加藤徹さんのNo.90を解かせてみるんですが、63手目で王手が続かなくなったようです。なんでかなーと思って解答を見たところ…

http://www.ne.jp/asahi/tetsu/toybox/kato/rsk/kato090.kif

これはすごい手順ですね。歩打って王手して、玉引いて、歩不成で進んで、玉を横に交わして、歩成って、同銀…。協力詰め特有の魔法のような手順です。

そして、以前書いたように、やねうら王miniではLEGALの指し手生成以外では、歩の不成などは生成していません。王手の指し手生成(CHECKS)や王手回避(EVASIONS)もご多分に漏れず、です。

MovePickerで歩の不成も生成する

そこで、MovePickerで歩の不成なども生成してみます。
これは次のように CHECKS_ALL , EVASIONS_ALLと “_ALL”を末尾につけるだけです。

※ 以前、LEGALは歩の不成も含むと書きましたが、これらと統一するためにLEGAL_ALLを不成を含むようにして、LEGALは不成を含まないように変更しました。過去の記事でそうなっているのがあれば脳内で修正してください。

あと、以前も書きましたがmovegen.cppの末尾のところでこのtemplateの実体化は必要と。

67手詰め、解けるかな?

ShogiGUIで実行させると…。

1秒かからず瞬殺でした。置換表、恐るべし。

No.45(153手詰め)

では張り切って153手詰めもやってみましょう。

協力詰(ばか詰) 101手~999手(加藤徹 全作品)
http://www.ne.jp/asahi/tetsu/toybox/kato/fbaka3.htm
から、No.45。

http://www.ne.jp/asahi/tetsu/toybox/kato/rsk/kato045.kif

※ kifファイルをテキストエディタで開いて、盤面のところコピーして、将棋所とかShogiGUIにCtrl+Vで貼り付けをすると盤面の入力がされます。便利ですね、将棋所&ShogiGUI。そしてkifファイルを公開してくださっている加藤徹さんに感謝!

MAX_PLYは128を想定しているのでこれ以上にするには、shogi.hの次のdefineの値を変更する必要があります。

これをもっと大きな数にして…。

1秒足らずで解答が表示されました。置換表凄すぎ!というか、協力詰めって、きっとほぼほぼ一本道なんでしょうね…。

No12a(263手詰め)

http://www.ne.jp/asahi/tetsu/toybox/kato/rsk/kato012a.kif

落ちました。stack overflowで…。まあ、MSVCでは、デフォルト1MBしかないですしね。

仕方ないので、構成プロパティの
リンカー→システム→スタックサイズ
byte単位で指定するようなので419430400(400MB)を指定。

これで数万手になっても(解けるかどうかは別として)stack overflowにはならないようです。

詰将棋エンジンの作法

将棋所やShogiGUIから詰将棋を解くボタンを押すと
> go mate infinite
というメッセージが送られてきます。(“infinite”のところは思考時間のときも)

これに対して解図できたときはUSIプロトコルでは
> checkmate 指し手..
詰まないときは
> checkmate nomate
と出力するようです。(知りませんでした)

停止シグナル

USIプロトコルで”go …”(思考開始)のあと”stop”(強制停止)が送られてきた場合、”bestmove XXX”とベストな指し手を返すことになっているのですが、”go mate infinite”(詰将棋探索をせよ)のあと、”stop”が送られてきたときに”bestmove resign”を返すのか、”checkmate nomate”を返すのか、いまひとつよくわかりません。

ともかく、”stop”コマンドが送られてきたときに、やねうら王miniではSignals.stopがtrueになりますので、探索部においてはときどきこのフラグを確認してtrueであれば探索を中断して終わる必要があります。

このとき正しい指し手が返せる必要はありませんが、置換表に変な値を書き込んでしまったりすると次の探索のときにその値が使われてしまうと探索結果がおかしくなるので、そういう注意は必要でしょう。

ここまでのまとめ

置換表を実装すると200手ぐらいの協力詰めが解けるようになりました。
次回は長編(1000手~)に挑戦します。


連載やねうら王miniを強くしよう!4日目” への5件のコメント

  1. 1秒でズバッととけちゃうなんてすごいことになってますねぇ。
    そこに痺れるあこがれる~。
    絶対自分がやると、頭フットーしてしまいます。

コメントを残す

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