Nim
Play Nim and misere Nim against a perfect opponent — and see exactly where the two games differ: only when every pile is down to one counter.
Click a counter to take it and everything to its right in that pile. The computer plays perfectly, so from a losing position it cannot be beaten — it will simply take one counter at a time and wait. Everything runs in your browser; nothing is uploaded.
Exactly where misère departs from normal play
Nim's rule is that the player to move loses, against perfect play, exactly when the pile sizes XOR to zero. Misère Nim — where taking the last counter loses — is usually described as "the same until the end". That is right, and it can be made precise: solve both games over every position up to a size, and see where the answers differ.
| Positions searched | How many | XOR rule correct | Misère rule correct | Games disagree | All piles = 1 |
|---|---|---|---|---|---|
| up to 4 piles of 6 | 209 | all | all | 4 | 4 |
| up to 5 piles of 8 | 1,286 | all | all | 5 | 5 |
| up to 6 piles of 9 | 5,004 | all | all | 6 | 6 |
| up to 4 piles of 15 | 3,875 | all | all | 4 | 4 |
| up to 7 piles of 7 | 3,431 | all | all | 7 | 7 |
The last two columns match on every row. The positions where the two games disagree are exactly those where every pile is down to a single counter — none missing, none extra, across all 13,805 positions solved. That is 0.19% of them.
And the count of disagreements is always the pile limit, never anything to do with how deep the piles are — there is one all-ones position per number of piles. Making the piles fifteen deep instead of six takes the search from 209 positions to 3,875 and leaves the disagreements at four.
So misère is the normal game with one clause added: while some pile still holds two or more, play the XOR rule; once every pile is down to one, invert it. Both rules were checked against a full game-tree search on every position above, and neither missed one.
The two famous setups fall on opposite sides
3-5-7 XORs to 1, so the player who moves first wins it. 1-3-5-7 XORs to 0, so the player who moves first loses — which is the whole trick of the game as played in Last Year at Marienbad. Offer someone the first move from 1-3-5-7 and, playing correctly, you cannot lose.
Worth checking rather than remembering: these two are easy to state backwards, and the pile counts look so similar that the difference is invisible until you take the XOR.
Why an XOR, of all things
The XOR is not a trick peculiar to Nim. Every impartial game has a Grundy value — the smallest number that is not the value of any position it can move to — and a sum of independent games has the XOR of theirs. A heap of n can move to heaps 0 through n−1, so the smallest value it cannot reach is n itself:
| Heap size | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Grundy value | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
A heap's value is just its size — so the XOR of the pile sizes is the Grundy value of the whole position, and "XOR to zero means you lose" is the general theory restated for one game. The row above is computed from the definition on every build, not typed out.
How to use
- Pick a starting arrangement of piles and whether taking the last counter wins or loses.
- Choose whether you move first or second.
- Click a counter to take it and everything to its right in that pile.
- The computer plays perfectly, so a winnable position is the only kind you can win.
- Press Hint to see why the position stands as it does.
Frequently asked questions
What are the rules of Nim?
There are several piles of counters. A move takes any number of counters, at least one, from a single pile. Under normal play the player who takes the last counter wins; under misere play that player loses. There is no luck and no hidden information, so with perfect play the winner is decided by the starting position.
What is the winning strategy?
Take the XOR of the pile sizes — write each in binary and add the columns without carrying. If it is zero, the player about to move loses against perfect play; if not, there is a move that makes it zero, and that move wins. This was checked here against a full game-tree search on 13,805 positions, and it was right on every one.
How is misere Nim different?
Only at the very end, and this page pins down exactly where. Solving both games over the same positions, the ones where they disagree are precisely those in which every pile holds a single counter — none missing and none extra. Everywhere else the two games have the same answer.
So what is the misere rule?
While some pile still holds two or more counters, play exactly as in the normal game: aim to leave a XOR of zero. Once every pile is down to one, invert it — you now want to leave an odd number of piles rather than an even one. That single clause is the whole difference between the two games.
Does making the piles bigger create more differences?
No, and that is the surprising part. The number of positions where the games disagree equals the number of piles allowed, not the pile depth, because there is exactly one all-ones position per pile count. Allowing piles of fifteen instead of six takes the search from 209 positions to 3,875 and leaves the disagreements at four.
Why does an XOR decide a game about counters?
Because of the Sprague-Grundy theory. Every impartial game has a value — the smallest number that is not the value of any position it can reach — and a sum of independent games has the XOR of theirs. A heap of n can reach heaps 0 to n minus 1, so its value is n, which makes the XOR of the pile sizes the value of the whole position.
What is the Marienbad position?
Piles of 1, 3, 5 and 7, played in the film Last Year at Marienbad. It XORs to zero, so whoever moves first loses to correct play — which is why the character who understands it always offers his opponent the first move. The similar-looking 3-5-7 XORs to 1 and is a first-player win.
Does this send anything anywhere?
No. Every game is played and solved entirely in your browser, and nothing is uploaded.
🔒 This tool runs entirely in your browser. Nothing you enter is uploaded, logged, or stored.