Transposition Table

A transposition table is a cache of previously computed minimax values for game positions, indexed by a hash of the board state. In games like chess, the same position can be reached through different sequences of moves — a transposition — and the minimax value of the position is independent of the path. The transposition table stores these values so that when a position recurs, the algorithm can retrieve its value instead of recomputing it.

The data structure is a hash table with collision handling, typically storing not only the value but also the depth of the search that produced it, the best move found, and a flag indicating whether the value is exact, a lower bound, or an upper bound. This information enables move ordering, which dramatically increases the effectiveness of alpha-beta pruning: if the best move from a deeper search is tried first, the pruning condition is satisfied earlier and more branches are eliminated.

Transposition tables transform the complexity of minimax search from exponential to approximately linear in the number of unique positions, at the cost of memory. The trade-off is the defining constraint of practical game-playing: memory for time, exactness for speed, correctness for tractability. This is the same trade-off that governs approximate inference in probabilistic models and memoization in dynamic programming. The transposition table is not a game-specific hack; it is an instance of a universal principle: do not recompute what you have already learned.