Wythoff's game, and the ratio nobody put there

Two heaps of counters. A move takes any positive number from one heap, or the same positive number from both. The player who cannot move — because both heaps are empty — loses.

That is the whole game, and it is barely a modification of two-heap Nim. Two-heap Nim is settled in a sentence: the losing positions are the ones where the heaps are equal, because whatever one player does to one heap the other copies in the other — the mirroring argument that runs through the whole subject. Adding the diagonal move destroys that argument completely, since a player can now take from both at once and equality no longer protects anybody.

The board #

It is easier to see as a board than as two heaps. Put a queen on a square of a quarter-infinite chessboard whose corner is at the origin; the coordinates are the two heap sizes. Taking from the first heap moves the queen left, taking from the second moves it down, and taking equally from both moves it diagonally down and to the left. The corner is the position with nothing left, and whoever is forced to sit there having no move has lost.

So the game is a queen restricted to moving towards the corner. That is the version Willem Wythoff described in 1907, and it is the reason the game has a picture at all.

The cold squares #

Call a square cold if the player who has to move from it loses. The corner is cold: no move exists at all. Every square a queen can reach the corner from in one move is therefore hot — a player standing on it wins by going there.

The rest follows by the usual recursion. A square is cold exactly when every move from it leads to a hot square, and hot when some move from it leads to a cold one. That is the same rule that gives every impartial position a Nim value, specialised to the question of whether that value is zero.

Running it produces the shaded squares in the figure above, and the first few are easy to read off:

$$(0,0), \quad (1,2), \quad (3,5), \quad (4,7), \quad (6,10), \quad (8,13), \ldots$$

together with the mirror images, since the game does not care which heap is which.

Two patterns are visible immediately and both are worth stating, because one of them is the answer and one of them is not.

The differences between the two coordinates go $0, 1, 2, 3, 4, 5, \ldots$ — the $n$th cold pair has a gap of exactly $n$. That is a real pattern and it is easy to prove, and on its own it identifies nothing, because it does not say what the smaller coordinate is.

The smaller coordinates go $0, 1, 3, 4, 6, 8, \ldots$, and every non-negative integer appears exactly once somewhere in the list — either as a smaller coordinate or as a larger one, never both and never twice. That is the fact the answer hangs on.

That comparison is the thing to hold on to. The position $(3,5)$ is a first-player win at Nim and a first-player loss at Wythoff’s game. The board is the same, the counters are the same, and one additional move has turned the theory inside out — which is a reminder that a Grundy value is a fact about a rule set and not about a pile of objects.

How a square gets its number #

The shading is only the zeros, and it is worth seeing where the rest of the table comes from, because the recursion is the only thing in this essay that is doing any work.

The options of a square are unusually numerous — an entire row, an entire column and an entire diagonal — which is why the zeros are so sparse. A cold square has to avoid every value in three whole lines, and that scarcity is what forces them onto a line of their own.

The last property is worth naming because it is the whole strategy in one sentence: no two cold squares attack each other. If two did, a player standing on the first could move to the second and hand a lost position back, and “cold” would be self-contradictory. So the cold squares form a set of mutually non-attacking queens, which is the connection to the name Wyt Queens and the reason the game is drawn on a board at all.

Where the ratio comes in #

Take the two sequences of coordinates:

$$a_n = 0, 1, 3, 4, 6, 8, 9, 11, \ldots \qquad b_n = 0, 2, 5, 7, 10, 13, 15, 18, \ldots$$

with $b_n = a_n + n$, which is the gap pattern already noticed. Between them they use every non-negative integer exactly once.

A pair of sequences that partitions the integers like that, each of the form $\lfloor n\alpha \rfloor$ for a fixed $\alpha$, is called a Beatty pair, and there is a clean condition for when it happens: two such sequences partition the positive integers exactly when

$$\frac{1}{\alpha} + \frac{1}{\beta} = 1$$

with $\alpha$ and $\beta$ irrational. Combine that with $b_n - a_n = n$, which forces $\beta = \alpha + 1$, and there is one equation left:

$$\frac{1}{\alpha} + \frac{1}{\alpha+1} = 1 \quad \Longrightarrow \quad \alpha^2 = \alpha + 1.$$

The positive root is the golden ratio. The cold positions are

$$\left(\lfloor n\varphi \rfloor, \; \lfloor n\varphi^2 \rfloor\right), \qquad \varphi = \tfrac{1+\sqrt5}{2},$$

and the second coordinate is the first plus $n$, because $\varphi^2 = \varphi + 1$.

The identity $\varphi^2 = \varphi + 1$ is the golden ratio’s entire content and is the property everything else about it descends from; it is not re-derived here. What is worth stopping on is that the equation arrived from a partition condition and a difference pattern, with no geometry, no rectangle and no limit anywhere in sight.

What the solver computed, and how #

The table in the first figure is built by the mex rule, and the code that builds it has never seen $\varphi$.

For each square $(a,b)$ in increasing order, the option set is assembled: every square to the left, every square below, and every square diagonally down-left. Their values are already known, and the value of $(a,b)$ is the smallest non-negative integer missing from that set. The cold squares are those with value zero.

The formula is then computed separately — $\lfloor n\varphi \rfloor$ and $\lfloor n\varphi \rfloor + n$, in double-precision floating point — and the two sets are compared as sets. The figure refuses to draw if a single square is in one and not the other, and the site’s gate makes the same comparison out to heaps of forty.

A comparison that can only pass is not evidence, so the gate also runs it with the wrong constant. The silver ratio $1+\sqrt2$ is the obvious near-miss — the same kind of number, arriving from the same kind of equation — and its pairs are not cold. Several of them fail immediately, and the gate requires them to.

Playing it #

The strategy that comes out of the table is unusually satisfying to execute, because it can be followed by a person with the first few cold pairs memorised.

From a hot square, some move reaches a cold one; find it and play it. From a cold square there is no such move, so anything is as good as anything else and the game is already lost against an opponent who knows the list.

The demonstration is worth attempting rather than reading about. The claim is not that the machine plays well; it is that the machine plays the move the table names, that the table is the mex recursion, and that there is consequently no line of play from a hot start in which the machine loses.

There is one honest caveat in the figure. The board is finite, so a few squares near its edge have options that would leave it, and those are simply not offered. A player who wants the real game should imagine the board continuing.

Where the model stops #

This is one game, not a family. Wythoff’s game has a closed form for its cold positions. Almost no impartial game does. Octal games mostly have periodic Grundy sequences and no formula at all, and the ones that resist periodicity have neither. Wythoff’s game is a beautiful exception, and treating it as typical would be a serious misreading of the subject.

Cold positions are not the same as values. The figure shows the full Grundy table, but the golden-ratio result is only about the zeros. The non-zero values in Wythoff’s game have their own structure, and it is considerably less tidy — no formula of comparable simplicity is known for the value of an arbitrary square. The zeros settle who wins; the rest of the table is what would be needed to add this game to another one, and that part has no closed form.

The convention is normal play. Under misère play, where the player unable to move wins, the answer changes and the golden ratio does not survive the change. That is the usual situation, and it is worth saying explicitly whenever a result this pretty appears.

The formula is checked, not proved, by the machinery here. The comparison covers heaps up to forty. The proof — that the Beatty condition and the difference pattern together force the cold set — is a paragraph of argument and is not something a table can supply.

The generalisation #

Wythoff’s game generalises in a direction that is more surprising than it sounds. Allow the diagonal move to be unequal — take $p$ from one heap and $q$ from the other, with $|p-q|$ bounded — and a whole family of games appears whose cold positions follow lines of other irrational slopes, each the root of a quadratic determined by the bound.

So the golden ratio is not doing anything mystical here. It is the answer to a particular quadratic, and the quadratic comes from the particular move set. Change the moves and the constant changes with them, in a way that can be predicted.

That is the correct reading of every appearance of $\varphi$ in this subject, and it is the reading that survives contact with the surrounding literature, much of which is not careful.

Reading a heap size instead of a table #

There is a way to decide a position without the list, and it is the most practical thing the golden ratio buys.

Every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers — 12 is $8+3+1$, 30 is $21+8+1$, and no representation ever uses two neighbours in the sequence. Write both heap sizes that way, and the status of the position can be read off the last term of each: a position is cold exactly when one representation ends in an even-indexed Fibonacci number and the other is its shift.

That is the same fact as the formula, in a different alphabet. Multiplying by $\varphi$ is, in this representation, shifting every term one place along the Fibonacci sequence — which is what $\varphi^2 = \varphi + 1$ says when it is applied to a sum rather than a single number.

The practical upshot is that a player can decide a position of any size with arithmetic small enough to do in their head, and does not need the table the first figure drew. That is not true of most games in this subject, where the value of a position of interesting size is out of reach of any exact evaluation.

What the picture cannot show #

The table is finite and the game is not, and the two differ in a way the shading quietly hides.

A drawn board stops at fourteen, so the squares along its top and right edge have had options removed — the moves that would have gone off the board. Their values in the figure are the values they would have in the real game, because every move goes towards the corner and never away from it, so nothing outside the drawn region is reachable. That is a genuine property of this particular game and is why the picture is honest; it would not hold for a game whose moves could increase a coordinate.

What the picture does hide is the irrationality. Any finite patch of shaded squares is consistent with infinitely many slopes, rational ones included, and the eye cannot tell $\varphi$ from a close rational approximation over fourteen rows. The claim that the slope is irrational is not something the figure demonstrates — it comes from the partition argument, and the figure’s job is only to show that the computed zeros and the formula’s pairs are the same set as far as both were taken.

The same caution applies to the strategy. Knowing a square is cold says the player to move loses; it does not name the move, because from a cold square there is no good move to name. Knowing a square is hot does name one, and the figure gives it.

Who found it, and when #

Willem Abraham Wythoff published the game in 1907 in a Dutch journal, under the title of a modification of Nim, and gave both the queen picture and the closed form.

Samuel Beatty’s theorem on the partitioning sequences dates from 1926, so Wythoff found the sequences without the general result that explains why they partition. The two were connected afterwards, which is the usual order of events.

The game turns up under other names — Wyt Queens in Winning Ways, and Tsyanshidzi or “picking stones” in a Chinese tradition that predates the European publication — and the independent appearances are a reasonable sign that the rule is a natural one rather than a construction built to have a pretty answer.

The ladder from here #

This is the base rung of its own anchor, and the ladder above it is unusually concrete.

Later rungs: the proof that the Beatty condition forces the cold set, which is short and worth doing properly. The generalised games with an unequal diagonal and the family of quadratic constants they produce. The Grundy values of the non-zero squares, and why they resist any description as neat as the periodic sequences a one-heap game produces. The connection to Fibonacci representations, in which a heap size written in a base of Fibonacci numbers reveals its status directly. And the misère version, which is worse behaved than the normal-play version by exactly the amount misère play usually costs.

The thing this rung establishes, and which the rest depend on, is that the table came first. The formula was checked against a recursion that had never been told what it was looking for, and that is the only reason the agreement means anything.