合法手じゃない合法手のこと
■ はじめに
Bonanzaの指し手生成/合法手判定は結構ややこしく、ややこしい原因は将棋用語にいくつかの用語が不足しているからなのですが、ここではその不足している用語を新たに定義しながら、自分自身のためのメモを書き残しておきます。
自分用のメモですので文章は著しく読みにくいと思います。(すみません。)
■ 王手がかかっているか、いないのかで分類する
まず、将棋には
1) 自玉(手番側)に王手がかかっている局面
2) 自玉(手番側)に王手がかかっていない局面
の2つがあり、あらゆる局面はこの2つに分類できます。
ちなみに、
3) 敵玉(非手番側)に王手がかかっている局面
4) 敵玉(非手番側)に王手がかかっていない局面
のような分類は不可能で、3)は手番側がその敵玉を取れるはずで、すなわち、敵は直前の王手を無視して回避する手を指さなかったということなのでその直前の指し手が非合法手であると言えます。
では、1),2)について考えを進めていきます。
1)の場合、make_move(指し手によって盤面を次の状態に更新する)のときに、
・動かした駒による直接王手 and/or 動かした駒の影の利きによる間接王手
という動かした駒に連動する王手が発生します。つまり、敵玉に王手になるかどうかは、動かす駒に着目すれば、処理を少し端折れます。
2)の場合、王手を回避する指し手を選ばなくてはなりません。この王手を回避する指し手のことをここでは「回避手」と呼ぶことにします。(この用語が将棋用語として欲しいですね。)
回避手はBonanzaではevasionという名前がついており、GenEvasionならば回避手のみを生成します。
■ 自殺手とは
つまり、1)で自玉が指し手のあとに王手になるパターンは、自殺手を指した場合のみで、ここで言う「自殺手」とは、
A) pinされている駒をpinされていない方向に動かす(空き王手)
B) 王を敵の利きに移動させてしまう
の2通りです。どちらも非合法手です。
■ 回避手とは
同じく2)で自玉が指し手のあとに王手になるパターンは、回避手を指さなかったときです。ところがこの回避手というのは分類がすこぶる難しいです。
・玉が敵の利きのないところに移動する
・王手している駒を取る(両王手の場合はこれでは回避不可)
・合駒を打つ(両王手の場合はこれでは回避不可。また、合駒を打つためには攻撃駒と玉との間に空間がなければならない)
・移動合(移動させて合いをする。ただし、移動させる駒をpinされていない方向に動かすわけにはいかない)
この4パターンにわかれます。
この4パターンのいずれかに該当するのかを調べるぐらいなら、回避手をすべて生成して、そのなかにその指し手が含まれるかどうかを判定するのとさほど変わりません。
よって2)のパターンである指し手が合法手かどうかを判定する簡単な方法は無いと言えます。
1)のパターンですと、ある指し手が合法手かどうかを判定するには、二歩になっていないかだとか、移動できる場所への移動なのかだとか、駒打ちなら打つ先のマスが空いているのかだとか、大駒の移動であれば、移動元と移動先の経路のマスがすべて空いているかだとか…、まあ、Bonanzaのis_move_valid関数の解説のときに解説したことですね。
要するに、Bonanzaのis_move_validは
1)のパターンでpinされている駒かどうかは判定してくれません。自殺手かどうかも判定してくれません。
2)のパターンでの回避手になっているかどうかは判定してくれません。
まず、この2つが大事です。
■ 一般的にpin_checkと言うと..
一般的にpin_checkと言うとA),B)のことで、要するに1)のケースで合法かどうかをチェックすることです。私はpin_check付きのmake_move(pinされていればリタイアする)で高速化を図っているのですが、それは、A),B)のケースを検出して、リターンするという意味で、回避手になっているかのチェックをするわけではありません。すなわち2)のケースではpin_check付きのmake_moveは意味がないわけです。
それでどうするかというと、2)のケースでは実際にmake_moveして、手番側が王手がかかっている状態かを(InCheck関数で)調べて、王手がかかっていればunmake_moveで戻すという方針になります。
■ 合法手生成アルゴリズム
つまり、本当の合法手のみを生成するアルゴリズムは次のようになります。
C) 1)のケースならばpinされている駒をpinされていない方向に動かす指し手を除いて指し手生成。また玉は敵の利きのないところへの移動のみを生成。
D) 2)のケースならば回避手のみを指し手生成
D)はともかくC)でpinされていない方向に動かす指し手なのかどうかを判定するのはとても大変なのでBonanzaではこれらも生成してしまっています。将棋の指し手のほとんどは悪手なので生成してもmake_moveされることもないまま終わるケースが大半ですから、実際にmake_moveして自玉が王手がかかっていればやめよう、という方針です。
■ is_move_validは実は合法手判定ではない
何が言いたいかというと、is_move_validは合法手判定ではなく、make_moveする最低限の条件(必要条件)を満たしているかを判定する関数だということです。is_move_validで非0が返ってくればそのあとmake_moveしていいですが、ただしmake_move後に自玉に王手がかかっていたら、それは非合法手だったということなのでunmake_moveしてくださいね、という使い方をします。
is_move_validはkiller moveなどがその局面で合法かどうかを判定するのに使います。
その局面で合法とはすなわち、
1) is_move_validが非0
2) make_move後に自玉に王手がかかっていない
という2つの条件が必要です。
Bonanzaは、そういう感じのコードが書かれています。
ところで、これをpin_check付きのmake_moveを使うなら、次のようになります。
1) is_move_validが非0
2a) 現局面に王手がかかっていないなら、make_move_pin_check(移動後にその移動させた駒に関連することで王手になったならリタイアする)で動かす
2b) 現局面に王手がかかっているなら、これを動かさずに合法手かどうかを判定しにくいのでmake_moveで実際に動かして、そのあと自玉に王手がかかっていないことを確認する
というようなアルゴリズムになります。
なにせ、合法手判定というのは、結構難しいということです。
■ make_moveのときに相手に王手がかかるか判定しよう!!
次に、make_moveのときに相手に王手がかかったかどうかを判定するという技があります。これは実は簡単で、make_moveする前は相手に王手はかかっていないはずです。王手がかかっていれば王を取られるわけですから、直前の指し手が非合法手であったことになり、非合法手を指した局面から、さらにmake_moveすることはありえないからです。
※ ちょっと説明が前後しますが、is_move_validの条件を満たすならば非合法手であってもmake_moveすることは出来ます。ところが、その局面からさらにmake_moveすることは出来ません。make_moveして、自玉に王手がかかっているとわかればその局面をunmake_moveして戻す作業が必要になります。
さて、make_moveする前の局面では敵玉に王手はかかっていないことはわかりましたので、make_moveによって敵玉に王手がかかるパターンというのは、この動かす駒による直接王手と間接王手のみです。まじめに検出するより条件を端折れるわけです。
■ make_moveのときに敵玉に王手がかかるかどうかを判定するのはそこそこ良いアイデア
すなわち、make_moveのときに、敵玉に王手がかかるかどうかを同時に調べてしまうのはそこそこ良いアイデアだと思います。
ただし、killer moveの場合などでmake_move前の局面で王手がかかっている場合は、make_move後に自玉に王手がかかっていないことを確認して、確認後に王手がかかっていれば即座にunmake_moveするかも知れないので、その場合は、敵玉に王手がかかるかどうかを調べていたのは無駄になります。ゆえに、killer move用のmake_moveなんかも必要だったりして、私のプログラムは複雑怪奇になっていくのでした。
■ make_moveの前で自玉に王手がかかっているかを判定して場合分け
結局、make_move前の局面で自玉に王手がかかっているか、そうでないかで場合わけするのが賢いです。
Bonanzaでは、make_move前の局面で王手がかかっているときに指し手を1つずつ生成する関数はgen_next_move、王手がかかっているときに指し手をひとつずつ生成する関数はgen_next_evasionとなっています。これらはnext.cに記述されており、これらの関数は擬似的なcoroutineとなっています。
