Is a transposition table the same as an opening book?

No. An opening book stores prepared knowledge or move choices; a transposition table usually stores information generated by the current or recent search.

Can it help without returning a cached score?

Yes. A stored move can improve move ordering even when the score is not reusable.

Does every entry survive for the whole search?

Not necessarily. Finite tables replace entries, so previously examined positions may need to be searched again.

AI Glossary / Graphs and symbolic AI / Intermediate

Transposition table

Definition

A transposition table stores information about game positions that a search has already examined, so the information can be reused when a different sequence of moves reaches the same position. It reduces repeated work in game-tree search.

What it means

A game tree records move sequences, but different sequences can lead to an equivalent game state. Those repeated appearances are called transpositions. Searching the same position from scratch each time can waste substantial computation.

The table typically associates a state identifier with information such as a searched depth, a score or score bound, and a useful move. Reuse must respect what that information actually means. A shallow estimate is not automatically a complete solution, and a bound from an interrupted search is not necessarily an exact value.

The state must contain every rule-relevant detail needed for the intended reuse. In chess, identical piece placement alone is not always enough: the side to move and other rights affect the position, while some draw conditions also involve history.

How it works

When the engine reaches a position, it computes a compact key and probes the table. A suitable entry can avoid further search, tighten the range of possible scores or suggest a move to examine early. After searching, the engine stores or updates the result.

Alpha-beta search often produces one of three kinds of information: an exact score for the searched conditions, a lower bound or an upper bound. These must be distinguished. The stored search depth and scoring convention also affect whether the entry can safely support the current query.

Memory is finite, so entries may be replaced according to age, depth or another policy. Compact keys and table indexing introduce collision concerns; implementations use checks and conventions to reduce incorrect reuse. Replacement that merely discards useful information generally costs speed, whereas confusing two different states can threaten correctness.

Three practical examples

A chess engine reuses analysis when two opening move orders reach an equivalent position.
A board-game search uses a stored promising move to improve move ordering even when the stored score is not deep enough for direct reuse.
A game-development team measures repeated-state hits and memory use when choosing a table size for a fixed search budget.

Think of it this way

Think of a research notebook indexed by the situation reached rather than the route taken to reach it. If two routes lead to the same situation, earlier work may still be useful.

The notebook analogy has an important limit: each note needs conditions. A conclusion based on looking only two moves ahead cannot silently become a conclusion about six moves ahead. Nor can a note about a similar-looking situation substitute for the correct one.

Worked example

Reusing a bound correctly

Suppose an invented minimax search reaches the same position P through two move sequences. A table entry says that, at the relevant search depth and score convention, P has a lower bound of six. It does not say that P's exact value is six.

In an alpha-beta search window with beta equal to five, that lower bound can justify a cutoff under the algorithm's usual conditions: P is already at least as good as the cutoff threshold. In a window from four to nine, the same entry cannot by itself supply an exact answer or prove that the value reaches nine. It can only improve the known lower bound.

If the entry were based on an insufficient depth or different state context, even that use would need reconsideration. The example demonstrates bound semantics rather than a complete engine implementation or a measured search speedup.

Illustrative case study

Fictional case: Cedar Games adds a cache to a small game-playing agent. Its key includes the board layout but omits which player moves next. During testing, a cached winning score from one turn is reused for a position with the other player to move.

The team expands the state representation and labels stored entries with depth and bound type. It adds paired tests in which the visible board is identical but rule-relevant context differs. The table's replacement policy is reviewed separately from the correctness of its keys.

The project report describes saved search work only under measured conditions. The case illustrates why a transposition table is more than an unqualified map from a picture of the board to a score.

Common misconceptions and mistakes

The same board image always means the same state. Turn, rights and history-dependent rules can matter.
Every stored score is exact. Alpha-beta cutoffs commonly yield bounds, which must be reused accordingly.
A larger table changes the rules of the game. It changes available memory for reuse, not the game's semantics or the correctness requirements.

Business use

Transposition tables can make fixed-budget search more effective when many paths reach repeated states. Their usefulness depends on the domain, search procedure and how accurately the state key captures the relevant context.

For an evaluation, compare searched nodes, elapsed time, memory and decision quality under the same conditions. Inspect collision handling, depth requirements and score-bound semantics. If the system's rules or evaluation function change, decide whether old entries remain valid rather than assuming all cached information can be carried forward.

Check your understanding

A table says a position's value is at least seven. Can the engine report seven as its exact value without further evidence?

Answer: No. A lower bound rules out values below seven but still permits larger values. Its type must be preserved when reusing it.

Related terms

Learn next

Read alpha-beta pruning and minimax. Draw two move sequences that reach the same state, then list the context and score information a reusable table entry would need to preserve.

Sources

Russell and Norvig, Adversarial Search, author-hosted chapter discussing transpositions and transposition tables: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap06.pdf

Stockfish project, transposition-table data structures and interface: https://github.com/official-stockfish/Stockfish/blob/master/src/tt.h

Relevant textbook passages and source declarations were read. The bound example and fictional defect are original illustrations. No Stockfish execution, benchmark result or exhaustive implementation audit is claimed.

Previous: Transpose Next: Traveling salesperson problem