Author: Gerd Isenberg
Date: 03:09:17 01/17/04
Go up one level in this thread
On January 16, 2004 at 15:51:42, Gerd Isenberg wrote: >On January 16, 2004 at 14:26:32, Alessandro Damiani wrote: > >> >>>i was asking because i'm generating all attacks in all positions (also the leaf >>>nodes), which takes a significant amount of time. i thought my >>>looping-over-bitboards was terribly slow, then i replaced it by the kogge-stone >>>stuff that was posted here a while ago, and it got even slower ;-) >>>so the next thing to try would be rotated bitboards, but it's rather a lot of >>>work to implement, i'm afraid. >> >>When I started working on my engine years back I first implemented the Chess 4.0 >>style attack tables. Then I read about Bob's Rotated Bitboards. I liked the >>idea, but found keeping updated rotated representations of the board too >>complicated. I therefore developed my own way of determining the attacked >>squares. I call it Rotated Indices. As its name suggests it keeps updated the >>indices used to access the attack tables. In contrast to Rotated Bitboards you >>don't have to extract the index out of the rotated bitboards, it is already >>there. The code is very simple. >> >>If you really want to implement Rotated Bitboards then you have to do it, >>waiting doesn't help. ;-) But, if you don't want to spend more than two hours >>for the implementation then you may have a look at Rotated Indices. You can find >>the source code on my homepage under "Chess programming: Bitboards in Fortress": >>http://freeweb.econophone.ch/fortress >> >>Alessandro >> ....eine Einbuchtung im Raum > >After looking a while to your source, i think your code is very similar to mine, >except the data density of your Indices and the identifiers ;-) > >// slide indices: >unsigned int SlideIndexH[8], // horizontal > SlideIndexV[8], // vertical > SlideIndexRU[16], // right up (RU) > SlideIndexRD[16]; // right down (RD) > >I use(d) something like this: > >// slide indices == rotated bitboards: >unsigned char SlideIndexH[8], // horizontal > SlideIndexV[8], // vertical > SlideIndexRU[8], // right up (RU) > SlideIndexRD[8]; // right down (RD) > >But with bitboard declaration instead of BYTE[8] (what about a union?). >The only trick is to pack the 15 diagonals byte aligned into eight bytes and >address them in this manner. > >rightupIdx = (sq-Rank(sq)) & 7; >rightDownIdx = (~sq-Rank(sq)) & 7; > >My drawback was the byte access with zero extending to 32-bit. >Your drawback is to update four SlideIndices additionally to the none rotated >one and i had only three additional ones. > >Gerd In my former approach as well in Bob's, both with packed diagonals in 45 or 135 degree rotated occupied boards, there are sideeffects from one diagonal to another which may yield to worse cache efficiency. 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 ^a1 E.g with my mapping the rightUp access with square a8 (ray a8-a8), is dependent on the state of all squares of diagonals with index 1, that is a8-a8 and b1-h7. Therefore each state change on b1-h7 does (not necessarily) effect the address of a1h8Attacks[a8][state of diagonal 1] ... even if their content is the same of course, an empty attack set for this particular square and diagonal. Due to such state side effects of "complement" or neighboured diagonals, much more elements of the huge attack array are addressed than necessary, which may yield to more cache pollution. Your unique diagonal index scheme 0..14 don't has this problem. In Bob's approach for diagonals, it may be worth to introduce a second lookup to consider the length of the diagonals by not anding with 63 but with diaMaskRU[sq] containing values 1,3,7,15,31,63. One possible shlight improvement in your approach is a lookup in precalculated tables to save some calculations for diagonals, even if they are cheap: (s>>3)+(s&7) 7-(s>>3)+(s&7) Gerd
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.