Author: Gerd Isenberg
Date: 16:14:00 07/10/03
Go up one level in this thread
On July 10, 2003 at 17:07:35, Russell Reagan wrote:
>On July 10, 2003 at 05:01:48, Gerd Isenberg wrote:
>
>>// int table[1 << 64] = {...}; // ?????????????
>>int table[64]; // seems more reasonable
>>
>>int lsb(BitBoard singlebit)
>>{
>> // Create mask of ones based on least significant one in x.
>> singlebit ^= (singlebit - 1);
>> return table[(singlebit * magic) >> (64 - 6)];
>>}
>
>This sounds very interesting, but I don't really understand how this is supposed
>to work. Does anyone have a working version (with an initialized table[] and
>magic number, for instance)?
Hi Russell,
Matt Taylor's great routine may scan each none zero bitboard, not necessary
single bits, due to the x ^(x-1) statement (-1 toggles lsb one and lower zeros).
Something with abstract algebra, modulo arithmetic and group theory - maybe you
look for some bit pattern in the magic numbers - there are at least 32 for 64
bit - maybe you found more.
A fast and portable C-Alternative for cpus with fast 64bit multiplication.
And may be faster, than the x86-64 vectorpath instructions, specially with reset
found bit.
bsf rax, [bb]
btr [bb], rax
On x86-32 it sucks of course, due too many 32-bit multiplications.
Cheers,
Gerd
#include <stdio.h>
typedef unsigned __int64 BitBoard;
BitBoard bitmask[64] =
{
0x0000000000000001, 0x0000000000000002, 0x0000000000000004, 0x0000000000000008,
0x0000000000000010, 0x0000000000000020, 0x0000000000000040, 0x0000000000000080,
0x0000000000000100, 0x0000000000000200, 0x0000000000000400, 0x0000000000000800,
0x0000000000001000, 0x0000000000002000, 0x0000000000004000, 0x0000000000008000,
0x0000000000010000, 0x0000000000020000, 0x0000000000040000, 0x0000000000080000,
0x0000000000100000, 0x0000000000200000, 0x0000000000400000, 0x0000000000800000,
0x0000000001000000, 0x0000000002000000, 0x0000000004000000, 0x0000000008000000,
0x0000000010000000, 0x0000000020000000, 0x0000000040000000, 0x0000000080000000,
0x0000000100000000, 0x0000000200000000, 0x0000000400000000, 0x0000000800000000,
0x0000001000000000, 0x0000002000000000, 0x0000004000000000, 0x0000008000000000,
0x0000010000000000, 0x0000020000000000, 0x0000040000000000, 0x0000080000000000,
0x0000100000000000, 0x0000200000000000, 0x0000400000000000, 0x0000800000000000,
0x0001000000000000, 0x0002000000000000, 0x0004000000000000, 0x0008000000000000,
0x0010000000000000, 0x0020000000000000, 0x0040000000000000, 0x0080000000000000,
0x0100000000000000, 0x0200000000000000, 0x0400000000000000, 0x0800000000000000,
0x1000000000000000, 0x2000000000000000, 0x4000000000000000, 0x8000000000000000,
};
// used to find magic
// if you pass single populated bitboards,
// the mask creation is not necessary!!
int lsb(BitBoard singlebit, BitBoard magic)
{
// Create mask of ones based on least significant one
// singlebit ^= (singlebit - 1);
return (int)((singlebit * magic) >> (64 - 6));
}
void findMagic64()
{
int count[64];
int bitpos;
int foundcount = 0;
bool found;
for ( BitBoard magic = 0x03f08c5392cd5dbd + 2750736;
magic >= 0x03f08c5392cd5dbd ; magic--)
{
found = true;
for (bitpos = 0; bitpos < 64; bitpos++)
count[bitpos] = 0;
for (bitpos = 0; bitpos < 64 && found; bitpos++)
{
int bit = lsb(bitmask[bitpos], magic);
if ( count[bit] > 0 ) // already used
found = false;
else
count[bit] = bitpos+1; // must be > 0
}
if ( found )
{
foundcount++;
printf("\n0x%08x:%08x\n",
(int)(magic>>32),
(int)(magic&0xffffffff));
for (bitpos = 0; bitpos < 64; bitpos++)
{
printf("%02d ", count[bitpos]-1);
if ( ((bitpos+1) & 7) == 0 )
printf("\n");
}
}
}
printf("\nmagics found %02d\n", foundcount);
}
#ifdef MAGIC_FOUND
// depending on the magic you choose
int table[64] = {};
int bitScanAndReset(BitBoard &bb)
{
BitBoard lsb = bb & -bb;
bb ^= lsb;
return table[(lsb * oneOfTheFoundConst) >> (64 - 6)];
}
void bitScanAndResetTest()
{
int sq[64];
BitBoard bb = -1;
int i = 0;
while(bb)
sq[i++] = bitScanAndReset(bb);
for (i = 0; i < 64; i++)
{
if ( (i & 7) == 0 )
printf("\n");
printf("%02d ", sq[i]);
}
printf("\n");
}
#endif
int main(int argc, char* argv[])
{
findMagic64();
// bitScanAndResetTest();
return 0;
}
This page took 0.01 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.