Author: Robert Hyatt
Date: 08:15:58 01/15/04
Go up one level in this thread
On January 15, 2004 at 06:38:19, Gerd Isenberg wrote:
>On January 14, 2004 at 22:08:11, Ed Trice wrote:
>
>>Hello Federico,
>>
>>>Hi to all
>>>
>>>In my engine I use some bitboards, but nothing about rotated bitboards for
>>>bishop, rooks and queen moves.
>>>
>>>What chess sources or web pages can you recommend me?
>>>
>>>One answer can be Crafty. Seems to be a little difficult to understand but I
>>>don't tried yet :-)
>>>
>>
>>I definitely recommend reading the Crafty code for rotated bitboards. Basically,
>>you create rotated versions of the board so the shifting left and right "behave"
>>like diagonal displacements. For example, shifting bits from left to right in
>>increments of 1 would be like moving a rook horiztonally.
>>
>>But, if you lay the board out like this (a 45 degree rotation)
>>
>>a1, b1,a2, c1,b2,a3, d1,c2,b3,a4, e1,d2,c3,b4,a5, ....
>>
>>you can perform shifts on the BITS corresponding to these squares as if you were
>>actually doing complex digaonl shifts.
>>
>>The hard part for will be keeping track of the length of the diagonals for all
>>of the rotation possibilies (rotating right 45, rotating left 45, etc.) as well
>>as all of the rotation data.
>>
>>--Ed
>
>Yes, for 8*8 boards there are eight files and eight ranks but 15 diagonals for
>each of the two diagonal directions. I my former rotated bitboard approach i
>used following scheme to index the diagonals eg. for a1h8 direction
>(file - rank):
>
>-7 -6 -5 -4 -3 -2 -1 0
>-6 -5 -4 -3 -2 -1 0 1
>-5 -4 -3 -2 -1 0 1 2
>-4 -3 -2 -1 0 1 2 3
>-3 -2 -1 0 1 2 3 4
>-2 -1 0 1 2 3 4 5
>-1 0 1 2 3 4 5 6
> 0 1 2 3 4 5 6 7
>
>to get byte aligned diagonals i map them in following manner in the rotated
>board:
>
> 7 -1 -1 -1 -1 -1 -1 -1
> 6 6 -2 -2 -2 -2 -2 -2
> 5 5 5 -3 -3 -3 -3 -3
> 4 4 4 4 -4 -4 -4 -4
> 3 3 3 3 3 -5 -5 -5
> 2 2 2 2 2 2 -6 -6
> 1 1 1 1 1 1 1 -7
> 0 0 0 0 0 0 0 0
>
>With these mapping, you get the occupied state for the desired diagonals by byte
>access without further shifting. Note that using only three lower bits as
>diagonal index leads to following mapping scheme (file - rank) & 7
>(ambiguous, but dosn't matter due to square index):
>
> 1 2 3 4 5 6 7 0
> 2 3 4 5 6 7 0 1
> 3 4 5 6 7 0 1 2
> 4 5 6 7 0 1 2 3
> 5 6 7 0 1 2 3 4
> 6 7 0 1 2 3 4 5
> 7 0 1 2 3 4 5 6
> 0 1 2 3 4 5 6 7
>
> 7 7 7 7 7 7 7 7
> 6 6 6 6 6 6 6 6
> 5 5 5 5 5 5 5 5
> 4 4 4 4 4 4 4 4
> 3 3 3 3 3 3 3 3
> 2 2 2 2 2 2 2 2
> 1 1 1 1 1 1 1 1
> 0 0 0 0 0 0 0 0
>
>Gerd
Note that I do this in a simple way also.
IE if you have a diagonal with only 3 bits, I still use the
entire 8 bit (actually 6 bits if you read the paper) contents.
IE rather than trying to figure out how long the diagonal really
is, I initialize the attack bitmap for that diagonal. To explain
the diagonal gets right-aligned on the shift, but rather than ANDing
the good diagonal bits and turning the rest to zero, I get this:
BBBBBGGG
where BBBBB are the 5 bits that don't belong to the 3 bit diagonal, while
GGG are the three good bits.
I then initialize all 256 (actually 64 as the paper says, but 256 is
easier to explain here) so that for all BBBBB in the above 8 bits, the
following is true:
00000GGG = attacks for GGG
00001GGG = attacks for GGG
00010GGG = attacks for GGG
...
11111GGG = attacks for GGG
This is slightly cache unfriendly, but since I really ignore the first and
last bit anyway, this table is only 64*64*8 bytes long, which is not that
bad for today's cache sizes. And it eliminates trying to AND off the BBBBB
bits above to make them 00000.
IE here is how I produce bishop moves (macro in chess.h):
# define AttacksDiaga1(a) \
bishop_attacks_rl45[(a)][(tree->pos.occupied_rl45>> \
bishop_shift_rl45[(a)])&63]
# define AttacksDiagh1(a) \
bishop_attacks_rr45[(a)][(tree->pos.occupied_rr45>> \
bishop_shift_rr45[(a)])&63]
bishop_attacks_rl45[64][64] is the pre-computed attack bitmaps, and is
interpreted as bishop_attacksa_rl45[square][diag_contents]. In the above,
just taking one of the two diagonals, what you see is
bishop_attacks_rl45[a][b]
a=square we are generating bishops for.
I then compute b = rotated_left_45degree (the occupied squares bitmap that is
rotated correctly for this diagonal) and shift it right bishop_shift_rr45[a]
bits which moves that diagonal bit set to the rightmost N bits of the value. I
then AND with 63 (the shift actually is one more than needed to cut off the
rightmost bit that does not affect attacks since it is attacked whether the
square is empty or occupied) which cuts off the left bit if this is a real 8-bit
diagonal. I now use this value as "b" above.
I hope that helps, if not feel free to ask questions or point out something that
might be faster. :)
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.