 |
 |
 |
 |
Writing a chess program in 99 steps
18 Quiescence search and SEE
Up to now the search simply stops when it has reached depth=0, and calls eval() to return a static evaluation . This can be a problem, because sometimes the position is not "quiet" : the game might be in the middle of an exchange of pieces, or there might be hanging pieces, the side to move might be in check, or might be able to promote a pawn. In such cases the static evaluation will not return a very representative score.
One way to eliminate this problem is to continue the search until we reach leaf positions that are "quiet", and then call the static evaluation function. This is the basic idea behind quiescence search. The quiescence search phase is started at depth=0 and continues until the position is "static" and can be evaluated, irrespective of the search depth. At this point you might wonder if this could explode the search? Well, the short answer is "no", because we will not investigate all moves, but only 'good' captures (bad captures are not going to change our score anyway), and the number of good captures will soon enough fade away as we traverse into the tree. Actually, any capture sequence will stop at the point where (in the minimax sense) one side does not gain anymore from a continuation of captures.
When is a position
"quiet" ? Different approaches exist, but winglet will
continue the search if one of the following cases is true:
1) the side to move is in check - in this case the normal full width search is
called, with a depth of 1.
This is done to ensure that all moves are
generated that could evade the check (not just capturing moves).
2) the side to move can make a capture that wins material, or a promote
a pawn.
All captures
are evaluated with a so-called Static Exchange Evaluator (SEE) to check
if material is lost or gained. If no material can be gained, then
that capture is discarded because the position is already considered to
be quiet. SEE evaluates captures without actually
performing the moves - hence the name static exchange evaluator.
The score is expressed in terms of material lost or gained
(centipawns). To enable this, there is a special-purpose move generator that
only generates captures and promotions. The quiescence
algorithm resembles alpha-beta to some extent:
are we in check? if yes then call the full-width alphabeta search()
value = eval() (in case there are no more captures to search, or we could get an early beta cut-off)
if value >= beta then return value (no need to search any further)
alpha = value;
captgen (generate & sort good captures & promotions)start of loop over 'good' captures & promotions
value = -qsearch(-beta, -alpha) (no depth parameter passed)
if value >= beta then return value
if value > alpha then alpha = value & remember this PV
end of loop over 'good' captures & promotions
return alpha
Also, there are no 50-move rule checks, or repetition checks, since these will not occur in capturing sequences. The move generator that generates captures and promotions is very similar to the normal move generator. The main difference is that we take blackPieces as target, instead of ~whitePieces, to generate the captures for white. Generating captures, evaluating each capture and sorting them is done in one loop, for efficiency reasons. moveBuffer is used to store the capture scores (using a location offset between a capture and its score). This prevents us from having to initialize a separate array. SEE is relatively expensive (compared to MVV/LVA), but the advantage of SEE is that it results in excellent move ordering & filtering during the quiescence search. The cost of SEE is more than compensated by improved capture ordering and selection.
The capture move generator returns a sorted list of capture moves (and filtered, because we leave out captures that do not win material), ready for the quiescence search to use:
start of capture & promotion generating loop
generate the next capture or promotion
call SEE (or MVV/LVA for that matter) to assign a score to the capture or promotion
is the score good enough?
if yes, then insert this move into the ordered listif no, then remove this move from the list and continue with the next move
end of capture or promotion generating loop
return the sorted & filtered move list to qsearch
SEE
SEE calculates the material score of a capture move. It does so by following the complete capture sequence for the target square of the first capture move, until there are no more pieces left that attack the target square. At the end of the capture sequence, SEE will have built up an array of material gains for both sides, and traverses this list back to the beginning of the sequence, in a minimax-sense, ending up with the minimax score of the first capture.
SEE does not carry out the moves on the board. Instead, it maintains a local attackers bitmap, holding all attackers for both sides. Attackers are removed one by one from the bitmap, after a capture has been made. New attackers might be revealed by removing pieces from the attackers bitmap. For instance, two rooks might be lined up on a rank, attacking an enemy piece on that rank. If the first rook is removed, then the second rook will be revealed and attacks the same target square. SEE checks if a new attacker is revealed after pieces are removed from the bitmap. If a new attacker is revealed, then this new attacker will be added to the attackers bitmap. On a high level, this is how SEE works:
calculate the attackers bitmap for the target square
while there are attackers:choose the next attacker for the side to move, in this order:
1) non-promoting pawns
2) knights
3) bishops
4) rooks
5) promoting pawns
6) queens
7) king (but only if there is no opponent attacker left)
update the array materialgains ('going forward')
remember the material value of the attacker (attackedpieceval), because it will be the next victimremove the attacker from the attackers bitmap
check if another attacker is revealed
end of loop
do a minimax-type calculation on materialgains ('going backward')
There are a couple of implementation details that are not clear from above explanation. The array of material gains for both sides is updated as follows (' going forward' ):
materialgains[nrcapts] = -materialgains[nrcapts - 1] + attackedpieceval;
And at the end of the capturing sequence, the minimax score is calculated as follows ('going backward'):
while (--nrcapts)
if (materialgains[nrcapts] > -materialgains[nrcapts - 1]) materialgains[nrcapts - 1] = -materialgains[nrcapts];
The SEE return value is materialgains[0].
The check to see if any new attackers are revealed is done only for one direction, depending on the target square and the removed piece. For this purpose, SEE maintains a local bitmap with all nonremoved pieces. In revealNextAttacker, this bitmap is used to determine if another attacker was lined up behind the removed attacker:. For instance (checking the 'North' direction for revealed rooks or queens):
targetBitmap = RAY_N[target] & ((whiteRooks | whiteQueens | blackRooks | blackQueens) & nonremoved);
step 80: board.h
#ifndef WINGLET_BOARD_H_
#define WINGLET_BOARD_H_
#include "defines.h"
#include "move.h"
#include "gameline.h"
#include "timer.h"
struct Board
{
BitMap whiteKing, whiteQueens, whiteRooks, whiteBishops, whiteKnights, whitePawns;
BitMap blackKing, blackQueens, blackRooks, blackBishops, blackKnights, blackPawns;
BitMap whitePieces, blackPieces, occupiedSquares;
unsigned char nextMove; // WHITE_MOVE or BLACK_MOVE
unsigned char castleWhite; // White's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2
unsigned char castleBlack; // Black's castle status, CANCASTLEOO = 1, CANCASTLEOOO = 2
int epSquare; // En-passant target square after double pawn move
int fiftyMove; // Moves since the last pawn move or capture
U64 hashkey; // Random 'almost' unique signature for current board position.
// additional variables:
int Material; // incrementally updated, total material on board,
// in centipawns, from white’s side of view
int square[64]; // incrementally updated, this array is usefull if we want to
// probe what kind of piece is on a particular square.
BOOLTYPE viewRotated; // only used for displaying the board. TRUE or FALSE.
// storing moves:
Move moveBuffer[MAX_MOV_BUFF]; // all generated moves of the current search tree are stored in this array.
int moveBufLen[MAX_PLY]; // this arrays keeps track of which moves belong to which ply
int endOfGame; // index for board.gameLine
int endOfSearch; // index for board.gameLine
GameLineRecord gameLine[MAX_GAME_LINE];
// search variables:
int triangularLength[MAX_PLY];
Move triangularArray[MAX_PLY][MAX_PLY];
Timer timer;
U64 msStart, msStop;
int searchDepth;
int lastPVLength;
Move lastPV[MAX_PLY];
unsigned int whiteHeuristics[64][64];
unsigned int blackHeuristics[64][64];
BOOLTYPE followpv;
U64 inodes;
void init();
int eval();
Move think();
int minimax(int ply, int depth);
int alphabeta(int ply, int depth, int alpha, int beta);
int alphabetapvs(int ply, int depth, int alpha, int beta);
int qsearch(int ply, int alpha, int beta);
void displaySearchStats(int mode, int depth, int score);
BOOLTYPE isEndOfgame(int &legalmoves, Move &singlemove);
int repetitionCount();
void mirror();
void initFromSquares(int input[64], unsigned char next, int fiftyM, int castleW, int castleB, int epSq);
void initFromFen(char fen[], char fencolor[], char fencastling[], char fenenpassant[], int fenhalfmoveclock, int fenfullmovenumber);
void display();
void rememberPV();
void selectmove(int &ply, int &i, int &depth, BOOLTYPE &followpv);
void addCaptScore(int &ifirst, int &index);
int SEE(Move &move);
BitMap attacksTo(int &target);
BitMap revealNextAttacker(BitMap &attackers, BitMap &nonremoved, int &target, int &heading);
};
#endif
step 81: search.cpp
(...)
int Board::alphabetapvs(int ply, int depth, int alpha, int beta){
// PV search
int i, j, movesfound, pvmovesfound, val;
triangularLength[ply] = ply;
if (depth == 0)
{
followpv = false;
// go into the quiescence search:
return qsearch(ply, alpha, beta);
}
(...)
step 82: qsearch.cpp
#include "defines.h"
#include "extglobals.h"
#include "protos.h"
#include "board.h"
int Board::qsearch(int ply, int alpha, int beta)
{
// quiescence search
int i, j, val;
triangularLength[ply] = ply;
if (isOwnKingAttacked()) return alphabetapvs(ply, 1, alpha, beta);
val = board.eval();
if (val >= beta) return val;
if (val > alpha) alpha = val;
// generate captures & promotions:
// captgen returns a sorted move list
moveBufLen[ply+1] = captgen(moveBufLen[ply]);
for (i = moveBufLen[ply]; i < moveBufLen[ply+1]; i++)
{
makeMove(moveBuffer[i]);
{
if (!isOtherKingAttacked())
{
inodes++;
val = -qsearch(ply+1, -beta, -alpha);
unmakeMove(moveBuffer[i]);
if (val >= beta) return val;
if (val > alpha)
{
alpha = val;
triangularArray[ply][ply] = moveBuffer[i];
for (j = ply + 1; j < triangularLength[ply+1]; j++)
{
triangularArray[ply][j] = triangularArray[ply+1][j];
}
triangularLength[ply] = triangularLength[ply+1];
}
}
else unmakeMove(moveBuffer[i]);
}
}
return alpha;
}
step 83: see.cpp
#include <iostream>
#include "defines.h"
#include "protos.h"
#include "extglobals.h"
#include "move.h"
// Macro's to define sliding attacks (note that these macro's slightly differ from the ones used in the move generator)
#define RANKATTACKS(a) (RANK_ATTACKS[(a)][((board.occupiedSquares & RANKMASK[(a)]) >> RANKSHIFT[(a)])])
#define FILEATTACKS(a) (FILE_ATTACKS[(a)][((board.occupiedSquares & FILEMASK[(a)]) * FILEMAGIC[(a)]) >> 57])
#define SLIDEA8H1ATTACKS(a) (DIAGA8H1_ATTACKS[(a)][((board.occupiedSquares & DIAGA8H1MASK[(a)]) * DIAGA8H1MAGIC[(a)]) >> 57])
#define SLIDEA1H8ATTACKS(a) (DIAGA1H8_ATTACKS[(a)][((board.occupiedSquares & DIAGA1H8MASK[(a)]) * DIAGA1H8MAGIC[(a)]) >> 57])
#define ROOKATTACKS(a) (RANKATTACKS(a) | FILEATTACKS(a))
#define BISHOPATTACKS(a) (SLIDEA8H1ATTACKS(a) | SLIDEA1H8ATTACKS(a))
int Board::SEE(Move &move)
{
// ===========================================================================
// This is a bitmap implementation of SEE (Static Exchange Evaluator),
// Captures that don't gain material are discarded during the quiescence search.
// SEE speeds up the search in two ways:
// 1) not all captures are searched, as in MVV/LVA
// 2) move ordering of captures is improved
// there is no check for captures that leave the king in check
// ===========================================================================
int nrcapts, from, target, heading, attackedpieceval;
int materialgains[32];
BitMap attackers, nonremoved;
unsigned char stm;
BOOLTYPE ispromorank;
#ifdef WINGLET_VERBOSE_SEE
BitMap previousattackers;
#endif
nrcapts = 0;
nonremoved = ~0;
stm = nextMove;
target = move.getTosq();
ispromorank = ((RANKS[target] == 8) || (RANKS[target] == 1));
attackers = attacksTo(target);
#ifdef WINGLET_VERBOSE_SEE
std::cout << "=== START OF SEE === " << std::endl;
displayMove(move);
std::cout << std::endl;
#endif
// do the first capture 'manually', outside of the loop, because it is prescribed
// take the first attacker from the supplied capture move:
from = move.getFrom();
#ifdef WINGLET_VERBOSE_SEE
std::cout << "first attacker from " << SQUARENAME[from] << std::endl;
#endif
// update the materialgains array:
materialgains[0] = PIECEVALUES[board.square[target]];
// remember the value of the moving piece because this is going to be captured next:
attackedpieceval = PIECEVALUES[board.square[from]];
// if it was a promotion, we need to add this into materialgains and attackedpieceval:
if (ispromorank && ((board.square[from] & 7) == 1))
{
materialgains[0] += PIECEVALUES[move.getProm()] - PIECEVALUES[WHITE_PAWN];
attackedpieceval += PIECEVALUES[move.getProm()] - PIECEVALUES[WHITE_PAWN];
}
nrcapts++;
// clear the bit of the last attacker:
attackers &= ~BITSET[from];
nonremoved &= ~BITSET[from];
// what direction did the attack come from:
heading = HEADINGS[target][from];
// another attacker might be revealed, update attackers accordingly:
#ifdef WINGLET_VERBOSE_SEE
previousattackers = attackers;
#endif
if (heading) attackers = revealNextAttacker(attackers, nonremoved, target, heading);
#ifdef WINGLET_VERBOSE_SEE
if (previousattackers != attackers) std::cout << "=>new attacker revealed" << std::endl;
#endif
// switch side to move:
stm = !stm;
while (attackers)
{
// select the least valuable attacker:
if (stm)
{
// pawn is only the first candidate if it does not promote:
if (RANKS[target] != 8 && blackPawns & attackers) from = firstOne(blackPawns & attackers);
else if (blackKnights & attackers) from = firstOne(blackKnights & attackers);
else if (blackBishops & attackers) from = firstOne(blackBishops & attackers);
else if (blackRooks & attackers) from = firstOne(blackRooks & attackers);
else if (RANKS[target] == 8 && blackPawns & attackers) from = firstOne(blackPawns & attackers);
else if (blackQueens & attackers) from = firstOne(blackQueens & attackers);
// king can only capture if there is no opponent attacker left
else if ((blackKing & attackers) && !(attackers & whitePieces)) from = firstOne(blackKing);
else break;
}
else
{
// pawn is only the first candidate if it does not promote:
if (RANKS[target] != 1 && whitePawns & attackers) from = firstOne(whitePawns & attackers);
else if (whiteKnights & attackers) from = firstOne(whiteKnights & attackers);
else if (whiteBishops & attackers) from = firstOne(whiteBishops & attackers);
else if (whiteRooks & attackers) from = firstOne(whiteRooks & attackers);
else if (RANKS[target] == 1 && whitePawns & attackers) from = firstOne(whitePawns & attackers);
else if (whiteQueens & attackers) from = firstOne(whiteQueens & attackers);
// king can only capture if there is no opponent attacker left
else if ((whiteKing & attackers) && !(attackers & blackPieces)) from = firstOne(whiteKing);
else break;
}
#ifdef WINGLET_VERBOSE_SEE
std::cout << "next attacker from " << SQUARENAME[from] << std::endl;
#endif
// update the materialgains array:
materialgains[nrcapts] = -materialgains[nrcapts - 1] + attackedpieceval;
// remember the value of the moving piece because this is going to be captured next:
attackedpieceval = PIECEVALUES[board.square[from]];
// if it was a promotion, we need to add this into materialgains and attackedpieceval:
if (ispromorank && ((board.square[from] & 7) == 1))
{
materialgains[nrcapts] += PIECEVALUES[WHITE_QUEEN]-PIECEVALUES[WHITE_PAWN];
attackedpieceval = PIECEVALUES[WHITE_QUEEN]-PIECEVALUES[WHITE_PAWN];
}
nrcapts++;
// clear the bit of the last attacker:
attackers ^= BITSET[from];
nonremoved ^= BITSET[from];
// what direction did it come from:
heading = HEADINGS[target][from];
// another attacker might be revealed, update attackers accordingly:
#ifdef WINGLET_VERBOSE_SEE
previousattackers = attackers;
#endif
if (heading) attackers = revealNextAttacker(attackers, nonremoved, target, heading);
#ifdef WINGLET_VERBOSE_SEE
if (previousattackers != attackers) std::cout << "=>new attacker revealed" << std::endl;
#endif
// switch side to move:
stm = !stm;
}
// ===========================================================================
// Start at the end of the capture sequence and use a Minimax-type procedure
// to calculate the SEE value of the first capture:
// ===========================================================================
while (--nrcapts)
if (materialgains[nrcapts] > -materialgains[nrcapts - 1])
materialgains[nrcapts - 1] = -materialgains[nrcapts];
#ifdef WINGLET_VERBOSE_SEE
std::cout << "SEE value of this capture = " << materialgains[0] << std::endl << std::endl;
#endif
return (materialgains[0]);
}
BitMap Board::attacksTo(int &target)
{
// attacksTo returns the first-line 'attackers' bitmap for SEE, it has all pieces that
// attack the target square (both colors), excluding any attackers that might be lined-up
// behind the first-line attackers (e.g. queen behind rook) - they will be dealt with by
// revealNextAttacker
BitMap attacks, attackBitmap;
// attacks along ranks/files (rooks & queens)
attackBitmap = ROOKATTACKS(target);
attacks = (attackBitmap & (blackQueens | whiteQueens | blackRooks | whiteRooks));
// attacks along diagonals (bishops & queens)
attackBitmap = BISHOPATTACKS(target);
attacks |= (attackBitmap & (blackQueens | whiteQueens | blackBishops | whiteBishops));
// attacks from knights
attackBitmap = KNIGHT_ATTACKS[target];
attacks |= (attackBitmap & (blackKnights | whiteKnights));
// white pawn attacks (except en/passant)
attackBitmap = BLACK_PAWN_ATTACKS[target];
attacks |= (attackBitmap & (whitePawns));
// black pawn attacks (except en/passant)
attackBitmap = WHITE_PAWN_ATTACKS[target];
attacks |= (attackBitmap & (blackPawns));
// king attacks
attackBitmap = KING_ATTACKS[target];
attacks |= (attackBitmap & (blackKing | whiteKing));
return attacks;
}
BitMap Board::revealNextAttacker(BitMap &attackers, BitMap &nonremoved, int &target, int &heading)
{
// ===========================================================================
// revealNextAttacker checks if there was another 'hidden' attacker that was
// lined-up after an attacker has been removed.
// If so, the attackers bitmap is updated accordingly.
// ===========================================================================
int state;
BitMap targetBitmap = 0;
switch (heading)
{
case 1: // EAST:
targetBitmap = RAY_E[target] & ((whiteRooks | whiteQueens | blackRooks | blackQueens) & nonremoved);
if (targetBitmap)
{
state = int((occupiedSquares & nonremoved & RANKMASK[target]) >> RANKSHIFT[target]);
targetBitmap = RANK_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case 7: // NORTHWEST:
targetBitmap = RAY_NW[target] & ((whiteBishops | whiteQueens | blackBishops | blackQueens) & nonremoved);
if (targetBitmap)
{
state = ((occupiedSquares & nonremoved & DIAGA8H1MASK[target]) * DIAGA8H1MAGIC[target]) >> 57;
targetBitmap = DIAGA8H1_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case 8: // NORTH:
targetBitmap = RAY_N[target] & ((whiteRooks | whiteQueens | blackRooks | blackQueens) & nonremoved);
if (targetBitmap)
{
state = ((occupiedSquares & nonremoved & FILEMASK[target]) * FILEMAGIC[target]) >> 57;
targetBitmap = FILE_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case 9: // NORTHEAST:
targetBitmap = RAY_NE[target] & ((whiteBishops | whiteQueens | blackBishops | blackQueens) & nonremoved);
if (targetBitmap)
{
state = ((occupiedSquares & nonremoved & DIAGA1H8MASK[target]) * DIAGA1H8MAGIC[target]) >> 57;
targetBitmap = DIAGA1H8_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case -1: // WEST:
targetBitmap = RAY_W[target] & ((whiteRooks | whiteQueens | blackRooks | blackQueens) & nonremoved);
if (targetBitmap)
{
state = int((occupiedSquares & nonremoved & RANKMASK[target]) >> RANKSHIFT[target]);
targetBitmap = RANK_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case -7: // SOUTHEAST
targetBitmap = RAY_SE[target] & ((whiteBishops | whiteQueens | blackBishops | blackQueens) & nonremoved);
if (targetBitmap)
{
state = ((occupiedSquares & nonremoved & DIAGA8H1MASK[target]) * DIAGA8H1MAGIC[target]) >> 57;
targetBitmap = DIAGA8H1_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case -8: // SOUTH:
targetBitmap = RAY_S[target] & ((whiteRooks | whiteQueens | blackRooks | blackQueens) & nonremoved);
if (targetBitmap)
{
state = ((occupiedSquares & nonremoved & FILEMASK[target]) * FILEMAGIC[target]) >> 57;
targetBitmap = FILE_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
case -9: // SOUTHWEST
targetBitmap = RAY_SW[target] & ((whiteBishops | whiteQueens | blackBishops | blackQueens) & nonremoved);
if (targetBitmap)
{
state = ((occupiedSquares & nonremoved & DIAGA1H8MASK[target]) * DIAGA1H8MAGIC[target]) >> 57;
targetBitmap = DIAGA1H8_ATTACKS[target][state] & targetBitmap;
return (attackers | targetBitmap);
}
else return attackers;
break;
}
return (attackers);
}
|
|
|
 |
|
last update: Saturday 25 June 2011