Rows of marks. On your turn, cross out as many as you like from one row — one, several, the whole row. Whoever takes the last mark wins.
That is the entire game, and it has been completely solved since 1901. Not solved in the sense of a computer worked it out — solved in the sense that one line of binary tells you the right move in every position that will ever arise, and you can learn it in about four minutes.
How to play Nim
Nim is a two-player game. Play a friend opens a table with a short code; send the code to anyone and they join from their own device, with a chat box for the arguing. Computer is the solo version, with three opponents.
One deliberate difference between them: against the computer the binary table starts open, because that is what the page is for and the machine knows the answer anyway. Against a person it starts closed — whoever can see it wins, and two people both reading it are not playing a game. The button is still there if you want to learn it together.
The table beside the board
A solved game makes a thin opponent. Set the computer to Perfect and it cannot be beaten from a position that was lost when you arrived at it; set it lower and you are playing against something deliberately worse.
What is worth your time is the binary table. It shows each row in binary, the count of ones in each column, and the one column that has gone odd — which is where the winning move lives. Play a few games watching it and the strategy stops being a rule you remember and becomes something you can see.
Then open a table, send someone the code, leave the table closed, and find out whether you actually learned it.
Nim strategy: how to find the winning move
Write each row length in binary, one under the other. Count the ones in each column. If every column is even, whoever is to move has already lost. If some column is odd, there is at least one winning move.
To find it: look at the leftmost odd column, pick a row with a 1 there, and reduce that row until every column comes out even. There is always such a move, and the arithmetic is easier than it sounds — the target size for that row is the exclusive-or of all the other rows.
Then do it again next turn, and every turn. Your opponent is handed an all-even table each time, and from an all-even table every possible move breaks some column. They cannot help but hand it back broken.
Why 1-3-5-7 is already lost for whoever starts
The board everybody draws is not a neutral starting point.
1 ⊕ 3 ⊕ 5 ⊕ 7 = 0. The classic arrangement is a lost position for the player who goes first, which puts the traditional courtesy of offering your opponent the first move in a rather different light.
If you want a fair game, use 3-4-5, or any set of rows whose nim-sum is not zero. Both are on the page.
Misère Nim: the ending that catches everyone
Agree beforehand whether taking the last mark wins or loses. The version where it loses is misère Nim — the game played in Last Year at Marienbad, which is why it turns up under that name.
The good news is that you barely have to learn anything new. The surprising part is how little.
Of the 2,400 positions we checked, 2,385 behave identically under both rules. Only 15 differ, and every one of those consists of nothing but rows of a single mark.
So the rule is: play misère Nim exactly like normal Nim — the nim-sum still decides everything — right up until no row has more than one mark left. At that moment the rule inverts. With only single marks on the table, you want to leave your opponent an odd number of them, because they must take one each turn and the last one is fatal.
That single-sentence exception is why almost everybody plays misère Nim correctly for twenty moves and then loses it in the last three.
The strategy most people know is only half of one
Ask someone who has played Nim what the trick is and you will usually hear: get the rows into equal pairs, then copy whatever the other player does. That is genuinely part of the truth, and it works surprisingly well — but only in one of the two versions.
We built that player and measured it. Starting from positions that were already won, the pairing strategy converts 51.5% of them in the normal game — a real, useful half-theory.
In misère it converts 0.3%, which is no better than moving at random.
The reason is exactly the exception above. Pairing carries you faultlessly to the endgame and then walks you straight into it: the last few single marks are precisely where the misère rule flips, and pairing has nothing to say about them. It is a good illustration of a general hazard — a rule of thumb that works can be worse than no rule at all, because it gets you confidently to the place where it fails.
Why every impartial game is secretly Nim
This is the reason Nim is in the textbooks rather than the toy shops.
An impartial game is one where both players have exactly the same moves available from any position, and nothing is hidden or random. Nim is impartial. So is a game where you remove coins under some other restriction, and so are a great many others.
The Sprague–Grundy theorem — found independently by Roland Sprague in 1935 and Patrick Grundy in 1939 — says that every impartial game position is equivalent to a single heap of Nim of some size. Not similar to: equivalent to. Work out that size, and everything you know about Nim transfers over wholesale, including the nim-sum trick for adding several games together.
Nim is therefore not one solved game among many. It is the thing all the others turn out to be.
Who invented Nim?
The game is old and its history is mostly unwritten; versions of it were played in China and around Europe long before anybody explained it. What is precisely dated is the solution: Charles Bouton, at Harvard, published Nim, a game with a complete mathematical theory in 1901. He gave it the name too, and suggested it comes from the German nimm — take.
In 1940 the Westinghouse company built the Nimatron, a relay machine that played Nim against visitors at the New York World's Fair. It was one of the earliest game-playing machines anybody built, and it won most of the time, which is not surprising: it knew the one thing there is to know.
If you would like the version with a pencil, there are printable Nim sheets — and if the idea of a game whose answer is known before you start appeals, the Towers of Hanoi does the same trick with arithmetic instead of binary.
