Back Up Next

Quiescent Search

Chess contains many forcing tactical sequences.  If someone takes your bishop with a knight, you'd better take their knight back.

Alpha-beta search is not particularly tolerant of this kind of thing.  You pass a depth parameter to the function, and when the depth gets to zero, it is done, even if someone's queen is hanging.

A method of dealing with this is called "quiescent search".  When alpha-beta runs out of depth, rather than calling "Evaluate()", a quiescent search function is called instead.  This function evaluates the position, while being careful to avoid overlooking extremely obvious tactical conditions.

Essentially, a quiescent search is an evaluation function that takes into account some dynamic possibilities.

The classic quiescent search searches only captures.  This causes a problem because captures are not compulsory in chess.  If a position is even, but if the only capture available to you is QxP (losing a queen), you aren't compelled to capture the pawn, and the quiescent search shouldn't be forced to capture it either.

Instead, the side to move is given a choice:  make a capture or do nothing.  Some people refer to doing nothing as "standing pat", a term taken from poker, which means to go with the cards you have now rather than discarding some and drawing replacements from the deck.

Here's the code:

int Quies(int alpha, int beta)

{

    val = Evaluate();

    if (val >= beta)

        return beta;

    if (val > alpha)

        alpha = val;

    GenerateGoodCaptures();

    while (CapturesLeft()) {

        MakeNextCapture();

        val = -Quies(-beta, -alpha);

        UnmakeMove();

        if (val >= beta)

            return beta;

        if (val > alpha)

            alpha = val;

    }

    return alpha;

}

This looks very similar to alpha-beta, but the differences are very important.  The function calls the static evaluation, and if the score is good enough that it can force a cutoff without captures being attempted, a cutoff is immediately made (return beta).  If the evaluation isn't good enough to cause a cutoff, but it's better than alpha, alpha is updated to reflect the static evaluation.

Then the captures are tried, and if any of them causes a cutoff, the search ends.  Perhaps none of them is any good, which is also no problem.

This function has several possible outcomes.  It's possible that the evaluation function will return a high enough score that the function can exit immediately via a beta cutoff.  It's also possible that a capture can result in a beta cutoff.  It's possible that the static evaluation will be bad, and none of the captures will be any good either.  Or it is possible that none of the captures are any good, but the static evaluation can raise alpha a little bit.

Note that there is no "depth" parameter passed in to the quiescent search function.  Because of this, the search can go very deep if a liberal definition of a "good" capture is applied, or if there is a long contentious forced capture sequence.

My example function doesn't detect checks, so it can't catch checkmates.  It is possible to make one that does by immediately asking if the side to move is in check, and if so, instead of doing "Evaluate()", and checking for a cutoff, instead the function calls alpha-beta with a depth of one.  For example:

int Quies(int alpha, int beta)

{

    if (InCheck())

        return AlphaBeta(1, alpha, beta);

    val = Evaluate();

    if (val >= beta)

        return beta;

    if (val > alpha)

        alpha = val;

    GenerateGoodCaptures();

    while (CapturesLeft()) {

        MakeNextCapture();

        val = -Quies(-beta, -alpha);

        UnmakeMove();

        if (val >= beta)

            return beta;

        if (val > alpha)

            alpha = val;

    }

    return alpha;

}

This version will find mates in quiescence if they involve captures.  Which version to use is a matter of taste and testing.

What to call a "good" capture is also a matter of taste and testing.  If you allow any capture, and search them in any old order, you'll destroy the efficiency of your search and create a quiescent search explosion, which will result in dramatically reduced depth and may cause a program crash.

There are a couple of obvious was of trying to avoid a quiescent explosion.

MVV/LVA

"MVV/LVA" stands for "Most Valuable Victim/Least Valuable Attacker".  It's a move ordering technique that is designed to be applied very cheaply.  The idea is always to search the best capture first.  This technique assumes that the best capture will be the one that captures the biggest piece.  If more than one of your pieces can capture a big piece, the assumption is made that it is best to capture with the smallest piece.

What this means is that PxQ is going to come first (assuming king in check is handled some other way).  Next comes NxQ or BxQ, then RxQ, then QxQ, then KxQ.  Followng that is PxR, B/NxR, RxR, QxR, KxR, and so on.

This works better than nothing, but it is obvious that there are some glaring problems.  RxR is searched before PxB, even if the rook is defended.

MVV/LVA will solve the quiescent explosion problem, but it will leave you with bloated quiescent search trees.

The advantage of MVV/LVA is that this is easy to implement and it results in a high nodes/second.  The disadvantage is that your search is inefficient -- you spend most of your time evaluating losing captures, so you search less deeply.

SEE

"SEE" stands for "Static Exchange Evaluation".  It's much more complicated than MVV/LVA, but allows for more accurate move ordering, and it allows for some captures to be discarded.

You can't discard QxP in MVV/LVA, because it's very possible that the pawn is undefended, which would mean that QxP is a good move.  Of course, if the pawn is defended, I doubt that you gain anything significant by searching this move at all.  With a SEE, you can figure out if QxP is a losing capture, and if so, either order the capture so that it is searched last, or simply prune it.

I don't have sample code for SEE yet, but how it works is that you apply a routine that resolves the captures, and then order moves by the amount of material that appears to be won.

SEE allows you to prune "bad" capturing moves very drastically, without many important captures being pruned out erroneously, and it improves move ordering.  Another thing you can do is prune out good captures, if they don't seem good enough.  If you are down a rook, a capture that wins a pawn is probably not worth trying in quiescent search.

I suspect that a program that uses SEE will be stronger than the same program using MVV/LVA.  The problem is writing the routine, and designing your data structures so the routine can be efficient.

Quiescent search is not perfect

It is very possible and in fact very likely that quiescent search will make mistakes.  This is a sad reality, but at least it's happening way out at the tips, where searches tend to be pretty stupid (a one-ply search is never going to be very good), so perhaps this is not a big deal.

If it were possible to make a more accurate quiescent search with no loss in speed, I'm sure that a program would be stronger than it was before.  However, I think it's important to understand the tradeoff that is being made if you try to make your quiescent search extremely powerful at the expense of time.  If making the quiescent search smarter costs you some number of plies of full-width search, it may not be worth it to make it smarter.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 11/04/02