Misère Nim

This game is Misère Nim, a twist on the classic game Nim. In Nim, players take turns removing any number of objects (here, cards) from a single pile, and in the classic version the player who takes the last object wins. This page flips the rule: the player who takes the last card loses. That "last one loses" version has a proper name — misère Nim, from the French word for misery.

The winning algorithm (Bouton, 1901)

In 1901, the mathematician Charles Bouton worked out the complete strategy for Nim. It uses one simple calculation called the nim-sum: write every pile size in binary and XOR them together (XOR means the bit is 1 when the two bits differ, 0 when they match).

• If the nim-sum is 0, the position is "safe": with perfect play, the player to move is in a losing position.
• If the nim-sum is not 0, there is always a winning move: find a pile whose size is bigger than (pile size XOR nim-sum), and reduce it to that smaller number. This makes the nim-sum 0 again and hands the safe position to your opponent.

Why it works: a move changes exactly one pile, so it can never turn a 0 nim-sum into another 0 nim-sum — the opponent can never hand you back a safe position. And from a non-zero nim-sum the fix above always exists. Repeat, and you are the one taking the last object.

Example with piles 3, 5, 7

In binary: 3 = 011, 5 = 101, 7 = 111. The nim-sum is 011 XOR 101 XOR 111 = 001 (that is, 1), which is not 0, so the player to move can win. The fix: 7 XOR 1 = 6, and 6 is smaller than 7, so take 1 card from the 7-pile, leaving 3, 5, 6. Check: 011 XOR 101 XOR 110 = 000. A safe position for the opponent.

Misère Nim — the twist for this game

The same nim-sum trick works, with one small change right at the end. When every pile has exactly one card left, players are forced to take one card per turn, so the game is decided by counting: with all piles of size 1, the player to move loses when there is an odd number of piles, because they will be the one forced to take the very last card. So in the endgame, misère Nim's winning move is to leave an odd number of one-card piles, while normal Nim would leave an even number.

The difficulty levels

Easy — the computer just picks random legal moves. Normal — it plays the best move most of the time, but every so often makes a blunder you can exploit. Hard — it always finds the mathematically best move, so beating it means starting from a winning position and not making mistakes yourself.