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