The Game of Nim: Strategies in Combinatorial Game Theory

Nim is a combinatorial game responsible for many advances in game theory. We divide a finite number of coins into a few piles. Two players take coins from any of the piles turn by turn. A player can take multiple coins in one turn, provided they belong to the same pile. The winner is either the player who removes the last coin(s) or the player who has no coins left to take on their turn, depending on the type of Nim being played. Pretty simple, right? Then why was Rory struggling with game theory at Yale? (If you know, you know xD) At its core, game theory is simple- deceptively so. A single glitch can cost a player the entire game. Tiny, seemingly insignificant errors in your game can make it impossible for you to ever win.

Ralph Waldo Emerson summarises it best:

An ounce of action is worth a ton of theory.

Today, for a change, we’ll be “complicating” a deceptively simple topic. Combinatorial game theory has all the spices: lessons in problem solving, decision making, mathematical proofs, tricks, intuition and foresight.

To start, suppose that two players, A and B, are playing the Nim game. Player A makes the first move. Is it possible to construct a winning strategy for A or B? Our goal Is to find a winning strategy for either player. Let us first make some assumptions.

The basic assumptions of Nim and most other combinatorial games are:

• There are two players.

• Players move alternately.

• The game is finite. It eventually ends.

• The game ends when a player cannot move on their turn.

• Rules set restrictions on which game positions each player can move to.
  

We rarely discuss games with infinite sets of positions. For now we shall assume that there is only a finite set of positions available in the game.

Nim is an impartial game, the only distinguishing property between two players being who moves first. Impartially dictates that the set of allowable moves depends only on the position of the game and not on whose turn it is. This differs from partisan games like chess and GO, where the set of allowable moves differs depending on which player moves.

There are two types of Nim play:

• Normal Play: The player who removes the last coin (s) wins.

• Misere Play: The player who is forced to take the last coin(s) loses.

These definitions hold good for impartial games in general: In a normal play game the last person that can make an allowed move wins. We can also define winning strategies for each case.We generally discuss the first case.

Suppose there are two piles X and Y, consisting of 5 and 7 coins respectively.

Let the games begin!

Heaps of Coins

X Y

5 7 A removes 2 from Y

5 5

A makes the number of coins in both piles equal. After every move by B, A can remove some coins to make the number of coins in both piles equal, possibly equal to zero. And just like that, A has the clear advantage and this is obviously a winning strategy. Tough luck, huh? As you'll find out, it's not luck. Every choice in life really is a tradeoff. And your choices will cost you.

If both piles consist of 7 coins then B can utilize this equalizing winning strategy.

Suppose there are three piles, containing 8, 13, and 15 coins. Let us denote the starting position by (8,13,15). Which one of the players A and B has a winning strategy?

How can we construct a winning strategy for one of the players? The first trick is to represent 8, 13, and 15 in binary:

8 = 8+0+0+0 = 1000 13 = 8+4+0+1 = 1101 15 = 8+4+2+1 = 1111

Assume that A decides to take 10 coins from the third pile in the first move. The position after that is (8,13,5).

Now we write out the numbers’ binary expansions, and then use the XOR operation (binary addition without carrying) to sum the two numbers. In this operation adding two zeroes or two ones yields zero. Adding a zero and a one yields one. Representing positions (8,13,15) and (8,13,5) in binary and operating with XOR,

8 1 0 0 0 8 1 0 0 0

13 1 1 0 1 13 1 1 0 1

15 1 1 1 1 5 0 1 0 1

1 0 1 0 0 0 0 0

The elements of the fourth column obtained via the XOR operation are called the nimsums or characteristics of the positions. Hence,

1010, which is 10 in the decimal system, is the nimsum of (8,13,15), and 0 is the nimsum of (8,13,5).

We shall now prove that any winning strategy in Nim involves finishing every move with a nimsum of zero.

First consider the following statements:

• If the nimsum of a position is not equal to 0, there exists a move such that the nimsum of the position after it is 0.

• If the nimsum of the position is 0, and there are coins left in the piles, then every subsequent move leads to a position with a nimsum that is not equal to 0.

Let’s call the event of having a nimsum of zero balanced. Every nonzero nimsum configuration is then imbalanced. If player A’s first move makes the nimsum zero, B’s move definitely imbalances the piles. If A continues to balance on every move, then B is forced to imbalance on every move. Eventually there will be no more balanced piles left and A wins!

Mathematician Charles Bouton was the first to devise a complete strategy for the Nim game, based on the proofs stated above. His 1902 paper birthed combinatorial game theory.

You have unearthed the elementary mathematics behind Nim, but are you really going to calculate the nimsum after every move while playing? Is it possible for you to do so with large and numerous piles? Clearly, we need a better, more general approach to the game- a plan we can easily stick to. Let us study some small sample games and discover a few of Bouton’s strategies for ourselves!

#1 Let’s consider two piles that consist of the same number of coins. Experiment with 2, 3, 4, 5 coins in each pile. If you’re feeling particularly ambitious, try devising a winning strategy for two piles of 10 stones each. Which player has the advantage? Can you generalize for two piles of n stones each?

#2 Generalize for two piles with a different number of coins in them. Which player can devise a winning strategy now?

In the first case the second player has the clear advantage. If A removes x coins from the first pile B should also remove x coins from the second pile. A can now never take the last coin. At some move A removes the last coins from one of the piles. B can now remove all the coins from the other pile. By following this strategy B is guaranteed a win.

In the second game A has a winning strategy. A needs to reverse the game and be able to use B’s strategy in the previous game. How can A do this? By removing stones from the larger pile on the first move such that the number of stones in both the piles is equal A is now in B’s position from the first case. A can now use precisely the same winning strategy to win.

And there you have it! You’ve discovered the secrets of Nim. This theoretical background is sufficient for you to explore many other combinatorial games. Next time you’re on a boring bus ride, you know what to do!

Yes, study other games! But, just to test you, I’ll leave you with this problem first.

Can you devise winning strategies for configurations A, B and C in the image below? Which player has the advantage in each?

If you liked this article, let me know using the contact forms below! Please feel free to email me at arushee.tj@gmail.com with any questions, problems, solutions or suggestions for future blog posts. Until next time :D