今回は、中編(100手以上～1000手未満)の協力詰めが解けるsolverを作ります。
MovePickerの設計
ここまで、LEGALで合法手のみを生成しているのですが、これはいったんすべての指し手を生成して、合法かどうかをひとつずつテストしているので無駄が多いというのは以前書きました。
また、先手は王手のみと限定できるならLEGALではなくCHECKS(王手)の指し手を生成したほうが生成の時間が短くて済みます。
やねうら王miniには高速なCHECKSの指し手の生成ルーチンがあります。おそらく、Bitboardを用いた高速なCHECKSの指し手の生成ルーチンが公開されるのはこれが始めてでしょう。書くのにずいぶん苦労しましたが、うまく動いているようですのでこれを使って書き換えてみましょう。
指し手生成を高速化した協力詰めsolver
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
namespace CooperativeMate { // 協力詰め用のMovePicker struct MovePicker { MovePicker(const Position& pos_) : pos(pos_) { // 協力詰めであれば段階的に指し手を生成する必要はない。 // 先手ならば王手の指し手(CHECKS)、後手ならば回避手(EVASIONS)を生成。 endMoves = (pos.side_to_move() == BLACK) ? generateMoves : generateMoves } // 次の指し手をひとつ返す // 指し手が尽きればMOVE_NONEが返る。 Move next_move() { if (currentMoves == endMoves) return MOVE_NONE; return *currentMoves++; } private: const Position& pos; ExtMove moves[MAX_MOVES], *currentMoves = moves, *endMoves = moves; }; } // end of namespace |
No.90に再挑戦
置換表も出来たことですし、再度加藤徹さんのNo.90を解かせてみるんですが、63手目で王手が続かなくなったようです。なんでかなーと思って解答を見たところ…
|
1 2 3 4 5 6 |
13 ２三歩打 ( 0:00/00:00:00) 14 ２一玉(22) ( 0:00/00:00:00) 15 ２二歩(23) ( 0:00/00:00:00) 16 １一玉(21) ( 0:00/00:00:00) 17 ２一歩成(22) ( 0:00/00:00:00) 18 同 銀(12) ( 0:00/00:00:00) |
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は不成を含まないように変更しました。過去の記事でそうなっているのがあれば脳内で修正してください。
|
1 2 3 4 5 6 7 |
MovePicker(const Position& pos_) : pos(pos_) { // 協力詰めであれば段階的に指し手を生成する必要はない。 // 先手ならば王手の指し手(CHECKS)、後手ならば回避手(EVASIONS)を生成。 endMoves = (pos.side_to_move() == BLACK) ? generateMoves : generateMoves } |
あと、以前も書きましたがmovegen.cppの末尾のところでこのtemplateの実体化は必要と。
|
1 2 |
// 協力詰めのときは必要 template ExtMove* generateMoves |
67手詰め、解けるかな？
ShogiGUIで実行させると…。
|
1 |
* 深さ 67 読み筋 ▲３二歩打 △２二玉(31) ▲２三歩打 △３二玉(22) ▲２二歩成(23) △同 玉(32) ▲２三歩打 △３一玉(22) ▲３二歩打 △同 銀(21) ▲２二歩成(23) △同 玉(31) ▲２三歩打 △２一玉(22) ▲２二歩(23) △１一玉(21) ▲２一歩成(22) △同 銀(12) ▲１二歩打 △２二玉(11) ▲２三歩打 △１二玉(22) ▲２二歩成(23) △同 玉(12) ▲２三歩打 △１一玉(22) ▲２二歩成(23) △同 銀(21) ▲１二歩打 △２一玉(11) ▲１一歩成(12) △同 銀(22) ▲２二歩打 △３一玉(21) ▲２一歩成(22) △同 銀(32) ▲３二歩打 △２二玉(31) ▲２三歩打 △３二玉(22) ▲２二歩成(23) △同 玉(32) ▲２三歩打 △３一玉(22) ▲３二歩打 △同 金(33) ▲２二歩成(23) △同 金(32) ▲３二歩打 △同 玉(31) ▲３三歩打 △４三玉(32) ▲５三桂成(65) △３三玉(43) ▲４三成桂(53) △２三玉(33) ▲３三成桂(43) △１二玉(23) ▲２二成桂(33) △同 玉(12) ▲１二金打 △２三玉(22) ▲１三金(12) △３二玉(23) ▲２三金(13) △３一玉(32) ▲４三桂打 |
1秒かからず瞬殺でした。置換表、恐るべし。
No.45(153手詰め)
では張り切って153手詰めもやってみましょう。
協力詰（ばか詰） １０１手～９９９手(加藤徹 全作品)
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 2 |
// 通常探索時の最大探索深さ #define MAX_PLY_ 128 |
これをもっと大きな数にして…。
|
1 |
* 深さ 153 読み筋 ▲９二桂成(84) △同 玉(91) ▲８四桂打 △８一玉(92) ▲７二桂成(84) △９一玉(81) ▲８一成桂(72) △９二玉(91) ▲９一成桂(81) △８二玉(92) ▲８一成桂(91) △７二玉(82) ▲７一成桂(81) △８二玉(72) ▲８一成桂(71) △９二玉(82) ▲９一成桂(81) △８二玉(92) ▲９二成桂(91) △７一玉(82) ▲７二歩打 △同 と(61) ▲８二成桂(92) △６一玉(71) ▲７二成桂(82) △同 と(62) ▲６二歩打 △７一玉(61) ▲６一歩成(62) △８一玉(71) ▲７一と(61) △８二玉(81) ▲７二と(71) △９一玉(82) ▲８一と(72) △９二玉(91) ▲９一と(81) △８二玉(92) ▲８一と(91) △７二玉(82) ▲８二と(81) △６一玉(72) ▲６二歩打 △同 と(51) ▲７二と(82) △５一玉(61) ▲６二と(72) △同 と(52) ▲５二歩打 △６一玉(51) ▲５一歩成(52) △７一玉(61) ▲６一と(51) △７二玉(71) ▲６二と(61) △８一玉(72) ▲７一と(62) △８二玉(81) ▲８一と(71) △７二玉(82) ▲７一と(81) △６二玉(72) ▲７二と(71) △５一玉(62) ▲５二歩打 △同 と(41) ▲６二と(72) △４一玉(51) ▲５二と(62) △同 と(42) ▲４二歩打 △５一玉(41) ▲４一歩成(42) △６一玉(51) ▲５一と(41) △６二玉(61) ▲５二と(51) △７一玉(62) ▲６一と(52) △７二玉(71) ▲７一と(61) △６二玉(72) ▲６一と(71) △５二玉(62) ▲６二と(61) △４一玉(52) ▲４二歩打 △同 と(31) ▲５二と(62) △３一玉(41) ▲４二と(52) △同 と(32) ▲３二歩打 △４一玉(31) ▲３一歩成(32) △５一玉(41) ▲４一と(31) △５二玉(51) ▲４二と(41) △６一玉(52) ▲５一と(42) △６二玉(61) ▲６一と(51) △５二玉(62) ▲５一と(61) △４二玉(52) ▲５二と(51) △３一玉(42) ▲３二歩打 △同 成香(21) ▲４二と(52) △２一玉(31) ▲３二と(42) △同 成香(22) ▲２二香打 △３一玉(21) ▲２一香成(22) △４一玉(31) ▲３一成香(21) △４二玉(41) ▲３二成香(31) △５一玉(42) ▲４一成香(32) △５二玉(51) ▲５一成香(41) △４二玉(52) ▲４一成香(51) △３二玉(42) ▲４二成香(41) △２一玉(32) ▲２二香打 △同 成桂(12) ▲３二成香(42) △１二玉(21) ▲２二成香(32) △同 成桂(11) ▲２四桂打 △２一玉(12) ▲１二桂成(24) △３一玉(21) ▲２二成桂(12) △４一玉(31) ▲３一成桂(22) △４二玉(41) ▲４一成桂(31) △３二玉(42) ▲４二成桂(41) △２二玉(32) ▲３四桂打 △２一玉(22) ▲３二成桂(42) △１二玉(21) ▲２二桂成(34) |
1秒足らずで解答が表示されました。置換表凄すぎ！というか、協力詰めって、きっとほぼほぼ一本道なんでしょうね…。
No12a(263手詰め)
http://www.ne.jp/asahi/tetsu/toybox/kato/rsk/kato012a.kif
落ちました。stack overflowで…。まあ、MSVCでは、デフォルト1MBしかないですしね。
仕方ないので、構成プロパティの
リンカー→システム→スタックサイズ
byte単位で指定するようなので419430400(400MB)を指定。
これで数万手になっても(解けるかどうかは別として)stack overflowにはならないようです。
|
1 |
* 深さ 263 読み筋 ▲８四歩打 △９三玉(83) ▲８三歩成(84) △同 玉(93) ▲９四と(95) △同 玉(83) ▲９五歩打 △９三玉(94) ▲９四歩(95) △８三玉(93) ▲９三歩成(94) △８四玉(83) ▲８三と(93) △９四玉(84) ▲８四と(83) △９五玉(94) ▲８五と(84) △同 玉(95) ▲８六歩打 △８四玉(85) ▲８五歩(86) △８三玉(84) ▲８四歩(85) △９三玉(83) ▲８三歩成(84) △９四玉(93) ▲８四と(83) △９五玉(94) ▲９四と(84) △８五玉(95) ▲９五と(94) △８六玉(85) ▲９六と(95) △同 玉(86) ▲９七歩打 △９五玉(96) ▲９六歩(97) △９四玉(95) ▲９五歩(96) △９三玉(94) ▲９四歩(95) △８三玉(93) ▲９三歩成(94) △８四玉(83) ▲８三と(93) △８五玉(84) ▲８四と(83) △８六玉(85) ▲８五と(84) △９六玉(86) ▲８六と(85) △９七玉(96) ▲８七と(86) △同 玉(97) ▲８八歩打 △８六玉(87) ▲８七歩(88) △８五玉(86) ▲８六歩(87) △８四玉(85) ▲８五歩(86) △８三玉(84) ▲８四歩(85) △９三玉(83) ▲８三歩成(84) △９四玉(93) ▲８四と(83) △９五玉(94) ▲８五と(84) △９六玉(95) ▲８六と(85) △９七玉(96) ▲９六と(86) △８七玉(97) ▲９七と(96) △８八玉(87) ▲９八と(97) △同 玉(88) ▲９九歩打 △９七玉(98) ▲９八歩(99) △９六玉(97) ▲９七歩(98) △９五玉(96) ▲９六歩(97) △９四玉(95) ▲９五歩(96) △９三玉(94) ▲９四歩(95) △８三玉(93) ▲９三歩成(94) △８四玉(83) ▲８三と(93) △８五玉(84) ▲８四と(83) △８六玉(85) ▲８五と(84) △８七玉(86) ▲８六と(85) △８八玉(87) ▲８七と(86) △９八玉(88) ▲８八と(87) △９九玉(98) ▲８九と(88) △同 玉(99) ▲９八銀打 △８八玉(89) ▲９七銀(98) △８七玉(88) ▲９六銀(97) △８六玉(87) ▲９五銀(96) △８五玉(86) ▲９四銀(95) △８四玉(85) ▲８三銀成(94) △８五玉(84) ▲８四成銀(83) △８六玉(85) ▲８五成銀(84) △８七玉(86) ▲８六成銀(85) △８八玉(87) ▲８七成銀(86) △８九玉(88) ▲８八成銀(87) △７九玉(89) ▲８九成銀(88) △６九玉(79) ▲７九成銀(89) △５九玉(69) ▲６九成銀(79) △４九玉(59) ▲５九成銀(69) △３九玉(49) ▲４九成銀(59) △２九玉(39) ▲３九成銀(49) △１九玉(29) ▲１八金(17) △同 玉(19) ▲１七金(16) △１九玉(18) ▲１八金(17) △同 玉(19) ▲１七金(27) △１九玉(18) ▲１八金(17) △同 玉(19) ▲２九成銀(39) △１七玉(18) ▲１八成銀(29) △１六玉(17) ▲１七成銀(18) △２五玉(16) ▲１六成銀(17) △同 玉(25) ▲１五と(14) △１七玉(16) ▲１六と(15) △１八玉(17) ▲１七と(16) △１九玉(18) ▲１八と(17) △２九玉(19) ▲１九と(18) △３九玉(29) ▲２九と(19) △４九玉(39) ▲３九と(29) △５九玉(49) ▲４九と(39) △６九玉(59) ▲５九と(49) △７九玉(69) ▲６九と(59) △８八玉(79) ▲７九と(69) △９八玉(88) ▲８八と(79) △９九玉(98) ▲９八と(88) △８九玉(99) ▲８八と(98) △７九玉(89) ▲８九と(88) △６九玉(79) ▲７九と(89) △５九玉(69) ▲６九と(79) △４九玉(59) ▲５九と(69) △３九玉(49) ▲４九と(59) △２九玉(39) ▲３九と(49) △１八玉(29) ▲２九と(39) △１七玉(18) ▲１八と(29) △１六玉(17) ▲１七と(18) △２五玉(16) ▲３五金(45) △１五玉(25) ▲２五金(35) △同 玉(15) ▲１六と(17) △３五玉(25) ▲２五と(16) △４五玉(35) ▲３五と(25) △５五玉(45) ▲４五と(35) △６四玉(55) ▲５四と(45) △６五玉(64) ▲６四と(54) △５五玉(65) ▲５四と(64) △４五玉(55) ▲４四と(54) △３五玉(45) ▲３四と(44) △２五玉(35) ▲３五と(34) △１五玉(25) ▲２五と(35) △１六玉(15) ▲１五と(25) △１七玉(16) ▲１六と(15) △１八玉(17) ▲１七と(16) △１九玉(18) ▲１八と(17) △２九玉(19) ▲１九と(18) △３九玉(29) ▲２九と(19) △４九玉(39) ▲３九と(29) △５九玉(49) ▲４九と(39) △６九玉(59) ▲５九と(49) △７九玉(69) ▲６九と(59) △８八玉(79) ▲７九と(69) △８七玉(88) ▲８八と(79) △８六玉(87) ▲７七と(88) △８五玉(86) ▲８六と(77) △９四玉(85) ▲９五歩打 △８四玉(94) ▲８五と(86) △９三玉(84) ▲９四と(85) |
詰将棋エンジンの作法
将棋所や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手～)に挑戦します。
1秒でズバッととけちゃうなんてすごいことになってますねぇ。
そこに痺れるあこがれる～。
絶対自分がやると、頭フットーしてしまいます。
＞長手数の協力詰めsolver書いた経験からかdf-pnの論文見ると一瞬で理解できた。・・・
まことに「長手数の協力詰めsolverの霊験あらたかなる効果」でありますなあ。
正月そうそう縁起の良い話であります。
https://twitter.com/yaneuraou/status/683555083003412480?ref_src=twsrc%5Etfw
通常の詰将棋より緩い条件である、協力詰めを足がかりにしたのはアプローチ的に正解だったということですな…。
横型探索のperft depth = ７～８相当のノード数ですね。
それで探索深さ４９９０９まで潜るのですから、、、。
縦型探索恐るべし、、、であります。
https://twitter.com/yaneuraou/status/683539246339112960?ref_src=twsrc%5Etfw
反復深化と置換表が恐るべしということですね…。