Author: Gerd Isenberg
Date: 12:35:24 05/08/03
Hi all,
Two versions of the same algorithm based on Walter Faxon's magic BitScan.
The idea is to map two single populated from/to-bitboards to an appropriate
integer range for history and hashkey indexing. It may help to avoid the
conversion to square coordinates via bitscan, to isolate bits only with x & -x.
From/to-bits may be combined by "or" and isolated back to from/to-bits by anding
with own pieces (is from).
//------------------------------------------------------------------------------
// The 1st takes about 12 seconds inside a test loop of 10**9 runs (XP2.1+).
// It maps the 1792 possible valid moves to unique values in a range of 11230.
unsigned int getMoveKey1 (BitBoard frBit, BitBoard toBit)
{
BB frbb, tobb; // msc union def see below
unsigned int frfd, tofd;
frbb.u = frBit - 1;
tobb.u = toBit - 1;
frfd = frbb.high ^ frbb.low ^ 0x01C5FC81;
tofd = tobb.high ^ tobb.low ^ 0x01C5F479;
frfd += frfd >> 16;
frfd -= frfd >> 8;
frfd &= 0xff;
tofd += tofd >> 16;
tofd -= tofd >> 8;
tofd &= 0xff;
return frfd * 72 + tofd - (51*72+21);
}
// The 2nd takes about 13 seconds inside a test loop of 10**9 runs (XP2.1+).
// It maps the 1792 possible valid moves to unique values in a range of 10620.
unsigned int getMoveKey2 (BitBoard frBit, BitBoard toBit)
{
BB frbb, tobb; // msc union def see below
unsigned int frfd, tofd;
frbb.u = frBit - 1;
tobb.u = toBit - 1;
frfd = frbb.high ^ frbb.low ^ 0x01C5FC81;
tofd = tobb.high ^ tobb.low ^ 0x013C4B4E;
frfd += frfd >> 16;
frfd -= frfd >> 8;
frfd &= 0xff;
tofd += tofd >> 16;
tofd += tofd >> 8; // + here
tofd &= 0xff;
return frfd * 68 + tofd - (51*68 + 4);
}
//------------------------------------------------------------------------------
The second one is a bit slower with msc and space optimization, due to mul 68 is
more expensive than mul 72 (more lea friendly).
The first one needs about 11K-Entry lookups, the second 10.5K-Entries, instead
of the usual 4K for 64*64 square indexing.
The first magic 0x01C5FC81 is from Walter's original routine. It maps single
populated Bitboards to a range of 154 with offset 51.
The second magic constants and factors (150...72,70,68) are determined
empirically after playing around with Walter's Routine - there are a lot, with
different ranges and derivations. Very interesting, but it's really magic. I see
the property of the magic numbers to get unique keys, but calculating them
instead of empirical try exceeds definitely my math skills ;-)
In Walter's initial BitScan algorithm there is even a solution with a range of
152 - Magic is 0x010404BE or 0x04BEFEFB, and for folding down the bits with plus
only:
bb.u = Bit - 1;
fd = bb.high ^ bb.low ^ 0x010404BE;
fd += fd >> 16;
fd += fd >> 8;
fd &= 0xff;
Another idea for this purpose is using the mod-operator with magic ranges (eg.
5811 or 9246).
But even using four integer muls for the mod(9246), it was too slow and no real
alternative to bitscan.
Cheers,
Gerd
--------------------------------------------------------------------------------
unsigned int getMoveKeyByMod (BitBoard frbb, BitBoard tobb)
{
unsigned int hash = mod9246(frbb|tobb);
if ( frbb < tobb )
hash = 9247-hash;
return hash;
}
union BB
{
BitBoard u;
struct
{
unsigned int low;
unsigned int high;
};
};
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.