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

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], [φ² n]) or ([φ² 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

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

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⁴₀ = (a⁴₀, b⁴₀) = (0, 4)

p⁴₁ = (a⁴₁, b⁴₁) = (1, 3)

p⁴₂ = (a⁴₂, b⁴₂) = (2, 5)

p⁴₃ = (a⁴₃, b⁴₃) = (6, 7)

p⁴₄ = (a⁴₄, b⁴₄) = (8, 8)

We already saw that the 0-values are given by p⁰_n = (a⁰_n, b⁰_n) = ([φ n], [φ² 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, and

  • an 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 2g diagonals.

And:

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

The latter lemma is proved using the following result:

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

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

–16g ≤ d^g_n – n ≤ 2g.

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₀, a^g₁, a^g₂, ...),

B = (b^g₀, b^g₁, b^g₂, ...).

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₀ < a₁ < a₂ < ...) be a sequence of increasing nonnegative integers, and let B = (b₀, b₁, b₂, ...) 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 – φ² 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¹² 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₁, r₂] 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₁. Namely, for some appropriate constant R_g, we let r₀ = r₁ – R_g, and we will attempt to calculate the h-values (0 ≤ h ≤ g) that lie within the interval [r₀, r₂].

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

(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′₁.

• Next we wish to know how many h-values lie below row r₀. We calculate this by working out how many reflected h-values lie below row r₀, and then complementing to r₀ + 1.

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

Denote the number of h-values lying below row r₀ by k_h.

• • We assume without justification that the k_h h-values lying below row r₀ occupy exactly the first k_h diagonals, all other diagonals being empty:

We also assume that none of the cells on row r₀ lying on empty diagonals have an h-value vertically below.

• • Starting from this state of row r₀, and using the reflected h-values on rows [r₀, r₂] that we already calculated, we run the greedy algorithm sequentially from row r₀ to row r₂, knowing exactly which h-values to insert in each row.

We hope that, despite having initialized row r₀ to an incorrect state, at some point before row r₁ 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₁, r₂].

If convergence did indeed occur by row r₁ (and if the recursive calculation of interval [r′₁, r′₂] was also correct), then our calculation for interval [r₁, r₂] 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₀ 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 ≤ r₀ ≤ r_max, how many rows convergence takes when starting from row r₀. Meaning, initialize the state of row r₀ 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₀, run the greedy algorithm row by row, inserting in each row the appropriate h-values, until we find that at some higher row r₁ the state of r₁ we are holding equals the correct, precalculated state of r₁.

The difference r₁ – r₀ is the number of rows it takes for convergence to occur when starting from row r₀.

We ran the above test for g = 0, 1, 2, and 3 using r_max = 10⁷. 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⁷ there are 3019 instances of convergence taking 45 rows.

  • For g = 2 the maximum found was 72 rows. Up to row 10⁷ 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⁶. 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₀.

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