Nim Game

How to play Nim

• The stones are laid out in rows. On your turn, take one or more stones from a single row. Tap a stone to select it and every stone to its right, then press “Take”. The number on the left shows how many stones are left in that row.
• Players take turns. With “Last stone loses”, the usual rule, the player who has to take the last stone loses. With “Last stone wins” (also called normal play), whoever takes the last stone wins.
• Play the computer on Easy, Normal or Hard, or choose 2 Players to share one device. Before your first move you can let the computer go first.
• Play a friend online. Choose “Online”, pick the stones and rule, and create a link. Send it to a friend; when they open it and press Play, the game starts on both devices. The player who made the link goes first in game 1, then you alternate. No sign-up or download needed.
• Choose the layout: the classic 1-3-5-7 pyramid, 3-4-5, a random set of 3 to 5 rows, or the 21 Game: one pile of 21 stones where you take 1, 2 or 3 at a time.
• The Daily puzzle is the same for everyone. You move first against the Hard computer, and the position can be won. Find the winning moves! The computer never slips, so you’ll know right away when a move lets it win.
• On a computer, move between stones with the arrow keys, press Enter or Space to select, T to take, H for a hint, and U or Ctrl+Z to undo. Your game is saved, so you can come back later.

Nim strategy: how to win every time

Nim is solved: one simple calculation tells you whether a position is winning and which move to make. Write the number of stones in each row in binary, then add the columns without carrying: a column is 1 if it has an odd number of 1s. The result is called the nim-sum (the bitwise XOR of the rows).

• If the nim-sum is 0, the player to move will lose against perfect play.
• If it is not 0, there is always a move that makes it 0. Make that move, and your opponent is stuck with a nim-sum of 0 again, whatever they do.

In the 3-4-5 layout the nim-sum is 2, so the first player can win. Taking 2 stones from the top row leaves 1, 4 and 5: 001 + 100 + 101 = 000. With two rows, the rule is easy to see: make the rows equal, then copy each move your opponent makes in the other row.

When the last stone loses, play exactly the same way until your move would leave only rows of a single stone. At that moment, leave an odd number of single-stone rows instead, so your opponent has to take the last one.

In the classic 1-3-5-7 layout the nim-sum is 0 (001 + 011 + 101 + 111 = 000), so the player who moves second can always win. Want to beat the Hard computer? Press “Computer first”.

The 21 Game (take 1 to 3)

In the 21 Game there is one pile of 21 stones and each turn you take 1, 2 or 3. Whatever your opponent takes, you can take enough to make 4 together, so you control the count:

• Last stone loses: always leave 1, 5, 9, 13 or 17 stones. With 21 stones the first player is in trouble, so let the computer start.
• Last stone wins: always leave a multiple of 4 (4, 8, 12, 16, 20). Take 1 on your first move.

It is the same as the counting game where players say 1 to 3 numbers in turn (“1, 2”, “3”, “4, 5, 6”…) and whoever has to say 21 loses: aim to say 4, 8, 12, 16 and 20.

History of Nim

Games of taking stones or matches in turn have been played for a long time, but the name Nim and its complete theory come from the Harvard mathematician Charles L. Bouton, who published “Nim, a game with a complete mathematical theory” in the Annals of Mathematics in 1901. Nim was also one of the first games played by machines: Westinghouse showed the Nimatron at the 1939 New York World’s Fair, and Ferranti built the Nimrod computer for the Festival of Britain in 1951. A version of Nim also appears in the 1961 French film Last Year at Marienbad. In the 1930s Roland Sprague and Patrick Grundy showed that every game of this kind can be played like Nim, which made it the starting point of combinatorial game theory.