User Tools

Site Tools


chess:programming:search:quiescence_search

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

References

chess/programming/search/quiescence_search.txt · Last modified: 2021/10/11 23:05 by peter

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki