Author: Gerd Isenberg
Date: 09:37:03 01/15/04
Go up one level in this thread
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) 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.