Source of Killer Heuristic killer-heuristic

  # Killer Heuristic

Killer Heuristic は、同じ深さの兄弟ノードで beta cut を起こした静かな手を覚えておき、
次の兄弟ノードでも優先して読む[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)手法である。

## 概要

[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)では、有望な手を先に調べるほど枝刈りが増える。
Killer Heuristic は、

- ある深さで cut を起こした静かな手は
- 似た局面でも有効であることが多い

という経験則を利用する。

ここでいう「静かな手」とは、通常は大きな駒取りではない手を指す。
良い捕獲手は別の方法で高順位に並べられることが多いので、
Killer Heuristic は主に quiet move の順序付けに効く。

## どう使うか

典型的には、各 ply ごとに 2 個前後の killer move を覚える。
探索中に quiet move が beta cut を起こしたら、
その手をその ply の killer として保存する。

次に同じ深さの別ノードを探索するときは、

- hash move
- 良い捕獲手
- killer move
- その他の quiet move

の順で調べることが多い。

## 実装例

```cpp
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](/shogi/shogiwiki/search/history-heuristic/) と組み合わせて、
killer を高い優先度ボーナスとして扱うことが多い。

## 将棋AIでの位置づけ

将棋では受けの手や形を整える手が強い quiet move になることがあり、
それらが兄弟ノードでも有効な場合がある。
そのため Killer Heuristic は、特に中盤の quiet move ordering に役立つ。

ただし、

- 王手
- 大きな駒取り
- 成り

などは別系統の優先付けをした方が自然なことが多い。

## 注意点

- captures と quiet moves を混ぜて使うと順序付けが崩れやすい
- 同じ ply でも局面が大きく違うと、killer が役に立たないこともある
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)や[countermove heuristic](/shogi/shogiwiki/search/countermove-heuristic/)の方が効くことも多い

## 関連項目

- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)
- [countermove heuristic](/shogi/shogiwiki/search/countermove-heuristic/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)

## 参考にしたホームページ

- [Chessprogramming Wiki: Killer Heuristic](https://www.chessprogramming.org/Killer_Heuristic)
- [Chessprogramming Wiki: MOVE Ordering](https://www.chessprogramming.org/Move_Ordering)
Killer Heuristic killer-heuristic killer-heuristic
