Draft:History Heuristic

This diagram illustrates how the history heuristic speeds up game-tree searches by using a global table to prioritize moves proven successful in one branch to induce early cutoffs in others.

History heuristic is a technique used to speed up search algorithms for making decisions faster, mostly used by chess engines. Instead of thinking about every possible action from scratch, the AI keeps a "history table" to remember which moves worked well in the past. If a specific move (like "move piece to square X") was successful in a previous part of the game, the AI gives it a higher score. When the AI has to choose its next move, it looks at this table and tries the high-scoring moves first. This helps the game engine save time because it can find a "good enough" solution quickly without checking millions of bad options.^[1]

History and development

The development of the history heuristic began in the early 1980s as researchers looked for ways to make computer chess programs more efficient without needing deep knowledge of chess theory.

Origin and invention

Jonathan Schaeffer, a computer science professor and the inventor of history heuristic.

The history heuristic was invented by Jonathan Schaeffer, a computer science professor, in 1983. At the time, most chess engines relied on the "Killer heuristic", which only remembered one or two successful moves for each specific level of the search tree. Schaeffer proposed a more "all-purpose" version that would maintain a history for every possible legal move in the game, regardless of the level.^[2]

In his original 1983 paper, Schaeffer showed that this simple method could decrease the running time of a chess program by as much as 21%. Later, in a 1989 study published in "IEEE Transactions on Pattern Analysis and Machine Intelligence", he demonstrated that when combined with transposition tables, the history heuristic outperformed almost all other common search enhancements used at the time.^[3]

Evolution in game engines

Since its invention, the technique has evolved from a basic table of counters into more complex systems used by modern AI.

• The Butterfly Board: Early versions often used a "butterfly board," a data structure that tracked moves by their starting and ending squares (a 64x64 grid). This allowed the engine to quickly give a "history score" to any move.
• Relative History Heuristic: Researchers later found that some moves appeared more often than others simply because they were more common, not because they were better. This led to the "relative history heuristic," which divides a move's success score by the number of times the move was actually searched. This helps the AI identify truly "clever" moves rather than just "frequent" ones.
• Modern Implementations: Today, famous chess engines like Stockfish use advanced versions called "Counter Move History" (introduced around 2016) and "Follow Up History". These systems don't just remember if a move was good; they remember if it was a good response to a specific previous move by the opponent.^[4][5]

Integration with hardware

During the 1980s and 1990s, the history heuristic became a standard feature in champion engines like Phoenix and Deep Blue. Because it uses very little memory, it was perfect for the limited hardware of that era. Even as hardware became faster, the heuristic remained relevant because it allowed engines to use their extra CPU power to search even deeper into the game.^[6]

Introduction

The history heuristic is a strategy used by artificial intelligence (AI) in game engines and computer chess to improve the efficiency of search algorithms. It is primarily used during a game tree search to decide which moves to evaluate first. Unlike other methods that rely on the specific rules of a game, the history heuristic is "all-purpose"; it maintains a record of which moves have been successful in previous searches, regardless of the current position on the board. By prioritizing these historically successful moves, the engine can perform Alpha-beta pruning more effectively, allowing the AI to "think" deeper and make faster decisions without requiring extra computational complexity.^[2]

• Move Ordering: It sorts possible actions based on their past success rates to find the best move sooner.

• Domain Independence: It works in almost any game because it does not need to know the specific rules of the game to function.

• Low Memory Usage: It stores information in a simple table, making it lightweight for real-time applications.

• Efficiency: It helps the engine ignore "bad" paths in the logic tree earlier, saving processing power.

How it works

The history heuristic operates by maintaining a data structure, usually a simple table or array, indexed by move coordinates. For example, in a chess engine, the table might track a move from square "e2" to "e4". Unlike a Transposition table, which remembers specific board positions, the history table remembers the moves themselves regardless of where the other pieces are located on the board.^[7]

Scoring and updates

During the Minimax search process, the engine uses Alpha-beta pruning to discard branches of the game tree that are not useful. When a specific move causes a "cutoff" (meaning the move is strong enough that the engine can stop searching that branch), the engine rewards that move by increasing its score in the history table.

Engines often use a mathematical formula to give more points to moves found at a greater search depth, because those moves are considered more valuable:

${\displaystyle {\text{score}}={\text{score}}+2^{\text{depth}}}$

Move ordering

When the AI begins a new search at a different position, it retrieves the scores from the history table for all legal moves. The engine then sorts these moves in a specific order:

• Proven moves: Moves that previously caused cutoffs (those with high history scores).

• Unexplored moves: Moves that have not yet been recorded or have low scores.

By checking the high-scoring moves first, the engine significantly increases the chance of finding an optimal move quickly. This allows the alpha-beta algorithm to "prune" (ignore) the remaining moves much sooner, which reduces the total number of nodes the CPU must process.

Score aging

To prevent moves that were only good in the early stages of a game from affecting the late-game search, many engines use "score aging". This is done by periodically dividing all scores in the table by a fixed number. This ensures that the AI's "memory" stays updated and focuses on moves that are relevant to the current state of the game.

Advantages and disadvantages

The history heuristic is widely considered one of the most important developments in computer game theory because it provides a massive boost to performance with very little effort. However, its "blindness" to the specific details of a game position can sometimes be a drawback.

Advantages and strengths

The history heuristic is valued for its versatility and its ability to improve search efficiency in real-time.

• Versatility and portability: Because the history heuristic does not require the engine to understand the specific rules or values of a game (such as the importance of a "King" or a "Goal"), it is described as "domain-independent". A developer can take the history heuristic code from a chess engine and put it into a checkers or Go engine, and it will still work effectively. This makes it a "general-purpose" tool for AI developers who want to improve search speed without writing complex, game-specific logic.^[8]
• Significant reduction in search effort: The primary goal of any search optimization is to find the "best" move as early as possible. If the best move is checked first, the Alpha-beta pruning algorithm can ignore almost all other branches of the search tree. The history heuristic is highly effective at this; by checking moves that were successful in other parts of the search, the engine can often find a "cutoff" move immediately. This allows the AI to search much deeper into the game's future, often reaching several extra levels of depth compared to an engine that does not use this technique.^[9]
• Minimal resource requirements: In modern computing, memory and CPU cycles are valuable. Unlike a transposition table, which requires a massive amount of RAM to store millions of specific game positions, the history table is very small, it usually only needs to store a few thousand integers in a simple grid. This makes it ideal for games running on hardware with limited resources, such as mobile phones or older consoles.

Disadvantages and limitations

Despite its strengths, the history heuristic is a "best guess" method and can sometimes mislead the AI.

• Lack of situational awareness: The biggest weakness of the history heuristic is that it is "position-blind". It remembers that a move like "Knight to f3" was good in the past, but it does not understand "why" it was good. In a new position, that same move might be a terrible mistake because the surrounding pieces have moved. Because the heuristic prioritizes moves based on their general history rather than the current specific board state, it may encourage the AI to spend time looking at moves that are irrelevant to the current situation.
• Information obsolescence and pollution: As a game progresses, the "history" of what worked in the early stages might become useless. For example, a strategy that worked well when the board was full of pieces might be useless when the board is nearly empty. If the engine does not have a good way to "forget" or lower the scores of old moves (a process called "aging"), the history table can become "polluted" with outdated information that slows down the search. This requires developers to implement extra logic to periodically clean the table.^[10]
• Startup delay: The history heuristic provides zero benefit when a search first begins. Because the history table starts with all scores at zero, the AI must search for a while to "learn" which moves are good. This means that in very fast games (like bullet chess), the heuristic may not have enough time to become fully effective before the AI must make its move. To fix this, developers often combine it with the Killer heuristic, which provides more immediate, but less general, move-ordering data.

See also

• Alpha-beta pruning - The primary search algorithm that the history heuristic is designed to optimize.
• Killer heuristic - A similar move-ordering technique that focuses on the best moves at a specific depth rather than the whole game.
• Minimax - The foundational decision-rule algorithm used in two-player game theory.
• Transposition table - A cache that stores previously calculated board positions to avoid redundant work.
• Iterative deepening depth-first search - A strategy that allows an AI to find a basic solution quickly and then search deeper as time allows.
• Game tree - The mathematical representation of all possible moves in a game, which heuristics help to navigate.
• Null-move pruning - A technique used to skip certain branches of a search tree to save time.

References

1. "A brief history of heuristics — Nature.com". Nature.com. Retrieved February 9, 2026.
2. "The Relative History Heuristic — SciSpace.com" (PDF). SciSpace.com. Retrieved February 9, 2026.
3. "Jonathan Schaeffer". Chess Programming Wiki. Retrieved February 9, 2026.
4. "Stockfish Website — Stockfish Chess". Stockfish Chess. Retrieved February 9, 2026.
5. "Stockfish — Github.com". Github.com. Retrieved February 9, 2026.
6. "History and Milestone Developments in Computer Chess Algorithms from 1947-1986 — Ijcaonline.org" (PDF). Ijcaonline.org. Retrieved February 9, 2026.
7. "What is Knowledge Representation in AI — Guvi.in". Guvi.in. Retrieved February 9, 2026.
8. Levy, David; Newborn, Monty (1991). How Computers Play Chess. Computer Science Press. ISBN 978-0716781219.
9. Schaeffer, Jonathan (1989). "The History Heuristic and Alpha-Beta Search Enhancements". ICGA Journal. 12 (1): 3–20.
10. Marsland, T. Anthony (1990). Computers, Chess, and Cognition. Springer-Verlag. ISBN 978-1461390824.

Category:Computer chess Category:Search algorithms Category:Heuristics