15-251: Great Theoretical Ideas in Computer Science Anupam Gupta

Notes on Combinatorial Games (draft!!) January 29, 2012

1 A Take-Away Game
Consider the following game: there are 21 chips on the table. You are challenged by your
arch-enemy to play the following game: you both have to alternate moves, where in each
move, you can take away either 1, 2, or 3 chips from the table. The person who has no more
chips to remove from the table chips loses.
Should you go first or second?
Hmm. Let’s try some small examples. Suppose there were n chips on the table. And if
n = 1, 2 or 3, clearly you should go first: you could pick up all the chips and win! But if
n = 4? Then you should go second: your arch-enemy would have to take away at least one,
but at most three of the chips, leaving you with a winning move! Hence, for n = 4, the first
player loses.
What about n = 5? Note, now, that if you went first, you could take away a single chip,
leaving the game at n = 4 with arch-enemy playing next. Similarly with n = 6 or 7: you
could get the game to n = 4 by removing 2 or 3 chips respectively—whence you would win.
And n = 8? Go second: no matter what arch-enemy does, he will leave behind 5, 6 or 7
chips on the table, you can remove some chips to get it to 4, and the process repeats. The
pattern seems pretty clear by now, so let’s prove the theorem.
Theorem 1.1 Suppose we start off with n chips. Then the first player has a winning strategy
for all n that is not a multiple of 4. For n being a multiple of 4, the second player can always
win, regardless of what strategy the first player plays.
Proof: The proof is by induction. Let’s start with n = 0 (which is a multiple of 4): then
the first player loses. And for n = 1, 2, 3 the first player wins.
Now suppose the theorem is true for all k < n. And suppose n = 4a + b for integers a, b,
where a ≥ 1 and b ∈ {0, 1, 2, 3}. If b 6= 0 (and hence n is not a multiple of 4), then consider
the move that removes b chips. This results in 4a chips on the table, so by the I.H. the next
player will lose. Hence we’ve given a winning strategy for the first player when n is not a
multiple of 4—namely, pick up n (mod 4) chips.
What if b = 0 and n is a multiple of 4. Then no matter how many chips c ∈ {1, 2, 3} the first
player picks up, the second player can remove 4 − c chips and return to a smaller multiple
of 4, which by the I.H. is a loss for the first player. This proves the result. 
Let us call this game TAG3 : the take-away game where one moves at most 3 chips at a time.
Exercise: Consider the game TAGk , where each move consists of removing at least one chip
and at most k chips, for k ≥ 1. For what values of n does the first player have a winning
strategy?
Exercise∗ : Suppose each move consisted of removing either 1 or 3 chips. For what values of
n does the first player have a winning strategy?

1
1.1 A Change of Perspective: You Win if You Can’t Move

What if we changed the rules to say: if it’s your turn and you have no more chips to remove,
you win. In this case, who wins? (Again, each player is allowed to take away 1, 2 or 3 chips
in any move.
Again, simple examples do the trick: n = 0, first player wins. n = 1, the first player has to
remove that one chip, and the second player wins. But now for n = 2, 3, 4, the first player
can remove 1, 2, 3 chips respectively, leaving behind a single chip, causing the next player to
lose! Hence, the pattern suggests that the first player wins for all n that are not of the form
4k + 1.
Exercise: Give a formal inductive proof of the statement the first player has a winning strategy
precisely for all values of n that are not 4k + 1.

2 Combinatorial Games
What’s a combinatorial game? It is a game involving two players (who we’ll often call Alice
and Bob). The game is in some state at any point in time, and this state is known to both
the players. (This is often called perfect information.) In any state, each of the two players
has a set of valid moves, and each of these valid moves causes the state to change to some
other, well-defined state.
The game starts in some initial state, and the players alternate moving. We say the game
has reached a terminal state when there are no valid moves for the player whose turn it is.
In this situation, one of the two players is declared the winner, and the other person the
loser. Notice: there are no draws.
Who wins? Well, under normal rules, The last player to play wins. So if Alice just played,
and Bob’s turn is next but he has no valid moves, then Alice wins and Bob loses. You want
to make sure you always have a valid move to make. However, under misère rules, it is the
opposite: the person who plays the last move loses: to win, you want to make sure the other
person always has a move. In the rest of this lecture we will talk about normal rules games;
however you will see misère games in exercises and homeworks.

2.1 The Take-Away Game

The take-away game in the previous section was a combinatorial game: the states can be
denoted by the numbers 0, 1, 2, . . . , 21. In state i, the valid moves for either player are to
change the state to i − 1, i − 2 or i − 3. (In any state, the set of valid moves are the same,
regardless of whose turn it is next.) Such a game is called an impartial game, as opposed to
“partizan” games. We’ll only study impartial games in this lecture, and our definitions are
only for such games.

2.2 What Are not Combinatorial Games?

Many of the games we play are not combinatorial games, and for various reasons:

1. Combinatorial Games are games of perfect information. Hence, e.g., battleship is not
a combinatorial game.

2
 2. Combinatorial Games are games without any element of chance: when you play a move
in a certain state, you know exactly what the resulting state is, there is no randomness.
Hence, e.g., backgammon or parcheesi or most other board games that involve dice are
not combinatorial games.

3. Combinatorial Games are games without draws: one person wins and the other loses.
Hence, e.g., chess, or tic-tac-toe are not combinatorial games.

However, we’ll see games like Chomp, or Nim, in this lecture, that are combinatorial games.

3 P and N positions
To make our discussion of combinatorial games precise, the definition that helps the most
is that of P -positions and N -positions. An N -position is one where the player to play next
has a winning strategy (and so it is a win for the Next player—hence the “N ”). I.e., he can
win no matter what the other player does. In contrast, a P -position is one where the player
to play next has no winning strategy — hence he will always lose against an adversary who
is playing optimally — so it is a win for the Previous player, which explains the “P ”.
Note that this means that in the take-away game TAG3 where you take away up to 3 chips
at a time, 21 chips is an N -position.

3.1 The Formal Inductive Definition

For a normal form game, we define P - and N -positions as follows:

• All terminal positions are P -positions.

• A position such that all moves from this position lead to N -positions is a P -position.

• A position such that there exists at least one move from this position leading to a
P -position is an N -position.

Note the asymmetry in the defintion: a N -position is one where at least one move leads
to a P -position, but a P -position is one from which there are no moves leading to an P -
position—all of them lead to N -positions.
By the very definition above, we know:

A position is a win for the first player if and only if it is an N -position.

Let us couch our observations about the take-away game in terms of this new terminology:
Example: Consider the take-away game TAG3 : the only terminal position is when there are
zero tokens left, and hence 0 is a P -position. Now 1, 2, 3 are all N -positions, because they
all have a move leading to a P -position. However, 4 can only lead to 1, 2, 3, which are all
N -positions, so it is a P -position.
In general, we inductively prove that n is a P -position if and only if n is a multiple of 4. The
base cases are proved above. Suppose this is true for all k < n. Then for n, if n is a multiple

3
 of 4, then the only positions it leads to are n − 1, n − 2, n − 3, all non-multiples of 4 and hence
N -positions (by the I.H.), so n is a P -position. Else one of n − 1, n − 2, n − 3 is a multiple of 4
and a P -position, so n must be an N -position.

Exercise: Prove that the P -positions for the take-away game TAGk (where you remove at
most k tokens at a time) are precisely those which are 0 mod (k + 1).

4 Chomp!
Consider the following combinatorial game where each position is a finite connected portion
of the positive two-dimensional grid: each square is numbered (x, y) for x ≥ 1 and y ≥ 1.
E.g.,

or

Each move consists of choosing a square (x, y) where x ≥ 1 and y ≥ 1—but not (1, 1) (the
square colored yellow)—and removing all the squares above and to the right of this chosen
square. Note that the terminal position is when only the square (1, 1) remains. E.g., in the
latter example above, one could choose (3, 2) and hence move to:

or choose (5, 1) and hence move to:

4.1 Small Examples

As with most games, it helps to play with some small examples. First, note that if the board
consists only of a single row or column, it is a N -position: the player can play either (2, 1)
or (1, 2) and win.
What about the following small L-shaped piece?

4
It’s a P -position: any move leads to a single row or column, which is an N -position. How
about this one:

It’s an N -position: by removing the top piece (1, 3) we get to the little L-shaped piece above,
which was a P -position. And how about the 2 × 2 square?

Again, removing (2, 2) gets us back to the little L, and hence the 2×2 square is a N -position.
Finally, how about this one:

We claim it is a P -position. Why? Well, the potential moves lead to:

Each of these pieces we’ve already shown to be P -positions.

And what about the position:

It is an N -position—simply because playing the move (3, 1) leads to the position

which we just showed was a P -position.

5
4.2 Chomp Starting at Square Boards

Let’s consider Chomp where the starting position is an n × n square board.

Theorem 4.1 If n > 1, the n × n-square position is an N -position.

Proof: To show this, it suffices to show a strategy for the first player: indeed, she should
play (2, 2) as the first move. Then we’re left with an L-shaped board with equal length arms,

which we claim is a P -position. Indeed, if the arms of the L-shaped piece have non-zero
length, whatever move the second player makes (which is either (1, y) or (x, 1)), the first
player can then play the “mirror-image” of that move (namely either (y, 1) or (1, x) respec-
tively) to get back to an L-shaped board with arms of equal length. Eventually both arms
will be depleted, and the second player will lose.
In other words, the L-shaped position with arms of equal length is a P -position. And hence
the square board is an N -position. 

Exercise: Show that an L-shaped position where the arms have unequal lengths is an N -
position.

Exercise: Bonzo claims that a non-square rectangular shape (i.e., an n×m board with n 6= m)
is a P -position. His argument is that by playing (2, 2), he can move to the L-shaped position
with unequal length arms, which is a N -position. Why is he incorrect?

4.2.1 Mirroring

The strategy we used above—one where we got into a position where we could ensure there
was always a valid move that “mirrored” the other player’s move—is an important strategy
in combinatorial games. This is a simple but surprisingly effective way of showing something
is a P -position: show that whatever the next player does, you can always make another valid
move to prevent him from winning.

4.3 Chomp Starting at Rectangle Boards

You just saw mirroring: we will now see another important proof technique. How to analyze
Chomp on rectangular boards?

6
We know that (2, 2) is not a good first move, since it leads to an N -position. What should
we play?
Well, in this case we don’t know an explicit strategy that shows that all rectangular boards
are N -positions.1 However, we will still prove the following:
Theorem 4.2 The m × n-rectangular position is an N -position as long as not both of n or
m equal 1.

Proof: Since at least one of m, n > 1, consider the move (m, n). The new board looks like:

Either this is a P -position, in which case the rectangular board was an N -position.
Or this is an N -position. So there must be some move (x, y) that leads to a P -position.

But then we could have made the move (x, y) right from the initial rectangular position to
get to the same P -position! So the original rectangular board is an N -position in this case
too!! 
Interesting. We don’t know what the winning first move is, but we know one exists.2 This
proof technique is often called “strategy stealing”: either our first move was a winning one,
or the other player now has a winning move and we can “steal” it!

5 Nim
Nim is another take-away game, but somewhat different from the ones we saw earlier in the
lecture. In Nim there are k piles of chips. In each move we choose one of the non-empty
piles and remove some number of the chips from that pile—at least one chip, at most all the
chips in that pile. The terminal position is when no chips remain.

5.1 A Single Pile

What if k = 1, and we have only one pile of chips? Well, we can just remove all the chips
from that pile, and win. A single pile is thus an N -position.
1
You can give an explicit strategy showing this for 2 × n boards.
2
It remains an open problem to give an explicit winning strategy for the first player.

7
5.2 Two Piles

What if we have two piles, with an equal number x of chips in the two piles. Let’s denote
this by (x, x). Then whatever the first player plays, say removing some chips from the first
pile to make it (y, x), the second player can mirror the strategy to make it (y, y) again. So
the first player loses, and hence (x, x) is a P -position. And since any position (x, y) with
x > y can move to (y, y), this is a N -position. So in two-pile nim, we have a P -position if
and only if both piles are equal.

5.3 Three Piles

This is when it gets interesting. We now consider positions (x, y, z). If any of these were
zero, we would have two piles, so consider x, y, z > 0.
If two piles are equal—say (x, x, z)—we could empty out the third pile to get (x, x, 0), which
is a P -position. So (x, x, z) is an N -position.
But what if x 6= y 6= z??
Hmm.
The thing to do again is to try small examples to see if you detect a pattern; this will require
some time — so let’s cut to the chase.

5.3.1 The Nim-Sum Operation

For naturals x, y, define their nim-sum x ⊕ y to be their sum modulo 2 without carry. Equiv-
alently, it is the bitwise exclusive-or of their binary representations. E.g.:

2 ⊕ 3 = (10)2 ⊕ (11)2 = (01)2 = 1

5 ⊕ 3 = (101)2 ⊕ (11)2 = (110)2 = 6
42 ⊕ 27 = (101010)2 ⊕ (11011)2 = (110001)2 = 49.

Fact 5.1 The following facts are easy to establish:

• Nim-sum is commutative: x ⊕ y = y ⊕ x.

• Nim-sum is associative: (x ⊕ y) ⊕ z = x ⊕ (y ⊕ x).

• For naturals x, y, x ⊕ y = 0 if and only if x = y.

From the second and third properties above, we get

x⊕y =x⊕z
=⇒ x ⊕ (x ⊕ y) = x ⊕ (x ⊕ z)
=⇒ (x ⊕ x) ⊕ y = (x ⊕ x) ⊕ z
=⇒ y = z

8
5.3.2 Bouton’s Theorem

We can now describe the characterization of the P -positions and N -positions of 3-pile Nim:
Theorem 5.2 (Bouton’s Theorem) The position (x, y, z) is a P -position if and only if
x ⊕ y ⊕ z = 0.

The proof is subtle but simple, directly using the definitions of P - and N -positions.
Proof: Define Z to be the set of positions (x, y, z) where x ⊕ y ⊕ z = 0, and N Z be the
other positions. We will show that Z and N Z satisfy the three properties of being the set
of P -positions and the set of N -positions respectively.
1. All terminal positions are P -positions. Indeed, the only terminal position is (0, 0, 0),
which is in Z.
2. All moves from a P -position lead only to N -positions. Consider any state (x, y, z) in
Z—so x ⊕ y ⊕ z = 0. Note that removing tokens from any of the piles (say x → x0 )
gives us x0 ⊕ y ⊕ z 6= 0 = x ⊕ y ⊕ z, by the cancellation property and the fact that
x 6= x0 . So all moves from (x, y, z) ∈ Z lead to positions in N Z.
3. There exists a move from an N -position to some P -position. Consider a position
(x, y, z) ∈ N Z: hence x ⊕ y ⊕ z = w 6= 0. We claim we can choose a pile and some
number of chips to remove from it to get to a position in Z. Since w 6= 0, let the ith
bit be the highest bit set to 1 in w. Since w is the bit-wise XOR of x, y, z, at least one
of these three must have their ith bit set to 1—say it is x.
Now consider x0 = x ⊕ w. We claim this is the binary representation of a number
strictly less than x. Why? Because
X X
x − x0 = 2j − 2j .
j≤i:xj =1,x0j =0 j≤i:xj =0,x0j =1

But, since the first sum contains at least the index i, this is at least 2i − j<i:xj 6=x0 2j ≥
P
j
1. Hence we can remove x − x0 chips from the pile x to get to (x0 , y, z). And moreover,
x0 ⊕ y ⊕ z = (x ⊕ w) ⊕ y ⊕ z = (x ⊕ y ⊕ z) ⊕ w = w ⊕ w = 0, so we have shown how
to get to some position in Z.


5.4 More Piles and Bouton

In fact, Bouton’s theorem easily generalizes to k piles:

(x1 , x2 , . . . , xk ) is a P -position ⇐⇒ x1 ⊕ x2 , ⊕ . . . ⊕ xk = 0.
∗
Exercise : Characterize the P - and N -positions for misère form of Nim.
There are many variants of Nim: you’ll probably see some in homeworks and recitations.
For example here is one of them.
Exercise∗ : Consider a restricted from of Nim, where we are allowed to only remove up to k
chips from the chosen pile. What are the P - and N -positions for this game?

9
6 Extensions and Further Reading
The theory of combinatorial games are intricately connected with Nim. Indeed, one can
show that, in a very precise sense, Nim captures all impartial games in normal form. Much
more about this can be found, e.g., in the book Game Theory by Tom Ferguson (available
online), or the book Winning Ways for your Mathematical Plays by Berlekamp, Conway
and Guy. And if you are interested, you should keep an eye out for the course (one in the
15-859 series of theory “topics” courses) on mathematical games that Alan Frieze and Danny
Sleator teach every couple of years.

7 To Do
• Add more exercises and examples.

• Add (optional) discussion about Nimbers, misère form games, some partizan games?

10