compact bitboard move generator
Posted: Mon Feb 25, 2008 10:26 pm
Last week we discussed the idea of eliminating replicated code completely from the Crafty move generator, and I mentioned that I had plans to test an array of function pointers approach. Here's what I tried:
Those five functions just return a bitboard set of <to> squares for a piece on from, with a requirement that the to squares must be in the set <target> as well.
I then declared this array of function pointers:
BITBOARD (*Generator[7]) (TREE*, int, BITBOARD) =
{ NULL, NULL, KnightMoves, BishopMoves, RookMoves, QueenMoves, KingMoves };
and used this for the compact move generator:
Much shorter and cleaner, but, as I suspected 5-10% slower to boot, because now the 5 functions above can't be inlned because they really are function calls because of the array of pointers to functions used.
I then tried replacing the array of functions by a switch that generated each piece type separately, rather than using the Generator() function pointer, but that was not much better.
So the explicitly unrolled form I am currently using is going to be the norm for a while, it seems, as the performance hit is too much, just to obtain more concise code...
BTW, CCC is slow as the devil today, often taking 2-3-4 minutes to refresh a page...
Code: Select all
BITBOARD KnightMoves(TREE *tree, int from, BITBOARD target) {
return (knight_attacks[from] & target);
}
BITBOARD BishopMoves(TREE *tree, int from, BITBOARD target) {
return (AttacksBishop(from, OccupiedSquares) & target);
}
BITBOARD RookMoves(TREE *tree, int from, BITBOARD target) {
return (AttacksRook(from, OccupiedSquares) & target);
}
BITBOARD QueenMoves(TREE *tree, int from, BITBOARD target) {
return (AttacksQueen(from, OccupiedSquares) & target);
}
BITBOARD KingMoves(TREE *tree, int from, BITBOARD target) {
return (king_attacks[from] & target);
}
I then declared this array of function pointers:
BITBOARD (*Generator[7]) (TREE*, int, BITBOARD) =
{ NULL, NULL, KnightMoves, BishopMoves, RookMoves, QueenMoves, KingMoves };
and used this for the compact move generator:
Code: Select all
target = x; /* Occupied[btm] to generate captures of opponent pieces for example */
for (ptype = knight; ptype <= king; ptype++) {
piecebd = Pieces(wtm, ptype);
while (piecebd) {
from = Advanced(wtm, piecebd);
moves = Generator[ptype[(tree, from, target);
temp = from + (ptype << 12);
Unpack(wtm, move, moves, temp);
Clear(from, piecebd);
}
}
I then tried replacing the array of functions by a switch that generated each piece type separately, rather than using the Generator() function pointer, but that was not much better.
So the explicitly unrolled form I am currently using is going to be the norm for a while, it seems, as the performance hit is too much, just to obtain more concise code...
BTW, CCC is slow as the devil today, often taking 2-3-4 minutes to refresh a page...