Nim Strategy
The classic mathematical strategy game. Remove any number of stones from a single heap on your turn. The player who takes the last stone wins. Play against an AI that uses the optimal XOR-based strategy. Watch the Nim-sum calculation in real time and learn why binary arithmetic determines the winner before the game even begins.
Nim-sum = h₁ ⊕ h₂ ⊕ h₃ ⊕ … Winning ⇔ Nim-sum ≠ 0 on your turn
The game of Nim
Nim is one of the oldest and most well-studied combinatorial games. Players alternate turns removing any positive number of objects from a single heap. In normal play (used here), the player who takes the last object wins. The game was mathematically solved by Charles Bouton in 1901.
The Nim-sum (XOR strategy)
The key insight is the Nim-sum: the bitwise exclusive-or (XOR) of all heap sizes. If the Nim-sum is zero, the position is losing for the player whose turn it is (assuming perfect play by the opponent). If non-zero, the current player can always make a move that leaves the opponent in a zero Nim-sum position. The winning move is to find a heap where removing some stones makes all the XOR values cancel out.
Binary representation
XOR operates on the binary representation of each heap size. For example, heaps of 3 (011), 5 (101), and 6 (110) give Nim-sum = 011 ⊕ 101 ⊕ 110 = 000. This is a losing position! The visualization shows each heap’s binary form and how the XOR combines them.
Sprague–Grundy theorem
Nim is the foundation of combinatorial game theory. The Sprague–Grundy theorem shows that every impartial game (where both players have the same available moves) is equivalent to a Nim heap of some size. This means Nim’s XOR analysis extends to an enormous class of mathematical games.