Killer Heuristic は、同じ深さの兄弟ノードで beta cut を起こした静かな手を覚えておき、 次の兄弟ノードでも優先して読む手の並べ替え手法である。
アルファベータ法では、有望な手を先に調べるほど枝刈りが増える。 Killer Heuristic は、
という経験則を利用する。
ここでいう「静かな手」とは、通常は大きな駒取りではない手を指す。 良い捕獲手は別の方法で高順位に並べられることが多いので、 Killer Heuristic は主に quiet move の順序付けに効く。
典型的には、各 ply ごとに 2 個前後の killer move を覚える。 探索中に quiet move が beta cut を起こしたら、 その手をその ply の killer として保存する。
次に同じ深さの別ノードを探索するときは、
の順で調べることが多い。
Move killerMoves[MAX_PLY][2];
void storeKiller(int ply, Move move) {
if (killerMoves[ply][0] != move) {
killerMoves[ply][1] = killerMoves[ply][0];
killerMoves[ply][0] = move;
}
}
int scoreQuietMove(int ply, Move move) {
if (move == killerMoves[ply][0]) return 900000;
if (move == killerMoves[ply][1]) return 800000;
return 0;
}実際には history heuristic と組み合わせて、 killer を高い優先度ボーナスとして扱うことが多い。
将棋では受けの手や形を整える手が強い quiet move になることがあり、 それらが兄弟ノードでも有効な場合がある。 そのため Killer Heuristic は、特に中盤の quiet move ordering に役立つ。
ただし、
などは別系統の優先付けをした方が自然なことが多い。