中合い問題の解説その5 - Bonanzaソース完全解析ブログ

大切なことをいくつか書くのを忘れていたので、解説。

■　3手詰みの打ち/移動中合い省略定理　の補足説明

まず上の局面は王手のかかっている局面です。(12飛打とした局面だと考えてください)
52金引だと83金で1手詰み。玉から4マス離れたところに移動合いして詰んだので、それ以上離れたところに移動合いしても無駄かと言えばそうではなく、42金で不詰み。(61に置いてある桂は、この桂を置いておかないと詰むようなので置いてみました。)

これは、52金引きだと13の飛車のラインが玉の8近傍に届くので、玉周辺の勢力関係が変わるためです。

そこで、実際のプログラムでは、次のような方法でこれを解決します。

まず中合いフェーズに入る前に(要するにこの時点で玉は逃げられず、かつ、飛び駒で王手されていて、それが取れず、両王手ではなく、かつ、玉の8近傍への合い駒では詰みを回避できないことが確定しています。)、飛び駒を消去して1手で詰むかを(mate1ply関数で)確認します。

a) これで詰むことがわかった場合

このとき、どこで飛び駒の利きを(受け方の利きのある場所に駒を打つなどして)遮断しても詰みます。(角のラインと交差するところに中合いして詰みを回避できるパターンは、「3手詰みの打ち中合い省略定理」のほうを参考に。)

また、移動中合いで詰みを回避するには、その移動によって受け方の駒を10近傍に利かせる必要があります。これは「3手詰みの移動中合い省略定理」の条件となります。

b) これで詰まないことがわかった場合

このとき、飛び駒の利きを(受け方の利きのある場所に駒を打つなどして)遮断できれば詰みません。

手駒がなかったり、あるいは利きのある場所に駒を打てないなどした場合は、移動中合いで回避できるか考える必要があります。しかし、移動中合いしたときに敵の飛び駒の利きが、玉の10近傍に利いてくると、詰まなかったものが詰むことになりかねません。上の局面は、このケースです。

※ 移動中合いして同角のように駒を渡す場合は、渡した駒によって詰まなかったものが詰むようになる可能性があります。

a) b) いずれにせよ、まず一番簡単なケースについて調べて、そこから王周辺の勢力関係が変わらなければ詰む/詰まないという状態は変わらないということを利用しています。王周辺の勢力関係(具体的には王の10近傍の利きの数)が変わったときにのみ1手詰め判定を呼び出して詰み/不詰みが変わっていないかを確認します。

■　「利きのある場所」の定義とは？

Bonanzaの3手詰みルーチンで利きのある場所をどうやって判定するかというと、中合いフェーズで、中合いできる場所を玉の近くから順番に探していきます。

この地点をXとしますと、このXに移動させられる駒を探します。(このときpin判定もします) すなわちXに利いている駒です。これらの駒をXに移動させる指し手を生成します。このとき生成された指し手の数がN個だとします。Nが2より大きければ、Xには2枚以上の駒が利いているわけで、Xには利きがあると言えます。

では、Nが1ならXには利きはないのでしょうか？私はこの部分を勘違いしていたのですが、

Ｘ
歩
香

こうなっていると、Ｘに移動させられる駒は歩しかありませんが、歩を移動させたあとＸには利きがあります。「利きのある場所に駒を移動させた」ことになっています。

Bonanzaではいままでこれで問題なかったのですが(すべての中合いする手を生成していたので)、もし移動合いの省略をするなら、上の図は N = 1ですが、利きのある場所への移動として扱わなければなりません。すなわち、歩の背後に香(or 飛車)がいるかをチェックして、もし香がいれば、香がpinされていないことも同時に判定しなければ、なりません。

そう考えると中合いの省略のためには、条件チェックがたくさんありますね。もちろんこれらの判定をしてでも中合いの応手生成を省略したほうが探索効率が上がり、全体的なnpsが増すことは間違いないのですが、いろいろ追加でコードが必要になり、どこかに条件的な抜けが1つでもあるとそれが原因で弱くなったりします。

■　3手詰みの移動中合い省略定理　の反例

こんな局面を思いつきました。

38角56香同角に65飛で3手詰めは逃れています。(3手詰めに限定しなければ、同角同飛に82飛で詰みます。)　この移動中合いで、香の移動元である55の地点と、角のラインとが交差するのは65の地点ですが、65の地点に利く駒は角で王手された瞬間には存在しないのに・・。

「交差している地点に利く受け方の駒があるか」という条件は、上の局面がうまく判定できるように飛車(or香)2枚とか角2枚(角で王手されているなら盤上の受け方に角が2枚あることはないのでこのチェックは省略できる)のチェックが必要なのでしょう。

■　交差している地点を見つける簡単な方法

例えば角のライン(diag1)で王手されているとします。

・diag1とそれと異なるラインのdiag1とは交わりません。なぜなら、平行だからです。
・diag1とdiag2とが交わるためには、その偶奇が一致していなればなりません。例えば、BoardPos(盤面座標で左上を0、右下を80とする番号)が3(6一の地点)にいる角のラインとBoardPos 4(5一の地点)にいる角のラインとは決して交わりません。筋違いの角になっているからですね。「偶奇が一致している」かどうかは、BoardPosを引き算して、bit 0を見ればわかります。

	BoardPos x,y;
	if ((x-y) & 1)
		continue; // 偶奇が異なるので決して交差しない

diag1,diag2の交点自体を計算式で求めることも出来るのですが(BoardPosを2次元座標に変換して直線の交点を求める公式にあてはめて、最後にまたBoardPosに戻す)、テーブルをlookupしたほうが確実に速いと思うので、それについては割愛。