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

[Volker Annuss]

Hi,

here 2 smaller magics for squares 52 and 53 found with a genetic optimization algorithm. The upper bits do NOT contain a shift count.

Code: Select all

52:  9 0xffffffe9ffe7ce00    512
53:  9 0xfffffff5fff3e600    512

Greetings
Volker

[Gerd Isenberg]

Hi Volker,
wow, great. I have just put it in the wiki's magic record table.
Can you give a brief description how your algorithm works?

Btw. the programmers tour was magnificent. Richard did a great job organizing this. More later. The nights were a bit short - l need some sleep now. You should arrange to enter next time - likely Feb, Mar next year.

Cheers,
Gerd

[Volker Annuss]

Hi Gerd,

my magic factor generation is much too experimental to give some code here. Most of the implementation details are just a guess what might work and you might better test your own ideas and come up with something better.

Evaluation function (fitness function)

First you need an evaluation function (or fitness function in terms of genetic algorithms) for a magic number.

(1) In the first place it evaluates the number of bits in the index table. This is what you want to minimize. All other terms just help to guide the search.

I tried various other terms. All these terms seem to have the nasty property that they are helpful for some squares but bad for others.

(2) The number of unused entries at the end of the index table.
(3) The number of good collisions.
(4) The number of bad collisions when using one index bit less.
(5) How close is the popcount of the factor to 5, 6 .. or 10 or 54, 56 ..?
(6) Count how often a bit is different from its neighbour. How close is popcount( factor ^ (factor>>1) ) to 8, 9, ...
(7) Invent your own.
(8) see (7)

Although (5) and (6) only need a very small weight in the evaluation, having one of them is very helpful.


Make children

Take two parents. Every bit the parents have in common is copied to the child. Every bit that is different in the parents is replaced by a random bit.

c = (p1 & p2) | ((p1 ^ p2) & rnd64());

Sometimes flip one (or more) random bit(s) in the child.

Exception 1: When the child becomes equal to one of the parents, flip a random bit.
Exception 2: If both parents are equal, make the child a random number.
This prevents the whole population from beeing filled with the same number, making progress difficult.


Optimization

Fill an initial population with random factors.
Then simply pick two parents with a good evaluation (the better they are, the higher the probatility to pick them), create lots of children and replace some factors with a bad evaluation (the worse they are, the higher the probability to pick them) by the best evaluated children.
Make sure, that even the best factors have a chance to get killed to avoid dead ends.
Repeat this as long as you have CPU time left.

A big hash table that maps magic factors to evaluations is helpful.

A modified optimization algorithm tries to keep some losely connected local populations:
Divide the population in a left and a right half.
Select one parent from the right and one from the left.
Make lots of children and replace one factor from the left and one factor from the right by a good child.
Optimize the right and the left half recursively.


Greetings
Volker

PS: Looking into the Wiki, there are at least some 4 bit bishop magics you could need. So here is my complete list. A 10 bit rook magic for square 55 like the one by Grant Osborne is still undiscovered.

Code: Select all

Rook magics
 0: 12 0x0080062081544001    4096
 1: 11 0x004004500040600a    2048
 2: 11 0xf7dfeff7fbfbf7df    2045
 3: 11 0xfdfff6fabfe9ffed    2047
 4: 11 0x7efffaffe9e7ffeb    2047
 5: 11 0x09000c00028a8b00    2047
 6: 11 0x7bfffeac6bfbfc02    2046
 7: 12 0x020000d200640051    4095
 8: 11 0x0002801082a4c000    2048
 9: 10 0x0001400cd0002000    1024
10: 10 0x00ff1fff3e7e80e0    1019
11: 10 0xfffdffe5fdcdedf2    1022
12: 10 0x0002001212020408    1021
13: 10 0xfffdfff2eff9fffb    1023
14: 10 0xfffbfff5ddadae17    1022
15: 11 0x0b260000488e8e7c    2046
16: 11 0xc25082100808200f    2047
17: 10 0x9040404010002000    1024
18: 10 0x0230002000240800    1024
19: 10 0x4002020040102008    1024
20: 10 0x0002020008106004    1024
21: 10 0x0221010002080400    1024
22: 10 0x00000c00028a8b10    1023
23: 11 0x0130220012a0cb04    2048
24: 11 0x0000400180096090    2048
25: 10 0x005050004004a00a    1024
26: 10 0x0490002020040800    1024
27: 10 0x0002401200082200    1024
28: 10 0x0202001200040820    1024
29: 10 0x0086008080040002    1024
30: 10 0x0000100c00028a8b    1023
31: 11 0xc001000100004082    2048
32: 11 0x0000814010800428    2048
33: 10 0x80401008052000a0    1024
34: 10 0x80010010c1002000    1024
35: 10 0x0080100103000820    1024
36: 10 0x0002001412002008    1024
37: 10 0x8800810200800400    1024
38: 10 0x0400802300800200    1024
39: 11 0x002000910a000044    2048
40: 11 0x0001c00420808012    2048
41: 10 0x00202001d0094004    1024
42: 10 0x4090040800202000    1024
43: 10 0xffffd1ffcbd9ffec    1023
44: 10 0xff7feff1edf1fff7    1022
45: 10 0x000a000804020011    1024
46: 10 0xdefbdfe05f7c7ffe    1023
47: 11 0x0000b0b0c79dfffc    2047
48: 10 0xbfffff35ff5e5e00    1024
49:  9 0xdfffff7f868ee600     512
50:  9 0xffbfff9dffaf2e00     512
51:  9 0xffffffd1ffcf9e00     512
52:  9 0xffffffe9ffe7ce00     512
53:  9 0xfffffff5fff3e600     512
54: 10 0x0000c8c950414400    1023
55: 11 0x000000a400c1a200    2047
56: 11 0xf3ffffc1ffbf4f6e    2048
57: 10 0xf1ffff8161014f52    1024
58: 10 0xffffff7fb5ffa7ea    1024
59: 10 0xffffffb9ffdfb3f6    1024
60: 10 0xaffffff5ffdff2e6    1024
61: 11 0xf9fffffdfffe7772    2048
62: 10 0xfb7fffef27eebeac    1024
63: 11 0xffffffff3bff5e5e    2048
---------------------------------
                            89566

Bishop magics:
 0:  5 0x0015090220e3fe00      32
 1:  4 0xffeaf6fe3effffff      16
 2:  5 0x550885d0e880dba0      30
 3:  5 0x000e394092000000      31
 4:  5 0x94170db89906a438      31
 5:  5 0x0000a253a8000000      29
 6:  4 0xffff5979f4ffffff      16
 7:  5 0xfffeef16e70dffff      32
 8:  4 0xffffd3eefbfe3fff      16
 9:  4 0xffffeaf6fe3effff      16
10:  5 0x020208a5c9007000      30
11:  5 0x8f328e3924a08806      31
12:  5 0xaf78a8f2476f92c9      31
13:  5 0x000000a293a80000      29
14:  4 0xfffffbb9ba73ffff      16
15:  4 0xfffffeadde3bffff      16
16:  4 0x0040000a1509cfe0      16
17:  4 0x0020001a850327f0      16
18:  7 0x848f001e21b0e2f0     126
19:  7 0x0020201202014000     128
20:  7 0x0040800401a08000     128
21:  7 0xfff71ff78fddbaff     124
22:  4 0x00040000c549ff00      16
23:  4 0x0002000052a4dfc0      16
24:  5 0x0008d102220a0a01      31
25:  5 0x1090103022854260      31
26:  7 0x13435000980b8234     128
27:  9 0x0007828028020002     512
28:  9 0x0101840000802004     512
29:  7 0xffefff1fff8edd7f     125
30:  5 0x00040100805890e8      31
31:  5 0xfffdfdffff2f5e7f      31
32:  5 0x0002861a00401000      31
33:  5 0xfff9f2f97fe8a5ff      30
34:  7 0x0400805000210400     128
35:  9 0x0040400a00006200     512
36:  9 0x0010088200012200     512
37:  7 0xfffb7ddf0ffe1eff     126
38:  5 0x796cc69a53db8c7e      30
39:  5 0x5861307869b8dbc0      30
40:  4 0xf7bff669b5ffc037      16
41:  4 0x0007f3253a002000      16
42:  7 0x00001828d0000800     127
43:  7 0x0000006128060400     128
44:  7 0xbffffc7dfd1fba3f     127
45:  7 0xffa1f1b8bf0ff878     126
46:  4 0x003f89c540a00400      16
47:  4 0x001fc2c191a00200      16
48:  4 0xfffffe3bedd5ffff      16
49:  4 0xfffffefe376affff      16
50:  5 0xfffffebdbb943fff      30
51:  5 0xb67fbfffed2c3fff      32
52:  5 0xffffffebf71c6fff      30
53:  5 0xffff37858320dffe      29
54:  4 0xfffff7fc7bbd5fff      16
55:  4 0xfffffbfe3ddeafff      16
56:  5 0xffffff8dfdef59ff      32
57:  4 0xfffffffe7d337aff      16
58:  5 0x64014186e5aae4a2      30
59:  5 0x0000000003f410b0      32
60:  5 0x567b4ffeebf71c6f      30
61:  5 0x0000000ac66d60de      28
62:  4 0xfffffff8fbfb7d5f      16
63:  5 0xfffffbbe173b76eb      32
---------------------------------
                             4745

[Pradu]

You could probably find the index-optimal magics for bishops for the upper squares even without trial-error tree-searching and cutoffs. For example you could try the "easiest" bishop square D8 because it has so many upper-redundant bits and you can do this simply by trying through all the numbers from 0->2^n-1 where n=64-(number of upper-redundant bits).

I just did the above and found all 9547 index-optimal 5-bit magics (there exist no 4-bit magics) for D8 (square 59). Sadly the very best you can do for D8 is from 0...31. However this will be a good test to bug-check more advanced algorithms by making sure they find all the magics. You can find the list of all index-optimal magics for D8 here.

[grant]

Volker

Congratulations on finding some very good magic numbers.

Square 55 for rooks is certainly a tough one to find. I have been concentrating my efforts on square 54 where so far, 992 out of the 1024 occupancies fit into 9 bits, but the magic number still eludes me. I'm beginning to think that this one is not possible.

Grant

[Gerd Isenberg]

Hi Gerd,

my magic factor generation is much too experimental to give some code here. Most of the implementation details are just a guess what might work and you might better test your own ideas and come up with something better.

Hi Volker,
Interesting, I used to try snoobing subset with same number of one bits of any set:

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;
}

Of course I am still interested in algorithms for faster finding dense magics - but since I didn't use magic bitboards, but fillstuff and rarely linewise
Hyperbola Quintessence, I am not that much motivated to burn cpu time to look for magics.

Cheers,
Gerd

[grant]

Gerd

This rook attack getter would only require 8 magic numbers and a table size of just 2.5K though it may be a fraction slower.

Code: Select all

rankAddress = (int)((Occupied >> (square & 56)) >> 1) & 0x3F; 
	occ = (int)((Occupied >> (square & 7)) & 0x0001010101010100);
	fileAddress = (occ * rookMagic[square >> 3]) >> 58;
	attacks = &#40;U64&#41;(*&#40;rankLookUp&#91;square & 7&#93; + rankAddress&#41;) << &#40;square & 56&#41;;
	attacks |= *&#40;fileLookUp&#91;square >> 3&#93; + fileAddress&#41; << &#40;square & 7&#41;;

I hope there are no errors.
Grant

[Gerd Isenberg]

Hi Grant,
your routine looks quite promising - it certainly deserved a page in CPW!
A mixture if magic bitboards for files only and rank attacks by classical rank-shift. This is how it looks slightly rewritten according to the CPW prototypes:

Code: Select all

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

   rankAddress = (int)((occ >> rkx8) >> 1) & 0x3F;
   occ = (int)((occ >> file) & 0x0001010101010100);
   fileAddress = (occ * rookMagic[rank]) >> 58;
   attacks  = *&#40;rankLookUp&#91;file&#93; + rankAddress&#41; << rkx8;
   attacks |= *&#40;fileLookUp&#91;rank&#93; + fileAddress&#41; << file;
   return attacks;
&#125;

I will have a closer look at it and compare its assembly and speed to Kindergarten-Bitboards and what I actually use to get disjoint attacks with Hyperbola Quintessence for the file and Attacks on all Ranks similar to your one:

Code: Select all

U64  fileMaskEx[64]; // 512 Bytes = 1/2KByte
U64  bitMask[64];    // 512 Bytes = 1/2KByte

U64 fileAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & fileMaskEx[sq];
   reverse  = _byteswap_uint64(forward);
   forward -= bitMask[sq];
   reverse -= _byteswap_uint64(bitMask[sq]);
   forward ^= _byteswap_uint64(reverse);
   forward &= fileMaskEx[sq];
   return forward;
}

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;

As I said, I rely on Kogge-Stone simd-fillstuff and use disjoint line attack getters only rarely in case of pinned pieces.

Gerd

[grant]

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

[rjgibert]

Make children

Take two parents. Every bit the parents have in common is copied to the child. Every bit that is different in the parents is replaced by a random bit.

c = (p1 & p2) | ((p1 ^ p2) & rnd64());

Sometimes flip one (or more) random bit(s) in the child.

Exception 1: When the child becomes equal to one of the parents, flip a random bit.
Exception 2: If both parents are equal, make the child a random number.
This prevents the whole population from beeing filled with the same number, making progress difficult.

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.

Also, I would expect the scheme might work better if you replaced "Exception 2: If both parents are equal, make the child a random number" with "Exception 2: If both parents are equal, derive a child a from a parent with a bit flipped."