Winning Wythoff’s game

Molly Ireland

8 November 2024

• Click to share on X (Opens in new window)
• Click to share on Facebook (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Threads (Opens in new window)
• Click to share on Mastodon (Opens in new window)

Are you looking for a new game to beat your friends at? If so, look no further! I’m going to show you a simple game—just two players and one piece on a board—where you will be able to beat your friends every time, meeting a well-known sequence on the way…

Let me introduce you to Wythoff’s game. Named after the Dutch mathematician Willem Abraham Wythoff, it involves moving a queen on a two-dimensional board. If you’ve ever played chess, the movements of a queen will be familiar to you: she can move right, left, up, down and along any of the diagonals until she reaches the boundaries of the board:

Here’s the catch: in Wythoff’s game, the queen can only have some of these moves. She must not move in any way right or up. This gives a reduced set of moves:

So for example, in Wythoff’s game, a move from $(4,3)$ to $(4,2)$ is allowed but moving from $(4,3)$ to $(4,4)$ is banned:

Below are some examples of the moves available when the queen is in different positions on the board. In the diagrams, the queen is allowed to move to any position along the arrows:

On a larger board, the pattern is the same: we’re always only interested in what’s below and to the left of the queen.

How to play

At the beginning of the game the queen is assigned a starting position by both of the players—this could be done by randomly choosing a square on the board or by you each picking your favourite number to get a coordinate.

The rules of the game are as follows:

• Two players take it in turns to move the queen.
• On each turn, a player must move the queen to a different square.
• The player who cannot move the queen on their turn loses the game.

A player loses the game when the queen can’t be moved due to the boundaries on the left-hand side and the bottom of the board. You can try it out and see that this only occurs at the square $(0,0)$. By ending a turn on $(0,0)$ we leave our opponents with no moves and win the game!

A little position analysis

Alright, so $(0,0)$ is the magic square to land on, but how do we make sure we get there before our opponent?

We start by grouping the squares into two groups: the helpful ‘P’ positions and the unhelpful ‘N’ positions:

• N positions are positions from which the next player to make a move will eventually win.
• P positions are positions from which the previous player (who ended their turn by moving to the P position) will eventually win.

Here, $(0,0)$ is a very special P position as the player to move the queen to $(0,0)$ will win the game immediately. The positions which end the game are given the special name of terminal positions.

In our quest to get to $(0,0)$, we should think about the relationship between P and N positions. Let’s define a follower, $x’$, of a position, $x$, as any position that can be reached from $x$ by a player in one turn. For example, $(0,0)$ is a follower of the position $(1,0)$, and is reached by moving the queen one position to the left.

We can now say something about the behaviour of P and N positions:

1. The terminal positions are P positions.
2. All the followers of P positions are N positions (since landing on a P position leads to a win, so the player starting from that position should lose).
3. Every N position has at least one follower which is a P position (which is how the next player will eventually win).

Starting from the terminal position $(0,0)$ and working backwards, we can categorise all the positions on the board of Wythoff’s game in the following way:

Step 1: Begin at the terminal position $(0,0)$ and highlight it blue. This is a P position by 1:

Step 2: Consider all the positions that have $(0,0)$ as a follower. From 2 we know all the followers of P positions are N positions. The positions we are considering all have a P position as a follower so must instead be N positions. Highlight these N positions orange:

Step 3: Move to a position that has not yet been coloured in, but where all the followers of this position have. If all the followers of this position are N positions then by 2 and 3 this must be a P position. If at least one of the followers is a P position then by 2 the position is an N position:

Step 4: Repeat the previous step until all the positions on the board have been coloured.

Filling in the P and N positions of Wythoff’s game for the board here then goes like this:

Tada! Once the P and N positions have been determined, the winning strategy is to always end your go by moving to a P position when possible. Using the P positions like stepping stones, you can reach the position $(0,0)$ and win.

Strategy in action

Time for an example game! Let’s consider the case where the queen begins at $(2,3)$ and that we are the player to move the queen first.

On our first move we move to the P position $(1,2)$:

This leaves our opponent with only N positions to choose from, and they choose to move to $(0,2)$:

We respond by moving to the terminal position $(0,0)$, winning the game and presumably lots of money/drinks/respect:

Are we the champions?

Alright, so you’ve trapped a friend or lured in an innocent bystander to play with you; you are eager to try out your strategy. But before you get too confident, you’ve got to ask yourself one question: are you guaranteed to win (punk)?

If you haven’t already noticed it, go back and see if you can spot the trick to this strategy. The guarantee is real… but you have to get to a P position before your opponent! This means we must be the first player if the queen starts on an N position, or the second player if the queen starts on a P position. Deciding who starts is then what determines the winner of the game if you both know the winning strategy.

If you want to stop your friend uncovering your winning strategy it might therefore be beneficial to deliberately make a few mistakes here and there, throwing them off the scent (or rip out these pages in Chalkdust before you let them borrow it).

With the colour-coded cheat sheet of the board we made earlier, you should be all set to go. But if lugging around a sheet of colourful paper does not appeal to you, it might interest you to take a look at the coordinates of the P positions. These are symmetric and the first of these pairs is $(1,2)$ or equivalently $(2,1)$. The second pair is at $(3,5)$ or $(5,3)$. Feel familiar?

It turns out that a subset of the P positions of the game are given by the positions corresponding to a pair of Fibonacci numbers! All the P positions of the game have coordinates of the form \[(\lfloor n \phi \rfloor, \lfloor n \phi^2 \rfloor)\] and the symmetric equivalent $(\lfloor n \phi^2 \rfloor, \lfloor n \phi \rfloor)$. Here, $\lfloor \cdot \rfloor$ is the floor function which will round the argument down to the nearest integer; and $\phi$ is the golden ratio, which is the number approached by the ratio of consecutive Fibonacci numbers as we tend to infinity. Here are the coordinates of the P positions for $0 \leq n \leq 7$:

This form of the P positions is given in Wythoff’s discussion of the game from 1907, A Modification of the Game of Nim, which you can find and read online.

The proof of this is a rather long proof by induction which I’ll let you try yourself, but essentially you have to show that these pairs satisfy the behaviour of the P and N positions set out in 1, 2 and 3.

What’s next?

A standard chess board is $8\times8$, but the terminal position of our game is only affected by the boundaries of the left and bottom edge of the board. If we extended the standard chess board to have more squares our strategy would remain unchanged. This means you can choose your board to be as large as you want—even infinite!—however you may want it to be a little smaller so that it fits on your coffee table. Here are the P positions on a $16\times16$ board:

If you’re keen to see what happens when you play with multiple queens, check out the book Winning Ways for Your Mathematical Plays, volume 1, by Berlekamp, Conway and Guy. The analysis of P positions for many different games and the behaviour discussed earlier is explored in Thomas Ferguson’s book A Course in Game Theory. For further discussion on how Fibonacci numbers link to the P positions see Around the World in 80 Games by Marcus du Sautoy.

You now have the knowledge to beat your friends! Good luck—but if you decide the starting order, you won’t need it.

Molly Ireland

Molly is a fourth-year mathematician at Durham University studying for her masters, where her favourite areas are mathematical biology, decision theory and, of course, game theory. She loves a puzzle: sudoku, cryptic crossword, … you name it! She is also working on crocheting miniatures of her family’s dogs.

All articles by Molly