Killer heuristic - chess engine move ordering

Killer heuristic

Definition

The killer heuristic is a move-ordering technique used in chess engines during alpha–beta search. It records one or two non-capturing moves at each search depth (ply) that previously caused a beta-cutoff—i.e., they were so good that the opponent would avoid allowing them. When the engine later explores other branches at the same ply, it tries these “killer” moves early, often leading to faster cutoffs and a large reduction in the number of nodes searched.

How it is used in chess (engine search)

Modern engines generate a set of legal moves and then search them in an order designed to maximize early cutoffs. A typical priority is:

• Transposition table (hash) move, if available
• Winning captures and promotions (often via MVV-LVA or SEE)
• Killer moves (1–2 non-captures stored for this ply)
• History/counter-move heuristic suggestions
• Remaining captures, checks, and quiet moves (often with late move reductions)

The killer heuristic specifically boosts certain quiet moves that might otherwise be searched late, because a quiet refutation can be just as decisive as a capture. Engines usually keep two killer moves per ply and update them when a non-capture triggers a beta-cutoff.

Why it works

Positions that share the same search depth (ply) in nearby branches are often structurally similar. A move that “killed” one branch—by refuting a plan or creating a threat the opponent cannot accept—often does the same in sibling positions. Prioritizing that move yields more alpha–beta pruning and accelerates the search without changing the evaluation function itself.

Strategic and historical significance

Although invisible to human over-the-board play, the killer heuristic is historically important in computer chess. Alongside transposition tables and good capture ordering, it became a staple in the 1970s–1980s computer chess community and helped programs search deeper within fixed time limits. Classic projects such as Chess 4.x (Atkin and Slate) and Belle (Thompson and Condon) popularized move-ordering techniques, including the killer heuristic, that remain foundational today. Modern engines like Stockfish still use killers in combination with history heuristics, counter-move tables, null-move pruning, and late move reductions.

Example: a quiet “killer” refutation in a typical middlegame

Consider this Ruy Lopez structure reaching a standard middlegame. After 10...c5, it is White to move. Suppose at depth 6 the engine found that 11. d4! consistently refuted several black plans and exceeded beta in one branch. It becomes a killer move for that ply. When the engine explores adjacent branches at the same ply (perhaps with slight move-order differences), it will try 11. d4 early, often causing immediate cutoffs.

Mini-line to the position:

In practice, the engine’s killer table would store “d4” for this ply after it once caused a cutoff. In subsequent sibling nodes, it would search “d4” right after the hash move and main captures, often pruning the rest of the move list.

Walk-through at the search level

• At ply 10 in one branch, the engine tries a quiet move Qe2 and then d4. The move d4 explodes the center and the evaluation exceeds beta → beta-cutoff occurs.
• The engine records d4 as a killer at ply 10 (often keeping two killer slots per ply).
• In another branch at the same ply, the engine’s order becomes: hash move → winning captures → d4 (killer) → …
• Because d4 again provokes a cutoff, most remaining moves at that node are never searched, saving time.

Notes and best practices (engine development)

• Only non-captures are usually stored as killers; good captures already get priority via capture ordering.
• Most engines keep two killer moves per ply and ignore illegal or duplicate entries.
• Killers are local to ply (and often thread) and reset/reused each iterative-deepening iteration.
• They interact well with history and counter-move heuristics, but are typically disabled in quiescence search.
• Misordered killers are low-cost: they are tried early but quickly discarded if they fail low.

Related concepts

• alpha–beta pruning and principal variation
• transposition table (hash move ordering)
• history heuristic and counter-move heuristic
• null-move pruning and late move reductions (LMR)
• quiescence search and move ordering

Interesting facts

• The name “killer” comes from the move “killing” a branch by forcing a cutoff.
• Even a harmless-looking waiting move can be a killer if it refutes a plan at that ply.
• Engines often show dramatic node-count reductions from good killer and history heuristics, especially in tactical positions with many plausible quiet moves.
• Humans sometimes call a decisive tactic a “killer move,” but in engine terminology the killer heuristic is strictly about search ordering, not the move’s objective brilliance.

Example from engine vs. human era

In matches like Kasparov vs. Deep Blue, 1997, the programs relied heavily on alpha–beta search with strong move-ordering, including techniques like killer and history heuristics, to reach competitive depths in complex middlegames. While we don’t point to a single “killer move” from a specific position, these heuristics were part of the toolkit that made deep, selective search feasible in tournament-time conditions.