Nim is won by leaving your opponent a position whose nim-sum is zero: split every heap into 4s, 2s and 1s, cross out equal pieces in pairs, and move so that nothing is left over. On this page you move first, and on the two lower levels every one of the 2,401 possible starting layouts is a win for you — the formula wins 100% of those games. On the “rigged start” level all 350 layouts are lost and the win rate is exactly 0%. The “makes mistakes” level misses its winning move on about 38% of its turns, so even after one slip you still win about three games in four.
The textbook says: write the heaps in binary and XOR them. You do not need binary for that. Every number is a sum of different powers of two in exactly one way, and with heaps of up to seven stones the only pieces are 4, 2 and 1: 7 = 4+2+1, 6 = 4+2, 5 = 4+1, 3 = 2+1.
| Heaps | Split | 4s | 2s | 1s | Left over (nim-sum) |
|---|---|---|---|---|---|
| 3, 5, 7 | 2+1, 4+1, 4+2+1 | two, cancel | two, cancel | three, one left | 1 |
| 7, 6, 4 | 4+2+1, 4+2, 4 | three, one left | two, cancel | one left | 4+1 = 5 |
| 3, 5, 6 | 2+1, 4+1, 4+2 | two, cancel | two, cancel | two, cancel | 0 |
| 4, 6, 7, 2 | 4, 4+2, 4+2+1, 2 | three, one left | three, one left | one left | 4+2+1 = 7 |
Bouton's theorem is about that leftover. If it is zero, the player to move loses against correct play; if it is not, the player to move can make it zero and wins. Zero positions are the ones to hand to your opponent: any move from a zero position breaks a pair, and the other side can always restore it.
In practice you only count parity: is the number of heaps containing a 4 odd or even? The same for 2 and for 1. Three quick looks at the board, no arithmetic.
Once you know the leftover pieces, the winning move takes three steps:
Example: 7, 6, 4 leaves 4+1. The heap of 6 = 4+2 contains the 4 but not the 1: remove the 4, add the 1, and you get 2+1 = 3. So take three stones from the heap of six: 7, 3, 4 has nothing left over.
| Position | Left over | Winning moves |
|---|---|---|
| 3, 5, 7 | 1 | take one stone from any heap: 3→2, 5→4 or 7→6 |
| 2, 5, 6 | 1 | 5→4 only (the 5 is the only heap containing a 1) |
| 7, 6, 4 | 4+1 | 7→2, 6→3 or 4→1 |
| 1, 3, 5, 6 | 1 | 1→0, 3→2 or 5→4 |
| 4, 6, 7, 2 | 4+2+1 | 4→3, 6→1 or 7→0 |
| 1, 1, 3 | 2+1 | 3→0 only |
The number of winning moves is the number of heaps that contain the biggest leftover piece, so it is always odd. On this page a starting layout has exactly one winning first move in 49.4% of games and exactly three in 50.6%. A start offers 14 legal moves on average and only 14.5% of them win, which is why guessing does not work.
With three heaps it also helps to know the zero positions by sight. With heaps of one to seven stones and three different sizes there are only seven: 1-2-3, 1-4-5, 1-6-7, 2-4-6, 2-5-7, 3-4-7 and 3-5-6. Two equal heaps on their own are zero as well, and from there you simply copy every move of the opponent in the other heap.
Here is one game from the start 3, 5, 7 against the level that plays the formula. Each row is your turn; the computer's replies are one possibility of many, because from a zero position it has no good move and takes stones at random.
| Before your move | Split | Left over | Your move | The computer then |
|---|---|---|---|---|
| 3, 5, 7 | 2+1, 4+1, 4+2+1 | 1 | one from the first heap: 2, 5, 7 | takes four from the third heap: 2, 5, 3 |
| 2, 5, 3 | 2, 4+1, 2+1 | 4 | 5→1, four stones: 2, 1, 3 | takes the whole third heap: 2, 1 |
| 2, 1 | 2, 1 | 2+1 | 2→1, one stone: 1, 1 | takes one of the two stones: 1 |
| 1 | 1 | 1 | the last stone | – |
The third row shows the rule at its smallest: the leftover is 2+1, the heap of two contains the 2 but not the 1, so it loses the 2 and gains the 1 and becomes a heap of one. Two equal heaps are left, and whatever the computer does, you take the rest.
The trainer under the game drills exactly this step, one position at a time, with heaps of up to nine stones, so an 8 appears among the pieces there. It opens after your first finished game.
You always move first. The game deals three or four heaps, equally often, of one to seven stones each, and what happens next depends on the level.
| Level | How the start is made | Possible layouts | Won for you, the first player |
|---|---|---|---|
| makes mistakes | random, redealt while the nim-sum is zero | 301 with three heaps, 2,100 with four | all 2,401 |
| plays the formula | the same | the same 2,401 | all 2,401 |
| formula + rigged start | the last heap is replaced so that the nim-sum is zero | 350 | none |
Layouts are counted with the order of the heaps. Without the redeal, a random layout would be lost for the first player in 12.2% of three-heap games and 12.5% of four-heap games; the page throws those away, so on the two lower levels you are winning before your first move in every single game, with 3 to 27 stones on the table, 14 on average.
On the rigged level the page drops the last heap and puts in exactly the heap that makes the nim-sum zero. Every one of the 350 layouts is lost for the player to move, and since this level never errs, your win rate there is exactly zero. It is a demonstration, not a contest.
A detail of the rigged start: in 2.2% of games it deals a heap of 8 and a heap of 15 (8, 7, 15, or 8 and 15 with two heaps between them that add up to 7), so the pieces there include an 8. The classic 1, 3, 5, 7 can turn up on this level too, and it is a zero position: 1, 2+1, 4+1, 4+2+1 cancel completely.
The three levels differ in two things only: whether the computer ever misses its winning move, and whether the start is rigged. In a zero position all three do the same thing — pick a heap at random and take a random number of stones from it — so the computer's moves tell you nothing when you are winning.
Here is what simple ways of playing score, as exact probabilities of winning with you to move first:
| How you play | makes mistakes | plays the formula | rigged start |
|---|---|---|---|
| The formula on every move | 100% | 100% | 0% |
| A random legal move | 24.1% | 1.8% | 0% |
| Always take the whole largest heap | 34.6% | 7.1% | 0% |
| Always take one stone from the largest heap | 21.4% | 0.9% | 0% |
| Endgame only: one heap — take it all, two heaps — make them equal, otherwise at random | 52.7% | 6.3% | 0% |
| A wrong first move, then the formula whenever a winning move exists | 75.7% | 0% | – |
The last row is the answer to “how many chances do I get”. Against the level that makes mistakes, every turn it has while it is winning is a chance of roughly 38% that it hands the game back, and once it does, the formula finishes the job. So when you are lost, play for time: take a single stone from the largest heap and check the leftover again after every reply. That is the 75.7% in the table; the best possible play scores 77.5%, and moving at random while you wait only 66.4%.
The last row averages over every wrong first move, each equally likely, in every start that has one. The only start with no wrong move is 1, 1, 1.
This page plays normal Nim: whoever takes the last stone wins. In misère Nim the last stone loses. The page does not offer misère, but the rule is worth knowing, because the two games are nearly the same.
Play misère exactly like normal Nim — leave a zero nim-sum — until your move would leave nothing but heaps of one stone. At that moment do the opposite: leave an odd number of single stones instead of an even one. That is the whole difference. We checked this rule by brute force against every position of up to four heaps of up to 15 stones, 3,876 of them, with no exceptions.
| Position | Normal play: move to | Misère play: move to |
|---|---|---|
| 1, 1, 3 | 1, 1 (take the three) | 1, 1, 1 (take two of the three) |
| 2, 2, 3 | 1, 2, 3 or 2, 2 | the same — heaps bigger than one remain |
| 1, 1, 1, 3 | 1, 1, 1, 1 | 1, 1, 1 |
| 1, 1, 1 | any stone: you win | lost: you will take the last stone |
How rarely it matters is easy to count. Of the 2,401 starting layouts of the two lower levels, only one would change hands under misère rules: 1, 1, 1, which is won in normal play and lost in misère. The set of winning first moves would differ in 3.7% of starts; in all the others you would make the same first move in either game.
The second game on the page is Nim with one heap and a limit: 21 stones, take one, two or three, the last stone wins. Here the zero positions are the multiples of four. If you leave 4, 8, 12, 16 or 20 stones, then whatever the opponent takes — call it k — you take 4−k and land on the next multiple of four.
From 21 you move first, so take one stone and then always answer with 4−k: 20, 16, 12, 8, 4, 0. Six moves, and it works against the first two levels every time. On the rigged level the game starts from 20 stones instead, and you are the one facing a multiple of four: 0%.
| How you play | makes mistakes | plays the formula |
|---|---|---|
| Take one, then answer with 4−k | 100% | 100% |
| A random legal move | 26.1% | 0.25% |
| Two or three on the first move, then correctly | 83.2% | 0% |
In this game the level that makes mistakes misses the multiple of four on 30% of its turns, not 45%: when it moves at random, one take in three is the right one anyway. After a wrong first move it has five turns to slip, and it gets through all five only 0.75 = 17% of the time.
Leave your opponent a position with a nim-sum of zero after every move. Split each heap into 4s, 2s and 1s, cancel equal pieces in pairs, and change one heap so that nothing is left unpaired. If the nim-sum is already zero on your turn, no move wins against correct play.
Break every heap into powers of two — 7 is 4+2+1, 6 is 4+2, 5 is 4+1, 3 is 2+1 — and cross out equal pieces in pairs. The pieces left without a partner, added up, are the nim-sum. For 3, 5, 7 the 4s and 2s cancel and one 1 is left, so the nim-sum is 1.
Only if the starting nim-sum is not zero. With three or four random heaps of one to seven stones that is about seven starts in eight. On this page zero starts are redealt on the two lower levels, so you, moving first, are winning in all 2,401 possible layouts; on the rigged level all 350 layouts are lost.
On the two lower levels here, always: every start is won for you, and the formula wins 100% of games. The level that makes mistakes also forgives a slip, missing its winning move on about 38% of turns. The rigged level cannot be beaten: the start is a zero position and the computer never errs.
In normal play the last stone wins, in misère it loses. The strategy is identical until a move would leave only heaps of one stone; then in misère you leave an odd number of them instead of an even number. This page plays the normal game.
Leave a multiple of four. With 21 stones and takes of one to three, the first player takes one and then answers every take of k with 4−k, leaving 20, 16, 12, 8, 4 and finally nothing. Starting from 20 the first player loses against correct play.