5. Quiescence SearchIn QS we search only captures. The underlying assumption is that we almost always have a non-capture that conserves the current evaluation score. So either we take this score ('stand pat'), or, if it is not good enough, we try to improve it by capturing something.
- Code: Select all
int Search(int alpha, int beta, int depth)
{
int bestScore = -INF;
MOVE bestMove = INVALID;
if(depth <= 0) { // *** in QS
bestScore = Evaluate(); // *** use evaluation heuristic on position
if(bestScore > alpha) { // *** score accounting for stand pat
alpha = bestScore; // ***
if(bestScore >= beta) return bestScore; // *** stand-pat cutoff
}
}
for(EVERY move) { // loop over moves
if(depth == 0 && !IsCapture(move)) continue; // *** skip all non-captures
MakeMove(move); // updates game state (board, side to move)
score = -Search(-beta, -alpha, depth-1); // recursion (flip sign because we change POV)
UnMake();
if(score > bestScore) { // score accounting: remember best (from side-to-move POV)
bestScore = score;
if(score > alpha) {
alpha = score;
bestMove = move;
if(score >= beta) break; // beta cutoff: previous ply is refuted by this move
}
}
} // next move
return { bestScore, bestMove }; // bestMove only used in root, to actually play it
}
Note that IID makes no sense; the loop over moves is never executed more than once. The IID loop of the normal search starts at an iterDepth of at least 1, which is a 1-ply search, already more than QS, because it also searches captures. One cannot really say QS is a '0-ply search', though, because the moves that are searched (the captures) are searched at 1-ply. It is more like the first (and only) depth iteration is only performed half (the captures part). This is in fact a very useful way to look at things, and suggests how we can use the normal Search routine for QS with minimal changes.
We let the IID loop run to max(depth, 1) instead of depth, so that even for depth <= 0 the first iteration can be done. The stand-pat code can be done (conditionally to depth <= 0) in place of the bestScore = -INF initialization at the start of each depth iteration. So in the first (and in fact every) iteration of a 1-ply search (or deeper) bestScore will be set to -INF as usual, but in QS, where there only will be one iteration, it will be set to the evaluation of the current position. Because the moves will already be sorted captures first, we can break out of the moves loop as soon as we see the first capture. For example by having NextMove return INVALID instead of the killer move when we are in QS.
The sorting of the moves in QS is very important. We must try to capture the most valuable piece first, for two reasons:
1) to make it more difficult for the opponent to get even (as when he cannot, we can stand pat, and it is done)
2) to minimize the number of counter-strikes he has (as valuable pieces usually have many moves, amongst which many captures)
So it limits the QS tree both in depth and in width! A secondary concern is to capture with the least valuable piece first, as this in general produces the best result when the piece is protected. This is called MVV/LVA ordering, and we achieve it by assigning a sort key like victimValue - attackerPieceType to each capture. Here victimValue is in centiPawn, or in any case increases in big steps, while the attacker piece type just numbers the piece types 1, 2, 3..., in order of increasing value. The routine ExtractMostPromisingCapture() then looks for the move with the largest sort key in the list of remaining moves.
- Code: Select all
int Search(int alpha, int beta, int depth)
{
int bestScore;
MOVE bestMove = INVALID;
int startDepth = 1;
int phase = HASHMOVE;
HASHENTRY *hash = HashProbe();
if(hash) { // position was searched before, and found in the table
if(UsefulScore(hash, alpha, beta)) { // upper/lower bound might be useless with current {alpha, beta}
startDepth = hash->depth + 1; // skip all depth iterations that were already done
bestScore = hash->score; // this only in case we do iterDepth loop zero times (i.e. hash->depth >= depth)
}
move = hash->move; // *** use move anyway, for lack of a better alternative (put in 'move', not bestMove)
}
for(iterDepth from startDepth to max(1,depth)) { // loop over all depths (and always allow iterDepth=1 iteration)
int iterAlpha = alpha; // as we touched alpha, we need to reset it to the original value
int current = 0; // move number
if(depth <= 0) { // *** in QS
bestScore = Evaluate(); // *** use evaluation heuristic on position (as guessed score of best non-capture)
if(bestScore > alpha) { // *** score accounting for stand pat
alpha = bestScore; // ***
if(bestScore >= beta) return bestScore; // *** stand-pat cutoff
}
if(!IsCapture(move)) bestMove = INVALID; // in QS we only can use a hash move that is a capture!
} else bestScore = -INF; // for every depth we start with a clean slate
do { // loop over moves
if(move) {
MakeMove(move); // updates game state (board, side to move)
score = -Search(-beta, -alpha, depth-1); // recursion (flip sign because we change POV)
UnMake();
if(score > bestScore) { // score accounting: remember best (from side-to-move POV)
bestScore = score;
if(score > iterAlpha) {
iterAlpha = score;
bestMove = move;
if(current) PutInFront(bestMove); // *** put best move in front of list (if not yet there), so next depth iteration tries it first
if(score >= beta) break; // beta cutoff: previous ply is refuted by this move
}
}
}
// INLINED NextMove CODE
if(phase == HASHMOVE) { // initialized like this when we entered the node
GenerateAllMoves(); // after hash move we need to generate our own
PutInFront(move); // but put the hash move (if any) in front of them
current = -(move == INVALID); // put it 1 before next move, -1 if we had no hash (to start with 0), 0 if we had (start with 1)
phase = CAPTURES; // after hash move captures are next in line
}
if(phase == CAPTURES) { // the captures have to be sorted in the right order before searching them
move = ExtractMostPromisingCapture(current); // swaps the move to the front of the remaining moves
if(!move) { // out of captures
if(depth <= 0) { move = INVALID; break; } // *** in QS we can now break out of the move loop, as we won't consider non-captures
ExtractKillerMove(); // put killers (if found) in front of the remaining moves
phase = NONCAPTS; // continue searching the non-captures
}
}
move = moveList[++current]; // take the next move from the list
} while(move != INVALID); // next move
HashStore(iterDepth, move, // save what we need in next depth iteration in global table
bestScore, alpha, beta); // alpha and beta are needed to determine meaning of score (bound type)
} // next depth
return { bestScore, bestMove }; // bestMove only used in root, to actually play it
}
Note that we moved putting the best move in front to the place where we do find a new best move. This because the code has evolved such that the hash move is treated special, not taken from the list, but already assigned to the 'move' variable when we first enter the loop. It has the additional advantage that any move that is certified good (i.e. not a fail low that could be arbitrarily bad) will float to the head of the list, not just the single best.
Posted: 28 Mar 2013, 22:15