Play Nim Online

The winner is decided before anyone moves

Nim is unusual among the games here: it is completely solved. Not “computers play it very well” — solved, in 1901, by Charles Bouton, with a rule you can apply in your head. Every position is either won or lost from the outset, and the only question is whether both players know which.

Write each heap in binary, stack them in columns, and ask of each column: is the number of 1s odd? If no column is odd, the position is balanced and the player about to move loses. If any column is odd, the player about to move can win, and can always do it by making every column even again.

Which starting position you pick decides who wins

This is the part worth knowing before you play. Of the four starting positions on this page, three are already won for whoever moves first — you — and one is not.

The default, 1–3–5–7, is the classic balanced position — and it is the one you cannot win against an opponent who knows the rule. If you want a game you can actually take, pick any of the other three and move first. If you want to see the theorem work against you, stay where you are.

How to actually apply the rule

You do not need to write anything down. Work down the place values — 8s, 4s, 2s, 1s — and for each one count how many heaps contain it.

Find the highest odd column. That is the one you must fix, and it tells you which heap to take from: it has to be a heap that contains that value, because only those can change it.

Then fix every lower column at the same time. Having chosen the heap, there is exactly one size to leave it at, and the arithmetic gives it to you directly: combine your target heap with the odd columns, and the answer is what to leave behind. Because the highest odd column is being switched off, the number always comes out smaller than the heap you started with — which is why a legal move always exists.

Then just keep restoring balance. Once you have handed over a balanced position, every move your opponent makes must unbalance it, and you rebalance it. The heaps shrink, the position stays balanced on their turn, and they run out.

Misère: the same game until the very end

Under misère rules, taking the last object loses. It sounds like it should invert everything. It changes almost nothing.

Play the identical balancing strategy right up until the moment your opponent's next move would leave every remaining heap holding a single object. At that point — and only that point — the rule flips: instead of leaving an even number of single heaps, leave an odd number, so that they are the one who must take the last. Everything before that transition is ordinary Nim.

Where players go wrong

Taking the largest heap because it is largest. Size is not the point; the columns are. Clearing a big heap often hands over a balanced position by accident.

Taking whole heaps. Emptying a heap is only correct when it is the move the arithmetic points to. Most of the time the right move leaves something behind.

Trying to compute from a lost position. If the position is balanced when it is your turn, there is no winning move — not a hard one, none at all. Your only hope is to make the position complicated and wait for a mistake. Take one object from the largest heap and keep the game going.

What was verified on this page

The Nim-sum rule was checked against a full exhaustive search — a solver that evaluates every position by playing out every continuation, and never mentions binary or XOR at all. The two agree on every one of the 714 positions reachable from the four presets, and on all 2,401 positions of four heaps up to seven objects, in both the normal and misère variants. The closed-form rule and brute force give identical answers everywhere.

The Hard AI was then played out in full: 960 complete games against an opponent driven by that exhaustive solver rather than by the theorem. It never once lost a game it started in a winning position, under either variant, and every move it chose from a winning position was checked to be genuinely winning — 622 such positions under normal rules, 618 under misère.

The easier settings were measured too. Easy plays randomly four times out of five and a perfect opponent beats it every game; Medium is random two times in five and loses 98% of the time. Both labels are honest.

Nim, and why it matters more than it looks

Bouton's 1901 solution was the first complete mathematical treatment of a game, and it turned out to be far more than a curiosity. Every impartial game — one where both players have the same moves available — is equivalent to a single Nim heap of some size. That result, the Sprague–Grundy theorem, means solving Nim solved an entire class of games at once.

Which is the appeal of it: a game simple enough to explain in a sentence, whose answer is a piece of arithmetic that generalises to games you have never heard of.

More games like this

If you like games where the right move can be calculated rather than guessed, try these: