Author: Gerd Isenberg
Date: 11:11:13 01/15/04
Go up one level in this thread
On January 15, 2004 at 12:37:03, Gerd Isenberg wrote:
>On January 15, 2004 at 11:15:58, Robert Hyatt wrote:
>
>>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]
>>
>
>
>My former attack getters were similar. But i didn't use the the bishop_shift
>lookup and the 64-bit shift right to get the occupied state.
>
>Instead i calculate the index (0..7) of the diagonals with
>
> (File(a)-Rank(a)) & 7 (a1h8)
> ((File(a)^7)-Rank(a)) & 7 (h1a8)
As i see my old sources now, a bit optimized:
(a-Rank(a)) & 7 (a1h8) // (file - rank) & 7
(~a-Rank(a)) & 7 (h1a8) // (mirrored file - rank) & 7
Inline members of my CNode class:
__forceinline BitBoard A1H8Attacks(unsigned int sq) const {
return sA1H8Atta[sq][(*(((BYTE*)&(m_Inc.m_OccuBBA1H8))+((sq-Rank(sq))&7))
& 0x7e) >> 1];
}
__forceinline BitBoard H1A8Attacks(unsigned int sq) const {
return sH1A8Atta[sq][(*(((BYTE*)&(m_Inc.m_OccuBBH1A8))+((~sq-Rank(sq))&7))
& 0x7e) >> 1];
}
Rank(sq) is sq>>3 of course.
Unfortunately the compiler didn't understand the "even" 2*state semantic due to
the previous "and 0x7e", and was not able to combine the final shift right with
the "sizeof(BitBoard)*state" address calculation.
Therefore i had even more unreadable versions of these inliners without >> 1,
but casts, using 2*state as 32-bit index to get state as 64-bit index ;-)
>
>and did a byte-access on the rotated occupied board with that index to get the
>state. Due to the 6 innner bits have to be masked to shrink the arrays, i and
>with 0x7e to get 2*state.
>
>I guess with 64-bit shift available your method requires less instructions and
>is favorable on 64-bit machines, even more if your rotated occupied bitboard is
>already inside a register.
>
>Another possible drawback of my method: the byte access requires the occupied
>board in memory, to cast BitBoard* to BYTE* and access via *(BytePtr+index).
>That may yield to load/store forewarding stalls, if short after the 64-bit store
>(in MakeMove) an "unsigned" byte load follows inside the same memory area.
>
>In the meantime, i don't use any rotated stuff anymore, but fill-algorithms and
>x^(x-2) trick with SIMD-instructions (MMX,SSE2) ;-)
>
>Gerd
>
>
>>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.