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
Volker
Moderators: bob, hgm, Harvey Williamson
Code: Select all
52: 9 0xffffffe9ffe7ce00 512
53: 9 0xfffffff5fff3e600 512
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
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.Pradu wrote: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).
Hi Volker,Volker Annuss wrote: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.
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;
}
Code: Select all
rankAddress = (int)((Occupied >> (square & 56)) >> 1) & 0x3F;
occ = (int)((Occupied >> (square & 7)) & 0x0001010101010100);
fileAddress = (occ * rookMagic[square >> 3]) >> 58;
attacks = (U64)(*(rankLookUp[square & 7] + rankAddress)) << (square & 56);
attacks |= *(fileLookUp[square >> 3] + fileAddress) << (square & 7);
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 = *(rankLookUp[file] + rankAddress) << rkx8;
attacks |= *(fileLookUp[rank] + fileAddress) << file;
return attacks;
}
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;
}
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.Volker Annuss wrote: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.