Occupancy Variations

Code, algorithms, languages, construction...
Post Reply
CDaley11
Posts: 42
Joined: Thu Jan 10, 2013 6:23 am
Real Name: Christian Daley

Occupancy Variations

Post by CDaley11 » Fri Jan 25, 2013 2:22 am

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
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Occupancy Variations

Post by hyatt » Fri Jan 25, 2013 7:07 pm

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. :)

CDaley11
Posts: 42
Joined: Thu Jan 10, 2013 6:23 am
Real Name: Christian Daley

Re: Occupancy Variations

Post by CDaley11 » Sat Jan 26, 2013 12:47 am

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
Posts: 616
Joined: Thu May 19, 2011 1:35 am

Re: Occupancy Variations

Post by User923005 » Sat Jan 26, 2013 3:55 am


Gerd Isenberg
Posts: 37
Joined: Wed Jul 07, 2010 11:11 pm
Real Name: Gerd Isenberg

Re: Occupancy Variations

Post by Gerd Isenberg » Sat Jan 26, 2013 11:33 am

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.
Last edited by Gerd Isenberg on Sat Jan 26, 2013 11:39 am, edited 1 time in total.

Gerd Isenberg
Posts: 37
Joined: Wed Jul 07, 2010 11:11 pm
Real Name: Gerd Isenberg

Re: Occupancy Variations

Post by Gerd Isenberg » Sat Jan 26, 2013 11:36 am

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
Posts: 2
Joined: Sun Jan 27, 2013 3:11 am
Real Name: chino

Re: Occupancy Variations

Post by chinanzio » Sun Jan 27, 2013 3:18 am

yea !, nice reading, little fancy XD

Post Reply