Magics generation

hgm · Post by **hgm** » Mon Jan 05, 2026 9:01 pm

I am trying to add some features to Fairy-Stockfish, and for one of these I need attacks for an unorthodox (bent) slider path. Since FSF uses magic bitboard generation, and doesn't necessarily rely on pext, I need a set of magic multipliers for that. FSF comments state that its method for generating the multipliers is 'very slow', which is why it uses per-initialized table for those.

Since FSF's board is rather large (12x10), it requires a lot of rather long (128 bit) multipliers. Because I was too lazy to make them all by hand (even though the paths are so regular that this was not difficult, but imagine having to type 120 32-hex-digit numbers...) I decided to program the way I usually do that. I wonder if this method has been used before. So I made a small trial program for ordinary 8x8 boards, the actual generator working like below. Nothing attempts to generate sub-minimal tables, but variable shift so the index length is always equal to the number of mask bits.

Code: Select all

// recursively find a magic that provides 1:1 mapping of mask population to key 
//   key = bits placed so far     (starts at 0)
//   p = bits still to place      (starts at mask)
//   magic = maps the placed bits (starts at 0)
Bitboard Puzzle(Bitboard key, Bitboard p, Bitboard magic)
{
  int i, k;
  cnt++;
  for(k = 63; (~p & 1LL << k); k--) {}                 // search highest set bit
//  printf("Puzzle(%016llx, %016llx, %016llx)  %d %016llx\n", key, p, magic, k, 1LL << k);
  for(i = (k > keyStart ? k : keyStart); i < 64; i++) {// i = where we try to place it in the key
    if(!(key & 1LL << i)) {                            // there is room there 
      int shift = i - k;                               // how much we have to shift the mask to get it there
      Bitboard newBits = p << shift;
      Bitboard newKey = key + newBits;
      Bitboard newMagic;
      if(key & newBits & keyBits) continue;            // collision: already placed key bits must not be disturbed
      if((newKey ^ key) & key & keyBits) continue;     // also not by carry
      newBits -= (newKey ^ key) & keyBits;             // erase bits that are now placed
      newMagic = magic | 1LL << shift;
      if(!newBits) return newMagic;                    // nothing left to place: success!
      newMagic = Puzzle(newKey, newBits >> shift, newMagic); // try placing remaining bits of mask
      if(newMagic) return newMagic;                    // success: return result
    }
  }
  return 0; // fail
}

If I run it for the Rook masks, I get the following output:

Code: Select all

00: mask = 000101010101017e, magic = 0080004000802010 shift = 52 in 55 attempts
01: mask = 000202020202027c, magic = 0200220100804010 shift = 53 in 260 attempts
02: mask = 000404040404047a, magic = 0200220080401008 shift = 53 in 301 attempts
03: mask = 0008080808080876, magic = 0200120040200804 shift = 53 in 350 attempts
04: mask = 001010101010106e, magic = 0100080100100402 shift = 53 in 449 attempts
05: mask = 002020202020205e, magic = 0200020010080401 shift = 53 in 1004 attempts
06: mask = 004040404040403e, magic = 0400100804020081 shift = 53 in 1011 attempts
07: mask = 008080808080807e, magic = 0200040200804021 shift = 52 in 1018 attempts
10: mask = 0001010101017e00, magic = 0000800040008020 shift = 53 in 1094 attempts
11: mask = 0002020202027c00, magic = 0002004201008020 shift = 54 in 1144 attempts
12: mask = 0004040404047a00, magic = 0002004200802010 shift = 54 in 1159 attempts
13: mask = 0008080808087600, magic = 0002004200201008 shift = 54 in 1171 attempts
14: mask = 0010101010106e00, magic = 0002002200100804 shift = 54 in 1189 attempts
15: mask = 0020202020205e00, magic = 0001000401000802 shift = 54 in 1450 attempts
16: mask = 0040404040403e00, magic = 0004001008040201 shift = 54 in 1456 attempts
17: mask = 0080808080807e00, magic = 0002000402008041 shift = 53 in 1462 attempts
20: mask = 00010101017e0100, magic = 0040008000804020 shift = 53 in 1467 attempts
21: mask = 00020202027c0200, magic = 0020004010004020 shift = 54 in 1477 attempts
22: mask = 00040404047a0400, magic = 0002020040802010 shift = 54 in 1485 attempts
23: mask = 0008080808760800, magic = 0002020040201008 shift = 54 in 1491 attempts
24: mask = 00101010106e1000, magic = 0002020020100804 shift = 54 in 1497 attempts
25: mask = 00202020205e2000, magic = 0001010004000802 shift = 54 in 1564 attempts
26: mask = 00404040403e4000, magic = 0000040010080201 shift = 54 in 1576 attempts
27: mask = 00808080807e8000, magic = 0000020004008041 shift = 53 in 1582 attempts
30: mask = 000101017e010100, magic = 0040008080004020 shift = 53 in 1588 attempts
31: mask = 000202027c020200, magic = 0020100040004020 shift = 54 in 1595 attempts
32: mask = 000404047a040400, magic = 0020010100402010 shift = 54 in 1601 attempts
33: mask = 0008080876080800, magic = 0010010100201008 shift = 54 in 1607 attempts
34: mask = 001010106e101000, magic = 0008010100100804 shift = 54 in 1613 attempts
35: mask = 002020205e202000, magic = 0002008080040002 shift = 54 in 1666 attempts
36: mask = 004040403e404000, magic = 0000100400080201 shift = 54 in 1672 attempts
37: mask = 008080807e808000, magic = 0000040200008041 shift = 53 in 1677 attempts
40: mask = 0001017e01010100, magic = 0040008040800020 shift = 53 in 1688 attempts
41: mask = 0002027c02020200, magic = 0040010081004020 shift = 54 in 1698 attempts
42: mask = 0004047a04040400, magic = 0020010041002010 shift = 54 in 1706 attempts
43: mask = 0008087608080800, magic = 0010010021001008 shift = 54 in 1714 attempts
44: mask = 0010106e10101000, magic = 0008010011000804 shift = 54 in 1722 attempts
45: mask = 0020205e20202000, magic = 0001000401000802 shift = 54 in 1734 attempts
46: mask = 0040403e40404000, magic = 0000100804000201 shift = 54 in 1740 attempts
47: mask = 0080807e80808000, magic = 0000040082000041 shift = 53 in 1746 attempts
50: mask = 00017e0101010100, magic = 0040008000408020 shift = 53 in 1757 attempts
51: mask = 00027c0202020200, magic = 0020004010004020 shift = 54 in 1770 attempts
52: mask = 00047a0404040400, magic = 0010002000808010 shift = 54 in 1785 attempts
53: mask = 0008760808080800, magic = 0008001000808008 shift = 54 in 1799 attempts
54: mask = 00106e1010101000, magic = 0004000800808004 shift = 54 in 1813 attempts
55: mask = 00205e2020202000, magic = 0002000400808002 shift = 54 in 1829 attempts
56: mask = 00403e4040404000, magic = 0002000804020001 shift = 54 in 1840 attempts
57: mask = 00807e8080808000, magic = 0000040080420001 shift = 53 in 1850 attempts
60: mask = 007e010101010100, magic = 0080004000200040 shift = 53 in 1901 attempts
61: mask = 007c020202020200, magic = 0040002010080020 shift = 54 in 2001 attempts
62: mask = 007a040404040400, magic = 0010002008040020 shift = 54 in 2094 attempts
63: mask = 0076080808080800, magic = 0010000804004040 shift = 54 in 2190 attempts
64: mask = 006e101010101000, magic = 0001008040201002 shift = 54 in 2230 attempts
65: mask = 005e202020202000, magic = 0004002010080401 shift = 54 in 2257 attempts
66: mask = 003e404040404000, magic = 0000800200010080 shift = 54 in 2336 attempts
67: mask = 007e808080808000, magic = 0000800100004080 shift = 53 in 2363 attempts
70: mask = 7e01010101010100, magic = 0080010080402011 shift = 52 in 2370 attempts
71: mask = 7c02020202020200, magic = 0040010080402011 shift = 53 in 2377 attempts
72: mask = 7a04040404040400, magic = 0020010040201009 shift = 53 in 2384 attempts
73: mask = 7608080808080800, magic = 0010010020100805 shift = 53 in 2391 attempts
74: mask = 6e10101010101000, magic = 0001000800100403 shift = 53 in 2400 attempts
75: mask = 5e20202020202000, magic = 0001000400080201 shift = 53 in 2408 attempts
76: mask = 3e40404040404000, magic = 0001000200040081 shift = 53 in 2416 attempts
77: mask = 7e80808080808000, magic = 0001000200804021 shift = 52 in 2422 attempts
102400 table elements (800 KB)

karin@Flamyngo2 MINGW64 /c/WinBoard-4.7.1/FSF/mysrc2
$ nano magics.h

The 'attempts' shows the number of calls to the Puzzle routine, which is on average 37 per generated magic. Considering that even an immediately successful attempt to assign the bits already takes several such calls (up to the number of index bits in the worst case, although usually mask squares close together in the bitboard can be placed in one call), it doesn't see to need very many backtracking attempt to achieve the result. When I activate the print statement, one can follow the process, e.g.

Code: Select all

Puzzle(0000000000000000, 0008760808080800, 0000000000000000)  51 0008000000000000
Puzzle(0043b04040404000, 0000760808080800, 0000000000000008)  46 0000400000000000
Puzzle(03f3f08080804000, 0000060808080800, 0000000000000808)  42 0000040000000000
Puzzle(1dc5b24242404000, 0000000808080800, 0000000000004008)  35 0000000800000000
Puzzle(1fc7b44442404000, 0000000008080800, 0000000000404008)  27 0000000008000000
Puzzle(3fe7d44442404000, 0000000000080800, 0000000400404008)  19 0000000000080000
Puzzle(3de5d26242404000, 0000000008080800, 0000000004004008)  27 0000000008000000
Puzzle(3fe7d46242404000, 0000000000080800, 0000000044004008)  19 0000000000080000
Puzzle(3b47b44444404000, 0000000808080800, 0000000000008008)  35 0000000800000000
Puzzle(3bc834c4c4404000, 0000000008080800, 0000000000108008)  27 0000000008000000
Puzzle(3fcc38c4c4404000, 0000000000080800, 0000000080108008)  19 0000000000080000
Puzzle(3f4bb84844404000, 0000000008080800, 0000000000808008)  27 0000000008000000
Puzzle(3fcc38c844404000, 0000000000080800, 0000000010808008)  19 0000000000080000
Puzzle(bfcc384844404000, 0000000000000800, 0000001000808008)  11 0000000000000800
53: mask = 0008760808080800, magic = 0008001000808008 shift = 54 in 1799 attempts

I noticed that in most cases it either takes very few, or very many calls for the Rook.

I added some verification (not shown) that tests whether all possible occupancies give a different index when muliplied with the magic. This did not flag any collisions. So it seems a pretty efficient algorithm. I wonder if this has been used before. Now the challenge of course is to make a 120-square 128-bit version of it.