Qhapaq Lab

Countermove Heuristic

Countermove Heuristic は、「ある手には自然な応手がある」ことを利用して、 直前の相手の手に対する有力な返し手を記録し、手の並べ替えに使う手法である。

概要

Killer Heuristicが同じ深さの兄弟ノードを横断して使われるのに対し、 Countermove Heuristic は

  • 直前の手 A に対して
  • 応手 B が強かった

という対応関係を覚える。

そのため、位置そのものより 「直前に何を指されたか」 に注目するヒューリスティクといえる。

どう保存するか

典型的には、

  • 直前手の from-to
  • または piece-to

をキーにして、その返し手を 1 つ記録する。

チェスでは 64x64 の butterfly 的な表や piece-to 表が使われる。 将棋でも考え方は同じだが、

  • 打つ手
  • 成り
  • 持ち駒

があるため、キー設計は少し複雑になる。

実装例

Move countermoveTable[PIECE_NB][SQ_NB];

void storeCountermove(Piece prevPiece, Square prevTo, Move reply) {
    countermoveTable[prevPiece][prevTo] = reply;
}

Move probeCountermove(Piece prevPiece, Square prevTo) {
    return countermoveTable[prevPiece][prevTo];
}

ordering では、probe した手に大きめのボーナスを付ける。

どんなときに効くか

たとえば、

  • 相手の歩突きに対する自然な受け
  • 相手の王手に対する有力な逃げ
  • 相手の攻め駒前進に対する反撃

のように、直前手に対して自然な応手が決まりやすい局面で効きやすい。

将棋AIでの位置づけ

Countermove Heuristic は、 history heuristicよりも局所的で、 Killer Heuristicよりも手順依存である。

そのため、

  • history で大まかな統計を取り
  • countermove で直前手への自然な返しを優先する

という併用がしやすい。

注意点

  • 直前手に引きずられすぎると、局面全体の事情を見落とすことがある
  • 将棋では打つ手や成りの扱いをどうキーに含めるかが悩ましい
  • 長い文脈を見たい場合は continuation history の方が強いこともある

関連項目

参考にしたホームページ