Author: Gerd Isenberg
Date: 14:45:33 03/03/06
Go up one level in this thread
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.
>
>
>Cheers,
>Steffan
Steffan,
again you hit the nail on the head!
The collapsed_files_index looks very 32-bit friendly
; bitboard is passed in 32-bit manner, eg, edx:eax
or eax, edx
mov edx, eax
shr edx, 16
or eax, edx
or al, ah
I will as well avoid rotated lookups but use those quadbitboard mutex-fills, to
have most likely one-to-one relationship between target and source squares.
I was fascinated by the possibility to generate moves rather branchless with De
Bruijn multiplication...
---
The rotated lookup alternative idea came in the thread initiated by Christopher
Conkie, where Dann mentioned the switch approach - while i was doing some De
Bruijn "research".
As Tony found out, random numbers are better suited to find magic factors for
that purpose.
For calculating an occupied index of a ray to index a precalculated attack table
with - you have to mask the occupied bitboard for that ray anyway. (Or to make
some parallel prefix fills).
So using the same cacheline twice to get a magic factor looks reasonable. Four
times mask[sq][dir] and magic[sq][dir] for all four directions are one amd64
cacheline.
64-bit Multiplication is rather cheap in 64-bit mode. So two most likely
L1-lookups, mul and shift sounds cheaper to me at the first glance, specially
than collapsed_ranks_index.
Cheers,
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.