Author: Robert Hyatt
Date: 07:54:02 10/30/01
Go up one level in this thread
On October 30, 2001 at 08:30:34, Sune Fischer wrote:
>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.
one will do it but you are right.... it is not free.. Unless you build
special-purpose hardware like DB's creators. Then you would just store
one occupied square bitboard and _really_ "rotate" it with three special
"access methods" as needed at no cost at all.
>
>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?).
Yes...
>
>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.
Best advice is "try it". That is what I did when I first came up with the
idea about the "rotated" stuff... And I wouldn't give up if it is slower
at first. It might take time to work out all the details...
However, the down-side is that 64 bit architectures will cut the work by
1/2 for normal rotated bitboards...
This page took 0 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.