Page 1 of 1
Occupancy Variations
Posted: Fri Jan 25, 2013 2:22 am
by CDaley11
I've been thoroughly studying the magic bitboard technique for quite some time now and I think I am starting to understand it. My question is: When calculating all the possible occupany variations (i.e, variations of possible blockers) for a sliding piece on a specific square, does it matter what order the variations are calculated and then stored in? So long as I have all the possible variations in an array, will there always be a magic number that will work to give the right indexes in that array?
Re: Occupancy Variations
Posted: Fri Jan 25, 2013 7:07 pm
by hyatt
CDaley11 wrote:I've been thoroughly studying the magic bitboard technique for quite some time now and I think I am starting to understand it. My question is: When calculating all the possible occupany variations (i.e, variations of possible blockers) for a sliding piece on a specific square, does it matter what order the variations are calculated and then stored in? So long as I have all the possible variations in an array, will there always be a magic number that will work to give the right indexes in that array?
I don't quite follow your "what order the variations are calculated and then stored in". What is a "variation" here? Each "thing" in the final table is a set of bits showing which squares the sliding piece attacks. Your main problem is finding a magic multiplier that produces unique values when it should, so that you can use those as an index into the attacks table, but without scattering the values out requiring a larger attacks array. Finding these "optimal multipliers" has burned a LOT of cpu time around the world.
Re: Occupancy Variations
Posted: Sat Jan 26, 2013 12:47 am
by CDaley11
What I'm trying to say is, lets say that I have an attack table for a rook. Is there a certain order that these attacks have to be put in? If I took the array of all the possible attacks, and jumbled up the order, would there still be a magic number that works?
Re: Occupancy Variations
Posted: Sat Jan 26, 2013 3:55 am
by User923005
Re: Occupancy Variations
Posted: Sat Jan 26, 2013 11:33 am
by Gerd Isenberg
CDaley11 wrote:What I'm trying to say is, lets say that I have an attack table for a rook. Is there a certain order that these attacks have to be put in? If I took the array of all the possible attacks, and jumbled up the order, would there still be a magic number that works?
You don't put all attack sets in any order into the table and then look for a fitting magic factor. For any magic factor to try, and amount of bits of the index for one square, you enumerate all relevant occupancies in any order, and then look whether applying the hash-function for each occupancy has no or only constructive collisions. You need an working attack getter (i.e. a loop-version) for that initial bootstrap process to check for collisions. I.e. occUniverse for a bishop on d4.
Code: Select all
. . . . . . . .
. . . . . . 1 .
. 1 . . . 1 . .
. . 1 . 1 . . .
. . . . . . . .
. . 1 . 1 . . .
. 1 . . . 1 . .
. . . . . . . .
With numberOfIndexBits == population count of occUniverse (9), you'll always find a magic factor, i.e. by trying randoms. For denser tables, one may try one bit less.
Code: Select all
bool testMagic( u64 magic2try, u64 occUniverse, u32 numberOfIndexBits, u32 sq) {
u64 table[1 << maxNumberOfBits];
memset(table, 0, sizeof(table));
u64 occ = 0;
do { // for all occupancies starting with empty set
u32 index = occ * magic2try >> (64 - numberOfBits);
u64 attacks = applySomeSlowAttackGetter(sq, occ);
if ( table[index] == 0 ) {
table[index] = attacks; // no collision, store attack set
} else {
// collision
if ( table[index] != attacks ) {
return false; // magic does not work
}
}
occ = (occ - occUniverse) & occUniverse; // next occupancy
} while ( occ );
return true;
}
some more links:
https://chessprogramming.wikispaces.com ... s+of+a+Set
https://chessprogramming.wikispaces.com ... for+Magics
https://chessprogramming.wikispaces.com ... ics+so+far
And yes, the order of bits of the masked occupancy is not necessarily preserved in the index. Most often, specially with denser indices, there is no one:one mapping at all, but only a surjective mapping of M occupancies to N attack-sets, where the cardinality M is (much) greater than N.
Re: Occupancy Variations
Posted: Sat Jan 26, 2013 11:36 am
by Gerd Isenberg
Nice reading and insight in congruent modulo arithmetic, but not particular fast approach for each line as the author claim.
https://chessprogramming.wikispaces.com ... +Bitboards
Re: Occupancy Variations
Posted: Sun Jan 27, 2013 3:18 am
by chinanzio
yea !, nice reading, little fancy XD