Code: Select all
U64 attack_table[85204];
struct SMagic {
U64 mask; // black magic mask
U64 magic; // magic 64-bit factor
int shift; // shift right
int offset; // or attack_table ptr directly
};
//Normal black variable shift
U64 idx = ((occ | mask) * magic) >> (64 - shift);
U64 atk = *(attack_table + offset)[idx];
Code: Select all
size 85204 entries 128
# piece sq magic shift offset
r 0 0x0050020428000410 12 9841
r 1 0x00300018008c0004 11 44117
r 2 0x00600101200c0002 11 13701
r 3 0x0050004050088001 11 37713
r 4 0x0030018003000090 12 38978
r 5 0x0040024241400040 11 18452
r 6 0x0060018000c00060 11 45655
r 7 0x0150002410080004 12 7232
r 8 0x0000500202280014 11 49682
r 9 0x8000500204140008 10 76574
r 10 0x4000601404200008 10 65783
r 11 0x0000600600212001 11 72417
r 12 0x0000a0050080a002 10 79830
r 13 0x0000a0028040a001 10 78550
r 14 0x0000c0018000c003 10 74209
r 15 0x0000300030001260 12 37343
r 16 0x0060003002180010 11 42577
r 17 0x000c003000980004 10 71734
r 18 0x4020006014000420 10 63940
r 19 0x000600600c000420 10 67542
r 20 0x0002003003800090 11 68307
r 21 0x0001806003000120 10 70963
r 22 0x0010030004840042 10 64827
r 23 0x8000141000600028 11 15726
r 24 0x0080062120100010 11 23643
r 25 0x0040600030300010 10 59029
r 26 0x80042001000b0004 11 0
r 27 0x100248001c005000 10 57028
r 28 0x1420010100100800 10 52974
r 29 0x2080010100440008 10 53981
r 30 0x40000040c0032200 10 60048
r 31 0x4c020b000aa88041 11 33775
r 32 0x0000123000600060 11 21601
r 33 0x8000080870200080 10 60978
r 34 0x4804002104008040 10 61931
r 35 0x3000044202001020 10 62920
r 36 0x1010010905000800 10 56014
r 37 0x0608005d02a00400 10 55003
r 38 0x000c004160400200 10 17743
r 39 0x1204001e4b500900 11 31796
r 40 0x0000041428005000 11 47122
r 41 0x09001006c9204000 10 72660
r 42 0x000001228c006000 10 66654
r 43 0x00000212420a0010 10 58033
r 44 0x000002400600c00c 10 70195
r 45 0x0000006001806003 11 73953
r 46 0x000400401002a00a 10 77176
r 47 0x0000002214015002 11 82649
r 48 0x0000085002280050 11 48402
r 49 0x0400041400280050 10 80486
r 50 0x00000240180500c0 10 68387
r 51 0x002000a00a0100a0 10 79190
r 52 0x000000a0064080a0 10 75727
r 53 0x00400040a00280a0 10 81111
r 54 0x12001000402002a0 10 77952
r 55 0x0002000a02a00090 11 50935
r 56 0x0000042900420012 12 -7
r 57 0x0000020049001422 11 25684
r 58 0x4080008a0087240a 11 29769
r 59 0x0002000040110886 11 27725
r 60 0x4001000084108801 11 19921
r 61 0x8800001190122436 11 35810
r 62 0x0004001010448804 12 4089
r 63 0x0000000884025022 12 4082
b 0 0x0002100448010802 7 2302
b 1 0x0004100890240800 6 14879
b 2 0x0004126088020000 6 35526
b 3 0x0006186408000000 5 34583
b 4 0x0016428200000200 5 8187
b 5 0x0801244281000000 5 32565
b 6 0x0200544840400000 6 3071
b 7 0x0100140828080020 7 2559
b 8 0x0000042080891004 6 34266
b 9 0x0000021011043004 6 34275
b 10 0x0000042160840200 6 35547
b 11 0x0000061864080000 5 34833
b 12 0x4800098281000000 5 35083
b 13 0x0000412442810000 5 32023
b 14 0x0200005448404000 6 3199
b 15 0x0200002a24202000 6 3135
b 16 0x002000048420c008 6 34039
b 17 0x0010000122109010 6 34502
b 18 0x0010000802121401 8 2046
b 19 0x0010801808180200 7 38190
b 20 0x4000600030804002 8 38599
b 21 0x00014000280a00a0 7 76303
b 22 0x0000800104884140 5 34046
b 23 0x0000800032052020 5 11143
b 24 0x0008080025110040 5 34021
b 25 0x0004040013084020 5 17990
b 26 0x0000300208081802 8 2815
b 27 0x0211044001040001 9 82129
b 28 0x000c008704002000 10 29773
b 29 0x0086006000300040 7 73120
b 30 0x000802008090c040 5 19045
b 31 0x00008080012a2020 5 19016
b 32 0x0080089280040400 6 19562
b 33 0x0100491080040400 5 19619
b 34 0x4018041010020080 7 61167
b 35 0x00002002e4080080 9 84692
b 36 0x4000204018003080 9 82635
b 37 0x00002a1410020100 7 39210
b 38 0x0000425108004100 6 18216
b 39 0x000020604800c400 5 18504
b 40 0x0000059011800800 5 35294
b 41 0x02000428a0800400 6 31069
b 42 0x0080011404120200 7 39291
b 43 0x0801000514040800 7 14745
b 44 0x1000001048188400 8 30813
b 45 0x0000111821080080 7 38270
b 46 0x0000848110480400 5 34559
b 47 0x0000421060440200 5 14715
b 48 0x0100024842081000 5 31962
b 49 0x00080a0141084000 5 32143
b 50 0x0000000890a44400 5 31842
b 51 0x010000000c522002 5 35052
b 52 0x0004080085414000 5 35314
b 53 0x0800008841812000 5 31903
b 54 0x0000201140508400 6 34768
b 55 0x0000820844082200 6 34777
b 56 0x010002004400c0a0 7 2687
b 57 0x020000021108a080 6 31149
b 58 0x000200000890a440 5 32383
b 59 0x0000000000144e18 5 14870
b 60 0x0000500001054140 5 35334
b 61 0x000010004420c090 6 32653
b 62 0x0000008222084410 6 34257
b 63 0x000009100401080a 7 2430Three tricks helped speed up the search.
1) rnd & rnd & rnd will produce too many duplicates - and its expensive to keep unique. Better to exactly Compute the lexicographically next bit permutation function NCR 64, N times,
Code: Select all
static void bit_twiddle_permute(uint64_t& v) {
uint64_t t = v | (v - 1);
v = (t + 1) | (((~t & -~t) - 1) >> (std::countr_zero(v) + 1));
}2) Still search over the space of rnd & rnd for additional magics. This means you searched 8bit magics exhaustively + a binomial distribution accross with center at 16bit popcount.
3) For masked_occ[4096] - here is a new trick. With this system you have the candidates lexographically sorted. Meaning if index 1243 collided with inded 2086 it will very likely do the same on the next iteration. Sounds expensive but its better to move the failed masked_occ and atk_id to 0, and 1 - std::memmove all items above. Each new iteration will now always collide very early!
4) Right after the fail condition after memmove still before break, loop test the next candidates on the first 8 elements for collisions. It will very likely happen. Do this in a hot loop on a small 8 slot buffer, to get the next index which will not break in the first few iterations.
