Quiescence search

From Wikipedia, the free encyclopedia

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.

[edit] The horizon effect

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 5 ply, for example, there is a possibility that it could make a move that would prove to be detrimental later on (say, after 6 moves), but it cannot see the consequences because it cannot search far into the tree. Consider this chess position (right), encountered in a match between Ponomariov (White) and the Fritz engine (Black) (Man vs. Machine, Bilbao, 2005), with Fritz to move: ↑ 

Here White is significantly down in terms of material, and a good move would be 39.... Qxg3+ 40.Kxg3 f5 (see algebraic chess notation). However, Fritz choose the suboptimal move 39....Bc2??. This move leads to White being able to 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.

[edit] Quiescence search

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. Quiescence search attempts to emulate this behaviour 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 criteria 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 othello, a rather large proportion of computer time may be spent on quiescence search.

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

[edit] References

^[1] [2]