cms271828 wrote:
Any suggestions on how I proceed? Thanks
Search your magics on your own - it is fun and gives you a unique engine
There are several brute force approaches.
The inner loop (likely inside a boolean routine) tries one magic/shift of one square - it traverses all subsets of the set of all relevant blockers of that ray - and looks if any negative collisions occurs:
Code: Select all
bool testMagicBishops(long magic2Try, int shift2Try, int square)
{
int count = 0;
int collision = 0;
Initialize bookholdingAttacks[maxsize] with -1
long oset = conventionalBishopAttacks(square, 0) & 0x007E7E7E7E7E7E00;
long occ = 0; // first empty subset
do
{ // for all subsets
index = (magic2Try * occ) >> shift2Try; // the magic hashing function
attacks = conventionalBishopAttacks(square, occ);
if ( bookholdingAttacks[index] == -1 )
{ // free slot, store attacks
bookholdingAttacks[index] = attacks;
count++;
}
else if ( bookholdingAttacks[index] == attack )
{
collision++; // different occupancies map same attack, fine
}
else
{
return false; // negative collision, fails
}
occ = (occ-oset) & oset; // next subset
}
while( occ != 0);
// print magic, shift, square, count and collisions
return true; // ok, magic, shift uniqly maps all relevant occupancies
}
I like snoob, same number of one bits, for magics with 4 to 8 or 56..60 bit sets.
http://chessprogramming.wikispaces.com/ ... 20a%20Set4
You may try random numbers as well or xor them with some constant, like a De Bruijn sequence or whatever else.
Code: Select all
bool tryShiftBishop(int shift2Try, int square, int nBits4magic)
{
long x, y, first;
first = (1 << nBits4magic) - 1;
for (x = first; (y = snoob(x)) > x; x = y)
if ( testMagicBishops ( x, shift, square) ) return true;
return false;
}
Finally you may traverse over shitf amounts, the higher the shift the denser the range per square. For bishops there are index ranges of only four bits.
Code: Select all
bool findMagicBishop(int square, int nBits4magic, int rangeBits)
{
for (int s = 64 - rangeBits; s > 64-12; s--)
if ( tryShiftBishop(s, int square, nBits4magic) ) return true;
return false;
}
41KByte bishops is a matter of seconds, the more denser you like the more time it takes - unless somebody finds a better algorithm.
Gerd
) but I have done it for 6-bits on A1 in a few minutes before.