Author: Robert Hyatt
Date: 09:39:47 01/17/04
Go up one level in this thread
On January 17, 2004 at 03:16:32, Alessandro Damiani wrote: >On January 16, 2004 at 23:00:01, Robert Hyatt wrote: > >>On January 16, 2004 at 16:16:08, Alessandro Damiani wrote: >> >>>On January 16, 2004 at 15:19:49, 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 >>>> >>>> >>>>Ahh, you incremental update occupied states for each ray - really nice >>>>improvement. >>>> >>>>What's about the occupied redundancy of the most outer squares of a ray? >>>>With two additional instructions, your 2nd level cache may happily wind a bit: >>>> >>>>inside your attack-getter-macros: >>>> ...[sq][(SlideIndexX[...] >> 1) & 63] >>>> >>>>// 128K instead of 512K >>>>BitBoard AFRhorizontal[64][64], >>>> AFRvertical[64][64], >>>> AFBrightup[64][64], >>>> AFBrightdown[64][64]; >>>> >>>>You may even better consider that property in incremental update and keep >>>>SlideIndexX in 0..63 range rather than 0..255. >>>> >>> >>>I read about Crafty using these smaller tables here in CCC. I like it, 128kByte >>>instead of 512kByte. I guess the additional cost for shifting and anding is >>>negligible, isn't it? >>> >>>Alessandro >> >> >>There is really no extra cost when you think about it. >> >>Before I had to shift right N bits to move the diag contents to the right >>end of the register, then AND with 255 to extract just the right 8 bits. >> >>Now I shift right 1 more bit, and AND with 63 instead. Absolutely free. >> >>:) > >I see now that my question was misleading. I meant in the context of Rotated >Indices, where these two instructions would be an additional cost. For instance, >the macro to determine attacked squares in the direction right up is now > It wasn't misleading at all. I'd like to take the testicles of the guy that invented these "laptop scratchpads" and ... I was responding to something else, but when I hit the scratchpad, I moved it and happened to click on your message. Without noticing the context, I then responded as though it were about how I am doing the rotated lookup now with the 64x64 tables rather than 64x256. I had known about this reduction for quite a while as several had mentioned it in the past. But since almost all machines were faster with the -DCOMPACT_ATTACKS stuff, I never took the time to fix this. But on the Opteron, compact attacks were slower so I decided to go ahead and fix things properly, and after doing so, it turned out to be close to the speed of compact attacks so I dumped that compact stuff completely to simplify the code. > #define AttackDiagRightUp(s) (AFBrightup[s][SlideIndexRU[(s >> 3)+(s & 7)]]) > >The new macro would be > >#define AttackDiagRightUp(s) (AFBrightup[s][(SlideIndexRU[(s >> 3)+(s & 7)] >>1 >) & 63]) > >As Gerd said, the two additional instructions can be put into the SlideIndexXX. >I am going to test the smaller tables. While I am not doing it exactly as he does, I found the 75% memory reduction helped performance. > >Alessandro
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.