Quiescence search

This article is part of the series on
Chess programming
Board representations 0x88 Bitboards
Evaluation functions Deep neural networks (Transformers) Attention Efficiently updatable neural networks Handcrafted evaluation functions Piece-square tables Reinforcement learning Stochastic gradient descent Supervised learning Texel tuning Unsupervised learning
Graph and tree search algorithms Minimax Alpha-beta pruning Principal variation search Quiescence search Monte Carlo tree search
Chess computers Belle ChessMachine ChipTest Cray Blitz Deep Blue Deep Thought HiTech Hydra Mephisto Saitek
Chess engines AlphaZero Chess Tiger Crafty CuckooChess Deep Fritz Dragon by Komodo Chess Fairy-Max Fritz Fruit GNU Chess HIARCS Houdini Ikarus Junior KnightCap Komodo Leela Chess Zero MChess Pro Mittens MuZero Naum REBEL Rybka Shredder Sjeng SmarThink Stockfish Torch Turochamp Zappa
v t e

Quiescence search is an algorithm typically used to extend search at unstable nodes in minimax game trees in game-playing computer programs. It is an extension of the evaluation function to defer evaluation until the position is stable enough to be evaluated statically, that is, without considering the history of the position or future moves from the position. It mitigates the effect of the horizon problem faced by AI engines for various games like chess and Go.

Human players usually have enough intuition to decide whether to abandon a bad-looking move, or search a promising move to a great depth. A quiescence search attempts to emulate this behavior by instructing a computer to search "volatile" positions to a greater depth than "quiet" ones to make sure there are no hidden traps and to get a better estimate of its value.

Any sensible criterion may be used to distinguish "quiet" positions from "volatile" positions. One common criterion is that moves exist in the position that can dramatically change the valuation of the position, such as captures in chess or Go. As the main motive of quiescence search is to get a stable value out of a static evaluation function, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply, i.e. a history criterion. The quiescence search continues as long as the position remains volatile according to the criterion. In order to get the quiescence search to terminate, plies are usually restricted to moves that deal directly with the threat, such as moves that capture and recapture (often called a 'capture search') in chess. In highly "unstable" games like Go and reversi, a rather large proportion of computer time may be spent on quiescence searching.