Wythoff's game corner the queen, add up the queens
A queen moves any distance left, down or diagonally down-left. With several queens on the board, a turn moves exactly one of them; whoever makes the last move wins. Each square has a Grundy value g(x, y), and a position is lost for the player to move exactly when the queens' values XOR to 0. Pick a queen: squares marked ✓ leave XOR 0 behind, ✗ do not.
value of the position
checked against the literature
the value table
g(x, y) for 0 ≤ x, y < 200; x up, y right. Hover for values.
every row is additively periodic
Why the queens add up
A position of one queen has value g(x, y) = mex of the values of the squares she can reach (the smallest number not among them). By the Sprague–Grundy theorem a set of queens, where each turn moves one of them, is worth the XOR of their values, and the player to move loses exactly when that XOR is 0. Value 0 squares are Wythoff's pairs (⌊nφ⌋, ⌊nφ²⌋), φ the golden ratio; the other values have no formula.
Rows, periods and a certificate
Along any row x the values satisfy g(x, y + p) = g(x, y) + p once y is past a preperiod (Dress, Flammenkamp and Pink, 1999). The sweep here computes rows 0–460 column by column in memory that does not grow with y, because all of a row's, a column's and a diagonal's relevant values lie in [y − 2x, y + x]. A period that only looks right is not trusted: a row counts as proved when its state (its own used values, relative to y) is the same at two columns a multiple of every lower row's period apart, with all lower rows already periodic — from then on it repeats forever.