Occupancy Variations

[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?

[hyatt]

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.

[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?

[User923005]

This is how magic bitboards work:
http://www.pradu.us/old/Nov27_2008/Buzz ... boards.pdf

Another fast approach:
http://www.dcs.bbk.ac.uk/~mark/download ... _final.pdf

[Gerd Isenberg]

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.

[Gerd Isenberg]

Another fast approach:
http://www.dcs.bbk.ac.uk/~mark/download ... _final.pdf

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

[chinanzio]

yea !, nice reading, little fancy XD