Move ordering

Move ordering refers to the practice of selecting the most promising moves first during game-tree search (especially in computer chess).^[1][2] In minimax searches with alpha–beta pruning, good move ordering is important, examining stronger moves early causes cutoffs that eliminate subtrees, vastly reducing the number of nodes searched. In the ideal case of perfect move ordering the search complexity drops from ${\displaystyle O(b^{d})}$ to approximately ${\displaystyle O(b^{d/2})}$, effectively halving the effective branching factor to ${\displaystyle {\sqrt {b}}}$ and allowing roughly twice the search depth for a given computational effort.^[3] Claude Shannon observed that although a typical chess position may have on the order of 30 legal moves, effective pruning and heuristics reduce the useful branching factor to only a few.^[4]

The idea of ordering moves came before computers. In his 1950 seminal paper "Programming a Computer for Playing Chess",^[5] Claude Shannon noted the enormous size of the full game tree (estimated at ${\displaystyle 10^{120}}$ nodes) and suggested that a simple evaluation coupled with search all variations to a fixed depth would be impractical. Shannon saw that any chess program would need to focus on selected moves and prune aggressively to be useful. The formal alpha–beta algorithm appeared in the late 1950s and 1960s as a way to prune branches without changing the minimax result. Early on, it was noted that alpha–beta's pruning power depends entirely on the order in which moves are examined. In 1963, Alexander Brudno independently described alpha–beta-like search and noted that best-case node counts occur when moves are tried in the right order; by the 1970s researchers such as Donald Knuth and Ronald Moore had mathematically analyzed alpha–beta and shown that under perfect ordering its time is ${\displaystyle O(b^{d/2})}$.^[6]

In the 1970s and 1980s the major practical heuristics for move ordering were introduced. The use of iterative deepening was rediscovered in chess programs and found to significantly improve move ordering for deeper searches. The idea was to use the best move found at shallow depth as the first move in the next deeper search.^[7] Transposition tables (Mac Hack by Richard Greenblatt in 1966 first used a hash) allowed the program to store the best move for each position and reuse it as the first choice on subsequent visits.^[8] In 1968 Barbara Liskov and others independently suggested storing moves that caused beta cutoffs. This eventually became known as the killer heuristic. In 1983 Jonathan Schaeffer proposed the history heuristic. Schaeffer showed that the history scores outperformed simpler heuristics.

The efficiency of a chess engine's search is almost entirely dependent on its ability to ignore "bad" moves as quickly as possible. Theoretically, if an engine could always examine the best move first, the search space would effectively be reduced to its square root.^[1] This is achieved through a combination of game theory and heuristic-based pruning.^[9]

A pure minimax game-tree search explores all moves to a fixed depth, which is exponentially expensive.^[10] Alpha–beta pruning improves this by carrying two bounds which are Alpha (α) and Beta (β).^[11] Alpha is the minimum score the maximizing player is assured of, and Beta is the maximum score the minimizing player can permit. Whenever a node's value cannot possibly influence the final decision because it is worse than a previously examined move, the branch is cut off. This has a probability to have the same result as full minimax but with fewer nodes.

Iterative deepening depth-first search is commonly used. The engine repeatedly searches with increasing depth limits, using the best move from depth ${\displaystyle d}$ as the first move to try at depth ${\displaystyle d+1}$.^[12] This almost produces a strong initial bound (alpha or beta) on the first move, which narrows the window for the rest of the search. Iterative deepening converts a depth-first search into something akin to a best-first search by leveraging past results. When a transposition table contains an entry for the current position, its stored best move is tried first.^[13] After a transposition move is considered, typical ordering heuristics prioritize captures and checks, since forcing tactical moves often lead to large advantages or immediate cut offs.^[14]

Engines sort capture moves by the Most Valuable Victim–Least Valuable Aggressor (MVV-LVA) heuristic.^[8] To avoid obviously losing trades, a static exchange evaluation (SEE) is often applied to prune captures that reduce material balance. If the forcing moves do not produce a cutoff, the engine then tries its stored killer moves, which are tried at early depth. If a non-killer move causes a cutoff, it becomes a new killer. Finally, any remaining quiet moves are ordered by their history heuristic scores, which accumulate bonuses when a move causes a cutoff.^[15] Each time a move causes a cutoff anywhere in the search, its history score increases. Thus moves that have historically caused cutoffs rank higher in future ordering.

Researchers have developed several refinements beyond the basic schemes. Countermove heuristic assumes that many moves have a "natural" response, irrespective of the actual position.^[16] Other miscellaneous techniques such as "Butterfly boards"^[17] and "last-best-reply" heuristics are related ideas that exploit local search history. Some engines use machine learning, early work by Kocsis et al. and Greer applied neural networks to predict move values or ordering. Most strong engines still rely on the simple set of PV moves, hash moves, MVV-LVA capture sorting, killer and history tables.

• Minimax
• Alpha–beta pruning
• Iterative deepening depth-first search
• Quiescence search
• Killer heuristic