magic search

[Daniel Shawul]

I am trying to find magic number for rook on a1 (0) with a shift of 53 (one less bit than usual). I already spent 24 hours with 16 processors working on "different" random numbers and nothing showed up yet ... I am beginning to doubt it ever will. Processors maybe working on same random numbers since the only precaution i took is to seed them with different numbers (processor rank 1 to 16). I am using code posted by Tord on chess programming wiki and modified it a bit. First 12 hours were spent with no changes but 11 bits for rook on a1. Then I switched to a different RNG ( 64bit mersenne twister with a huge period) and took more bits (removed one & from the few_bits func)... nothing so far! I think that the number of bits (cardinality) of the magic number matters more than anything else. If i took the full random number and look for a magic on a1 with a shift of 52, it never finds it but it takes only a second otherwise. So the question is how to determine the cardinality of the magic number for a given shift. Even random guess will do.

[Gerd Isenberg]

I am trying to find magic number for rook on a1 (0) with a shift of 53 (one less bit than usual). I already spent 24 hours with 16 processors working on "different" random numbers and nothing showed up yet ... I am beginning to doubt it ever will. Processors maybe working on same random numbers since the only precaution i took is to seed them with different numbers (processor rank 1 to 16). I am using code posted by Tord on chess programming wiki and modified it a bit. First 12 hours were spent with no changes but 11 bits for rook on a1. Then I switched to a different RNG ( 64bit mersenne twister with a huge period) and took more bits (removed one & from the few_bits func)... nothing so far! I think that the number of bits (cardinality) of the magic number matters more than anything else. If i took the full random number and look for a magic on a1 with a shift of 52, it never finds it but it takes only a second otherwise. So the question is how to determine the cardinality of the magic number for a given shift. Even random guess will do.

The 12 bits {1,2,3,4,5,6} and {8,16,24,32,40,48} need to squeezed to 53..63 (instead of 52..63).

Code: Select all

. . . . . . . .    1 1 1 1 1 1 1 1
1 . . . . . . .    . . . . . 1 1 1
1 . . . . . . .    . . . . . . . .
1 . . . . . . . => . . . . . . . .
1 . . . . . . .    . . . . . . . .
1 . . . . . . .    . . . . . . . .
1 . . . . . . .    . . . . . . . .
. 1 1 1 1 1 1 .    . . . . . . . .

The minimal population count of the magic factor seems six, one bit for 1..8, one further bit for the five remaining file squares. IIRR I already tried snoob with all six bit factors, without success.

It is amazing that the 49 disjoint attacksets for a rook on a1 (0) and h1 (7) requires a table 4096 entries, while the other edge squares (56, 63) with relevant occupancies already inside the upper result bits have enough constructive collisions for 11 bit indices with high population factors like 0xEBFFFFB9FF9FC526 or 0x7645FFFECBFEA79E.

[Daniel Shawul]

The minimal population count of the magic factor seems six, one bit for 1..8, one further bit for the five remaining file squares. IIRR I already tried snoob with all six bit factors, without success.

If i understand you correct, since bits 1--8 are close one multiply with a single bit is enough and separate bits for the bits on file A , above rank 3. That makes sense. I will switch to snoobing 7,8,9 bits etc.. Trying denser magics randomly seems hopeless so far.

It is amazing that the 49 disjoint attacksets for a rook on a1 (0) and h1 (7) requires a table 4096 entries, while the other edge squares (56, 63) with relevant occupancies already inside the upper result bits have enough constructive collisions for 11 bit indices with high population factors like 0xEBFFFFB9FF9FC526 or 0x7645FFFECBFEA79

That is also what got me started there must be something better than one-to-one mapping for a1. If additional operations other than one multiply were allowed (as in kindergarten bb), better compression could be achieved.

p.s : I see 10 bit indeces for squares (56,53) on chess wiki

[Daniel Shawul]

Do you know a parallel version of the below code with good load balancing ?

Code: Select all

   const int n = 14; //cardinality of magic
	uint64 magic, y, first = (1 << n) - 1;
	for (magic = first; (y = snoob(magic)) > magic; magic = y) {
                /*......*/
   }

[Daniel Shawul]

Oh It is like indexing of n similar pieces for bitbases, which I already have code for.
Total positions is B(64,n) then i divide that by number of processors (NP = 16 for my case) => x = B(64,n) / NP.
Then all I need is to set the start point for each processor at 0,x,2x,3x,...(NP - 1)*x indexed Bitboard.
That should result in same number of magics for each... But still some processors will probably finish quick
if most of the magics tend to give few bits in the upper byte after multiply with pre_mask, which I am afraid is the case for the smaller magics.

[Gerd Isenberg]

Do you know a parallel version of the below code with good load balancing ?

Code: Select all

   const int n = 14; //cardinality of magic
	uint64 magic, y, first = (1 << n) - 1;
	for (magic = first; (y = snoob(magic)) > magic; magic = y) {
                /*......*/
   }

You may use snoob from a set, so that different processors try disjoint sets:

Code: Select all

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

To use for instance the union of 0x0200000000000040 as outer bits and snoob N inner bits from 0x01FFFFFFFFFFFF80 with first subset 0x0F80 (5 bits), 0x1F80 ...

I fear, since so many people already searched for magics there are no 11-bit tables for rook squares 0, 7.

[Edmund]

Two years ago there was a long thread on CCC about how to find smaller magic factors: link

In it I posted my solution of how to find magics systematically without having to rely on magic numbers. It is based on the fact that only certain bits of the magic factor multiplied with a certain occupacy change the index number. So I split the calculation in parts. eg. in a first step I optimized the magic factor of the row occupacy. The row for square 0 has the very low bits set in the occupacy. To have an effect on the index, only some very high bits of the magic factor are relevant. These don't overlap with the relevant bits for most of the file occupacy bits. In other words these can be optimized seperatly. All in all it is now possible to analyze the complete subset of a certain mask of relevant bits in a reasonable time.

[Daniel Shawul]

A smarter approach like yours is indeed necessary. I completed 6,7,8,9 bits magic for a1 with no success. I started 10 bits but i gave up after a search of 50 billion or so magics. The problem is the number of constructive collisions doesn't seem to decrease. At best I have all 2048 (i.e 1 << 11) slots occupied with 64 unresolvable collisions, for magics of up to cardinality 8. No improvements from 6 to 8, so i don't think more bits will help. Well atleast i now know magics for a1 do not exist if popcnt(magic) <= 9