置換表は、すでに探索した局面の結果を記録して再利用するための表である。 異なる手順から同じ局面へ到達することがあるため、 その結果を覚えておくことで探索を大きく節約できる。
探索中には、別の指し手順から同一局面へ合流することがある。 このような局面の重複をトランスポジションと呼ぶ。
置換表は、その局面に対して
を保存する。
典型的なエントリには次のような情報が入る。
EXACT, LOWERBOUND, UPPERBOUND最善手は手の並べ替えに使え、 bound 情報はアルファベータ法の枝刈りにも使える。
置換表は通常、ゾブリストハッシュのような局面ハッシュをキーにしたハッシュ表として実装される。 将棋では持ち駒や手番も局面の一部なので、ハッシュ値にもそれらを反映する必要がある。
enum BoundType {
BOUND_EXACT,
BOUND_LOWER,
BOUND_UPPER
};
struct TTEntry {
uint64_t key;
int depth;
int score;
BoundType bound;
Move bestMove;
};検索時は次のように使う。
TTEntry* entry = probeTT(hashKey);
if (entry && entry->key == hashKey && entry->depth >= depth) {
if (entry->bound == BOUND_EXACT) return entry->score;
if (entry->bound == BOUND_LOWER && entry->score >= beta) return entry->score;
if (entry->bound == BOUND_UPPER && entry->score <= alpha) return entry->score;
}置換表は次の2つの役割が特に大きい。
同じ局面を読み直さずに済むため、ノード数を大きく減らせる。
保存された最善手は hash move として最優先で試されることが多い。
これはアルファベータ法の効率に非常に強く効く。
ハッシュ表なので、異なる局面が同じ場所に入る衝突は避けられない。 そのため、
といった置換戦略が必要になる。