Author: Alessandro Damiani
Date: 00:16:32 01/17/04
Go up one level in this thread
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
#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.
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.