Bonanzaの3手詰み判定関数はどういう処理になっているのか【中編】

前回(→ http://d.hatena.ne.jp/LS3600/20091205 )の続き。

今回は、Bonanzaの3手詰み判定関数のis_mate_in3plyについての解説。ソースは私がいくつか書き換えている。ソースに書かれたコメントは私の手によるコメント。

// 3手詰みなのか。
bool is_mate_in3ply( Tree * restrict ptree, Turn turn, Ply ply )
{
	// 3手で探索打ち切りまで行ってしまうなら探索しない。
  if ( ply >= PLY_MAX-2 ) { return false; }

  ptree->anext_move[ply].move_last = ptree->move_last[ply-1];

	// 王手になる手をすべて生成
	// 前の探索深さで生成した指し手の最後から続きを生成する。
  ptree->move_last[ply] = GenCheck( turn, ptree->move_last[ply-1] );

	// ptree->anext_move[ply].move_lastが生成された指し手の開始点。
	// ptree->move_last[ply]が生成された指し手の終端。

	// 生成されたすべての指し手に対して、ひとつでも詰む手があれば詰み。(or接点なので)
  while ( ptree->anext_move[ply].move_last != ptree->move_last[ply] )
    {
			// 生成された指し手のうちひとつ取り出す。
      MOVE_CURR = *ptree->anext_move[ply].move_last++;

			// この生成された指し手が合法手であるか
      assert( is_move_valid( ptree, MOVE_CURR, turn ) );

			// 指し手で局面を進める。
      MakeMove( turn, MOVE_CURR, ply );
      if ( InCheck(turn) )	// 王手が回避できていないのでこの王手は無効な指し手。(pinされている駒を動かした。)
      {
        UnMakeMove( turn, MOVE_CURR, ply ); // 局面を戻して次の手を調べる。
        continue;
      }

			// この進めて局面に対してすべての回避手が詰みならこの局面は詰み(and接点なので)
      bool value = mate3_and( ptree, (Turn)~turn, ply+1 );
      
      // 指し手で局面を戻す。
      UnMakeMove( turn, MOVE_CURR, ply );

			// 回避不能な王手が見つかったので詰み。
      if ( value ) { return true; }
    }

  return false;
}

move_lastは指し手生成用のバッファを指し手いる。plyは探索開始局面からの深さ。指し手生成バッファは、(move_last[ply-1] - 1)までが使用済みなので、深さplyでは、move_last[ply-1]から使っていく。深さplyで、生成された指し手の終端を move_last[ply]に入れておく。こうすることによって、指し手生成バッファは先頭から隙間なく使用される。この部分、うまく考えてあると思う。

anext_move[ply]は、C++派には、"iterator"だと言えばわかりやすいだろう。Bonanzaでは、全体的に、move_lastに生成しておいて、anext_moveをインクリメントしながら、1手ずつ調べていくという書き方をしてある。またMOVE_CURRは、C++派に説明するなら、"*iterator"を表現するマクロである。Bonanzaでは現在の探索深さの評価中の指し手をこのマクロを用いて書くことが多い。

3手詰めの範囲で言えば、このanext_moveに格納する必要はないのでローカル変数を使ったほうがこの部分は高速化できる。あと、3手詰み判定では指し手のオーダリングは行なわないのですべての王手(GenCheck)を生成してしまうとその生成時間がもったいない。ここは逐次生成にすると途中でリタイアしたときに無駄な手を生成せずに済むのでその分だけ高速化する。逐次生成に変更するなら、指し手生成バッファ自体不要である。あとplyを引数渡しにする必要もなくなる。どうせ探索限界(PLY_MAX = 32)に達することはまず無いだろうし。

また、上のソースを見てわかるようにpinされているかも知れない指し手をMakeMoveしてから、自玉が王手であれば(pinされている駒だったのであるなら)手を戻しているが、たとえば駒打ちでpinされることは無いので、こういう判定方法をとると、MakeMove(これでハッシュ値も更新している)/UnMakeMoveを行なう時間が無駄である。また駒移動の場合も、IsDiscoverBK/WKマクロを用いると事前にpinされているかどうかは判定できるのでMakeMoveの前に行なうか、MakeMoveとIsDiscoverBK/WKとが合体した関数を作るかすれば、この部分は高速化できる。

それから3手詰め判定では置換表を用いないのでハッシュ値の更新は不要である。この部分、高速化するならハッシュ値を更新しないカスタム版のMakeMove/UnMakeMoveを作るべきだろう。ついでに、指し手生成バッファを用いないならMakeMove/UnMakeMoveなどもplyを渡す必要がなくなるるのでこの部分でも高速化できる。