1 Definition and purpose

1.1 Basic concept

A transposition table is a data structure that stores previously evaluated states of a problem, such as board positions in a game, along with their computed values. It is typically implemented as a hash table, where each entry corresponds to a unique state identified by a compact key. When the same state is encountered again during a search, the stored value can be retrieved directly, avoiding redundant computation.

In artificial intelligence for game-playing, programs explore a game tree—a directed graph of positions and moves. Many distinct sequences of moves (transpositions) can lead to the same position. Without a transposition table, each occurrence would be evaluated from scratch, wasting computational effort.

1.2.1 Mitigating transpositions

Transpositions are common in games like chess, where pieces can reach the same square via different paths. The transposition table detects these equivalences and returns the stored result, effectively converting the tree into a directed acyclic graph for search purposes.

1.2.2 Improving depth and speed

By eliminating redundant evaluations, the transposition table allows search algorithms such as minimax with alpha-beta pruning to search deeper within the same time budget. The speedup is particularly pronounced in positions with many transpositions, leading to stronger play.

2 Hashing techniques

2.1 Zobrist hashing

Zobrist hashing is the most common method for generating hash keys in game-playing programs. It maps each possible game state (e.g., a chessboard configuration) to a nearly unique, fixed-size bit string.

2.1.1 Key generation

A table of random numbers is precomputed, one for each combination of piece type, color, and square. The hash key is the XOR of all random numbers corresponding to the pieces currently on the board. Starting from a zero key, each piece contributes its associated random value.

2.1.2 Incremental update

When a move is made, the hash key can be updated incrementally by XORing out the random numbers of the moved pieces from their source squares and XORing in those for the destination squares. This avoids recomputing the entire key from scratch, making updates extremely fast.

2.2 Collision handling

Despite the use of large hash keys (e.g., 64-bit), collisions are still possible, especially in memory-constrained tables. Two common strategies exist.

2.2.1 Open addressing

In open addressing, when a collision occurs (the desired table slot is occupied by a different state), the system probes subsequent slots—often linearly—until it finds an empty slot or a matching key. This method is simple and cache-friendly.

2.2.2 Separate chaining

Separate chaining uses linked lists to store multiple entries that hash to the same slot. While it reduces the probability of overwriting useful data, it increases memory overhead and can degrade cache performance.

3 Implementation details

3.1 Entry structure

Each entry in a transposition table typically contains several fields that encode the state and its search information.

3.1.1 Hash key

A full or partial hash key (e.g., 64-bit) is stored to verify that a retrieved entry corresponds to the queried state. Some implementations store a truncated key to save memory, at the cost of increased collision risk.

3.1.2 Value and depth

The computed value (e.g., a score in centipawns for chess) and the search depth at which it was computed are stored. The depth allows the algorithm to decide whether the stored result is still useful for deeper searches.

3.1.3 Flag (exact, lower bound, upper bound)

A flag indicates the type of stored value:

  • Exact: the true minimax value at the stored depth.
  • Lower bound: the value is a lower bound (beta cutoff).
  • Upper bound: the value is an upper bound (alpha cutoff).

This information allows alpha-beta pruning to refine subsequent searches.

3.2 Replacement strategies

When the table is full, new entries must replace old ones. The chosen strategy affects performance.

3.2.1 Always replace

The simplest policy: new entries overwrite whatever occupies their slot. This can discard deep, useful entries in favor of shallow ones.

3.2.2 Depth-based replacement

Entries are kept or replaced based on the depth they were searched. Deeper entries are considered more valuable and are retained over shallower ones. This is a common and effective heuristic.

3.2.3 Age-based replacement

Entries are tagged with a timestamp or generation number. Older entries are preferentially evicted. This is useful in iterative deepening, where recently computed results are more relevant.

3.3 Memory management

3.3.1 Fixed-size tables

Transposition tables are usually allocated as a fixed-size array of entries at program startup. The size is chosen based on available memory (e.g., several hundred megabytes for a chess engine). The fixed size simplifies memory management and access.

3.3.2 Table clearing and reset

Between games or search phases, the table may be cleared to avoid stale data. Some programs reset only the depth or flag fields, while others clear the entire table. Partial clearing (e.g., setting all entries to invalid) is often faster.

4 Applications

4.1 Chess engines

Transposition tables are a cornerstone of modern chess programs. They enable deep searches by reusing evaluations across different move sequences.

4.1.1 Stockfish and Crafty

Stockfish, one of the strongest chess engines, uses a heavily optimized transposition table with Zobrist hashing, depth-based replacement, and a fixed-size memory pool. Crafty, another well-known engine, also relies on transposition tables and pioneered many implementation techniques.

4.2 Other combinatorial games

4.2.1 Go

In Go, the large branching factor and long game duration make transposition tables less dominant than in chess, but they are still used in combination with Monte Carlo tree search (MCTS). Some MCTS variants store state-value estimates in a transposition-table-like structure.

4.2.2 Checkers and Othello

Programs for checkers and Othello benefit significantly from transposition tables, as these games have many transpositions. The tables help search algorithms solve endgame databases and improve tactical play.

4.3 Beyond games

4.3.1 Constraint satisfaction problems

In constraint satisfaction, transposition tables can cache the result of exploring a partial assignment, avoiding redundant search when the same partial state is reached via different variable orderings.

4.3.2 Pattern databases

Pattern databases used in heuristic search (e.g., for sliding-tile puzzles) store distances to goal states. Although not always called transposition tables, they share the same principle of memoizing state evaluation to speed up search.

5 Limitations and trade-offs

5.1 Hash collisions

A collision occurs when two different states map to the same table slot. This can cause incorrect results or lost information. While large hash keys and careful replacement policies reduce the risk, collisions are unavoidable with finite memory and can lead to degraded search quality.

5.2 Memory consumption

Large tables require substantial RAM, which may be limited on some platforms (e.g., mobile devices or embedded systems). Conversely, small tables may thrash, evicting useful entries too frequently. Balancing memory usage and performance is a key design decision.

5.3 Accuracy degradation in non-deterministic contexts

In games with stochastic elements (e.g., dice in backgammon) or in nondeterministic problem domains, the stored value may depend on random outcomes that are not fully captured by the state. Using a transposition table in such contexts can introduce approximation errors unless special care is taken.

6.1 Caching and memoization

Transposition tables are a specialized form of caching or memoization, where results of expensive function calls (state evaluation) are stored for reuse. The key distinction is the use of hashing for compact state representation and the emphasis on depth and bound information.

Iterative deepening depth-first search (IDDFS) is often used in conjunction with transposition tables. As the search depth increases gradually, the table accumulates results from previous shallow passes, guiding the deeper search.

In graph search, the principle of transposition refers to the fact that different paths can lead to the same node. Recognizing transpositions is essential for avoiding redundant work in many search algorithms, from game trees to planning and theorem proving.