Home * Search * Quiescence

Most chess programs, at the end of the main search perform a more limited quiescence search, containing fewer moves. The purpose of this search is to only evaluate "quiet" positions, or positions where there are no winning tactical moves to be made. This search is needed to avoid the horizon effect. Simply stopping your search when you reach the desired depth and then evaluate, is very dangerous. Consider the situation where the last move you consider is QxP. If you stop there and evaluate, you might think that you have won a pawn. But what if you were to search one move deeper and find that the next move is PxQ? You didn't win a pawn, you actually lost a queen. Hence the need to make sure that you are evaluating only quiescent (quiet) positions.

Limiting Quiescence

Despite the fact that quiescence searches are typically very short, about 50%-90% nodes are spent there, so it is worthwhile to apply some pruning there. Apart from not trying moves with the static exchange evaluation < 0, delta pruning can be used for that purpose.

Standing Pat

In order to allow the quiescence search to stabilize, we need to be able to stop searching without necessarily searching all available captures. In addition, we need a score to return in case there are no captures available to be played. This is done by a using the static evaluation as a "stand-pat" score (the term is taken from the game of poker, where it denotes playing one's hand without drawing more cards). At the beginning of quiescence, the position's evaluation is used to establish a lower bound on the score. This is theoretically sound because we can usually assume that there is at least one move that can either match or beat the lower bound. This is based on the Null Move Observation - it assumes that we are not in Zugzwang. If the lower bound from the stand pat score is already greater than or equal to beta, we can return the stand pat score (fail-soft) or beta (fail-hard) as a lower bound. Otherwise, the search continues, keeping the evaluated "stand-pat" score as an lower bound if it exceeds alpha, to see if any tactical moves can increase alpha.

Checks

Some programs search treat checks and check evasions specially in quiescence. The idea behind this is that if the side to move is in check, the position is not quiet, and there is a threat that needs to be resolved. In this case, all evasions to the check are searched. Stand pat is not allowed if we are in check, for two reasons. First, because we are not sure that there is a move that can match alpha--in many positions a check can mean a serious threat that cannot be resolved. Second, because we are searching every move in the position, rather than only captures. Standing pat assumes that even if we finish searching all moves, and none of them increase alpha, one of the non-tactical moves can most likely raise alpha. This is not valid if we search every move. The other case of treating checks specially is the checking moves themselves. Some programs, after searching all the captures in a position without finding a move to raise alpha, will generate non-capture moves that give check. This has to be limited somehow, however, because in most given positions there will be very many long and pointless checking sequences that do not amount to anything. Most programs achieve this limit by delta pruning checks, as well as limiting the generation of checks to the first X plies of quiescence.

Pseudo Code

int Quiesce( int alpha, int beta ) {
    int stand_pat = Evaluate();
    if( stand_pat >= beta )
        return beta;
    if( alpha < stand_pat )
        alpha = stand_pat;

    until( every_capture_has_been_examined )  {
        MakeCapture();
        score = -Quiesce( -beta, -alpha );
        TakeBackMove();

        if( score >= beta )
            return beta;
        if( score > alpha )
           alpha = score;
    }
    return alpha;
}

Publications

1975

Larry Harris (1975) The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. IJCAI 1975 Tbilisi, Georgia: 334-339. reprinted (1988) in Computer Chess Compendium

1980 ...

Hermann Kaindl (1982). Dynamic Control of the Quiescence Search in Computer Chess. Cybernetics and Systems Research (ed. R. Trappl), pp. 973-977. North-Holland, Amsterdam.
Hermann Kaindl (1982). Quiescence Search in Computer Chess. SIGART Newsletter, 80, pp. 124-131. Reprinted (1983) in Computer-Game-Playing: Theory and Practice, pp. 39-52. Ellis Horwood Ltd., Chichester.
Don Beal (1984). Mating Sequences in the Quiescence Search. ICCA Journal, Vol. 7, No. 3
Prakash Bettadapur (1986). Experiments in Chess Capture Search, M.Sc. Thesis, Department of Computing Science, University of Alberta.
Prakash Bettadapur (1986). Influence of Ordering on Capture Search. ICCA Journal, Vol. 9, No. 4
Prakash Bettadapur, Tony Marsland (1988). Accuracy and Savings in Depth-Limited Capture Search. In International Journal of Man-Machine Studies, 29 (5) pp. 497-502
Don Beal (1989). Experiments with the Null Move. Advances in Computer Chess 5, a revised version is published (1990) under the title A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702, edited version in (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348. Chapter 10, pp. 101-116 » Null Move
Günther Schrüfer (1989). A Strategic Quiescence Search. ICCA Journal, Vol. 12, No. 1 » Bobby's Strategic Quiescence Search

1990 ...

Don Beal (1990). A Generalized Quiescence Search Algorithm. Artificial Intelligence, Vol. 43, No. 1, pp. 85-98. ISSN 0004-3702
Sören Walter Perrey (1991). Mathematische Methoden der Künstlichen Intelligenz: Zur Quiescence-Suche in Spielbäumen. Diplom thesis, Sonderforschungsbereich 343, E91-006, University of Bielefeld (German) ^[2]
Michael Gherrity, Paul Kube (1993). Quiescent Search is Beneficial. Technical Report CS93-289, University of California, San Diego
Don Beal (1999). The Nature of MINIMAX Search. Ph.D. thesis, IKAT, ISBN 90-62-16-6348