Tic-Tac-Toe
Classic Paper & Pen Play now
Nim is one of the oldest known mathematical games, and Harvard mathematician Charles Bouton published a complete winning theory for it in 1901. Players take turns removing objects from a single heap. Depending on the version, taking the last object wins or loses.
Set up several heaps (rows) of objects such as coins, matchsticks or pebbles. A common starting position uses rows of 1, 3, 5 and 7 objects, but any number of heaps and sizes works.
On your turn you must take at least one object, and you can take as many as you like, but all from a single heap. You can't take from two heaps in one move, and you can't skip your turn.
Players alternate until every object is gone. In normal play, whoever takes the last object wins. In the more common misère version, whoever is forced to take the last object loses.
Write each heap size in binary and XOR them together. If the result is zero, you're in a losing position against perfect play. If it's nonzero, you can win by moving to make it zero.
To win in normal play, always leave your opponent a position with a Nim-sum of zero. Find a heap you can reduce so the XOR of all heaps becomes zero, and take exactly that many.
Misère play follows the same Nim-sum rule until the heaps with two or more objects are nearly gone. When only heaps of size one would remain, leave an odd number of those single-object heaps instead.
If it's your move and only one nonempty heap remains, you can always win normal-play Nim by taking the whole heap. Spotting this endgame instantly is the foundation of the full strategy.
Pure skill. Nim is mathematically solved, so a player who knows the Nim-sum strategy and moves first from a winning position can't lose.
The Nim-sum is the bitwise XOR of all the heap sizes in binary. A position with a Nim-sum of zero loses under perfect play, and any nonzero Nim-sum is a win for the player to move.
A popular layout uses four rows of 1, 3, 5 and 7 objects, but Nim works with any number of heaps of any size. The strategy is the same whatever the arrangement.
It splits Nim into two versions. In normal play, taking the last object wins. In misère play, taking it loses, and the best endgame differs between the two.