Brain Games
All games
Brain Games › Games › Heaps
Heaps
Board · Classics · plays in your browser, no download
A few heaps of counters. On your turn you take as many as you like — but from one heap only. Whoever takes the last counter wins. It is the oldest completely solved game there is, and the solution is a piece of binary arithmetic you can do in your head.
Where it comes from
The game is old and probably Chinese — it closely resembles jiǎn-shízǐ, “picking stones” — but its real date is 1901, because that is when it stopped being a pastime and became mathematics.
Charles L. Bouton, at Harvard, published the complete theory that year: not a strategy, not a set of tips, but a proof covering every possible position of every possible game. He also gave it the name. Where nim comes from was never properly explained; the Oxford English Dictionary points at German nimm, “take”, and there is an obsolete English verb nim meaning the same thing.
What matters is what the proof turned out to be worth. The theory built on Nim — the Sprague–Grundy theorem — says that every game of this kind, however complicated it looks, is secretly a game of Nim. A pile of counters is the atom that the whole of combinatorial game theory is built out of. That is a large return on a game you can explain in one sentence.
The trick
Write each heap size in binary and add the columns without carrying — which is the same as exclusive-or. The answer is called the nim-sum.
If the nim-sum is not zero, you are winning: there is always a move that makes it zero, and you should play it. If the nim-sum is zero when it is your turn, every move you make will break it, and against somebody who knows this you have already lost.
The classic three-heap setup of 3, 5 and 7 has nim-sum one. So the first player wins — by taking a single counter, from the heap of three, which looks like the most timid move on the board.
| Taking | As many as you like, from one heap, at least one. |
|---|---|
| Winning | Take the last counter. |
| Misère | In the reversed version, the player who takes the last counter loses — and the strategy is the same until the very end, which is the only moment it changes. |
Our version
Heaps you can see and count, and an opponent that knows the nim-sum. You will not beat it from a losing position, and from a winning one you only have to not slip.
Three things that help
Two equal heaps is a death sentence — for whoever moves. Mirror everything your opponent does and you take the last counter. This is the whole theory in miniature.
Do the binary on the big heaps only. Small heaps rarely change the nim-sum. Find the largest heap, and ask what it would have to become.
Watch the endgame switch. In misère play you follow the normal strategy right up until heaps of one are all that is left, and then you do the opposite. Getting that moment wrong loses a won game.