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 — its nim-sum is six — 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.

The overlap being a single square is the sharpest form of it. If the diagonal move had merely made some positions harder to win, the two cold sets would share most of their members and differ at the edges. They share the corner and nothing else.

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 twenty-two options is what that means at one modest square of a fourteen-square board. That scarcity is what forces the zeros onto a line of their own.

That 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.

It is also a claim over every pair rather than over the pairs anybody looked at, so it is checked that way.

The “at most one to a row” is not a separate observation. A shared row is an attack, so the non-attacking property already forbids two, and the rows holding none are the ones where the two rays have not yet arrived.

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, over the whole of whatever board it was asked for, which is what makes the shading in every board here a report rather than a decoration.

A comparison that can only pass is not evidence, and the obvious thing to ask is what happens with the wrong constant. The silver ratio $1+\sqrt2$ is the near-miss to try — the same kind of number, arriving from the same kind of quadratic — and so is a rational approximation to $\varphi$ itself, which no finite window can distinguish from the real thing. A golden ratio thirty years early runs both and reports where each first misses a zero.

And the contrast with a game that does settle is worth keeping in view. A one-heap subtraction game has an eventually periodic Grundy sequence — always, as a theorem — so a finite window certifies every heap there is. Wythoff’s cold squares are not periodic in either coordinate and never become so: the gaps between consecutive ones follow the golden ratio’s continued fraction rather than repeating, which is what an irrational slope means in a picture made of squares.

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.

Why a game with two moves has such a complicated answer #

Wythoff’s game adds one move to Nim on two heaps — take the same amount from both — and the answer goes from three exclusive-ors to a pair of Beatty sequences. It is worth asking what that one clause did, because the change is out of proportion to the addition.

Two-heap Nim’s cold positions are the pairs with equal heaps, which is a condition on the difference. Every move changes one heap, so it changes the difference, so a player facing equal heaps must break the equality and the opponent restores it. The whole analysis is a mirroring strategy over one quantity.

The diagonal move changes both heaps by the same amount, so it leaves the difference alone. The one quantity the old strategy was maintaining is now maintainable by the opponent too, and the mirror is gone. What replaces it has to be a condition the diagonal move also breaks, which means it has to involve both heaps in a way no single difference or sum can express.

So the complication is not that a move was added; it is that the move added was invariant under the old strategy’s invariant. A third move that changed the difference — take from either heap, twice over, anything — would have left the analysis alone.

That is a useful thing to carry to an unfamiliar variant. Look at what the new move preserves, not at how much freedom it adds. A move that respects the existing invariant destroys the analysis; a move that breaks it, however large, usually does not.

A third description of the same set #

The cold positions have a formula and a table. They also have a digit rule, in a numeral system that has nothing to do with games.

Where the ladder goes next #

wythoff opens here with the game and its cold positions.

A golden ratio thirty years early is where those positions get their closed form, and where the constant turns up thirty years before anybody was looking for it — in a game whose rules contain no geometry, no continuity and nothing that suggests an irrational number. The essay’s argument is that the constant is inherited from a recurrence rather than discovered in the game, which is the reading that keeps it from being a mystery.

The digits say which move wins then changes what the answer is written in, and the change buys two things the formulas do not give. Written in Fibonacci base, a cold position is a statement about digits — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — so the condition is checkable by inspection with no arithmetic on an irrational number anywhere, and it answers a question about a heap of a trillion as easily as one about a heap of five.

And the numeral names the move, which a pair of Beatty sequences does not. A formula for the cold positions tells a player whether they are in one; the digits show which operation reaches the nearest one, because the operation is visible in the representation.

Which is the pattern this site keeps finding and Wythoff’s game is its cleanest instance. The golden ratio is the description and the numeral is the mechanism, and a constant appearing in a description is evidence about the description.