Disproving the existence of some magics

[niklasf]

I want to share a little observation that makes it possible to limit the search space for magic candidates. For some squares it is then possible to exhaustively test them all.

Consider a relevant occupancy r. Then there is a smallest period p(r) > 0 such that

r * p(r) = 0 (mod 2^64)

namely

p(r) = 2^64 / gcd(r, 2^64)

If you go one step further it will just wrap around completely.

r * (p(r) + 1) = r (mod 2^64)

Now take the least common multiple of the p(r) for all relevant occupancies of a square s.

P(s) = lcm(p(r_1), ..., p(r_n))

We know that r * P(s) = 0 (mod 2^64) for all relevant occupancies of that square. In other words all magic candidates are equivalent to a candidate in the range [0, P(s) - 1].

It depends on the relevant occupancies (specifically the lowest relevant square) if P(s) is small enough to have any practical consequences. Some bishop squares have very low periods, so the best possible magics can be easily found by exhaustive search:

Bishops squares:

Code: Select all

   |  s | P(s) | c | best magic shift 9     | best magic shift c  | best magic shift c-1
---+----+------+---+------------------------+---------------------+---------------------
d8 | 59 | 2^26 | 5 | 0x84030 (maps to 0-60) | 0x208800 (0-31)     | disproven
e8 | 60 | 2^31 | 5 | 0x1002020 (0-31)       | 0x4f68bcb9 (0-29)   | disproven
d7 | 51 | 2^34 | 5 | 0x8403000 (0-60)       | 0x20880000 (0-31)   | disproven
c8 | 58 | 2^34 | 5 | 0x8208060 (0-35)       | 0x50c3417a (0-29)   | disproven
e7 | 52 | 2^39 | 5 | 0x100202000 (0-31)     | 0x4f68bcb86d (0-29) | disproven
f8 | 61 | 2^39 | 5 | 0x40408020 (0-31)      | 0x74486419f (0-26)  | disproven
h2 | 15 | 2^42 | 5 | e0x820820020 (0-61)    | 0x29748305f5 (0-22) | 0x410509fff0 (*) (0-15)
d6 | 43 | 2^42 | 7 | 0x8840200040 (0-132)   | 0xa44000800 (0-127) | disproven
c7 | 50 | 2^42 | 5 | 0x820806000 (0-35)     | 0x50c34179e6 (0-29) | disproven
b8 | 57 | 2^42 | 5 | e0x820820020 (0-61)    | 0x58c328c2ee (0-22) | 0x1ec04eae595 (*) (0-15)

  ( ... snip ... )

h8 | 63 | 2^55 | 6 |                        |                     | exists (Gerd Isenberg)

(*) Previous magic found by Gerd Isenberg are equally good

Rook squares generally have higher periods, because there's always a relevant second rank or even first rank occupancy. I still think some of them are now very much feasible, and I definitely plan to check them (after spending some time optimizing the magic testing).

Unfortunately the most practically intresting squares a1 and h1 remain among the most difficult ones.

Rook squares:

Code: Select all

   |  s | P(s) |  c | magic with shift c-1
---+----+------+----|--------------------------
h3 | 23 | 2^49 | 11 |
h4 | 31 | 2^49 | 11 |
h5 | 39 | 2^49 | 11 |
h6 | 47 | 2^49 | 11 |
h7 | 55 | 2^49 | 11 | exists (Grant Osborne)
h8 | 63 | 2^49 | 12 | exists (Grant Osborne)

  ( ... snip ... )

h1 |  7 | 2^63 | 12 |

Previous results taken from https://chessprogramming.wikispaces.com ... ics+so+far

[Gerd Isenberg]

Very interesting ... good luck in further testing to half the size of the big rook squares. While it seems that clever fixed shift has the edge now, your findings may even help for denser ranges in Volker's packed or black magics.

Gerd

[grant]

I am doubtful you will find a1 or h1 but good luck to you.

Grant

[niklasf]

Agreed, those squares remain out of reach.

Some unscientific thoughts about them: So far it seems that there are either no magics at all, or hundreths of thousands of them. And indeed so far for each square a magic had already been found or there was none. So I'd personally bet that a1/h1 have no shift 11 magics.

[Evert]

It's probably not worth it, but one could flip the occupancy board (bswap64) if the square is on the lower half of the board, do the table-lookup for a8/h8, then flip the resulting move set (another bswap). This could even cut the size of the tables fully in half, and allow for a more compact table because you don't need the problematic squares a1/h1.
Cost: two conditional bswaps. Might be interesting to try though.