How to reduce the "bits" used in a magic number ca

[Zach Wegner]

Your "c = (p1 & p2) | ((p1 ^ p2) & rnd64());" does not do what you say it does. It only preserves bits in common =1. It ignores bits in common =0.

Actually, it does work.

I agree with your second point though. Maybe flipping more bits might be better too.

[rjgibert]

In my 1st point, I see I was superficial in my assessment. The way you had it was perfect. Sorry about that.

[Gerd Isenberg]

Gerd

A MagicMix routine - I like it.

Thank you for taking the time to compare this with Kindergarten. I look forward to seeing your results.

Grant

Grant

After some closer look, the MagicMix seems to disappear.
You use six bit indices in a 0..63 range for both rankAddress and fileAddress - due to the mask by 0x3f or shift right by 58 - for all ranks and files. Since each square takes the same space, you can use a two-dimensional [8][64] array rather than an indirection via pointer array + address. Thus, instead of 8 magic numbers, a constant flip-factor is appropriate, to map relevant file 0 bits (a2..a7) to the upper six bits. That takes 4.5K lookups. How do you get the 2.5K, you mentioned?

After some re-scheduling, your initial routine may look like that:

Code: Select all

U64 fileLookUp[8][64]; // 4   KB
U8  rankLookUp[8][64]; // 0.5 KB

U64 rookAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rkx8 = sq & 56; // rank * 8
   unsigned int rank = sq >> 3;

   rankAddress = (int)((occ >> rkx8) >> 1) & 0x3F;
   attacks  = rankLookUp[file][rankAddress];
   attacks<<= rkx8;

   occ = &#40;int&#41;(&#40;occ >> file&#41; & 0x0001010101010100&#41;;
   fileAddress = &#40;occ * 0x0080402010080400&#41; >> 58;
   attacks |= fileLookUp&#91;rank&#93;&#91;fileAddress&#93; << file;

   return attacks;
&#125; 

This is exactly the kindergarten file-getter ...

Code: Select all

U64 aFileAttacks [8][64];  // 4 KByte
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rank = sq >> 3;

   occ =  0x0101010101010101 & (occ   >> file);
   occ = (0x0080402010080400 *  occ ) >> 58;
   return aFileAttacksx&#91;rank&#93;&#91;occ&#93;    << file;
&#125; 

... combined with Attacks on all Ranks, which is optimized by an one-dimensional byte-array to safe the shift right one.

Code: Select all

BYTE arrFirstRankAttacks64x8[64*8]; // 512 Bytes = 1/2KByte

U64 rankAttacks(U64 occ, enumSuare sq) {
   unsigned int file = sq &  7;
   unsigned int rkx8 = sq & 56; // rank * 8

   occ = (occ >> rkx8) & 2*63;
   U64 attacks = arrFirstRankAttacks64x8[4*occ + file];
   return attacks << rkx8;
&#125;

Did I miss something?

Gerd

[Gerd Isenberg]

Did I miss something?

Guess you mean this one for the filewise MagicMix?

Code: Select all

U64 aFileAttacks[8][32];  // 2KByte
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7;
   unsigned int rank = sq >> 3;

   occ =  0x0001010101010100 &  (occ >> file);
   occ = (rookMagic[rank] *  occ )   >> 59; // five bit index
   return aFileAttacks&#91;rank&#93;&#91;occ&#93;    << file;
&#125;

That makes sense.

[grant]

Gerd

For the rank, no magic numbers are required as the lookup table is already very small (512 bytes).

Code: Select all

U64 rankAttacks(U64 occ, enumSuare sq) { 
   unsigned int file = sq &  7; 
   unsigned int rkx8 = sq & 56; // rank * 8 

   occ = (occ >> rkx8) & 2*63; 
   U64 attacks = arrFirstRankAttacks64x8[4*occ + file]; 
   return attacks << rkx8; 
&#125;

For the file, the lookup table can be made smaller still (1536 bytes) as there are at least four 4-bit magic numbers. I expect this would require the use of a pointer. The shift is in the magic.

Code: Select all

U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7; 
   unsigned int rank = sq >> 3; 

   occ =  0x0001010101010100 &  (occ >> file);
   occ = (rookMagic[rank] * occ) >> (rookMagic[rank] >> 58);  // four&five bit index 
   return *&#40;aFileAttacks&#91;rank&#93; + occ&#41; << file;
&#125; 

//A1    0	  EE404B349599FF88     5-bit
//A2    1	  F2FF5D69D4E3E7D6     4-bit
//A3    2	  F2FF594E14D8801C     4-bit
//A4    3	  EC87CB0D961EC43A     5-bit
//A5    4	  ED6EDFBE467977D5     5-bit
//A6    5	  F2808817CAD6FF0C     4-bit
//A7    6	  F024691A3227FF42     4-bit
//A8    7	  EFFFA39DB01B23A3     5-bit

I make it just 2Kb in total.

Grant

[Gerd Isenberg]

Gerd

For the rank, no magic numbers are required as the lookup table is already very small (512 bytes).

Yes, I was aware of the rank-attacks.

Gerd

Code: Select all

U64 rankAttacks(U64 occ, enumSuare sq) { 
   unsigned int file = sq &  7; 
   unsigned int rkx8 = sq & 56; // rank * 8 

   occ = (occ >> rkx8) & 2*63; 
   U64 attacks = arrFirstRankAttacks64x8[4*occ + file]; 
   return attacks << rkx8; 
&#125;

For the file, the lookup table can be made smaller still (1536 bytes) as there are at least four 4-bit magic numbers. I expect this would require the use of a pointer. The shift is in the magic.

Code: Select all

U64 fileAttacks(U64 occ, enumSquare sq) {
   unsigned int file = sq &  7; 
   unsigned int rank = sq >> 3; 

   occ =  0x0001010101010100 &  (occ >> file);
   occ = (rookMagic[rank] * occ) >> (rookMagic[rank] >> 58);  // four&five bit index 
   return *&#40;aFileAttacks&#91;rank&#93; + occ&#41; << file;
&#125; 

//A1    0	  EE404B349599FF88     5-bit
//A2    1	  F2FF5D69D4E3E7D6     4-bit
//A3    2	  F2FF594E14D8801C     4-bit
//A4    3	  EC87CB0D961EC43A     5-bit
//A5    4	  ED6EDFBE467977D5     5-bit
//A6    5	  F2808817CAD6FF0C     4-bit
//A7    6	  F024691A3227FF42     4-bit
//A8    7	  EFFFA39DB01B23A3     5-bit

I make it just 2Kb in total.
Grant

I see. This is really a nice didactical example, to understand how magic bitboards work in a nutshell aka with one file - to dense the initial six-bit occupied index to 4 or 5 bits to address the {7,6,10,12,12,10,6,7} distinct attack sets on that file. Whether it is worth for practical purpose is another question, since we are already in a memory range far less L1 size of recent processors, where one additional lookup of a magic/shift and additional indirection of a pointer likely don't pays off. As always - one has to try it in a concrete chess program.

Gerd

[Rein Halbersma]

I will most certainly update it as soon as I've finished the new implementation and will also try to make it more rigorous and easier to read. I will also post the sources to the magic-generator as well (I didn't post the sources for my old one because it was really hacked up and poorly documented).

How the above improvements fit in the existing algorithm is as follows:

1. Generate input keys (occupancies) and give each input key a group number so that two input keys with the same group number have the same set of moves.
2. Pick the number of bits in the index that you'd like to try to generate a magic for.
3. A variable magic can be represented by two 64-bit integers. All unguessed bits are '1' in u and all guessed bits are '0' in u. All unguessed bits are '0' in g and all guessed bits are either '0' or '1' in g depending on the guessed value.
4. First, all upper-redundant bits in the variable magic are set to 0 by u&=(U64FULL>>FirstOne(preMask[sq]))
5. Lets consider using a guessing order where you always guess 0 first and 1 next and you guess bits from bit 0 to bit 63 and lets start a recursive bit-guessing search using this guessing order:
   1. First you perform a 1-ply search of guessing bits to see if some bits can be determined upfront. When you find out that you can determine the value of a bit you set its value, you can repeat the 1-ply search until no bits can be determined. This is where the new improvements (the one using difference keys that tries to determine if some bad collisions are unpreventable regardless of what bits you guess) come in. After you guess a bit you can check to see if you can determine upfront if the bit guessed will lead to an unpreventable bad collision. If both values (0 and 1) will cause an unpreventable collision you can return from this node (no value of this bit can help prevent a bad collision). If only 0 causes an unpreventable collision, then the value of the bit must be guessed as 1. If only 1 causes an unpreventable collision, then the value of the bit must be guessed as 0.
   2. After the 1-ply search you can guess the next bit which is determined by your guessing order.

The recursive search will eventually guess all the bits without unwanted collisions and it will produce a magic number. Then you can return from the leaf-node and continue the search to find another magic number. And in this process you can go through them all and pick the one that produces the smallest index for the given number of bits. If there's no magic number for the number of bits that you've chosen then the recursive search will never get to a leaf node and so it'll never produce a magic number.

Looking for all possible magics for a given pattern has an unrestricted search tree of 2^64 = 1.8*10^19 nodes. This is equivalent in size to the search tree of the game of checkers. Now of course, checkers has been solved, by basically three search improvements: alpha-beta cutoffs in combination with hashtables and endgame databases.

Since the search tree for magics is already ordered, there are no transpositions and hashtables are of no use. The method to identify unpreventable collissions by difference keys is the equivalent of an alpha-beta cutoff. It should also possible to combine this with the equivalent of endgame databases. Analogously to pre-computing the outcome of all endgames with a few pieces on the board, one could pre-compute the unpreventability of collissions for all magics with a few bits set to 1.

E.g. a 2-bit database is a table of all 64*63/2 pairs of bits that are to be guessed in the magic. Each pair can take on 2^2 values. In all, there are about 8K entries in the table. Each entry states whether the values of a pair of bits in a magic lead to an unpreventable collission. Similarly, a 3-bit database has 64*63*62*/6 triplets of bits, with 2^3 values for each triplet. All in all about 33K values. These tables will have to be computed once for every pattern before searching for a magic.

Step 5.a) of Pradu's algorithm can then be extended by first running over the magic guessed so far to see whether there is any 2-bit or 3-bit pattern present in the set of guessed bits that will always lead to a collission. If so, then terminate this node. If not, proceed by guessing the next bit, see if this in isolation will lead to an unpreventable collission etc.

If the percentage of disallowed pairs or triplets of bits is large, and the cost of searching for such patterns is low, then a considerable speedup might be gained.

Rein

[Pradu]

Since the search tree for magics is already ordered, there are no transpositions and hashtables are of no use. The method to identify unpreventable collissions by difference keys is the equivalent of an alpha-beta cutoff. It should also possible to combine this with the equivalent of endgame databases. Analogously to pre-computing the outcome of all endgames with a few pieces on the board, one could pre-compute the unpreventability of collissions for all magics with a few bits set to 1.

I found out that the name of the algorithm we are using is called Backtracking. But I found a mistake in the difference key approach. It seems intuitively correct but it isn't mathematically correct. There are exceptions where difference keys will say that the collision is unpreventable when it is in fact preventable. I found the error when I tried to compare all possible magics for bishops on D8 to the ones generated by the algorithm using the new difference key metric to determine whether the collision is preventable or not and found out that they didn't generate them all. I've been working on another metric that's mathematically (not just intuitively) correct to try to check if a collision is unpreventable. Here are my efforts so far:

http://pradu.us/research/magics/uc.pdf

E.g. a 2-bit database is a table of all 64*63/2 pairs of bits that are to be guessed in the magic. Each pair can take on 2^2 values. In all, there are about 8K entries in the table. Each entry states whether the values of a pair of bits in a magic lead to an unpreventable collission. Similarly, a 3-bit database has 64*63*62*/6 triplets of bits, with 2^3 values for each triplet. All in all about 33K values. These tables will have to be computed once for every pattern before searching for a magic.

Interesting, I haven't considered tablebases before to speed up the search. Your idea might help a lot.

Rein