Disproving the existence of some magics
Posted: Sat Sep 16, 2017 10:03 am
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:
(*) 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:
Previous results taken from https://chessprogramming.wikispaces.com ... ics+so+far
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)
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 |