Author: Sune Fischer
Date: 05:30:34 10/30/01
Hi
I have some questions for those that use rotated bitboards.
I've been reading up on them, and I'm concerned about the number
of 64-bit operations required for this scheme.
As far as I can tell one needs 4 occupied bitboards
and they are to be incrementally updated at every move.
This is at least four 64-bit operations, probably more like eight.
This is just the pre-calculation, needed only once for all the sliding
pieces. The rest goes something like this:
BITBOARD attacks=0;
if (BishopMover(piece)) {
get diaga1 status (shift/AND);
attacks|=diaga1h8_attacks[square][status];
get diagh1 status (shift/AND);
attacks|=diagh1a8_attacks[square][status];
}
if (RookMover(piece)) {
get rank status (shift/AND);
attacks|=rank_attacks[square][status];
get file status (shift/AND);
attacks|=file_attacks[square][status];
}
For a rook and bishop that is 6 operations, and for the queen
about 12.
These numbers seem to be static through out the game,
completely independent of the position on the board (right?).
If there are many sliding pieces on the board, then the pre-calculation
is relative cheap, but what happens if there are only e.g. 4 sliding pieces
on the board? That is not unusual in the endgame I think.
Lets look at the rook, suppose we construct an array like this:
BITBOARD Rook[64];
Rook[3]:
00010000
00010000
00010000
00010000
00010000
00010000
00010000
11101111
(and so on...)
That would be the rook attack bitboard on an empty board.
Now we need another array:
BITBOARD RookPieces[64][64];
RookPieces[3][19]:
00000000
00000000
00000000
00000000
00000000
00010000
00010000
11101111
This is a rook with one other piece on the board (you get the idea).
Those two arrays are just constant and can be calculated in Init().
To find the rook's attack board we can simply do:
BITBOARD bb;
rook_attack = Rook[square];
bb = Rook[square] & occupied;
while(bb)
{
rook_attack&=RookPieces[square][FirstOne(bb)];
bb&=bb-1;
}
I need the occupied bitboard of cause, but that can be done incrementally with 1
or 2 operations.
The beauty of this is if bb=0 or only has 1 bit set, in other words; if there is
nothing standing in the lines of the rook then we are done after only 3
operations!
I think in these cases it will be faster than the rotated boards.
Too slow if there are lots of pieces in the *rays*,
which is why it only has a chance in the endgame.
The queen will be a problem, it attacks so many squares.
Not sure how slow FirstOne() is compared to a 64-bit operation on a 32-bit chip,
but if bb=0 then it's not even called.
Perhaps a hybrid algorithm would be optimal, use rotated from the start,
when fewer than x sliding pieces left make the switch.
okay, that's it, I'm done :)
-S.
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.