Combinatorial Games

Combinatorial games are two-person games with perfect information and no chance moves, and with a win-or-lose outcome. Such a game is determined by a set of positions, including an initial position, and the player whose turn it is to move. Play moves from one position to another, with the players usually alternating moves, until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other is declared the loser.

A simple take-away game

A Simple Take-Away Game. Here are the rules of a very simple impartial combinatorial game of removing chips from a pile of chips.

1. There are two players. We label them I and II.
2. There is a pile of 21 chips in the center of a table.
3. A move consists of removing one, two, or three chips from the pile. At least one chip must be removed, but no more than three may be removed.
4. Players alternate moves with Player I starting.
5. The player that removes the last chip wins. (The last player to move wins. If you can’t move, you lose.)

How can we analyze this game? Can one of the players force a win in this game? Which player would you rather be, the player who starts or the player who goes second? What is a good strategy?

We analyze this game from the end back to the beginning. This method is sometimes called backward induction.

If there are just one, two, or three chips left, the player who moves next wins simply by taking all the chips.

Suppose there are four chips left. Then the player who moves next must leave either one, two or three chips in the pile and his opponent will be able to win. So four chips left is a loss for the next player to move and a win for the previous player, i.e. the one who just moved.

With 5, 6, or 7 chips left, the player who moves next can win by moving to the position with four chips left.

With 8 chips left, the next player to move must leave 5, 6, or 7 chips, and so the previous player can win.

We see that positions with 0, 4, 8, 12, 16, . . . chips are target positions; we would like to move into them. We may now analyze the game with 21 chips. Since 21 is not divisible by 4, the first player to move can win. The unique optimal move is to take one chip and leave 20 chips which is a target position.

Definition of a Combinatorial Game

We now define the notion of a combinatorial game more precisely. It is a game that satisfies the following conditions.

1. There are two players.
2. There is a set, usually finite, of possible positions of the game.
3. The rules of the game specify for both players and each position which moves to other positions are legal moves. If the rules make no distinction between the players, that is if both players have the same options of moving from each position, the game is called impartial; otherwise, the game is called partizan.
4. The players alternate moving.
5. The game ends when a position is reached from which no moves are possible for the player whose turn it is to move. Under the normal play rule, the last player to move wins. Under the misère play rule the last player to move loses.
6. The game ends in a finite number of moves no matter how it is played.

We can also consider games without the sixth condition, i.e. if the game never ends, it is declared a draw. For these notes, however, we will always assume it to be true.

It is important to note what is omitted in this definition. No random moves such as the rolling of dice or the dealing of cards are allowed. This rules out games like backgammon and poker. A combinatorial game is a game of perfect information: simultaneous moves and hidden moves are not allowed. This rules out battleship and scissors-paper-rock. No draws in a finite number of moves are possible. This rules out tic-tac-toe. In these notes, we restrict attention to impartial games, generally under the normal play rule.

P-positions and N-positions

Returning to our simple take-away game, we see that 0, 4, 8, 12, 16, . . . are positions that are winning for the Previous player (the player who just moved) and that 1, 2, 3, 5, 6, 7, 9, 10, 11, . . . are winning for the Next player to move. The former are called P-positions, and the latter are called N-positions. The P-positions are just those with a number of chips divisible by 4, called target positions above.

In impartial combinatorial games, one can find in principle which positions are P-positions and which are N-positions by (possibly transfinite) induction using the following labeling procedure starting at the terminal positions. We say a position in a game is a terminal position, if no moves from it are possible. This algorithm is just the method we used to solve the take-away game above.

1. Label every terminal position as a P-position.
2. Label every position that can reach a labelled P-position in one move as an N-position.
3. Find those positions whose only moves are to labelled N-positions; label such positions as P-positions.
4. If no new P-positions were found in step 3, stop; otherwise return to step 2.

It is easy to see that the strategy of moving to P-positions wins. From a P-position, your opponent can move only to an N-position (3). Then you may move back to a P-position (2). Eventually the game ends at a terminal position and since this is a P-position, you win (1).

Here is a characterization of P-positions and N-positions that is valid for impartial combinatorial games satisfying the ending condition, under the normal play rule. You can use this when analyzing games.

Characteristic Property. P-positions and N-positions are defined recursively by the following three statements.

1. All terminal positions are P-positions.
2. From every N-position, there is at least one move to a P-position.
3. From every P-position, every move is to an N-position. For games using the misère play rule, condition (1) should be replaced by the condition that all terminal positions are N-positions.

Mirroring

Mirroring is an important concept in game theory that will let you invent simple, but powerful strategies for combinatorial games. A mirroring strategy can usually be found in combinatorial games where the game is lost by the player who runs out of valid moves, or by whoever makes the last move; we can show such games have a winning strategy for the second player.

The basic concept is "whatever you can do, I can do." The game must start in a mirror-able position, with the first player moving. We should show inductively that if the first player ever makes a move from a mirror-able position, then the second player can also make a move that brings the board back into a mirror-able position. This means that as long as the first player can still play, the second player can still play as well, implying that the second player can never lose until the first player loses first. A simple example of mirroring can be shown for the game "Chomp" below.

Chomp

A game invented by Fred. Schuh (1952) in an arithmetical form was discovered independently in a completely different form by David Gale (1974). Gale’s version of the game involves removing squares from a rectangular board, say an m by n board. A move consists in taking a square and removing it and all squares to the right and above. Players alternate moves, and the person to take square (1, 1) loses. The name “Chomp” comes from imagining the board as a chocolate bar, and moves involving breaking off some corner squares to eat. The square (1, 1) is poisoned though; the player who chomps it loses.

Here's a version of Chomp on the web.

Square board

The easiest case to analyze is the board (for ). We want to use mirroring. Can you find a first move such that no matter what they do afterwards, you can always mirror their move?

Think about this for a second. After this move, no matter what they do, you'll do something equivalent. Thus, they have to eventually chomp (1, 1) and lose. What move can you make...

Take a look at this:

Now, whichever one they move to, you can just do the same thing on the other side. Eventually it'll come down to (1, 1) and the second player will lose.

Rectangular board

There is a beautiful proof for the board (for ) that shows the first player can win. Its actually an existence proof - it asserts that there is some move the first player can make to get to a P-position, but it doesn't actually tell you what that move is.

If you want to try to find it on your own, keep the following fact in mind.

• Every position is either an N-position or a P-position. If the first player makes a move to a P-position, then he clearly wins. If he moves to an N-position, however, then the second player can move to a P-position and win.

Can you see how to prove the existence of a winning strategy for Player 1?

Take a look at this move:

This is either an N-position or a P-position

• Case: P-position. The first player can win.
• Case: N-position. The second player can now move to a P-position. However, the first player could have made that same move. Therefore, there is some move the first player can make to get to a P-position.

This is a fairly cool proof, and perhaps our first example of a non-constructive existence proof: A proof that asserts the existence of an object with some property P without actually finding or constructing that object.

Nim

The most famous take-away game is the game of Nim, played as follows. There are three piles of chips containing and chips respectively. (Piles of sizes 5, 7, and 9 make a good game.) Two players take turns moving. Each move consists of selecting one of the piles and removing chips from it. You may not remove chips from more than one pile in one turn, but from the pile you selected you may remove as many chips as desired, from one chip to the whole pile. The winner is the player who removes the last chip.

Preliminary Analysis

There is exactly one terminal position, namely (0, 0, 0), which is therefore a P-position. The solution to one-pile Nim is trivial: you simply remove the whole pile. Any position with exactly one non-empty pile, say (0, 0, x) with is therefore an N-position. Consider two-pile Nim. It is easy to see that the P-positions are those for which the two piles have an equal number of chips, (0, 1, 1), (0, 2, 2), etc. This is because if it is the opponent’s turn to move from such a position, he must change to a position in which the two piles have an unequal number of chips, and then you can immediately return to a position with an equal number of chips (perhaps the terminal position).

If all three piles are non-empty, the situation is more complicated. Clearly, (1, 1, 1), (1, 1, 2), (1, 1, 3) and (1, 2, 2) are all N-positions because they can be moved to (1, 1, 0) or (0, 2, 2). The next simplest position is (1, 2, 3) and it must be a P-position because it can only be moved to one of the previously discovered N-positions. We may go on and discover that the next most simple P-positions are (1, 4, 5), and (2, 4, 6), but it is difficult to see how to generalize this. Is (5, 7, 9) a P-position? Is (15, 23, 30) a P-position?

If you go on with the above analysis, you may discover a pattern. But to save us some time, I will describe the solution to you. Since the solution is somewhat fanciful and involves something called nim-sum, the validity of the solution is not obvious. Later, we prove it to be valid using the elementary notions of P-position and N-position.

Nim-sum

The nim-sum of two non-negative integers is their addition without carry in base 2. Let us make this notion precise.

Every non-negative integer can be uniquely represented in base 2 as follows.

for some , where each is either zero or one.

We use the notation to denote this representation of x in base two. Thus, . The nim-sum of two integers is found by expressing the integers to base two and using addition modulo 2 on the corresponding individual components:

Definition. The nim-sum of and is , and we write , where for all k, . Note that this is exactly bitwise XOR.

For example, . This says that .

Since Nim-sum is just addition in mod 2, its both associative ( and commutative (), since addition modulo 2 is. Thus we may write without specifying the order of addition. Furthermore, 0 is an identity for addition (), and every number is its own negative (), so that the cancellation law holds: implies . (If , then , and so .)

Nim-sum has a lot in common with ordinary addition, but what does it have to do with playing the game of Nim? The answer is contained in the following theorem of C. L. Bouton (1902).

Theorem. A position, , in Nim is a P-position if and only if the nim-sum of its components is zero, .

As an example, take the position . Is this a P-position? If not, what is a winning move? We compute the nim-sum of 13, 12 and 8:

Since the nim-sum is not zero, this is an N-position according to Bouton's Theorem. Can you find a winning move? You must find a move to a P-position, that is, to a position with an even number of 1’s in each column. One such move is to take away 9 chips from the pile of 13, leaving 4 there. The resulting position has nim-sum zero:

Another winning move is to subtract 7 chips from the pile of 12, leaving 5. Check it out. There is also a third winning move. Can you find it?

Proof of Bouton's Theorem

Let P denote the set of Nim positions with nim-sum zero, and let N denote the complement set, the set of positions of positive nim-sum. We check the three conditions of the definition above.

1. All terminal positions are in P. That’s easy. The only terminal position is the position with no chips in any pile, and .
2. From each position in N, there is a move to a position in P. Here’s how we construct such a move. Form the nim-sum as a column addition, and look at the leftmost (most significant) column with an odd number of 1’s. Change any of the numbers that have a 1 in that column to a number such that there are an even number of 1’s in each column. This makes that number smaller because the 1 in the most significant position changes to a 0. Thus this is a legal move to a position in P.
3. Every move from a position in P is to a position in N. If is in P and is changed to , then we cannot have , because the cancellation law would imply that . So , implying that is in N.

These three properties show that P is the set of P-positions.

It is interesting to note from (2) that in the game of Nim the number of winning moves from an N-position is equal to the number of 1’s in the leftmost column with an odd number of 1’s. In particular, there is always an odd number of winning moves.