SEE with magic bitboards
Posted: 12 Jan 2007, 11:51
I've rewritten a bitscan-free x-raying SEE optimized for magic bitboards. The basic idea is that one can assume that a piece behind another piece is always of a greater or equal value. This way order of captures in battery doesn't matter. The exception is for the queen for which new attackers must be generated. Any comments or suggestions on this approach?
- Code: Select all
//the board structure
typedef struct _board //104 bytes
{
U64 AllPieces; //All the pieces on the board
U64 PiecesSide[2]; //All the pieces belonging to each side
U64 Pieces[NUMPIECETYPES]; //Specific pieces on the board eg Pieces[R]
U64 hashkey; //the hash key for the transposition table
unsigned char PieceTypes[64]; //All the piece types according to squares
unsigned char KingPos[2]; //King position for a side
unsigned char EP; //The enpassant square
unsigned char castling; //Castling privilages - format defined below
unsigned char fifty; //Fifty move count
unsigned char SF; //Search Flags (see Search Related section)
bool side; //the side to play
bool xside; //the side opposite to play
}board;
#define LSB(X) ((X)&-(X))
//full static exchange evaluvation
int SEE(const board* pos, const move m)
{
//The variables are set to the inital state where the move in question has been played
int SEEscore=pieceValue[extractCapture(m)]; //The score to be returned
int SEEmax, SEEmin; //Maximum and minimum SEE scores (alphbeta approach)
int target=extractTo(m); //The square that we are doing a SEE on
int currentPieceValue=pieceValue[extractPiece(m)]; //Value of the piece currently on the target square
U64 used=toBit(extractFrom(m)); //Used attackers
//Battery attacks will be calculated instead of regular attacks
//Piece order isn't a problem (except when dealing with Queens)
U64 occupancy=(pos->AllPieces^used) &
~(pos->Pieces[B]|pos->Pieces[R]|( (pos->Pieces[P]) & (Pcaps(target,WHITE)|Pcaps(target,BLACK))));
U64 attackers; //attackers of each piece type from both sides
U64 attackersSide; //attackers for each piece type for a particular side
U64 attackersPiece; //attackers for a particular color and a particular type
//handle enpassant and promotion
if(currentPieceValue==Pval)
{
if(extractEP(m))
{
used|=toBit(extractEP(m));
occupancy^=toBit(extractEP(m));
SEEscore=Pval;
}
else if(extractPromotion(m)!=E)
{
SEEscore+=pieceValue[extractPromotion(m)]-Pval;
currentPieceValue=Qval
}
}
//these are the bounds, we will be doing an alphabeta-like search in SEE
SEEmax=SEEscore; //upperbound
SEEmin=-INF; //lowerbound
//Generate attackers
attackers=attacksToOcc(*pos,target,occupancy)^used;
//Loop Through Opponent Captures
while(attackersSide=attackers&pos->PiecesSide[pos->xside])
{
SEEscore-=currentPieceValue;
if(SEEscore>=SEEmax) return SEEmax;
if(SEEscore>SEEmin) SEEmin=SEEscore;
if(attackersPiece=attackersSide&pos->Pieces[P]) //Pawn
{
used|=LSB(attackersPiece);
attackers^=LSB(attackersPiece);
currentPieceValue=Pval;
}
else if(attackersPiece=attackersSide&pos->Pieces[N]) //Knight
{
attackers^=LSB(attackersPiece);
currentPieceValue=Nval;
}
else if(attackersPiece=attackersSide&pos->Pieces[B]) //Bishop
{
attackers^=LSB(attackersPiece);
used|=LSB(attackersPiece);
currentPieceValue=Bval;
}
else if(attackersPiece=attackersSide&pos->Pieces[R]) //Rook
{
attackers^=LSB(attackersPiece);
used|=LSB(attackersPiece);
currentPieceValue=Rval;
}
else if(attackersPiece=attackersSide&pos->Pieces[Q]) //Queen
{
used|=LSB(attackersPiece);
occupancy^=LSB(attackersPiece);
attackers=attacksBQRToOcc(*pos,target,occupancy)^used;
currentPieceValue=Qval;
}
else //King
{
attackers^=toBit(pos->KingPos[pos->xside]);
currentPieceValue=Kval;
}
//Loop Through My Captures
if(!(attackersSide=attackers&pos->PiecesSide[pos->side])) break;
SEEscore+=currentPieceValue;
if(SEEscore<=SEEmin) return SEEmin;
if(SEEscore<SEEmax) SEEmax=SEEscore;
if(attackersPiece=attackersSide&pos->Pieces[P]) //Pawn
{
used|=LSB(attackersPiece);
attackers^=LSB(attackersPiece);
currentPieceValue=Pval;
}
else if(attackersPiece=attackersSide&pos->Pieces[N]) //Knight
{
attackers^=LSB(attackersPiece);
currentPieceValue=Nval;
}
else if(attackersPiece=attackersSide&pos->Pieces[B]) //Bishop
{
attackers^=LSB(attackersPiece);
used|=LSB(attackersPiece);
currentPieceValue=Bval;
}
else if(attackersPiece=attackersSide&pos->Pieces[R]) //Rook
{
attackers^=LSB(attackersPiece);
used|=LSB(attackersPiece);
currentPieceValue=Rval;
}
else if(attackersPiece=attackersSide&pos->Pieces[Q]) //Queen
{
used|=LSB(attackersPiece);
occupancy^=LSB(attackersPiece);
attackers|=attacksBQRToOcc(*pos,target,occupancy)&~used;
currentPieceValue=Qval;
}
else //King
{
attackers^=toBit(pos->KingPos[pos->side]);
currentPieceValue=Kval;
}
}
if(SEEscore<SEEmin) return SEEmin;
if(SEEscore>SEEmax) return SEEmax;
return SEEscore;
}