Combinatorial Game Theory

What is a “combinatorial game”?

For the purposes of this course we will work with a restricted definition of a combinatorial game – a game which satisfies the following properties:

Two players alternate turns making a move
Every move is defined before it is made (there is no luck or randomness involved and nothing can be hidden from either player)
It is only possible for one person to win and the other to lose, vice versa, or for the game to go on forever (which is considered as a draw)

Then the Fundamental Theorem of Combinatorial Games states that precisely one of these two options must be the case: exactly one of the two players can force a win (i.e. they have a winning strategy), or both players can force the game to go on forever.

Particularly of interest are short games – games that end with some player winning and the other losing after a finite (not necessarily bounded) number of turns – and impartial games – games where the rules for what moves are available do not depend on the player.

Strategy Stealing

One of the easiest ways to win is to copy your opponent. Try playing the following games with a friend.

The game of miséré naughts and crosses is being played on a 4 by 4 grid. Two players take turns placing an X and an O on the grid respectively, and the first person to make a line of 3 consecutive identical symbols loses. Can the first player guarantee a win?

Note: Technically this is not a combinatorial game because it is possible to draw, but this works for the sake of illustration.
A rook is placed at a1 on a chessboard, and two players take turns up or to the right any number of squares. The player who moves it to h8 wins, so which player has a winning strategy?
Alice and Bob have a large pile of identical coins and a small rectangular table (bigger than the size of a coin). They take turns placing coins on the table such that the coins are all entirely on the table and no two coins overlap. The loser is the first player who cannot move. Which player has a winning strategy?

Strategy stealing can be useful even in the case where there is no explicit winning strategy in games which are impartial up to some kind of colouring, by using proof by contradiction. For example, suppose player 2 has a winning strategy, but player 1 can get back to the starting position at the end of their turn, they can now copy player 2's strategy – i.e. they also have a winning strategy, which is a contradiction by the Fundamental Theorem of Combinatorial Games.

Note: neither of these two are combinatorial games because a draw is possible, but these work for the sake of illustration.

The game of Double Chess is identical to normal chess except on each turn each player makes two legal moves. Can player 2 have a winning strategy?
The game of Gomoku is played on a 14x14 grid. On each turn players take turns playing black and white stone respectively on the grid intersections. The first person to make a line of 5 of their colour stone (vertically, horizontally or diagonally) wins. Show that player 1 cannot lose with optimal play.

Winning and Losing Positions

In short games, we can classify every position as either winning or losing. We will call a position winning (technically known as an N-position) if the person whose turn it is to move has a winning strategy, and losing (a P-position) if the person whose turn it is to move has no winning strategy. Then we can make the observation that:

From a winning position, it must always be possible to move to a losing position
From a losing position, all moves must go to a winning position

By working back from the definite winning/losing positions (the ends of the game), we can often work out a pattern in which positions are winning and losing, and from there sometimes a winning strategy.

There are 2019 tokens on the table, and two players alternate taking one, two or three tokens. The person who takes the last token loses. Which player can force a win?
Note: in a way, this problem gives rise to an infinite set of problems. Instead of being able to take {1,2,3} coins, try {positive squares} or {primes numbers and 1} and other similar variants, for example.
Two piles with 20 and 19 jellybeans are on the table. Two players take turns eating all the jellybeans in one pile and splitting the remaining pile into two piles of at least one jellybean. The player who cannot move loses (this occurs when both piles have exactly one jellybean). Which player has a winning strategy?
There are 2019 seeds on the table. Two players alternate taking either 1 seed or half the seeds (rounded up). If the person who takes the last seed wins, which player has a winning strategy?
Note: 2019 is an "easy" number to analyse. For a bit more of a challenge, try solving the general case with any number of seeds.

Nim, nimbers and the Sprague-Grundy theorem

The game of Nim is played as follows:

There are some piles of lollies on the table. Two people alternate turns, and on each turn they select a pile and take some number of lollies from that pile. The person who takes the last lolly wins. Given the initial number of piles and how many lollies are in each pile, who wins with optimal play?

The game with one pile is trivial, and the game with two piles is easily solved with strategy stealing (if this isn't obvious). However, the game with three or more piles becomes more complicated to analyse.

Interestingly, there is a way to solve it, which involves Nim addition, also known as bitwise XOR and represented by the symbol ⊕. To work out a ⊕ b, we compare their binary strings and place 1 where they don't match. For example (using ^ instead of ⊕, which it is in programming):

  a | (5) 101     | (19) 10011      | (43) 101011
  b | (6) 110     | (14)  1110      | (43) 101011
a^b |     011 (3) |      11101 (29) |      000000 (0)

In particular, if there are k piles with x₁, x₂, ..., x_k tokens, the position is winning for the first player if x₁ ⊕ x₂ ⊕ ... ⊕ x_k > 0 and for the second player if that value is equal to 0. It is interesting to prove that these are correct classifications of winning and losing positions (it is useful to note ⊕ behaves like addition in most cases, and that x ⊕ x = 0).

The winning strategy for Nim is therefore to always move to a position whose Nim-value is zero.

Interestingly, this technique can be used for more than just Nim. The Sprague-Grundy Theorem states that in a short game, all positions can be labelled with a number which represents an equivalent Nim value.

This is done by labelling all winning end states as 0 (or losing end states as 1: we can consider them as being a winning position for the next player), then for each state which does not yet have a value but all states it can move to have values s₁, s₂, ..., s_i, assign it the value mex(s₁,s₂,...,s_i) where mex is the minimum excludant function: the smallest non-negative integer which is not in s₁, s₂, ..., s_i.

By doing this, we can "add" two or more short games: if at any turn the player can make a valid move on any game with the player who loses the last game still being played losing, we can take their Nim-values and Nim-add them to work out who has a winning strategy and what it is.

Using this strategy, try to find a pattern to the following games.

In the game of Turning Turtles, there is a line with 19 tails-up coins, and two players alternate making moves. At any turn a player may turn a coin to heads, then if they wish turn over any one coin to its left if there is such a coin. If a player cannot move, they lose. Which player has a winning strategy?
Albert and Barbara play the following game. At the beginning there are some piles of coins on the table, not all necessarily with the same number of coins. The players move in turn and Albert starts. Each player makes one and only one of the following possible moves:
- Removing one coin from a pile; or
- Dividing a pile into two piles, each pile with at least one coin.
The one who takes the last coin wins the game. Depending on the number of piles and on the number of coins that each pile contains at the beginning, find which of the players has a winning strategy.
There is a chessboard with a rook on a2, a pile with 20 tickets in it and the number 19 written on a blackboard. Two players take turns making a move, which consists of either moving the rook up or right (but not both) any number of squares while still remaining on the chessboard, removing some tickets from the pile or replacing the number on the blackboard with a positive number 1, 2 or 3 less than what is already written there. The person who cannot move loses. Which player has a winning strategy?

Miscellaneous Problems

The problems here aren't in any particular order so you'll have to apply the skills you've learnt to solve them.

In the game of Bubbly, there are some non-intersecting bubbles floating in the air, some of which are in some of the other bubbles, and all of them contained inside an outer bubble. Two players take turns choosing a bubble to pop, and they pop that bubble and all bubbles containing it. The person to pop the last bubble wins. Which player has a winning strategy?
In the game of Cartesian Chase, a counter is placed at (1, 1) with the objective of getting to (20, 19). Two players take turns moving either one unit right, one unit up or √2 units diagonally up and to the right, as long as they don't go right of x=20 or above y=19. Which player should win if they play perfectly?
In the game of Chomp, two players have a 20x19 rectangular block of chocolate. They take turns choosing a square of chocolate and eating that square and all squares to the up and right of it (they are facing the same direction). Unfortunately the bottom-right square is poisoned, so the person who eats it loses. Assuming both players play optimally, who wins?
The number 2019 is written on the blackboard. Two players take turns subtracting a proper divisor of the number currently on the blackboard, erasing it and writing the new number. The player who cannot move (i.e. has the number 1 on the board at the start of their turn) loses. Which player has a winning strategy?
Note: A proper divisor of a number is any positive factor of the number less than the number itself.
The game of Hex is played on the following grid. Two players take turns colouring cells red and green respectively. Player 1 wins if they make a red chain from the top side to the bottom side, and player 2 wins if they make a green chain from the left side to the right side. Assuming optimal play from both sides, who wins?
Note: you can assume that a draw is impossible, but this is also interesting to prove.
The game of Kayles is played with a line of counters touching end to end. Two players take turns removing one or two adjacent counters (if two counters, the counters must still be touching each other). The person to take the last counter wins. Which player has a winning strategy?
The game of 2D-Nimbles is played on a checkerboard. Four checkers are on the squares a1, a2, b2 and c4, with two players alternating moving them. At any stage a player can move any counter up or to the right (but not both at once) any number of squares while remaining on the board (including landing on another counter). The person who moves the last token to h8 wins. Which player can win if they play optimally?
Northcott's game is played on a chessboard. The pawns are set up as usual, except two players alternate moving a pawn of their colour up or down its file (column) as many squares as desired as long as it doesn't capture or jump over the other pawn in the column. If a player cannot move, they lose. Does one player have a winning strategy? Who?
The Silver Dollar Game is played on a finite strip of boxes. Some coins have been placed on the strip, and two players take turns moving coins left without jumping over or landing on another coin. The player who cannot move (due to all the coins being at the very left) loses. Determine which player has a winning strategy depending on the position.
The game of Udokus is played on a 9x9 grid divided into 3x3 boxes. Two player take turns placing any whole number from 1 to 9 in an empty cell, such that no two identical numbers are in the same row, column or box. The first player who cannot move loses. Assuming optimal play, who wins?