← Iris
Lab / Experiment

Nim

The ancient game of strategy with a perfect mathematical solution. Take objects from any heap — whoever takes the last one wins. The AI knows the XOR trick. Can you beat it?

Your turn. Click stones to select them from one heap, then press Take.
Your turn

Game state

Turn You
Move number 0
Total stones 0
Heaps 0
Your wins 0
AI wins 0

Nim-sum (XOR)

Guide

Available stone
Selected to take
Removed stone
Click stones in one heap to select them  ·  Press Take selected to remove them  ·  You must take at least one stone per turn, all from the same heap  ·  Whoever takes the last stone wins (or loses in Misère mode)  ·  Watch the XOR panel to learn the AI’s strategy

What’s happening

The game of Nim

Nim is one of the oldest strategy games, analyzed mathematically by Charles Bouton in 1901. Two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object from a single heap (they may take as many as they like from that heap). In normal play, the player who takes the last object wins. In misère play, taking the last object loses.

The Nim-sum (XOR strategy)

The key insight is the Nim-sum: write each heap size in binary and XOR them all together. If the Nim-sum is zero, the position is losing for the player about to move (with perfect play by the opponent). If the Nim-sum is nonzero, there always exists a move that makes it zero — which is the optimal play. The AI in this simulation always makes the Nim-sum-zeroing move when one exists.

Why XOR works

Heaps:    3, 5, 7
Binary:   011
          101
          111
XOR:      001  (Nim-sum = 1, nonzero = winning)

Optimal: take 1 from heap of 7 → heaps become 3, 5, 6
Binary:   011
          101
          110
XOR:      000  (Nim-sum = 0 → opponent is now losing)

XOR has a beautiful property: flipping bits in one row can always zero out the total if it starts nonzero, but can never keep it at zero. This is because XOR is its own inverse, is associative, commutative, and has identity 0.

The Sprague–Grundy theorem

Nim’s solution generalizes enormously. The Sprague–Grundy theorem (1930s) shows that every impartial game — where both players have the same moves available — is equivalent to a Nim heap of some size (its Grundy number). The Grundy number of a combined game is the XOR of the Grundy numbers of its parts. This means Nim’s XOR strategy applies to hundreds of combinatorial games: Wythoff’s game, Turning Turtles, various subtraction games, and more.

Misère Nim

In misère Nim, the player who takes the last object loses. The optimal strategy is almost identical: play the same XOR strategy until all heaps have size 0 or 1, then switch to leaving an odd number of heaps (so the opponent takes the last stone). The mathematical twist: misère Nim requires exactly one change in endgame logic, making it a fascinating edge case in combinatorial game theory.