Magic bitboards, Java

[Rein Halbersma]

index = (occupancy & mask) & magic >> (32-9)

index = (occupancy & mask) * magic >> (32-9)


ok, I also second to extend the 15-minute edit window

[Gerd Isenberg]

Hi Gerd,

OK, it seems that I can't add an Excel-attachment on this forum?

Here's a 32-bit example where the LSB is bit 0 and the MSB is bit 31. I wish to index a bitmask with the following bits: 8,9,10,16,17,18,24,25 and 26. This means I AND my occupancy bitboard with the configuration 0x7070700 = 2^8 + ... + 2^26. I use the following magic: 0x82001 = 2^19 + 2^13 + 2^0, so the magic has only 3 active bits.

index = (occupancy & mask) & magic >> (32-9)

You can check that with mask = 0x7070700 and magic = 0x82001 this gives a 9-bit index. To check this with a multiplication table:

Code: Select all

       8   9  10  16 17 18 24 25 26
 0   -15 -14 -13  -7 -6 -5  1  2  3 
13    -2  -1   0   6  7  8 14 15 16
19     4   5   6  12 13 14 20 21 22

The above table shows the active bits in the mask (columns) and in the magic (rows). The entries in the table are the active bits in the index (entry_ij = i+j-(32-9)). Only bits 0...8 are used in the actual index.

Rowwise, notice that bit 0 in the magic fills bits 1,2,3 in the index, bit 13 in the magic fills bits 0,6,7,8 and bit 19 in the magic fills bits 4,5,6. Columnwise, notice that all bits in the mask almost uniquely fill a bit in the index.

There is only a single overlap: bit 6 in the index is filled by bits 0 and 13 in the magic when bits 16 and 10, respectively, are set in the mask. Fortunately, bit 10 in the mask is also uniquely filling bit 0 in the index. This means that the carry of bit 6 in the index can freely propagate to bits 7 and 8 since bit 0 in the index marks whether there has been a carry forward in the index.

It's reasoning like this that I would like to generalize when generating magics for arbitrary bitmasks.

Rein

Hi Rein,

thanks, that becomes much clearer now - may be I should work a bit more with Excel

Despite the fascination of this practical math application and the "research" - I am actually a bit tired and less motivated on magics.
I don't really believe in major space improvements by factors. With your skills you may someday find a mathematical prove of a minimal table and disabuse me.

I won't use it anyway in my current 64-bit (128-bit?) program, since it is fill-based with disjoint directions, where I rarely used raywise kindergarten, or actually thanks to Aleks the hyperbola-quintessence described elsewhere.

Cheers,
Gerd

[Rein Halbersma]

Here's a 32-bit example where the LSB is bit 0 and the MSB is bit 31. I wish to index a bitmask with the following bits: 8,9,10,16,17,18,24,25 and 26. This means I AND my occupancy bitboard with the configuration 0x7070700 = 2^8 + ... + 2^26. I use the following magic: 0x82001 = 2^19 + 2^13 + 2^0, so the magic has only 3 active bits.

index = (occupancy & mask) & magic >> (32-9)

You can check that with mask = 0x7070700 and magic = 0x82001 this gives a 9-bit index. To check this with a multiplication table:

Code: Select all

       8   9  10  16 17 18 24 25 26
 0   -15 -14 -13  -7 -6 -5  1  2  3 
13    -2  -1   0   6  7  8 14 15 16
19     4   5   6  12 13 14 20 21 22

The above table shows the active bits in the mask (columns) and in the magic (rows). The entries in the table are the active bits in the index (entry_ij = i+j-(32-9)). Only bits 0...8 are used in the actual index.

Despite the fascination of this practical math application and the "research" - I am actually a bit tired and less motivated on magics.
I don't really believe in major space improvements by factors. With your skills you may someday find a mathematical prove of a minimal table and disabuse me.

Hi Gerd,

OK, here's a new mathematical insight that might revive some of your intestest in magic The above multiplication table implies a set of linear equations that map the bitmask to the index. This is equivalent to the following matrix multiplication

index = A * bitmask

where index and bitmask are 9-dimensional bitvectors and where A is equal to the following 9x9 matrix with binary coefficients

Code: Select all

0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0

Notice that the ij-entry of matrix A is equal to 1 if, according to the multiplication table, the i-th bit in the bitmask sets the j-th bit in the index. Thus, e.g., the 5th bit in the 1st row is set to 1 because the 1st bit in the bitmask (bit 8 in the occupancy board) is mapped to the 5th bit in the index (i.e. 4, since we start counting from 0)

All that is needed for the magic to be valid (i.e. that every configuration of the bitmask is mapped to precisely one index value) is that this 9x9 matrix is invertible over the binary numbers, i.e. det(A) = 1 mod 2. Putting this matrix into Excel shows that det(A) = -1 = 1 mod 2. So indeed, this is a valid magic.

Corollary: there is no need to test every 2^n configuration of the bitmask, just computing a nxn matrix determinant suffices. This should speed up the magic generation by several orders of magnitude.

Btw, I am mostly interested in magic because of the evaluation function, not for the move generator. Indexing arbitrary sparse bitmasks will speed up my eval code a lot more than the move generator.

Rein

[Rein Halbersma]

[
index = A * bitmask

where index and bitmask are 9-dimensional bitvectors and where A is equal to the following 9x9 matrix with binary coefficients

Code: Select all

0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0

Notice that the ij-entry of matrix A is equal to 1 if, according to the multiplication table, the i-th bit in the bitmask sets the j-th bit in the index. Thus, e.g., the 5th bit in the 1st row is set to 1 because the 1st bit in the bitmask (bit 8 in the occupancy board) is mapped to the 5th bit in the index (i.e. 4, since we start counting from 0)

All that is needed for the magic to be valid (i.e. that every configuration of the bitmask is mapped to precisely one index value) is that this 9x9 matrix is invertible over the binary numbers, i.e. det(A) = 1 mod 2. Putting this matrix into Excel shows that det(A) = -1 = 1 mod 2. So indeed, this is a valid magic.

Corollary: there is no need to test every 2^n configuration of the bitmask, just computing a nxn matrix determinant suffices. This should speed up the magic generation by several orders of magnitude.

Corollary #2: there is also no need to test the carry effects of overlapping bits in the magic multiplication since this is taken care of by the determinant computation!

[Gerd Isenberg]

index = A * bitmask

where index and bitmask are 9-dimensional bitvectors and where A is equal to the following 9x9 matrix with binary coefficients

Code: Select all

0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0

Notice that the ij-entry of matrix A is equal to 1 if, according to the multiplication table, the i-th bit in the bitmask sets the j-th bit in the index. Thus, e.g., the 5th bit in the 1st row is set to 1 because the 1st bit in the bitmask (bit 8 in the occupancy board) is mapped to the 5th bit in the index (i.e. 4, since we start counting from 0)

All that is needed for the magic to be valid (i.e. that every configuration of the bitmask is mapped to precisely one index value) is that this 9x9 matrix is invertible over the binary numbers, i.e. det(A) = 1 mod 2. Putting this matrix into Excel shows that det(A) = -1 = 1 mod 2. So indeed, this is a valid magic.

Corollary: there is no need to test every 2^n configuration of the bitmask, just computing a nxn matrix determinant suffices. This should speed up the magic generation by several orders of magnitude.

Corollary #2: there is also no need to test the carry effects of overlapping bits in the magic multiplication since this is taken care of by the determinant computation!

Hi Rein,

those matrices aka bitboards are much more familar to me.
At least some min-max-bit considerations are already tried by Pradu and others iirc.
Using some recombinatorical set traversals like all sub-sets of a set or snoob.

Code: Select all

void enumerateAllSubsets(SetType_t d) {
  SetType_t n = 0;
  do {
    doSomeThingWithSubset(n);
    n = (n - d) & d;
  } while ( n );
}


const u64 deBruijn = 0x03f79d71b4cb0a89;
const unsigned int deBruijnLookup[64] =
{
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6,
};

// get next greater value with same number of one bits
u64 snoob (u64 x) {
    u64 smallest, ripple, ones;
    smallest = x & -(i64)x;
    ripple   = x + smallest;
    ones     = x ^ ripple;
    ones     = (ones >> 2) >> deBruijnLookup[(smallest*deBruijn) >> 58];
    return ripple | ones;
} 

// get next greater subset of set with same number of one bits
u64 snoob (u64 sub, u64 set) {
   u64 tmp=sub-1, rip=set&(tmp+(-(i64)sub&sub)-set);
   for(sub=(tmp&sub)^rip;sub&=sub-1;rip^=tmp,set^=tmp)
       tmp=set&-(i64)set;
   return rip;
} 

Gerd

[Pradu]

[
index = A * bitmask

where index and bitmask are 9-dimensional bitvectors and where A is equal to the following 9x9 matrix with binary coefficients

Code: Select all

0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 
1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 0

I don't understand clearly what each variable means or how they are aranged. Could you explain it real slow (aka how you get your linear system of equations in non-matrix form first)? Also how is this going to help find optimal magics? If "bitmask" (key) and index are of the same size, then the magic will be sub-optimal. Is it possible to have the key and the index of different sizes? How would it handle carries and allowed collisions?

Corollary #2: there is also no need to test the carry effects of overlapping bits in the magic multiplication since this is taken care of by the determinant computation!

[Rein Halbersma]

Hi Pradu,

I've rewritten my previous posts a bit with some more clarification.

Here's a 32-bit example where the LSB is bit 0 and the MSB is bit 31 (all other counting also starts at 0!) I wish to index 9 scattered bits in my occupancy board, namely bits 8,9,10,16,17,18,24,25 and 26. This means I AND my occupancy bitboard with the configuration 0x7070700 = 2^26+ ... + 2^8. I then use the following magic: 0x82001 = 2^19 + 2^13 + 2^0, so the magic has only 3 active bits. You can check by brute force that with mask = 0x7070700 and magic = 0x82001 this gives a 9-bit index.

index = (occupancy & mask) * magic >> (32-9)

Noting that 2^a * 2^b = 2^(a+b), and that 2^a >> b = 2^(a-b), we can construct a multiplication table that shows the active bits in the magic (rows, label i=0,13,19) and in the mask (columns, label j=8,...,26). The entries in the table are the active bits in the index (multiplicationtable_ij = i+j-(32-9)). Only bits 0...8 are used in the actual index.

Code: Select all

  |     8   9  10  16 17 18 24 25 26
__|____________________________________
 0|                          1  2  3 
13|             0   6  7  8 
19|     4   5   6  

The above multiplication table implies a set of linear equations that map the 9 bits in the bitmask to 9 bits in the index (the notation i->j means that the i-th bit in the bitmask activates the j-th bit in the index):

8 -> 4
9 -> 5
10 -> 0 + 6
16 -> 6
17 -> 7
18 -> 8
24 -> 1
25 -> 2
26 -> 3

This is equivalent to the following matrix multiplication

index = A * bitmask

where we have 9-dimensional bitvectors for the index (representing bits 0...8) and bitmask (representing bits 8,...,26 in the occupancy board), and where A is equal a 9x9 matrix with binary coefficients. The ij-entry of matrix A is equal to 1 if, according to the multiplication table, the i-th bit in the bitmask sets the j-th bit in the index (i.e. A_ij = 1 if and only if i->j). Thus, e.g., the 4th bit in the 0th row is set to 1 because the 0th bit in the bitmask (bit 8 of the occupancy board) is mapped to the 4th bit in the index ("8->4"). Similarly, the 0th and 6th bit in the 2nd row are set to 1 since the 2nd bit in the bitmask (bit 10 of the occupancy board) is mapped to the 0th and 6th bit of the index ("10 -> 0+6").

Code: Select all

    0 0 0 0 1 0 0 0 0
    0 0 0 0 0 1 0 0 0 
    1 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 
A = 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 0 1 
    0 1 0 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 
    0 0 0 1 0 0 0 0 0

If and only if the magic induces an invertible linear mapping from the bitmask to the index, do we have a true "magic". Algebraically, this means that the 9x9 matrix A has to be invertible over the binary numbers, i.e. det(A) = 1 mod 2. Putting this matrix into Excel shows that det(A) = -1 = 1 mod 2. So indeed, this is a true magic.

Corollary #1: there is no need to test all 2^n configurations of the bitmask, just computing an nxn matrix determinant suffices. Why? Because the matrix A is invertible, meaning that all 2^n distinct configurations of (occupancy & bitmask) are mapped to one of the 2^n distinct indices under magic multiplication and right-shifting by 23.

Corollary #2: the carry effects are taken care of by this determinant test. Why? Because the matrix A contains the information that both bit 10 and bit 16 in the occupancy board activate the 6th bit in the index, and the fact that det(A)=1 mod 2 proves that this does not effect the indexation.

Does this clarify my approach a bit? (I would like to call this "Matrix Magic": there is no spoon )

Now your question about collision groups is a bit more tricky and I will have to think about it. But basically, everything works the same, except that the matrix will no longer be a square matrix and will not be invertible. The test in this case is if the linear mapping is surjective, i.e. if different values of the index come from different configurations of (occupancy & bitmask). The problem is checking if all instances of a collision group map to the same index.

Rein

[Pradu]

Hi Pradu,

I've rewritten my previous posts a bit with some more clarification.

Here's a 32-bit example where the LSB is bit 0 and the MSB is bit 31 (all other counting also starts at 0!) I wish to index 9 scattered bits in my occupancy board, namely bits 8,9,10,16,17,18,24,25 and 26. This means I AND my occupancy bitboard with the configuration 0x7070700 = 2^26+ ... + 2^8. I then use the following magic: 0x82001 = 2^19 + 2^13 + 2^0, so the magic has only 3 active bits. You can check by brute force that with mask = 0x7070700 and magic = 0x82001 this gives a 9-bit index.

index = (occupancy & mask) * magic >> (32-9)

Noting that 2^a * 2^b = 2^(a+b), and that 2^a >> b = 2^(a-b), we can construct a multiplication table that shows the active bits in the magic (rows, label i=0,13,19) and in the mask (columns, label j=8,...,26). The entries in the table are the active bits in the index (multiplicationtable_ij = i+j-(32-9)). Only bits 0...8 are used in the actual index.

Code: Select all

  |     8   9  10  16 17 18 24 25 26
__|____________________________________
 0|                          1  2  3 
13|             0   6  7  8 
19|     4   5   6  

The above multiplication table implies a set of linear equations that map the 9 bits in the bitmask to 9 bits in the index (the notation i->j means that the i-th bit in the bitmask activates the j-th bit in the index):

8 -> 4
9 -> 5
10 -> 0 + 6
16 -> 6
17 -> 7
18 -> 8
24 -> 1
25 -> 2
26 -> 3

Ok, I think I understand what it's doing now. Basically you are trying to answer how does this bit affect the bit in the upper index bits. For me, I believe this concept is expressed in the form of "index mappings".

This is equivalent to the following matrix multiplication

index = A * bitmask

Ah, here comes the new idea.

where we have 9-dimensional bitvectors for the index (representing bits 0...8) and bitmask (representing bits 8,...,26 in the occupancy board), and where A is equal a 9x9 matrix with binary coefficients. The ij-entry of matrix A is equal to 1 if, according to the multiplication table, the i-th bit in the bitmask sets the j-th bit in the index (i.e. A_ij = 1 if and only if i->j). Thus, e.g., the 4th bit in the 0th row is set to 1 because the 0th bit in the bitmask (bit 8 of the occupancy board) is mapped to the 4th bit in the index ("8->4"). Similarly, the 0th and 6th bit in the 2nd row are set to 1 since the 2nd bit in the bitmask (bit 10 of the occupancy board) is mapped to the 0th and 6th bit of the index ("10 -> 0+6").

Code: Select all

    0 0 0 0 1 0 0 0 0
    0 0 0 0 0 1 0 0 0 
    1 0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 
A = 0 0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 0 1 
    0 1 0 0 0 0 0 0 0
    0 0 1 0 0 0 0 0 0 
    0 0 0 1 0 0 0 0 0

If and only if the magic induces an invertible linear mapping from the bitmask to the index, do we have a true "magic". Algebraically, this means that the 9x9 matrix A has to be invertible over the binary numbers, i.e. det(A) = 1 mod 2. Putting this matrix into Excel shows that det(A) = -1 = 1 mod 2. So indeed, this is a true magic.

Corollary #1: there is no need to test all 2^n configurations of the bitmask, just computing an nxn matrix determinant suffices. Why? Because the matrix A is invertible, meaning that all 2^n distinct configurations of (occupancy & bitmask) are mapped to one of the 2^n distinct indices under magic multiplication and right-shifting by 23.

Corollary #2: the carry effects are taken care of by this determinant test. Why? Because the matrix A contains the information that both bit 10 and bit 16 in the occupancy board activate the 6th bit in the index, and the fact that det(A)=1 mod 2 proves that this does not effect the indexation.

Does this clarify my approach a bit? (I would like to call this "Matrix Magic": there is no spoon )

Yes I understand it now.

Now your question about collision groups is a bit more tricky and I will have to think about it. But basically, everything works the same, except that the matrix will no longer be a square matrix and will not be invertible. The test in this case is if the linear mapping is surjective, i.e. if different values of the index come from different configurations of (occupancy & bitmask). The problem is checking if all instances of a collision group map to the same index.

Not much of a linear algebra guy here, but how will the surjective test be done? Hopefully it will be faster than the way I check for unwanted collisions. Also, I guess this approach naturally handles checking whether not a bit will produce enough influence to propogate it up to the index bits as well. Soutions to this elegant approach will also need the same questions answered -- ie which order to guess bits to update the matrix. So people who are working on that won't have to give up on it.

Rein

[Rein Halbersma]

Code: Select all

  |     8   9  10  16 17 18 24 25 26
__|____________________________________
 0|                          1  2  3 
13|             0   6  7  8 
19|     4   5   6  

Not much of a linear algebra guy here, but how will the surjective test be done? Hopefully it will be cheaper than guessing bits and checking for unwanted collisions. However, I guess this approach naturally handles checking whether not a bit will produce enough influence to propogate it up to the index bits as well. Soutions to this elegant approach will also need the same questions answered -- ie which order to guess bits to update the matrix. So people who are working on that won't have to give up on it.

Yes, you are right: Matrix Magic is no solution to the guessing problem. All it does is to quickly test (by the determinant test, rather than by enumerating all possible inputs) a candidate magic constant for a given bitmask.

And yes, the carry bit propagation is taken care of automatically. Harmless carry bits appear as lower diagonal entries in a suitable transform of the matrix A (the fast algorithms for determinants first transform A = LU with L lower diagonal and U upper diagonal).

What I would try as a magic generation algorithm (this is how I constructed the above magic by hand) is to set as few bits as possible in the magic (starting from the LSB) that fill every column at least once in the multiplication table, with as little overlap as possible (i.e. with the least amount of carry bits). Then translate the multiplication table into a matrix and testing whether the determinant is non-zero (mod 2, i.e. odd-valued)

[Gerd Isenberg]

those matrices aka bitboards are much more familar to me.

oups 9x9 matrices - ok not familar with
Need some more time to refresh my linear algebra knowledge a bit...