What this game is
Nim is the one game on this site where the computer does not search at all. It knows the answer as a formula.
Charles Bouton published the solution in 1901, half a century before the first game program. Write the heap sizes in binary, add them column by column without carrying — that is a bitwise XOR. If the result is zero, the player about to move loses against correct play. If it is not zero, there is a move that makes it zero, and whoever finds it wins.
Rules
- Three or four heaps of stones. A move is taking any number of stones from exactly one heap — at least one.
- Whoever takes the very last stone wins. (The reverse convention, where the last stone loses, is a different game with a slightly different formula.)
- You move first. Clicking a stone takes it together with everything to its right in the same heap.
- In the 21 game there is one row of twenty-one stones and you may take one, two or three. The same idea shrinks to a much simpler rule: leave a multiple of four.
Why the levels differ so much
On the middle level the computer plays the formula perfectly — but the starting position is random, and a random position usually has a non-zero XOR. That means the winning side is you, if you find the right move every single turn.
On the top level the start is rigged: the XOR is zero before your first move. From there nothing can be done — every move you make breaks the balance, and the computer restores it. This is the whole point of a solved game: the machine is not thinking faster, it is holding a theorem you do not have. Which is why the trainer above matters more than the score.