Quiescence search

Quiescence search is an algorithm typically used to evaluate minimax game trees in game-playing computer programs. It is a remedy for the horizon problem faced by AI engines for various games like chess and Go.

The horizon effect

The horizon effect is a problem in artificial intelligence where, in many games, the number of possible states or positions is immense and computers can only search a small portion of it, typically a few ply down the game tree. Thus, for a computer searching only five ply, there is a possibility that it could make a move that would prove to be detrimental later on (say, after six moves), but it cannot see the consequences because it cannot search far into the tree. Consider this chess position with black to move:^[1]

Ponomariov vs. Fritz
(Man vs. Machine, Bilbao, 2005)

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

This game illustrates the danger of searching a shallow, fixed ply.

Here White is down a pawn in material, and a good move for black would be 39... Qxg3+ 40. Kxg3 f5. However, Fritz chooses the suboptimal move 39... Bc2??. This move lets White force many of Black's moves, but Fritz doesn't care because it appears to be able to win more material along the way. White responds with 40. Qxh4 and Black resigns after 40. ... gxh4 41. Rc1 Rxb3? 42. Nxb3 Bxb3 43. a5 Nc4 44. b5 Ba4 45. bxa6 Bc6 46. a7 Kg7 47. a6 Ba8 48. Rb1.

This problem occurs because computers only search a certain number of moves ahead. 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 "interesting" positions to a greater depth than "quiet" ones (hence its name) to make sure there are no hidden traps and, usually equivalently, to get a better estimate of its value.

Any sensible criterion may be used to distinguish "quiet" moves from "noisy" moves; high activity (high movement on a chess board, extensive capturing in Go, for example) is commonly used for board games. As the main motive of quiescence search is usually to get a good value out of a poor evaluation function, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply. Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum. In highly "unstable" games like Go and reversi, a rather large proportion of computer time may be spent on quiescence searching.

This pseudocode illustrates the concept in an algorithmic manner:

function quiescence_search(node, depth)
    if node appears quiet or node is a terminal node or depth = 0
        return estimated value of node
    else
        //One might use minimax or alpha-beta search here...
        search children of node using recursive applications of quiescence_search
        return estimated value of children

//...and here
function normal_search(node, depth)
    if node is a terminal node
        return estimated value of node
    else if depth = 0
        if node appears quiet
            return estimated value of node
        else
            return estimated value from quiescence_search(node, reasonable_depth_value)
    else
        search children of node using recursive applications of normal_search
        return estimated value of children

References