THE GOBLIN’S TREASUREA GAME OF NIM
✦ THE EMERALD HOLLOW Your turn
GRIBBLE, KEEPER OF GEMS

“We take turns. Click one or more gems from one pile, then End turn. Take the last gem to win.”

YOUR MOVE

Click the gems you want to take.

One pile per turn · Click again to deselect
12 gems remain

Game settings

YOUR GAME

Three piles. One ancient puzzle. You move first.

Choosing a challenge starts a fresh game. Close settings to return to the cavern.

How to play

You and Gribble alternate turns. Remove one or more gems from exactly one nonempty pile. You may empty that pile. Whoever takes the final gem wins. Click individual gems in the cavern to select them, then press End turn. Selected gems glow gold. Click a selected gem again to deselect it, or use Clear selection to choose a different pile. You can also Tab to a gem and press Enter or Space. Gribble plays optimally. Use Restart to try another approach.

Reveal the mathematical background

Nim is a finite, impartial game: both players have the same legal moves, there is no hidden information, and every move reduces the total. Charles L. Bouton published its mathematical solution in 1901–1902.

1. Write each pile size in binary

We normally write numbers in decimal, where the place values are 1, 10, 100, and so on. Binary uses only the digits 0 and 1, with place values that double: 1, 2, 4, 8, 16…, reading from right to left. A 1 means “include this value”; a 0 means “leave it out”.

For our piles of 3, 4, and 5 gems, we need just three columns, worth 4, 2, and 1:

Converting the pile sizes to binary
Gems 4s 2s 1s Meaning
3 0 1 1 0 + 2 + 1 = 3
4 1 0 0 4 + 0 + 0 = 4
5 1 0 1 4 + 0 + 1 = 5

So 3 is 011, 4 is 100, and 5 is 101 in binary. The zero at the front of 011 does not change its value; it just keeps the columns lined up.

2. Combine the columns using XOR

The symbol ⊕ means exclusive OR, usually called XOR. For two binary digits, the result is 1 when they are different and 0 when they are the same: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, and 1 ⊕ 1 = 0.

For several numbers, there is an easy shortcut: count the 1s in each column. An odd count gives 1; an even count gives 0. Zero is even too. Each pair of 1s cancels out.

This is not ordinary addition: you never carry anything into the next column. Work on each column separately.

Working out 3 ⊕ 4 ⊕ 5
Number 4s 2s 1s
3 0 1 1
4 1 0 0
5 1 0 1
Count of 1s 2 (even) 1 (odd) 2 (even)
XOR result 0 1 0

The result is 010 in binary. Read it using the same place values: 0 × 4 + 1 × 2 + 0 × 1 = 2. That is why 3 ⊕ 4 ⊕ 5 = 2. The XOR of all the pile sizes is called the nim-sum.

3. Use the result to choose a move

The goal is to leave your opponent a nim-sum of zero. Zero does not mean that there are no gems left: it means every binary column has an even number of 1s.

With piles of 3, 4, and 5, take 2 gems from the first pile, leaving 1, 4, and 5. Their binary forms are 001, 100, and 101. The 4s column now has two 1s, the 2s column has none, and the 1s column has two. Every count is even, so 1 ⊕ 4 ⊕ 5 = 0.

The nim-sum is not generally the number of gems to take; both happen to be 2 in this example. To find a move systematically, XOR each pile size with the nim-sum. If the result is smaller than that pile, reduce the pile to that result. Here, 3 ⊕ 2 = 011 ⊕ 010 = 001 = 1, so reduce the first pile from 3 to 1.

A nonzero nim-sum means the player whose turn it is can force a win by leaving zero after every move. A nonempty position with nim-sum zero is losing for the player about to move if the opponent plays perfectly. It is not an immediate loss; an opponent's mistake can still give you a chance.

Why it works

If the sum is S and a pile changes from a to b, the new sum is S ⊕ a ⊕ b. When S = 0, every legal change makes this nonzero, since a ≠ b. When S ≠ 0, choose a pile a with a 1 in S’s highest set bit and set b = a ⊕ S. Then b < a, so the move is legal, and the new sum is 0. Repeating this eventually leaves all piles empty after your move.

At university level, interpret XOR as vector addition over the field with two elements, and investigate the Sprague–Grundy theorem, which connects other finite impartial games to Nim.

Learn more: University of Toronto’s Nim strategy ↗

The game works offline. The further-reading link needs an internet connection.