Source of History Heuristic history-heuristic

  # History Heuristic

History Heuristic は、過去に枝刈りへ貢献した quiet move に高い履歴スコアを与え、
次回以降の[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)で優先する手法である。

## 概要

Killer Heuristic が「同じ深さ」の経験を使うのに対して、
History Heuristic はより広い範囲で

- この手は過去に良い結果を出した

という履歴を蓄積する。

典型的には、

- quiet move が beta cut を起こしたら加点する
- 深いところで起こした cut ほど大きく加点する
- ordering では score の高い手を先に読む

という形で使う。

## どう保存するか

チェスでは `from-to` や `piece-to` をキーにすることが多い。
将棋でも同様に、

- 駒種
- 移動先
- 打ち駒かどうか
- 成りかどうか

を含めた形で拡張して持つことが考えられる。

## 実装例

```cpp
int historyTable[PIECE_NB][SQ_NB];

void updateHistory(Piece pc, Square to, int depth) {
    historyTable[pc][to] += depth * depth;
}

int historyScore(Piece pc, Square to) {
    return historyTable[pc][to];
}
```

使いすぎるとスコアが偏るので、実戦的には aging や clamp を入れることが多い。

## Killer Heuristic との違い

- Killer は ply ごとの局所的な記憶
- History は局面横断的な統計的記憶

という違いがある。

そのため、

- killer は即効性が高い
- history はより広く安定して効く

という見方ができる。

## 将棋AIでの位置づけ

将棋では quiet move の候補数が多くなりやすいため、
captures や王手以外の手に順序を付ける材料が重要になる。
History Heuristic はその中核になることが多い。

また、近年は

- [countermove heuristic](/shogi/shogiwiki/search/countermove-heuristic/)
- continuation history
- capture history

のように発展した履歴系も使われる。

## 注意点

- 局面依存性の低い統計なので、外れた場面では逆効果もある
- 更新量が大きすぎると偏りやすい
- 打つ手や成りの扱いなど、将棋では設計が少し複雑になる

## 関連項目

- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [Killer Heuristic](/shogi/shogiwiki/search/killer-heuristic/)
- [countermove heuristic](/shogi/shogiwiki/search/countermove-heuristic/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)

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

- [Chessprogramming Wiki: History Heuristic](https://www.chessprogramming.org/History_Heuristic)
- [Chessprogramming Wiki: MOVE Ordering](https://www.chessprogramming.org/Move_Ordering)
History Heuristic history-heuristic history-heuristic
