History heuristic - move ordering in chess engines

History heuristic

Definition

The history heuristic is a move-ordering technique used in chess engines to accelerate game-tree search. It assigns a score to moves based on their past success at causing cutoffs (fail-highs) during alpha-beta search. Moves that have historically been effective are tried earlier in future searches, increasing the likelihood of early pruning and reducing the number of nodes the engine must examine.

Unlike the killer heuristic (which stores a few strong refutation moves per depth), the history heuristic maintains a global “memory” of effective moves across the entire tree and all depths, typically indexed by from–to squares and side to move, or by piece and destination square.

How it is used in chess (computer chess)

Core usage in alpha-beta search

The heuristic influences the order in which moves are searched. A common order is:

• PV/hash move from the transposition table
• Forcing moves (checks, high-value captures; often guided by MVV-LVA or SEE)
• Killer moves (quiet refutations found at the same depth)
• History-heuristic moves (quiet moves sorted by their history scores)
• Remaining quiet moves and “bad” captures

When a move causes a beta cutoff, its history score is increased—often scaled by the search depth (e.g., add depth × depth). Over time, such moves float to the top of the move list in similar contexts, improving the chance of quick cutoffs on future nodes.

Strategic and historical significance

Why it matters

Efficient move ordering is crucial: alpha-beta’s pruning power depends on trying good moves first. The history heuristic provides a lightweight, continuously-learned guide for ordering quiet moves—those not obviously forced by material considerations. In practical terms, it often yields double-digit percentage reductions in node counts compared to naive ordering, especially when combined with iterative deepening and transposition tables.

Place in engine evolution

The history heuristic entered the computer-chess literature in the late 1980s, notably through work by researchers including Jonathan Schaeffer and colleagues. It became a standard component of strong engines in the 1990s and beyond, contributing to the depth and speed that helped programs like Deep Blue (Kasparov vs. Deep Blue, 1997) reach formidable search horizons. Modern engines (including those with neural evaluation) still rely on history-like tables—often in multi-dimensional, refined forms—to keep move ordering sharp.

Implementation outline

Data structures

• Basic table: history[side][fromSquare][toSquare] → integer score.
• Variants:
  • Piece–to-square history: history[side][pieceType][toSquare]
  • Continuation history: history keyed by the previous move and the current move pair (helps predict replies)
  • Countermove table: best reply indexed by the opponent’s last move
  • “Butterfly” history: counts aggregated by from–to irrespective of piece identity

Update policy

• On beta cutoff (quiet move): history += depth × depth (or a similar nonlinear scale)
• On fail-low (quiet move): optionally decrease history (negative update) to discourage ineffective tries
• Saturate and periodically decay values to avoid overflow and to keep the table responsive
• Clear or downscale between iterative-deepening iterations, or age entries gradually

Move ordering

• Compute a move’s sort key as a tuple, for example:
  • (isPvHash, isWinningCaptureSEE, isCheck, isKiller, historyScore, …)
• Within the “quiet” class, sort descending by history score
• Combine with late move reductions (LMR): later, low-history quiet moves are more aggressively reduced

Examples

Conceptual example: rewarding a quiet refutation

Imagine a middlegame position where White threatens a kingside push. Among many quiet moves, Black’s 1...h5! neutralizes the threat. At a node in the search, trying 1...h5 first causes a beta cutoff. The engine then updates history[Black][h6][h5] (from h6 to h5 for illustration), increasing its score. Later, in sibling or similar positions, 1...h5 will be searched earlier, increasing the chance of fast pruning.

Search-order impact in practice

Consider a typical move ordering:

• PV/hash move: 1...Re8
• Captures: 1...Qxd4, 1...Nxd4
• Killer moves: 1...Rg8, 1...Bd6
• History moves: 1...h5, 1...a5, 1...Kh8 (sorted by history score)

If 1...h5 previously caused cutoffs in related nodes, it will outrank 1...a5 and 1...Kh8 among quiet moves. If it again refutes White’s plan, the node will prune quickly, shrinking the tree at this depth and at many similar nodes elsewhere.

Mini-illustration with a plausible line

In this line, a quiet prophylactic move earns “history” credit by shutting down a tactic, making it likely to be tried earlier in similar structures:

While many forcing moves exist, engines often find that a simple quiet resource (e.g., ...h6 or ...Re8 at the right moment) earns repeated cutoffs against overextended plans. The history table then learns to prefer those quiet moves in structurally similar positions.

Interesting facts and anecdotes

• The name “history” reflects that a move’s past performance across the entire search tree informs its future priority, not just its local, tactical characteristics.
• Early experiments reported substantial node-count reductions when adding the history heuristic atop alpha-beta with iterative deepening and transposition tables; exact gains vary by position and engine, but double-digit percentage improvements are common.
• Modern top engines generalize the idea: piece–square history, continuation history (history conditioned on the previous move), and countermove tables are all descendants of the original concept.
• Even engines guided by neural networks (which evaluate positions) keep classic move-ordering machinery like history tables, because evaluation strength and search efficiency solve different problems.

Related concepts

• alpha-beta pruning: The search framework whose effectiveness hinges on good move ordering.
• iterative deepening: Re-searching deeper with knowledge (PV, TT, history) gathered at shallower depths.
• killer heuristic: Stores one or two strong quiet refutations per depth; complements the history heuristic.
• MVV-LVA and SEE: Methods to prioritize captures and checks before quiet moves.
• late move reductions: Reduce depth for late, low-priority moves; history scores help decide which moves are “late.”
• transposition table: Supplies the hash move (often searched first) and bounds that interact with history-based ordering.

Practical tips for engine authors

• Use depth-scaled updates (e.g., +depth × depth on fail-high) and modest negative updates on fail-low quiets.
• Keep separate histories for white and black; consider piece–to-square or continuation history for more granularity.
• Saturate and decay scores to prevent runaway values; normalize when combining multiple history sources.
• Integrate with a full ordering pipeline: PV/hash move → good captures/checks → killers → history quiets → others.
• Tune LMR thresholds using history: reduce more aggressively for moves with very low history scores.