PinCheck機構つきのMakeMoveの提案 - Bonanzaソース完全解析ブログ

■　「pin」という用語の定義

駒を動かすと王手になる駒は「pinされている」と言う。

玉金　　　　^飛

のようになっていれば(飛車は後手の飛車)、金を右以外に動かすと玉をとられてしまう。すなわち、非合法手である。
このとき「金は、横方向にpinされている」と言う。横方向にしか動けないように"ピン"で固定されていると捉えるわけだ。

■　pinの判定

pinされうる方向は、「横」(rank)、「縦」(file)、「斜め左上から右下」(diag1)、「斜め右上から左下」(diag2)の4種類である。

さきほどの金は、玉との位置関係は「横」rankであるから、「横」以外に移動させるなら、pin判定が必要である。
Bonanzaには、adirec[ nsquare ][ nsquare ]という位置関係を判定するためのテーブルがある。
これを使えば、盤上の2つの位置がrank,file,diag1,diag2,misc(それ以外)の5つのなかのいずれに属するかが一発で判定できる。

■　指し手生成時にpin判定をしてはならない

指し手生成時にpin判定をついでにしてしまおうと思うかも知れない。これは基本的にはよくないアイデアだ。指し手生成は、実際には生成した指し手を使わずに枝刈りが発生することは多々ある。そこで、指し手生成時に余計なことまですべきではない。指し手生成時にpin判定をするのはこの意味においては良くないアイデアだと言える。

■　MakeMoveのあとに王手がかかっているかを調べてはならない

MakeMove → InCheck(自王に王手がかかっているかを判定)　→(自玉に王手がかかっているなら)　UnMakeMove というのは良くない。それというのも、MakeMoveでは局面ハッシュ値やoccupied bitboardなどを更新したりしているのが普通であり、王手がかかっているのがわかってから局面を戻すというのは無駄なやりかただ。

また、InCheckは王手がかかっているかどうかをチェックするために自玉の地点に敵の利きがあるかを調べるが、それは利き情報を保たないプログラムにとっては結構大変なことであって、効率が良いとは言い難い。

■　移動させる前にpin判定を行なう

移動させる前にpin判定を行なうのは悪くないアイデアだ。

しかしpin判定のためには、指し手構造体(u32)からFrom(移動元)、To(移動先)をdecodeする(取り出す)必要がある。わざわざそれをdecodeしてMakeMoveの関数を別で呼び出すとそのなかでもdecodeすると2度手間である。

■　PinCheck機構つきのMakeMove

よって、私はPinCheck機構つきのMakeMove(Pinされていて移動させられない or 王手のかかっているところに玉を移動させるなら、MakeMoveをリタイアする)を作るのが良いと思う。

たとえば、駒打ちの場合は、pin判定自体が不要だ。(自玉に王手がかかっていない局面で駒を打って王手になることはないため)
駒を移動させる場合も、移動元が玉の8方向ray(rank,file,diag1,diag2)でなければ、その移動で空き王手になることはない。

移動先が移動元と異なるrayへの移動(例: rank→diag1や、rank→miscなど)のときだけ、その移動元がpinされているか判定すれば良い。これはBonanzaで言うとIsDiscoverBK/WKがそれである。(ただし、BonanzaはMakeMoveのなかでこの判定を行なっているのではなく、MakeMoveしてから、このIsDiscoverBK/WKは呼び出さずに、InCheckという王手がかかっているかを判定する関数で判定している。これではあまり効率はよろしくない。)

■　指し手生成時にpin判定すると本当に無駄なのか？

指し手生成時のpin判定が無駄だとは限らない。なぜなら、ひとたび、pinされている駒だと判定されれば、その駒を「移動先が移動元と異なるrayへの移動」させる手はすべて非合法手であるとわかるからだ。例えば、金が斜め(diag1)方向にpinされているとしたら、移動先のうち5箇所は非合法手である。

しかし、その場合でも玉が敵の利きのある場所への移動に関しては、(利き情報を保たないソフトの場合)まとめて除去できないため、この部分は、「PinCheck機構つきのMakeMove」を使ってMakeMoveのなかで行なうべきだ。

また、このように指し手生成時にpin判定を行なえば、1度のpin判定によって生成される非合法手をまとめて除去できるというメリットがある。指し手をオーダリングして並び変えたあとでは、まとめて除去は不可能に近い。

それなら、指し手生成時にpinされているか判定しなければならないが、これを高速化することは出来ないだろうか？私はこれに関していくつかのアイデアを考えたのだが、あまりうまくいきそうにない。この部分にこれ以上時間を費やしている時間が惜しいので、これに関しては今回は見送る。

また、BonanzaのMate3Plyのように、gen_check(王手になる手の生成)をしたあとオーダリングのために生成された指し手の並び変えを行なわない場合に限り、生成後にまとめて除去は可能である。しかしgen_check(王手になる手)で、その駒がpinされていて、かつ、それらがまとめて除去できるケースはかなりのレアケースなので、これに関してはたいした効果が見込めない。

そこで、ここでの結論はひとまず「PinCheck機構つきのMakeMove」を使うということにしたい。
MakeMoveで相手に王手がかかったかどうかも同時に判定するバージョンも別途用意すれば良いように思う。