Chess - Programming - Search - Quiescence Search

At the end of the main search a more limited quiescence search should be performed.

• 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 a search when the desired depth is reached and then evaluated, is very dangerous.
• Consider the situation where the last move you consider is QxP.
  • If the search is stopped there and evaluated, it might think that a pawn has been won.
  • But what if the search was made one move deeper; and found that the next move is PxQ?
  • A pawn has not really been won; instead a queen has been lost.
  • Hence the need to make sure that only quiescent (quiet) positions are evaluated.

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.

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;
}

http://web.archive.org/web/20120427185347/http://chessprogramming.wikispaces.com/Quiescence+Search

http://web.archive.org/web/20120420061736/http://chessprogramming.wikispaces.com/Pruning