It seems I need to explain how the code works, since I have a lot of people saying a lot of wildly different things about my code.
It is based on an old post by Andrew Tridgell (
https://groups.google.com/forum/#!msg/r ... yOjo4ybE0J) in RGCC in 1999, but contains a few innovations of my own (so far as I can tell).
Here is my board structure:
Code: Select all
struct Board {
uint32_t bitlist[64]; /* For each square, what pieces attack it? */
char piecelist[32]; /* For each piece, which square is it on? */
char index[64]; /* For each square, which piece is on it? */
uint32_t sidemask[2];
char side;
char castle;
char ep;
char fifty;
uint32_t piecemask[6];
uint64_t hash;
uint32_t rep[100];
};
Most of it is reasonably self-explanatory, I think.
Bitlist is my attack table, which states which pieces attack this square for a given square. Each piece has its own unique bit. This gets updated after MakeMove().
Sidemask is a mask that contains all the piece bits for a given side. Likewise, piecemask is a mask that contains all the piece bits for a given piece type.
Bitlist, sidemask and piecemask all have a one-to-one correlation in that the Nth bit refers to the Nth piece for all of them. (What N actually is does not matter, so long as it is less than 32 for my case.) In Tridgell's post, sidemask and piecemask were fixed macro constants that I felt were too inflexible, so I took the liberty of making them variables of the board structure instead.
Of course, these bits alone are meaningless - they do not correlate to a square at all. For this, I have index and piecelist. Index is about as close to a mailbox as I get - it states what N is for a given square, or INVALID if there is no piece on that square. Likewise, piecelist is a piecelist, that states what square a piece is on for a given N, or INVALID if there is no piece there.
With all this in mind, let's revisit the capture generator I posted earlier. The algorithmic skeleton looks like this, with how the code does it in comments:
Code: Select all
int GenerateCaptures(...)
{
enemy_pieces = GetEnemyPieces(); // Done by a sidemask lookup.
for each enemy in enemy_pieces { // Done by LSB counting of enemy_pieces.
enemy_square = GetPieceSquare(enemy); // Done by a piecelist lookup.
attacks = GetFriendlyAttacksToSquare(enemy_square); // Done by the intersection of the attack table entry
// and sidemask for the friendly side.
for each friend in attacks { // More LSB counting.
// Remember that my attack table stores an entry as a piece attack to this square.
friendly_square = GetPieceSquare(friend); // Piecelist lookup.
if (IsPawn(friend) && // Piecemask intersection.
IsCapturePromotion(friendly_square)) { // Rank calculation.
AddCapturePromotions(friendly_square, enemy_square); // Add to movelist.
continue;
}
AddCapture(friendly_square, enemy_square); // Add to movelist.
}
}
if (CanEnPassant()) { // b->ep != INVALID
enemy_square = EnPassantSquare();
attacks = GetFriendlyPawnAttacksToSquare(enemy_square); // More mask intersection.
for each friend in attacks { // More LSB counting. Max 2 iterations.
friendly_square = GetPieceSquare(friend); // Piecelist lookup.
AddEnPassant(friendly_square, enemy_square);
}
}
return MoveList(); // I actually return movecount, with movelist as an out parameter.
}
Is it perfect? No. I do still rely on the attack table code heavily and pay in speed, but I think this elegance is worth it, and it relies on no external tables - all of the data is within the board representation.