Qhapaq Lab

History Heuristic

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

概要

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

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

という履歴を蓄積する。

典型的には、

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

という形で使う。

どう保存するか

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

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

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

実装例

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 はその中核になることが多い。

また、近年は

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

注意点

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

関連項目

参考にしたホームページ