Bonanzaの1手詰み判定関数はどういう処理をしているのか
■ Bonanzaの詰み判定ルーチン
Bonanzaの詰み判定は1手詰み判定(mate1ply.c)と3手詰み判定(mate3ply.c)とがある。今回は前者を解説。
■ mate1ply.c
// 1手詰みチェック関数を手番に応じて呼び分けるためのマクロ #define IsMateIn1Ply(turn) \ ( (turn) ? is_w_mate_in_1ply( ptree ) \ : is_b_mate_in_1ply( ptree ) )
1手詰み判定関数本体は次のもの。
// 先手番の1手詰みのチェック(後手玉が1手で詰むかどうか) // 先手玉に王手自体がかかっていないなら、このメソッドの呼び出しをしてはならない。 // 戻り値は、詰みに導く指し手のひとつ。 // 詰まなければ0(MOVA_NA = 指し手なし)が返る。 Move is_b_mate_in_1ply( const Tree * restrict __ptree__ )
Bonanzaは利きを持っていないので比較的この関数は重い。(処理時間がかかる)
この関数は、後手玉に対して王手になる先手の手を順番に試してみる。駒の取り合いがあるとややこしいので、駒を取り合うケースはmate_3plyのほうがその処理を担う。
また、1手詰め判定のときにMakeMove/UnMakeMoveをするともったいないので、この関数のなかではMakeMove/UnMakeMoveは一切呼び出されない。
この関数のなかでやっていることは、次のことだけである。
1. 後手が王手になる手を生成する。王手になる手がなくなれば詰まないので関数は0(MOVE_NA)を返して終了。
2. 1.の手のTo(先手の駒の移動先 or 先手が駒を打った地点)に先手の利きなければその手は無効。1.へ。
3. 1.の手を着手してみて、王の退路(先手の利きのない場所)があるかを探す。退路があればその手は無効。1.へ。
4. 退路がなければその駒を取れるか調べる。すなわち、Toに後手の利きがあればその手は無効。1.へ。
5. 以上で王手が回避できなければその手によって詰むことが確定するのでその手を返して終了。
たいていの局面は詰まないので、この関数を一番最後までそれぞれの指し手を試して抜ける。これは非常に時間がかかる。事前に後手の利きのあるbitboardを生成できるなら、それを生成して、それとはmaskして無駄な指し手を試す時間を省略したほうがいいと思うが、利きのbitboardを高速に生成するのは(現状のBonanza)では難しいので、それはされていない。
あと、以下の関数も意味がわかっているとmate1plyを読みやすいだろう。
// 玉の退路を探す。敵の利きのない退路があるなら1。さもなくば0。 // bb = 玉が行けないところのmask。行けないところは1。 // ここには、toに(いま置いたばかりの)駒による利きがあると考えられる。 // また、玉はtoの場所にも特別に行けないと仮定する。 // (toには敵の利きのある場所に敵の駒を打つと仮定しているのでこの駒を玉では取れない。) // 自駒があるところも、玉はもちろん行けない。 static int can_w_king_escape( Tree * restrict ptree, BoardPos to, bitboard bb ); static int can_b_king_escape( Tree * restrict ptree, BoardPos to, bitboard bb ); // toにある駒を取るとこが出来るのか。toにある駒を取って空き王手にならないのか。 // 取ることができるなら1。さもなくば0。 // toの地点には敵の利きがあるので王で取る手は考えない。 // また、toの地点にある駒をとるときにpinされているかはチェックする。 static int can_w_piece_capture( const Tree * restrict ptree, BoardPos to ); static int can_b_piece_capture( const Tree * restrict ptree, BoardPos to );
実際にmate1plyを読んでみる。
// 先手玉に王手自体がかかっていないなら、このメソッドの呼び出しはおかしい。 assert( ! is_【black】_attacked( ptree, SQ_【B】KING ) ); /* Drops */ // 駒が打てる場所 bb_drop = ~ (BB_BOCCUPY | BB_WOCCUPY); // 飛車を持っていたなら if ( HAND_【B】.HasRook() ) { // 後手玉の上下左右の4つのマスで駒の打てるところ。 // 遠い位置からの飛車打ちは合駒が出来てややこしいのでmate3plyのほうで行なうことにして // ここでは除外されている。 // // 十字の利きを持つbitboardを作るために先手・後手の金の利きを合成しているのは // 面白い。十字の利きを持つbitboardを事前に用意しておいたほうが高速化できるが、 // 保木さんはなるべく無駄なテーブル作成をしたくないのかも知れない。 bb = (abb_【w】_gold_attacks[SQ_【W】KING] & abb_【b】_gold_attacks[SQ_【W】KING]) & bb_drop; foreach_bitboard_firstone_no_check(bb , to , { // そこに先手の利きがないならその手は考えない。 if ( ! is_【white】_attacked( ptree, to ) ) { continue; } // 飛車の利きを表現するbitboardを得る。 bb_attacks = abb_file_attacks[to][0]; bb_attacks.p[aslide[to].ir0] |= ai_rook_attacks_r0[to][0]; // 打った飛車の利きが生きているものとして、玉の退路があるかを探す。 if ( can_【w】_king_escape( ptree, to, bb_attacks ) ) { continue; } // あとは、後手が王以外の駒でこの打ったばかりの飛車を取れるのか調べる。 if ( can_【w】_piece_capture( ptree, to ) ) { continue; } // もし退路がなく駒を取りながらの移動もできないならこの指し手で詰みである。 return To2Move(to) | Drop2Move(rook); }); // 以下は香打ちだが、 // 飛車打ちを試したのならば、飛車は香の利きを包含するので香打ちを試す必要はない。 // そこでelse ifで書かれている。また、後手玉が1〜8段目にいなければ香打ちで王手にならないので // そのケースも事前に除外しておく。 } else if ( HAND_【B】.HasLance() && SQ_【W】KING 【<=】 【I2】 ) {
私のコメントがついているので、それ以上の解説は不要だろう。
"【 】"で書かれているところは、YaneLispを使って私が書き換えたもので、先手用と後手用の場合とで適宜文字置換がなされる。(例 【B】は先手用なら"B"、後手用なら"W"と文字置換される。)
■ まとめ
今回は1手詰み判定関数を詳しく解説した。次回は3手詰み。