# Wythoff's game

*(Updated January 2006)*

**Wythoff's game** is an impartial game played with two piles of tokens. On each turn, a player removes either an arbitrary number of tokens from *one* pile (between one token and the entire pile), or the *same* number of tokens from both piles. The game ends when both piles become empty. The last player to move is the winner.

Wythoff's game can be represented graphically with a quarter-infinite chessboard, extending to infinity upwards and to the right. We number the rows and columns sequentially 0, 1, 2, .... A chess queen is placed in some cell of the board. On each turn, a player moves the queen to some other cell, except that the queen can only move left, down, or diagonally down-left. The player who takes the queen to the corner wins.

This article is based on my M.Sc. thesis. Look in there for the full details.

### The *P*- and *N*-positions of Wythoff's game

*P*- and

*N*-positions of Wythoff's game

Willem A. Wythoff showed in 1907 that the *P*-positions of this game have a very elegant formula. Let *φ* = (1+√5)/2 be the golden ratio, and let [] denote the floor function. Then the *P*-positions are exactly those of the form

([*φ n*], [*φ*^{2} *n*]) or ([*φ*^{2} *n*], [*φ n*]),

for *n* = 0, 1, 2, ... . All other positions are *N*-positions.

The *P*-positions, therefore, lie roughly along two diagonals, of slopes *φ* and *φ*^{–1}.

### The Sprague-Grundy function of Wythoff's game

Here is the Sprague-Grundy function of Wythoff's game:

The colored entries illustrate how this matrix is calculated. Each entry *G*(*x*, *y*) equals the smallest nonnegative integer that does not appear among the entries directly reachable from (*x*, *y*) according to the game's rules. So the red entry **7** is the smallest nonnegative integer that does not appear among the green entries **0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12**.

Note that the zeros of the Grundy function are the *P*-positions of the game, which we have seen already.

### Notation

Throughout this article we use the convention that cell (*x*, *y*) denotes the cell at row *x* and column *y*. (This is the opposite of the conventional order of coordinates. We apologize...)

### Some facts about *G*

*G*

At first look the function *G* appears quite chaotic. In fact, nobody knows of a simple, closed formula that gives *G*(*x*, *y*) in terms of *x* and *y*. Nevertheless, we *do* know several nice properties of *G*. We already saw one of them: Wythoff's formula for the zeros of *G*.

Here are some further properties of *G*:

Every row (and column) contains each nonnegative integer exactly once.

The same is true of the diagonals parallel to the main diagonal: Every such diagonal contains every nonnegative integer exactly once.

Every row (and column) is additively periodic. Meaning, for every row

*x*there exists a pre-period*n*and period*p*such that*G*(*x*,*y*+*p*) =*G*(*x*,*y*) +*p*for all*y*≥*n*. For example, here is the additive periodicity of row 3 illustrated:

### The sequences of *g*-values

*g*-values

We will now talk about another property of *G*.

Let *g* be a nonnegative integer. Let us take all the *g*-values in the matrix *G*, and discard all those that appear *above* the main diagonal, retaining only those that are located *on* or *right of* the main diagonal.

Arrange these *g*-values according to increasing row. For example, here are the first 4-values:

We denote the *n*-th *g*-value in the sequence by *p*^{g}_{n} = (*a*^{g}_{n}, *b*^{g}_{n}). We start our sequences at *n* = 0. Thus, from the above picture we see:

*p*^{4}_{0} = (*a*^{4}_{0}, *b*^{4}_{0}) = (0, 4)

*p*^{4}_{1} = (*a*^{4}_{1}, *b*^{4}_{1}) = (1, 3)

*p*^{4}_{2} = (*a*^{4}_{2}, *b*^{4}_{2}) = (2, 5)

*p*^{4}_{3} = (*a*^{4}_{3}, *b*^{4}_{3}) = (6, 7)

*p*^{4}_{4} = (*a*^{4}_{4}, *b*^{4}_{4}) = (8, 8)

We already saw that the 0-values are given by *p*^{0}_{n} = (*a*^{0}_{n}, *b*^{0}_{n}) = ([*φ n*], [*φ*^{2} *n*]).

We call the entries above the main diagonal (gray in the above picture) *reflected* *g*-values.

Here are the first 20-values (filled squares) shown alongside the first 0-values (framed squares):

A pattern is immediately evident: The 20-values seem to lie within a strip of constant width around the 0-values. In fact, more than this is true: The *n*-th 20-value in the sequence is within a constant distance to the *n*-th 0-value in the sequence! This is true in general:

**Theorem 1:** For every *g* there exists a constant *k*_{g} such that for all *n*, the *n*-th *g*-value is within Manhattan distance *k*_{g} of the *n*-th 0-value.

We now sketch the proof of this theorem.

### The greedy algorithm for finding the g-values

Given an integer *g*, we can find all the 0-, 1-, 2-, ..., *g*-values of *G* without calculating any larger Grundy values. The basic idea is to use a greedy algorithm, in which we place each Grundy value in the first legal place available, while going through the values 0 through *g* in increasing order.

The algorithm is as follows. We work row by row, finding for each row all its *h*-values, 0 ≤ *h* ≤ *g*, which by definition lie on or right of the main diagonal. Whenever we find an *h*-value, we reflect it with respect to the main diagonal, producing a reflected *h*-value in a higher row, left of the main diagonal.

Suppose we have already found all the *h*-values in rows 0 through *r* – 1, and we now have to calculate row *r*. We do the following successively for *h* = 0, 1, 2, ..., *g*:

If row

*r*already contains an*h*-value left of the main diagonal, then it is clearly illegal to place an*h*-value right of the main diagonal, so we skip this value of*h*for this row:

Otherwise, we place an

*h*-value on or right of the main diagonal,*in the leftmost legal cell we find*. A given cell*C*could be illegal for one of three reasons:There is already an

*h*-value down on*C*'s diagonal.There is already an

*h*-value down on*C*'s column.*C*itself is already occupied by a*k*-value,*k*<*h*.

In the above picture, the first cell starting from the main diagonal is illegal for the first reason. The second cell is illegal for the second reason, and the third cell for the third reason. The fourth cell, however, is legal, so we place in it an *h*-value.

Once we have placed an *h*-value, we reflect it with respect to the main diagonal into a higher row, as shown.

### Occupying the diagonals

Let us number the diagonals parallel to the main diagonal 0, 1, 2, ..., starting from the main diagonal, as follows:

Let *d*^{g}_{n} = *b*^{g}_{n} – *a*^{g}_{n} denote the diagonal occupied by the *n*-th *g*-value, and let us look at how the *g*-values, for a given *g*, occupy the diagonals. For example, here is how the 4-values occupy the diagonals:

As we can see, the 4-values seem to occupy the diagonals *roughly in sequential order*. This turns out to be true for all *g*:

**Theorem 2:** For every *g* the *g*-values occupy the diagonals roughly in sequential order. Namely, for every *g* there exists a constant *δ*_{g} such that for all *n*,

|*d*^{g}_{n} – *n*| ≤ *δ*_{g}.

For comparison, the 0-values occupy the diagonals *exactly* in sequential order:

Our first step in proving Theorem 1 is to prove Theorem 2.

### Skipped diagonals

We say that *g*-value *p*_{m} *skips* diagonal *e* if *p*_{m} lies right of *e*, while *e* has not yet been occupied by any *g*-value preceding *p*_{m}:

By the greedy algorithm described above, *p*_{m} must have skipped diagonal *e* for one of two reasons: Either the intersection of *p*_{m}'s row with diagonal *e* was already occupied by an *h*-value, *h* < *g*, or there is already a *g*-value vertically below this intersection.

To prove Theorem 2, it suffices to show

an upper bound on the number of diagonals a given

*g*-value can skip, andan upper bound on the number of

*g*-values that can skip a given diagonal, before the diagonal is finally occupied.

We omit the details, but it can be shown that:

**Lemma:** No *g*-value can skip more than 2*g* diagonals.

And:

**Lemma:** No diagonal can be skipped by more than 16*g* *g*-values.

The latter lemma is proved using the following result:

**Lemma:** An interval of *k* consecutive rows must contain at least (*k*/3 – 2*g*) *g*-values.

Therefore, we get the following numerical bounds for Theorem 2:

–16*g* ≤ *d*^{g}_{n} – *n* ≤ 2*g*.

### A somewhat "general" theorem

Let us now take a look at the sequences of first and second coordinates of the *g*-values:

*A* = (*a*^{g}_{0}, *a*^{g}_{1}, *a*^{g}_{2}, ...),

*B* = (*b*^{g}_{0}, *b*^{g}_{1}, *b*^{g}_{2}, ...).

Putting together everything we know, we get that *A* and *B* satisfy the following properties:

*A*is a strictly increasing sequence.*B*has no repeated elements.*A*and*B*together cover all the nonnegative integers.There is exactly one nonnegative integer that appears in both sequences. (This corresponds to the

*g*-value occupying the main diagonal.)The expression |

*b*^{g}_{n}–*a*^{g}_{n}–*n*| is bounded for all*n*.

This last property follows from Theorem 2.

It turns out that these properties are enough to imply Theorem 1. We state this in the form of a somewhat "general" theorem, for which we skip the proof:

**Theorem 3:** Let *A* = (*a*_{0} < *a*_{1} < *a*_{2} < ...) be a sequence of increasing nonnegative integers, and let *B* = (*b*_{0}, *b*_{1}, *b*_{2}, ...) be a sequence of *distinct* nonnegative integers. Suppose the following conditions hold:

The intersection of

*A*and*B*is finite.The union of

*A*and*B*is the set of all nonnegative integers.The expression |

*b*_{n}–*a*_{n}–*n*| is bounded for all*n*.

Then the expressions |*a*_{n} – *φn*| and |*b*_{n} – *φ*^{2} *n*| are bounded for all *n*, where *φ* is the golden ratio.

Theorem 3 clearly implies Theorem 1.

### Calculating far-out g-values

We *think* that the trillionth *g*-values for *g* = 0, 1, ..., 20 are given as follows:

As we said, these should be considered as *conjectures*; we do not have absolute proof (only for the case *g* = 0, which can be easily verified).

Now, it is clear that row 10^{12} is *way* beyond the reach of the greedy row-by-row algorithm. So how in the world did we come up with these numbers? And why do we think that they are correct?

The answer lies in a recursive technique, which depends on an unproven *convergence* property.

### A recursive algorithm

Suppose we are given an interval [*r*_{1}, *r*_{2}] of rows, and we wish to calculate all the 0-, 1-, ..., *g*-values that lie within this interval. We do this using the following steps:

We start our calculation a few rows below

*r*_{1}. Namely, for some appropriate constant*R*_{g}, we let*r*_{0}=*r*_{1}–*R*_{g}, and we will attempt to calculate the*h*-values (0 ≤*h*≤*g*) that lie within the interval [*r*_{0},*r*_{2}].We first calculate all the

*reflected**h*-values (lying left of the main diagonal) that lie within the interval of rows [*r*_{0},*r*_{2}]. We do this by taking an appropriate range of columns [*r*′_{1},*r*′_{2}] (where roughly*r*′_{1}≈*φ*^{–1}*r*_{0}and*r*′_{2}≈*φ*^{–1}*r*_{2}) that is guaranteed to contain all these reflected*h*-values, and making a recursive call on [*r*′_{1},*r*′_{2}]:

(Of course, calculating these reflected *h*-values is equivalent to calculating their unreflected originals.)

We assume that the recursive call also gives us, for each *h*, how many reflected *h*-values lie *left* of column *r*′_{1}.

Next we wish to know how many

*h*-values lie*below*row*r*_{0}. We calculate this by working out how many*reflected**h*-values lie below row*r*_{0}, and then complementing to*r*_{0}+ 1.

How many reflected *h*-values lie below row *r*_{0}? All those that lie left of column *r*′_{1} must lie below row *r*_{0} (by the choice of *r*′_{1}). And possibly some of those that lie between columns *r*′_{1} and *r*′_{2} (which we have already calculated) also lie below row *r*_{0}. (All those lying right of column *r*′_{2} must lie above row *r*_{2}, so they also lie above row *r*_{0}.)

Denote the number of *h*-values lying below row *r*_{0} by *k*_{h}.

We

*assume without justification*that the*k*_{h}*h*-values lying below row*r*_{0}occupy exactly the first*k*_{h}diagonals, all other diagonals being empty:

We also assume that none of the cells on row *r*_{0} lying on empty diagonals have an *h*-value vertically below.

Starting from this state of row

*r*_{0}, and using the reflected*h*-values on rows [*r*_{0},*r*_{2}] that we already calculated, we run the greedy algorithm sequentially from row*r*_{0}to row*r*_{2}, knowing exactly which*h*-values to insert in each row.

We *hope* that, despite having initialized row *r*_{0} to an incorrect state, at some point before row *r*_{1} the greedy algorithm will *converge* to the correct state. (By the *state* of a row we mean, roughly speaking, which cells are occupied diagonally and which are occupied vertically in that row, for each 0 ≤ *h* ≤ *g*.)

Once the greedy algorithm converged to the correct state at a certain row, the state of all subsequent rows will necessarily be correct (since the state of row *r* depends only on the state of row *r* – 1 and on which *h*-values are inserted in row *r* – 1).

We output the

*h*-values we obtained for interval [*r*_{1},*r*_{2}].

If convergence did indeed occur by row *r*_{1} (and if the recursive calculation of interval [*r*′_{1}, *r*′_{2}] was also correct), then our calculation for interval [*r*_{1}, *r*_{2}] will necessarily be correct.

This is the recursive algorithm. To find the *n*-th *g*-value for a given *n*, all we have to do is run this algorithm on an appropriate interval around *φn*.

### Measuring convergence

As we can see, the only weak point of our recursive algorithm is the assumption that, for a suitably chosen *R*_{g}, the convergence that we described will always occur within at most *R*_{g} rows, no matter what our starting row *r*_{0} is.

We can test this assumption experimentally for different values of *g*. We do this as follows:

Choose some integer

*r*_{max}, and for each*r*, 0 ≤*r*≤*r*_{max}, precalculate, using the greedy algorithm, the true state of row*r*and the set of*h*-values (0 ≤*h*≤*g*) to insert in row*r*.Go back and test for each

*r*_{0}, 0 ≤*r*_{0}≤*r*_{max}, how many rows convergence takes when starting from row*r*_{0}. Meaning, initialize the state of row*r*_{0}as having, for each 0 ≤*h*≤*g*, all the occupied diagonals before all the empty diagonals (with the appropriate number of occupied diagonals), and no cells occupied vertically.

Starting from this state of row *r*_{0}, run the greedy algorithm row by row, inserting in each row the appropriate *h*-values, until we find that at some higher row *r*_{1} the state of *r*_{1} we are holding equals the correct, precalculated state of *r*_{1}.

The difference *r*_{1} – *r*_{0} is the number of rows it takes for convergence to occur when starting from row *r*_{0}.

We ran the above test for *g* = 0, 1, 2, and 3 using *r*_{max} = 10^{7}. Our findings are as follows:

For

*g*= 0 (not surprisingly) convergence always takes 0 rows, i.e. convergence is immediate.For

*g*= 1 the maximum time to convergence found was 45 rows. In fact, up to row 10^{7}there are 3019 instances of convergence taking 45 rows.For

*g*= 2 the maximum found was 72 rows. Up to row 10^{7}there are 91 instances of convergence taking 72 rows.For

*g*= 3 there is one instance of convergence taking as many as 140 rows.

For higher values of *g* we only ran the test up to *r*_{max} = 10^{6}. The maximum numbers of rows to convergence found are as follows:

The *Convergence Conjecture* is:

**Conjecture:** For every *g* there exists an upper bound *R*_{g} on the number of rows to convergence, when starting from any row *r*_{0}.

Of course, no amount of experimental testing of the kind described above will prove this conjecture for any *g*.