将棋プログラムに何故coroutineが必要なのか
■ 将棋プログラムに何故coroutineが必要なのか
Bonanzaの3手詰めルーチンや静止探索ではcoroutineが使われている。coroutineについて理解していないとこれらの処理はとても読みがたく、理解できない。
今回は、将棋プログラムに何故coroutineが必要なのかについて考えてみたい。
■ 将棋プログラムを遅延処理(lazy evaluation)という観点で捉える
探索はいい手が見つかるとそこで打ち切られる。打ち切りというより、以前の分岐場所まで巻き戻す(unwind)というほうが近いかも知れない。
つまり、
・すべての指し手を生成しても、それらをすべて使わないかも知れない。
・局面を正確に評価しても本当はその時点ではそこまで正確な評価は必要ないかも知れない。
・盤面の各情報を更新しても、すぐに巻き戻すことがわかっているときはその更新は無駄になる。
など。高速化のためには必要に迫られない限り処理するべきではない。
例えば、詰め将棋ルーチンで、王手されてそれを回避する手を考えてみる。いきなりすべての回避手を生成するのは無駄である。たいていは、利きのないところに王を移動させるか王手している駒を取る変化を調べれば詰まないことが確定するからである。
つまり、典型的な詰み判定ルーチンは遅延指し手生成を行なうなら、
while (move = 王手回避手を1手取り出す() )
{
tree.MakeMove(move); // その指し手で局面を進める
// なにか処理
tree.UnMakeMove(move); // その指し手で局面を戻す
}こういう構造になる。
「王手回避手を1手取り出す」関数では、必要に応じて指し手を生成して返す。Bonanzaの3手詰み判定ルーチンならば、この「王手回避手を1手取り出す」に相当する関数がgen_next_evasion_mateだ。
必要に応じて指し手を生成するためには、C#ならyieldしていけばいいだけだが、C/C++なら前回どこまで処理したかを記録しておかないといけない。また、関数の先頭で、前回処理していた次のところにジャンプしなければならない。これは典型的にはswitch〜caseで書かれる。
また、「前回どこまで実行していたか」という状態は(王手回避ルーチンならば)ひとつずつ進んでいくだけなので、caseから次のcaseに落ちられる(fall through)というテクニックを使ったほうがcoroutineは書きやすい。
そもそも、caseでbreakを書かないと次のcaseラベルに進むという仕様は、switch〜caseでcoroutineを実現するために考え出されたものではないかと思う。そういう意味ではCが誕生したときからcoroutineはそこにあったと言っても過言ではない。
■ gen_next_evasion_mate
「王手回避手を1手取り出す」関数で使うenumと、その関数の実装は、Bonanzaならば次のようになっている。コメントはすべて私が追加した。またプログラムは一部変更してある。コメントを書いたのは、ずいぶん以前(Bonanzaの全体構造がよくわかっていないとき)なのでコメント自体が間違っていることもあることをいまさらながら申し上げておく。
// gen_next_evasion_mate(coroutine)で使うphaseを表わすenum。 // 詰み回避の検査のためのphase。 mate_king_cap_checker = 0, // まず王手している駒を王で取る手を生成 mate_cap_checker_gen, // 王手している駒を移動して捕獲する手の生成 mate_cap_checker, // ↑で生成した駒をひとつずつ渡す mate_king_cap_gen, // 王を移動して逃げる手の生成。駒の捕獲あり。ただし王手している駒を捕獲する手は除外。 mate_king_cap, // ↑で生成した駒をひとつずつ渡す mate_king_move_gen, // 王を移動して逃げる手の生成。駒の捕獲なし。 mate_king_move, // ↑で生成した駒をひとつずつ渡す mate_intercept_move_gen, // 利きのある場所へ合駒して受ける手の生成の生成 mate_intercept_move, // ↑で生成した駒をひとつずつ渡す mate_intercept_weak_move, // ↑↑で生成した駒をひとつずつ渡す。intercept_weak_moveとは利きのない場所への中合い。
// 王手の回避手を生成する。ここで生成される手によって王手は100%回避できている。
// 生成された指し手は、MOVE_CURRに入る。呼び出されるごとに新しい手が生成されて、
// それ以上生成できなくなれば(回避する手がない)、この場合、この関数の返し値としてfalseが返る。
// すなわち、この関数はcoroutineになっている。
bool gen_next_evasion_mate( Tree * restrict ptree, const BoardPos *psq, Ply ply , Turn turn )
{
switch ( ptree->anext_move[ply].next_phase )
{
// まず王手している駒を王で取る手を生成
case mate_king_cap_checker:
ptree->anext_move[ply].next_phase = mate_cap_checker_gen;
MOVE_CURR = gen_king_cap_checker( ptree, psq[0], turn );
// その手があったのならいったん返ってその手を評価する。
if ( MOVE_CURR ) { return true; }
// 王手している駒を移動して捕獲する手の生成
case mate_cap_checker_gen:
// まず生成する。(複数あり)
ptree->anext_move[ply].next_phase = mate_cap_checker;
ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
ptree->move_last[ply] = ptree->move_last[ply-1];
if ( psq[1] == nsquare )
{
ptree->move_last[ply]
= gen_move_to( ptree, psq[0], turn, ptree->move_last[ply-1] );
}
// ↑で生成した指し手に関してひとつずつ調べていく。
case mate_cap_checker:
if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
{
MOVE_CURR = *(ptree->anext_move[ply].move_last++);
return true; // まだ処理は続きますよー
}
// 王を移動して逃げる手の生成。駒の捕獲あり。ただし王手している駒を捕獲する手は除外。
case mate_king_cap_gen:
// まず生成する。(複数あり)
ptree->anext_move[ply].next_phase = mate_king_cap;
ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
ptree->move_last[ply]
= gen_king_move( ptree, psq, turn, true, ptree->move_last[ply-1] );
// ↑で生成した指し手に関してひとつずつ調べていく。
case mate_king_cap:
if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
{
MOVE_CURR = *(ptree->anext_move[ply].move_last++);
return true; // まだ処理は続きますよー
}
// 王を移動して逃げる手の生成。駒の捕獲なし。
case mate_king_move_gen:
ptree->anext_move[ply].next_phase = mate_king_move;
ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
ptree->move_last[ply]
= gen_king_move( ptree, psq, turn, false, ptree->move_last[ply-1] );
// ↑で生成した指し手に関してひとつずつ調べていく。
case mate_king_move:
if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
{
MOVE_CURR = *(ptree->anext_move[ply].move_last++);
return true; // まだ処理は続きますよー
}
// 合駒して受ける手の生成。利きのある場所に合駒(移動合い)するのが優先。
case mate_intercept_move_gen:
ptree->anext_move[ply].remaining = 0;
ptree->anext_move[ply].next_phase = mate_intercept_move;
ptree->anext_move[ply].move_last = ptree->move_last[ply-1];
ptree->move_last[ply] = ptree->move_last[ply-1];
if ( psq[1] == nsquare && abs(BOARD[psq[0]]) != knight )
{
ptree->move_last[ply] = gen_intercept( ptree, psq[0], turn,
&(ptree->anext_move[ply].remaining) , ptree->move_last[ply-1] );
}
// ↑で生成した指し手に関してひとつずつ調べていく。
case mate_intercept_move:
if ( ptree->anext_move[ply].remaining-- )
{
MOVE_CURR = *(ptree->anext_move[ply].move_last++);
return true;
}
ptree->anext_move[ply].next_phase = mate_intercept_weak_move;
// 弱移動合い(この指し手生成は、mate3_andのほうで行なっている。)
// 弱移動合いとは、利きの無い場所への移動中合い。これで詰みを逃れることは滅多にないのだが。
case mate_intercept_weak_move:
if ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
{
MOVE_CURR = *(ptree->anext_move[ply].move_last++);
return true;
}
break;
default:
#if defined(NDEBUG)
__assume(0); // こう書いて心持ち高速化
#else
assert(0); // ここに飛んできちゃ駄目。
#endif
}
// 王手を回避する指し手が尽きたのでfalse。あるいはcoroutineが終了したのでfalse。
return false;
}■ まとめ
将棋プログラムに何故coroutineが必要なのか、Bonanzaではそれがどう使われているかについて解説した。現実的には高速化のためにはcoroutineにしないケースもあるが、この手の処理は基本的にはcoroutineで書くものなのだと知って欲しい。
