(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 gameWillem 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 gameHere 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. NotationThroughout 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 GAt 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:
The sequences of g-valuesWe 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 pgn = (agn, bgn). We start our sequences at n = 0. Thus, from the above picture we see: p40 = (a40, b40) = (0, 4)
We already saw that the 0-values are given by p0n = (a0n, b0n) = ([φ 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 kg such that for all n, the n-th g-value is within Manhattan distance kg of the n-th 0-value. We now sketch the proof of this theorem. The greedy algorithm for finding the g-valuesGiven 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:
Occupying the diagonalsLet us number the diagonals parallel to the main diagonal 0, 1, 2, ..., starting from the main diagonal, as follows:
Let dgn = bgn – agn 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, |dgn – 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 diagonalsWe say that g-value pm skips diagonal e if pm lies right of e, while e has not yet been occupied by any g-value preceding pm:
By the greedy algorithm described above, pm must have skipped diagonal e for one of two reasons: Either the intersection of pm'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
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 ≤ dgn – n ≤ 2g. A somewhat "general" theoremLet us now take a look at the sequences of first and second coordinates of the g-values:A = (ag0, ag1, ag2, ...),
Putting together everything we know, we get that A and B satisfy the following properties:
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 = (a0 < a1 < a2 < ...) be a sequence of increasing nonnegative integers, and let B = (b0, b1, b2, ...) be a sequence of distinct nonnegative integers. Suppose the following conditions hold:
Then the expressions |an – φn| and |bn – φ2 n| are bounded for all n, where φ is the golden ratio. Theorem 3 clearly implies Theorem 1. Calculating far-out g-valuesWe 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 1012 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 algorithmSuppose we are given an interval [r1, r2] 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:
Measuring convergenceAs we can see, the only weak point of our recursive algorithm is the assumption that, for a suitably chosen Rg, the convergence that we described will always occur within at most Rg rows, no matter what our starting row r0 is. We can test this assumption experimentally for different values of g. We do this as follows:
We ran the above test for g = 0, 1, 2, and 3 using rmax = 107. Our findings are as follows:
For higher values of g we only ran the test up to rmax = 106. The maximum numbers of rows to convergence found are as follows:
The Convergence Conjecture is: Conjecture: For every g there exists an upper bound Rg on the number of rows to convergence, when starting from any row r0. Of course, no amount of experimental testing of the kind described above will prove this conjecture for any g. |
Fun > Impartial games >