Nim Game: Rules and the Winning Strategy Explained Simply
Nim is a two-player game with a few piles of coins, matches or sweets. It takes seconds to learn, and it is one of the few games where a simple trick tells you, from any position, whether you can force a win. Here are the rules, the winning strategy explained without heavy maths, and some easy variations.
Rules
- Set out a few piles of objects, for example piles of 3, 4 and 5.
- Decide who starts with a coin flip.
- On your turn, take as many objects as you like from one pile, at least one.
- Players take turns. Whoever takes the last object wins.
In the other common version, called misère Nim, whoever takes the last object loses. The strategy for both is almost the same, as shown below.
The Winning Trick, Simply
Split every pile size into the numbers 1, 2, 4, 8 and so on (each used at most once). Then cross out matching pairs across all piles. Whatever is left over tells you who is winning:
- Nothing left over: the player about to move will lose if the opponent plays perfectly.
- Something left over: the player about to move can win, by taking objects so that nothing is left over.
Take piles of 3, 4 and 5:
| Pile | Split |
|---|---|
| 3 | 2 + 1 |
| 4 | 4 |
| 5 | 4 + 1 |
| Left over | 2 |
The two 4s cancel and the two 1s cancel, leaving a 2. So the first player can win: take 2 from the pile of 3, leaving 1, 4 and 5. Now everything cancels, and whatever the opponent does, you can make it cancel again. Mathematicians call this left-over value the nim-sum; it is the binary XOR of the pile sizes.
Who Wins These Starting Positions?
We checked each of these by computer, trying every possible game:
| Piles | Left over | Mover |
|---|---|---|
| 1, 2, 3 | 0 | Loses |
| 2, 2 | 0 | Loses |
| 1, 3, 5, 7 | 0 | Loses |
| 3, 4, 5 | 2 | Wins |
| 4, 5, 6 | 7 | Wins |
“Mover” is the player whose turn it is. When the left-over value is 0, the second player wins with perfect play, so offer to go second.
Playing Misère Nim
If taking the last object loses, play exactly the normal strategy until your move would leave only piles of size 1. At that point, leave an odd number of single-object piles instead of an even one, so your opponent is forced to take the last one.
Easy Variations
- One pile, take 1 to 3: start with 21 objects and let each player take 1, 2 or 3. If the last taker wins, always leave a multiple of 4.
- Random piles: use a random number generator to set the size of each pile, so neither player can prepare.
- Coins on a table: pennies or sweets work fine; let the winner eat the sweets.
- Lines of matches: the classic 1, 3, 5, 7 rows; with perfect play the second player wins.
Where Nim Comes From
Games of taking objects from piles are very old, and their exact origin is unknown. The name Nim and its full solution come from the mathematician Charles Bouton, who published the strategy in 1901. If you like small games with a hidden trick, try dots and boxes or tic tac toe.
For a guessing game where a smart search beats luck, see our Battleship strategy guide.
FAQ
How do you play Nim?
Set out a few piles of objects. Players take turns removing any number of objects from one pile, and whoever takes the last object wins (or loses, in misère Nim).
What is the winning strategy for Nim?
Split each pile size into 1s, 2s, 4s and 8s, cancel matching pairs, and move so that nothing is left over. This is the nim-sum, or binary XOR, of the piles.
Who wins Nim with piles of 1, 3, 5 and 7?
The second player, with perfect play, because the nim-sum of 1, 3, 5 and 7 is 0.
How do you win the 21 game?
If each player takes 1, 2 or 3 and the last taker wins, always leave a multiple of 4. From 21, the first player takes 1 to leave 20.
What is misère Nim?
A version where taking the last object loses. Play the normal strategy until only single-object piles would remain, then leave an odd number of them.