ハッシュテーブルは、キーから高速に値を引くためのデータ構造である。 将棋AIでは主に置換表として使われるが、 評価や持ち駒構成などの補助表にも応用される。
ハッシュテーブルでは、
を組み合わせて高速な参照を行う。
探索では、
などをキーにして、すでに計算した結果を再利用する。
もっとも重要なのが置換表である。 ゾブリストハッシュなどの局面キーを使って、
を保存する。
評価関数が高価な場合は、 評価結果だけを保存するハッシュテーブルを持つこともある。
チェスでは material hash や pawn hash が有名だが、 将棋でも持ち駒や駒組みのまとまりに対して補助表を持つ発想は応用できる。
struct HashEntry {
uint64_t key;
int value;
};
HashEntry table[TABLE_SIZE];
HashEntry* probe(uint64_t key) {
return &table[key % TABLE_SIZE];
}実戦的には、
といった工夫が入る。
ハッシュテーブルでは、異なるキーが同じ場所へ落ちる衝突が起こる。 そのため、
といった設計が必要になる。
将棋AIでは分岐数が大きく、同じ種類の計算を何度も行いやすい。 そのためハッシュテーブルは、単なる高速化ではなく探索全体の基盤といえる。