Magic News?

[Gerd Isenberg]

Hi,

I tried to dense Pradu's magic bishop tables a bit with the help of constructive collisions, where different occupied bits map same attack sets. But I only found to condense edges, boarder and extended boarder squares. (number*range) 15*16, 9*30, 9*31 and 15*32, despite 12*128 for extended center and 4*512 for the center squares. 38824 bytes < 38K.

I used snoob for popcounts 4..8 (56..60) xor some 64-bit DeBruijn constant to find magics to maximize collisions.

Somehow i feel there is no way to shrink the sizes for the inner squares. Does somebody has better values?

Cheers,
Gerd

Code: Select all

u64 bishopMagic[64] =
{   //               0                  1                  2                  3
   0xffedf9fd7cfcffff,0xfc0962854a77f576,0xc3879718b46a0c89,0x43d7df9dbcca0c89,
   0xc3fbfbdcf4ca0c89,0x03f71c59b4ca0c89,0xfc0a66c64a7ef576,0x7ffdfdfcbd79ffff,
   0xfc0846a64a34fff6,0xfc087a874a3cf7f6,0xc3f7c75e34fa8c89,0x03f79f5e74820c89,
   0x43f79c0ca0ca0c89,0xc3f79e38f5ee0c89,0xfc0864ae59b4ff76,0x3c0860af4b35ff76,
   0xc3f7ff0cb1d20c89,0xc3f61f6cb2ca0cd9,0x0001000202020200,0x0000800410220000,
   0x0000800400a00001,0x0000200100884000,0x7c0c028f5b34ff76,0xfc0a028e5ab4df76,
   0xc3e7bfdcb5cb04c9,0x33f79f5cb0ca0e09,0x0000208004010400,0x0000404004010200,
   0x0000404004010040,0x0000404002011000,0x43f51f5cb6c80989,0x03f59e1cb4cb0c09,
   0xc3e71c5cb4f20c89,0xc3f3865cb4e00c89,0x0000104400080800,0x0000020080080081,
   0x0000404040040100,0x0000808100020100,0x33ff975cb4ca0e89,0x43fe9f1c34cb0c09,
   0xc3f78eceb0ca1889,0xc3f305dcb6ca0c09,0x0000082088001000,0x0000000a44000800,
   0x0000010122000400,0x0001010101000200,0x43ff9a5cf4ca0c01,0xc3f79b7cb68a0cad,
   0xfc0ff2865334f576,0xfc0bf6ce5924f576,0x03f79e5cd4eb2c89,0x23f79f5ca0880c89,
   0x33f79f5ca08a0c89,0x43f7b75c34cade89,0xc3ffb7dc36ca8c89,0xc3ff8a54f4ca2c89,
   0xfffffcfcfd79edff,0xfc0863fccb147576,0x43f79f5cb3831c89,0x33f79f5cb4c20881,
   0x33f79f5cb0ca0881,0xc3f79f2c94e808a9,0xfc087e8e4bb2f736,0x43ff9e4ef4ca2c89
};

u8 bishopShift[64] =
{
   59,60,59,59,59,59,60,59,
   60,60,59,59,59,59,60,60,
   59,59,57,57,57,57,60,60,
   59,59,57,55,55,57,59,59,
   59,59,57,55,55,57,59,59,
   59,59,57,57,57,57,60,59,
   60,60,59,59,59,59,60,60,
   59,60,59,59,59,59,60,59
};

// used to calculate pointer offsets
u16 bishopSizeOfEachArray[64] =
{
   32, 16, 30, 32, 32, 30, 16, 32,
   16, 16, 30, 32, 32, 30, 16, 16,
   30, 30,128,128,128,128, 16, 16,
   31, 32,128,512,512,128, 31, 32,
   31, 31,128,512,512,128, 32, 31,
   30, 31,128,128,128,128, 16, 31,
   16, 16, 31, 32, 32, 30, 16, 16,
   32, 16, 30, 32, 32, 31, 16, 32
};


[Pradu]

Hi,

I tried to dense Pradu's magic bishop tables a bit with the help of constructive collisions, where different occupied bits map same attack sets. But I only found to condense edges, boarder and extended boarder squares. (number*range) 15*16, 9*30, 9*31 and 15*32, despite 12*128 for extended center and 4*512 for the center squares. 38824 bytes < 38K.

I used snoob for popcounts 4..8 (56..60) xor some 64-bit DeBruijn constant to find magics to maximize collisions.

Somehow i feel there is no way to shrink the sizes for the inner squares. Does somebody has better values?

Cheers,
Gerd

For move bitboards with higher bits, you can prove that there exists no better magics pretty easily by getting rid of upper redundant bits only. For example, for square 51:

Code: Select all

AttackBB =
00000000
00000000
00101000
01000100
00000010
00000000
00000000
00000000


You will only need to concider these bits in the magic because the others make all the bits in the occupancy shift away too far:

Code: Select all

00000000
00000000
00000000
11000000
11111111
11111111
11111111
11111111

With today's processing power, one could just iterate through all possible magics and prove that no 4-bit magic exists for square 51, but there are more efficient tree-searching techniques that take into account partial upper-redundant bits, lower-redundant bits and unwanted collisions.

Actually, I wrote a silly paper on magic searching techniques a long time back being certain that tree-traversing techniques would work well. Regretfully, I was not able to complete it because the proof was not fast enough when there are few redundant bits during the search and when the possible range of occupancy inputs are more or less independent of each other (I had to run it overnight to prove that square 0 had no possible 6-bit rook magic). Here's the unfinished paper on finding optimal magics for anyone who has the computational resources and time to find and prove optimal magics. There are inaccurate assumptions in the paper when discussing searching order of magic bits for the fastest search, but the rest should be more or less rigorous.

Here's a sample run of the tree-traversing magic generator running on Square 51 to prove that no 4-bit magic exists (took less than a minute on my lousy P4 with lousy guessing ordering).

Code: Select all

Square=51
Num Bits=4

Direct Influence:
00000000
00000000
00000000
11000000
11111111
11111101
00000000
00000000

Carry Influence:
00000000
00000000
00000000
00000000
00000000
00000010
11111111
11111111

#Guess bits, Guessed magic so far, Unknown bits

 1) 0000000000000000 00000003FFFCFFFF
 2) 0000000000000000 00000003FFF8FFFF
 3) 0000000000080000 00000003FFF0FFFF
 4) 0000000000080000 00000003FFE0FFFF
 5) 0000000000080000 00000003FFC0FFFF
 6) 0000000000080000 00000003FF40FFFF
 7) 0000000000080000 00000003FE40FFFF
 8) 0000000000080000 00000003FC40FFFF
 9) 0000000002080000 00000003F840FFFF
10) 0000000002080000 00000003F040FFFF
11) 0000000002080000 00000003E040FFFF
12) 0000000002080000 00000003C040FFFF
13) 0000000052080000 000000038040FFFF
14) 0000000052080000 000000030040FFFF
15) 0000000052080000 000000020040FFFF
16) 0000000052080000 000000000040FFFF
17) 0000000052080000 000000000040FFFE
18) 0000000052080000 000000000040FFFC
19) 0000000052080000 000000000040FFF8
20) 0000000052080000 000000000040FFF0
21) 0000000052080000 000000000040FFE0
22) 0000000052080000 000000000040FFC0
23) 0000000052080000 000000000040FF80
24) 0000000052080000 000000000040FF00
25) 0000000052080000 000000000040FE00
26) 0000000052080000 000000000040FC00
27) 0000000052080000 000000000040F800
28) 0000000052080000 000000000040F000
29) 0000000052080000 000000000040E000
30) 0000000052082000 000000000040C000
31) 0000000052085000 0000000000408000
No 4 bit key exists.
Trying 5 bits...

Num Bits=5


Direct Influence:
00000000
00000000
00000000
11000000
11111111
11111111
00000001
00000000

Carry Influence:
00000000
00000000
00000000
00000000
00000000
00000000
11111110
11111111

 1) 0000000000000000 00000003FFFE7FFF
 2) 0000000000000000 00000003FFFC7FFF
 3) 0000000000000000 00000003FFF87FFF
 4) 0000000000080000 00000003FFF07FFF
 5) 0000000000080000 00000003FFE07FFF
 6) 0000000000080000 00000003FFC07FFF
 7) 0000000000080000 00000003FF807FFF
 8) 0000000000080000 00000003FF007FFF
 9) 0000000000080000 00000003FE007FFF
10) 0000000000080000 00000003FC007FFF
11) 0000000002080000 00000003F8007FFF
12) 0000000002080000 00000003F0007FFF
13) 0000000002080000 00000003E0007FFF
14) 0000000002080000 00000003C0007FFF
15) 000000000A080000 0000000380007FFF
16) 000000000A080000 0000000300007FFF
17) 000000000A080000 0000000200007FFF
18) 000000004A080000 0000000000007FFF
19) 000000004A080000 0000000000007FFE
20) 000000004A080000 0000000000007FFC
21) 000000004A080000 0000000000007FF8
22) 000000004A080000 0000000000007FF0
23) 000000004A080000 0000000000007FE0
24) 000000004A080000 0000000000007FC0
25) 000000004A080000 0000000000007F80
26) 000000004A080000 0000000000007F00
27) 000000004A080000 0000000000007E00
28) 000000004A080000 0000000000007C00
29) 000000004A080000 0000000000007800
30) 000000004A080000 0000000000007000
31) 000000004A081000 0000000000006000
32) 000000004A083000 0000000000004000
33) 000000004A086800 0000000000000000
D7 & 0x000000004A086800 & 5 \\
\hline

Anyways, I believe you can ask Grant for the best magics for both rooks and bishops so far.

[Gerd Isenberg]

Hi Pradu,

great paper, thanks! Actually I am too small on time to make a more detailed reply. I wonder why i accidently found a four bit bishop key for square 46, but not for 47. Maybe i understand it, after working through your paper

After finding 5-bit keys for the corner squares last weekend, and even 15 4-bit keys, i was quite confident to get below 32K for bishops.
The inner squares with the four diagonal neighbours, imply too much constrains due to the two potential none redundant 101 occupancy pattern.

Cheers,
Gerd

[Grant Osborne]

Gerd

My program uses the 32-bit magic numbers as they proved to be 10%+ faster so I have abandonded the 64-bit magics. But from what I can remember, I managed to find 19 4-bit magics for the bishops.

As you know, I also found 2 11-bit magics for the rooks in the corners (A1 & H1). For the other 2 corners, H8 is definately 12-bit but A8 is a possible 11-bit and might be worth further investigation.

Grant

[Pradu]

Gerd

My program uses the 32-bit magic numbers as they proved to be 10%+ faster so I have abandonded the 64-bit magics. But from what I can remember, I managed to find 19 4-bit magics for the bishops.

I don't think the 32-bit optimization would be faster in 64-bits so you might also want to keep a 64-bit version. Perhaps someone who has a 64-bit CPU can check this. Also it is much tougher to reduce 32-bit magics beyond 1-1 (eg number of bits in occupancy=number of bits in index).

As you know, I also found 2 11-bit magics for the rooks in the corners (A1 & H1). For the other 2 corners, H8 is definately 12-bit but A8 is a possible 11-bit and might be worth further investigation.

Grant

How does the technique that you used to prove that H8 (this is square 7 in your representation?) is definitely 12-bit key work? I have much trouble using my technique to prove that (7+)-bit magics don't exist for low-rook corners. This is possibly because of my poor static ordering scheme but I'm not sure. I'll try to come up with a better dynamic ordering scheme this weekend and see if that helps any.

[Grant Osborne]

Pradu

You are right of course, and I was not thinking ahead to a time when I may buy a 64-bit machine.

The technique I use, as I may have said before, is a sort of homing-in technique. Using different ranges of random numbers and monitoring the magics and the collisions, I found it not too difficult to spot bits that were repeatedly set or unset. With this information I could construct the key by setting or unsetting certain bits according to the previous search.

Doing this for the H8 square (11-bit rooks) the results were poor, very few collisions even after 24 hours of continuous searching and unable to get any closer to finding a key - conclusion 11-bit impossible. A8 on the other hand was very promising, lots of collisions, and was able to get nearer and nearer to the key but it was just taking too much time.

You might say that this method is not very conclusive but after many days of searching just one square you begin to realize that the quest is futile.

Grant

[Onno Garms]

Why do you address bishop's magic multipliers? The rook's tables are much larger. I guess that 70k oder 38k in bishop's table won't make a big difference, but 1M oder 512k in the rook's tables might.

Do you consider any further progress on the rook's tables hopeless?

[H.G.Muller]

Progress is hopeless in the sense that sub-minimal keys don't seem to exist with conventional square numbering. Other square numberings have not been exhaustively tried. As it seems to be easier to produce sub-minimal keys if all the contributing occupancy bits are not in the high end of the word, it would be logical to try mapping these bits to the center squares. But arbitrary mappings have many disadvantages in other areas of bit-board usage.

If you accept extra memory accesses, through introducing additional levels of indirection, the idea of the split lookups by Michael Sherwin seems a solution that is so good, that it is futile to try improve on it. (i.e. do 12-bit key lookup as 2 lookups with a 6-bit key, so that you need in stead of 64 x 4K = 256K in tables only 2 x 64 x 64 = 8K).

[Gerd Isenberg]

Why do you address bishop's magic multipliers? The rook's tables are much larger. I guess that 70k oder 38k in bishop's table won't make a big difference, but 1M oder 512k in the rook's tables might.

Do you consider any further progress on the rook's tables hopeless?

The rook tables are quite too huge for my taste. Huge ressources for a relativ small win compared to 9.5 kindergarten bitboards, where you can get file- and rank-attacks in parallel with independent instructions. Cache pollution might not be an issue in a perft framework, but probably in a real chess program.

38K otoh still looks acceptable for combined bishops attacks. As always, things may change with future hardware, and may behave diffrently from program to program with different cache- and memory footprints. I suggest to keep that stuff in a header file with some conditinal switches to test differences from time to time.