Nim

Nim is a combinatorial game for two players. There are many variations of Nim, but the method of play is similar for all variations. A number of objects (you can use counters, toothpicks, matches, marbles, coins, or whatever you happen to have on hand) are divided into two or more heaps. Two players take turns; when it is one player's turn, that player may select any one heap, and remove any number (but not zero) of objects from that heap. The player removing the last counter loses (in some variations, the player removing the last counter wins).

A word about terminology is in order. In combinatorial game theory, a normal play game is one in which the person making the last move (here, taking the last object) wins; a misère game is one where the person making the last move loses. Nim can be played either way, but the "normal" way of playing Nim is as a misère game, not as a normal play game.

The history of Nim is obscure. It first gained the attention of mathematicians in 1902, when C. L. Bouton discussed the theory of the game in a paper in Annals of Mathematics. Due to the simplicity of the game, it is likely games similar to Nim was played before this date, but it is possible that Nim as we know it may only date to Bouton's article. Bouton also gave the game its current name, the origin of which is also obscure, but which resembles the word for "take" in certain Germanic languages.

Here is a sample game of Nim played between two players, A and B, where there are three heaps, of 7, 5, and 3 counters:

*******     *******    
*****       ****        ****        ***         ***
***         ***         ***         ***         *

Initial     A takes 1   B takes all A takes 1   B takes 2
position    counter     counters    counter     counters
            from heap 2 from heap 1 from heap 2 from heap 3


**          *
*           *           *           
A takes 1   B takes 1   A takes 1   B takes 1 counter
counter     counter     counter     from heap 3, and loses.
from heap 2 from heap 2 from heap 2

Given that Nim is a combinatorial game, and given that no draws are possible, it seems intuitive that one player or another should have a winning strategy, and this is in fact the case.

We'll start by analyzing the variation of Nim where a player wins by taking the last counter; it's a bit easier to analyze. Say that the game had only one heap. The first player could win by taking all of the counters. With two heaps, the first player can win by drawing so as to equalize the number of counters in each heap, and continuing to keep them equal on every turn (however, if the two heaps are of equal size initially, the first player must lose). The strategy is similar in the misère game; with one heap, the first player wins by taking all counters but one, and with two heaps, the same strategy applies above except that, when only one counter remains in one heap, the player takes all of the counters in the other heap.

With three (or more) heaps, things get a little more complicated. Before going further, it is useful to note that, in the study of Nim, position are classified as "safe" or "unsafe".

• A safe position is one that, with best play, the player who just moved will win.
• An unsafe position is one that, with best play, the player who just moved will lose.

From a safe position, any move will turn it into an unsafe position, while from an unsafe position, it is always possible to make a move that creates a safe position, although making such a move is not automatic. So, if you create a safe position, your opponent will be forced to create an unsafe position, which makes it possible for you to create a safe position, forcing your opponent to create an unsafe position, and so on until you win the game. So, with two heaps, any position where the numbers of counters in each pile are the same is safe; other positions are unsafe.

Here are a few positions with three heaps, labeled "safe" or "unsafe". Try to see if you can see a pattern before going on: (Note: The three numbers in brackets represent the number of counters in each pile)

• (7, 5, 3): Unsafe
• (6, 4, 2): Safe
• (6, 4, 1): Unsafe
• (5, 4, 3): Unsafe
• (5, 4, 2): Unsafe
• (5, 4, 1): Safe
• (5, 3, 1): Unsafe
• (3, 2, 1): Safe
• (2, 1, 1): Unsafe
• (1, 1, 1): Unsafe (Safe in misère version)

To determine whether a position is safe or unsafe, represent the number of counters in each pile in binary. If the total number of ones over all the numbers in each binary place is even, the position is safe; otherwise it is unsafe. For example, take (5, 4, 1), which is safe. 5 is 101₂, 4 is 100₂, and 1 is 1₂. The number of ones in the ones place is 2, the number of ones in the twos place is 0, and the number of ones in the fours place is 2, so the position is safe.

So, the strategy for the normal play version of Nim is to play to cause a safe position as above. The strategy for the misère version of Nim is similar, except that, when the required move would cause there to be no piles with more than one counter, play to leave an odd number of piles with one counter instead of an even number.