Author: Dann Corbit
Date: 20:32:54 03/03/06
Go up one level in this thread
On March 03, 2006 at 18:49:39, Gerd Isenberg wrote:
>On March 03, 2006 at 18:29:46, Dann Corbit wrote:
>
>>On March 03, 2006 at 17:14:54, Tony Werten wrote:
>>
>>>On March 03, 2006 at 15:58:21, Steffan Westcott wrote:
>>>
>>>>Gerd,
>>>>
>>>>I may have terribly misunderstood things, but there is direct algorithm for
>>>>mapping the 128 possible attack bitboards to 7 bit numbers. Additionally, the
>>>>algorithm does not need the location of the ray source square, nor any lookup
>>>>tables.
>>>>
>>>>For a ray along a rank or diagonal, it is sufficient to collapse the files:
>>>>
>>>>typedef unsigned __int64 BitBoard;
>>>>
>>>>int collapsed_files_index(BitBoard b)
>>>>{
>>>> b |= b >> 32;
>>>> b |= b >> 16;
>>>> b |= b >> 8;
>>>> return b & 0xFF;
>>>>}
>>>>
>>>>For a ray along a file, a little more trickery is needed:
>>>>
>>>>int collapsed_ranks_index(BitBoard b)
>>>>{
>>>> b |= b >> 4; // No masking needed
>>>> b |= b >> 2; // " "
>>>> b |= b >> 1; // " "
>>>> return ((b & 0x0101010101010101) * 0x0102040810204080) >> 56;
>>>>}
>>>>
>>>>Both of the above routines return 8 bit results. Depending on the left/right
>>>>orientation of the ray in relation to your chosen bitboard bit numbering scheme,
>>>>you may need to shift the result right by 1 bit.
>>>>
>>>>In addition, if you know the co-ordinates of the source square (either at
>>>>runtime or compile time), simpler variants of the above routines are possible.
>>>>
>>>>I don't use techniques like these as I avoid serialisation of moves or features
>>>>as much as possible. However, I offer you and Dann the above as it may be of
>>>>interest.
>>>
>>>Hi Steffan,
>>>
>>>although the algoritm looks simpler (allthough I'm not sure I understand) , (BB
>>>& mask)*magic_number will give a better performance.
>>
>>Why not just: switch (BB) {/*128 cases go here */}
>>?
>>What is the value of the transform into a shorter integer type?
>>Has anyone measured that it makes the switch faster? For me it is only
>>important if it makes it faster for 64 bit hardware anyway.
>
>Branchless stuff and memory access versus a 7 folded cmp-jxx chain and a lot of
>btb-entries on some good chance of a miss-prediction here and there.
>
>Of course if you index a function pointer table a "save" missprediction" occurs
>as well. So the folding is intented to avoid branches at all and to index
>precaluclated attack bitboards the same way as in a rotated framework.
>
>While your switch approach seems to cover much more items. All precalculated
>raywise properties of a square one may think about, "indexed" somehow by all up
>to seven other man on that ray - not only occupied states.
OK. So you make an array of 128 function pointers then, and do this:
status = method[hashval(BB)]();
PGO seems to take a lot of the sting out of missed branch predictions, but of
course there will always be some.
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.