 |
 |
 |
 |
Writing a chess program in 99 steps
step 84: movegen.cpp
(...)
int captgen(int index)
{
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// generate pseudo-legal captures and promotions generator,
// using magic multiplication instead of rotated bitboards.
// The first free location in moveBuffer[] is supplied in index,
// and the new first free location is returned
//
// this function keeps the move list sorted (using SEE) and shortens
// the list by discarding 'bad' moves.
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
unsigned char opponentSide;
unsigned int from, to;
int ifirst;
BitMap tempPiece, tempMove;
BitMap targetBitmap, freeSquares;
Move move;
ifirst = index;
move.clear();
opponentSide = !board.nextMove;
freeSquares = ~board.occupiedSquares;
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black to move
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
if (board.nextMove) // black to move
{
targetBitmap = board.whitePieces; // we want captures only!
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black Pawns
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(BLACK_PAWN);
tempPiece = board.blackPawns;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = BLACK_PAWN_ATTACKS[from] & targetBitmap; // pawn captures
if ((RANKS[from]) == 2) tempMove |= BLACK_PAWN_MOVES[from] & freeSquares; // promotions
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
if ((RANKS[to]) == 1)
{
move.setProm(BLACK_QUEEN); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(BLACK_ROOK); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(BLACK_BISHOP); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(BLACK_KNIGHT); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(EMPTY);
}
else
{
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
}
tempMove ^= BITSET[to];
}
if (board.epSquare)
{
if (BLACK_PAWN_ATTACKS[from] & BITSET[board.epSquare])
{
move.setProm(BLACK_PAWN);
move.setCapt(WHITE_PAWN);
move.setTosq(board.epSquare);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
}
}
tempPiece ^= BITSET[from];
move.setProm(EMPTY);
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black Knights
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(BLACK_KNIGHT);
tempPiece = board.blackKnights;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = KNIGHT_ATTACKS[from] & targetBitmap;
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black Bishops
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(BLACK_BISHOP);
tempPiece = board.blackBishops;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = BISHOPMOVES(from); // see Macro's
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black Rooks
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(BLACK_ROOK);
tempPiece = board.blackRooks;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = ROOKMOVES(from); // see Macro's
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black Queens
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(BLACK_QUEEN);
tempPiece = board.blackQueens;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = QUEENMOVES(from); // see Macro's
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Black King
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(BLACK_KING);
tempPiece = board.blackKing;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = KING_ATTACKS[from] & targetBitmap;
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
move.setProm(EMPTY);
}
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White to move
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
else
{
targetBitmap = board.blackPieces;
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White Pawns
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(WHITE_PAWN);
tempPiece = board.whitePawns;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = WHITE_PAWN_ATTACKS[from] & targetBitmap; // pawn captures
if ((RANKS[from]) == 7) tempMove |= WHITE_PAWN_MOVES[from] & freeSquares; // promotions
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
if ((RANKS[to]) == 8)
{
move.setProm(WHITE_QUEEN); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(WHITE_ROOK); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(WHITE_BISHOP); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(WHITE_KNIGHT); board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
move.setProm(EMPTY);
}
else
{
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
}
tempMove ^= BITSET[to];
}
if (board.epSquare)
{
if (WHITE_PAWN_ATTACKS[from] & BITSET[board.epSquare])
{
move.setProm(WHITE_PAWN);
move.setCapt(BLACK_PAWN);
move.setTosq(board.epSquare);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
}
}
tempPiece ^= BITSET[from];
move.setProm(EMPTY);
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White Knights
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(WHITE_KNIGHT);
tempPiece = board.whiteKnights;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = KNIGHT_ATTACKS[from] & targetBitmap;
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White Bishops
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(WHITE_BISHOP);
tempPiece = board.whiteBishops;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = BISHOPMOVES(from); // see Macro's
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White Rooks
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(WHITE_ROOK);
tempPiece = board.whiteRooks;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = ROOKMOVES(from); // see Macro's
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White Queens
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(WHITE_QUEEN);
tempPiece = board.whiteQueens;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = QUEENMOVES(from); // see Macro's
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst,index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
}
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// White king
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
move.setPiec(WHITE_KING);
tempPiece = board.whiteKing;
while (tempPiece)
{
from = firstOne(tempPiece);
move.setFrom(from);
tempMove = KING_ATTACKS[from] & targetBitmap;
while (tempMove)
{
to = firstOne(tempMove);
move.setTosq(to);
move.setCapt(board.square[to]);
board.moveBuffer[index].moveInt = move.moveInt;
board.addCaptScore(ifirst, index);
index++;
tempMove ^= BITSET[to];
}
tempPiece ^= BITSET[from];
move.setProm(EMPTY);
}
}
return index;
}
(...)
void Board::addCaptScore(int &ifirst, int &index)
{
int i, val;
Move capt;
capt = moveBuffer[index];
// Following 2 lines of code is an MVV/LVA scheme:
// val = 128 * PIECEVALUES[capt.getCapt()] + PIECEVALUES[capt.getPiec()];
// if (capt.isPromotion()) val += 512 * PIECEVALUES[capt.getProm()];
val = SEE(moveBuffer[index]);
// Discard this move if the score is not high enough:
if (val < MINCAPTVAL)
{
index--;
return;
}
// now insert the move into the sorted list at the right location:
// i = descending because the capture generated should deliver moves be in pretty reasonable order
// (captures by pawns are generated first, queens last), so if we're lucky we don't need to sort.
i = index - 1;
while (i > ifirst -1 && val > moveBuffer[i+OFFSET].moveInt) i--; // find the insertion location
memmove(&moveBuffer[i+2], &moveBuffer[i+1], (index-i-1)*sizeof(capt)); // move aside moves
memmove(&moveBuffer[i+2+OFFSET], &moveBuffer[i+1+OFFSET], (index-i-1)*sizeof(capt)); // move aside scores
moveBuffer[i+1].moveInt = capt.moveInt; // insert the move
moveBuffer[i+1+OFFSET].moveInt = val; // insert the score
return;
}
step 85: globals.h
(...)
//// Search parameters start here:
//
int LARGE_NUMBER = KING_VALUE + 1;
int CHECKMATESCORE = KING_VALUE;
int STALEMATESCORE = 0;
int DRAWSCORE = 0;
Move NOMOVE;
HashKeys KEY;
// variables for quiescence and SEE:
int OFFSET = 128;
int MINCAPTVAL = 1;
int WEST = -1;
int NORTHWEST = +7;
int NORTH = +8;
int NORTHEAST = +9;
int EAST = +1;
int SOUTHEAST = -7;
int SOUTH = -8;
int SOUTHWEST = -9;
BitMap RAY_W[64];
BitMap RAY_NW[64];
BitMap RAY_N[64];
BitMap RAY_NE[64];
BitMap RAY_E[64];
BitMap RAY_SE[64];
BitMap RAY_S[64];
BitMap RAY_SW[64];
int HEADINGS[64][64];
#endif
step 86: extglobals.h
(...)
extern int LARGE_NUMBER;extern int CHECKMATESCORE;
extern int STALEMATESCORE;
extern int DRAWSCORE;
extern Move NOMOVE;
extern HashKeys KEY;
extern int OFFSET;
extern int MINCAPTVAL;
extern int WEST;
extern int NORTHWEST;
extern int NORTH;
extern int NORTHEAST;
extern int EAST;
extern int SOUTHEAST;
extern int SOUTH;
extern int SOUTHWEST;
extern BitMap RAY_W[];
extern BitMap RAY_NW[];
extern BitMap RAY_N[];
extern BitMap RAY_NE[];
extern BitMap RAY_E[];
extern BitMap RAY_SE[];
extern BitMap RAY_S[];
extern BitMap RAY_SW[];
extern int HEADINGS[64][64];
#endif
step 87: data.cpp
(...)
NOMOVE.moveInt = 0;
KEY.init();
// ===========================================================================
// HEADINGS and RAYS, used in SEE:
// ===========================================================================
for (i = 0 ; i < 64; i++)
{
RAY_W[i] = 0;
RAY_NW[i] = 0;
RAY_N[i] = 0;
RAY_NE[i] = 0;
RAY_E[i] = 0;
RAY_SE[i] = 0;
RAY_S[i] = 0;
RAY_SW[i] = 0;
for (square = 0 ; square < 64; square ++)
{
HEADINGS[i][square] = 0;
}
}
for (rank = 1 ; rank < 9; rank++)
for (file = 1 ; file < 9; file++)
{
i = BOARDINDEX[file][rank];
// WEST:
for (afile = file - 1 ; afile > 0; afile--)
{
HEADINGS[i][BOARDINDEX[afile][rank]] = WEST;
RAY_W[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[afile][rank]];
}
// NORTHWEST:
for (afile = file - 1, arank = rank + 1 ; (afile > 0) && (arank < 9); afile--, arank++)
{
HEADINGS[i][BOARDINDEX[afile][arank]] = NORTHWEST;
RAY_NW[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[afile][arank]];
}
// NORTH:
for (arank = rank + 1 ; arank < 9; arank++)
{
HEADINGS[i][BOARDINDEX[file][arank]] = NORTH;
RAY_N[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[file][arank]];
}
// NORTHEAST:
for (afile = file + 1, arank = rank + 1 ; (afile < 9) && (arank < 9); afile++, arank++)
{
HEADINGS[i][BOARDINDEX[afile][arank]] = NORTHEAST;
RAY_NE[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[afile][arank]];
}
// EAST:
for (afile = file + 1 ; afile < 9; afile++)
{
HEADINGS[i][BOARDINDEX[afile][rank]] = EAST;
RAY_E[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[afile][rank]];
}
// SOUTHEAST:
for (afile = file + 1, arank = rank - 1 ; (afile < 9) && (arank > 0); afile++, arank--)
{
HEADINGS[i][BOARDINDEX[afile][arank]] = SOUTHEAST;
RAY_SE[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[afile][arank]];
}
// SOUTH:
for (arank = rank - 1 ; arank > 0; arank--)
{
HEADINGS[i][BOARDINDEX[file][arank]] = SOUTH;
RAY_S[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[file][arank]];
}
// SOUTHWEST:
for (afile = file - 1, arank = rank - 1 ; (afile > 0) && (arank > 0); afile--, arank--)
{
HEADINGS[i][BOARDINDEX[afile][arank]] = SOUTHWEST;
RAY_SW[BOARDINDEX[file][rank]] |= BITSET[BOARDINDEX[afile][arank]];
}
}
return;
}
void info()
{
// your playground... display variables - meant for testing/verification purposes only
std::cout << std::endl << "============ info start ==============" << std::endl;
std::cout << "size of board, in bytes = " << sizeof(board) << std::endl;
std::cout << "Material value = " << board.Material << std::endl;
std::cout << "White castling rights = " << int(board.castleWhite) << std::endl;
std::cout << "Black castling rights = " << int(board.castleBlack) << std::endl;
std::cout << "En-passant square = " << board.epSquare << std::endl;
std::cout << "Fifty move count = " << board.fiftyMove << std::endl;
std::cout << "bitCnt of white pawns = " << bitCnt(board.whitePawns) << std::endl;
std::cout << std::endl << "bitmap of blackKnights | board.whitePawns:" << std::endl;
displayBitmap(board.blackKnights | board.whitePawns);
std::cout << "============ info end ================" << std::endl << std::endl;
return;
}
|
|
|
 |
|
last update: Saturday 25 June 2011