Nim

Nim is the ancient strategy game where two players take turns removing objects from rows; the player forced to take the last object loses (or wins, depending on variant). Dating back at least to 1907 (when first analyzed by Charles L. Bouton), Nim is one of the few perfectly-solved combinatorial games. The optimal strategy depends on the binary XOR of the row counts (“Nim-sum”). Used as the foundational example in combinatorial game theory.

How to play

• Several rows of objects (matchsticks, stones, etc.).
• On your turn, remove ANY number from ONE row (minimum 1).
• The player who takes the LAST object wins (normal Nim) or loses (Misère Nim).

The Nim-sum strategy

The mathematical solution by Charles Bouton (1907): XOR all row counts together. If Nim-sum is non-zero, the player to move can win with perfect play. If it’s zero, they lose.

• Calculate Nim-sum. XOR all row counts. Example: rows of 3, 5, 7 → 3 XOR 5 XOR 7 = 1.
• If Nim-sum is 0, any move you make gives opponent a winning position.
• If non-zero, there’s a move that returns Nim-sum to 0. That’s your winning move.
• Find the winning move. XOR Nim-sum with each row count. The row where this is smaller than current count is the row to reduce.

Beginner strategy

• Learn the Nim-sum technique. It’s the only optimal strategy.
• Practice small cases. Solve 1, 2, 3 stone games to internalize.
• Misère Nim differs slightly. Endgame strategy depends on whether multiple rows have >1 object.
• Force opponent into Nim-sum 0. Move them into a losing position.

Nim history

• 1907 — Charles Bouton: publishes “Nim, A Game with a Complete Mathematical Theory.”
• 1939 — Eduard Hopf: generalizes to Sprague-Grundy theory.
• 1950s — Sprague and Grundy: show all impartial games reduce to Nim.
• 1990s — combinatorial game theory: Berlekamp, Conway, Guy publish “Winning Ways” using Nim as foundation.

FAQ

• Q: Can I always win? A: Yes, if Nim-sum at your move is non-zero. With optimal play, you have a forced win.
• Q: Misère vs normal Nim? A: Normal: take last object = win. Misère: take last = lose. Strategy differs slightly.
• Q: What’s Nim-sum? A: Binary XOR of row counts. Determines who wins with optimal play.
• Q: Variants? A: Wythoff’s game, Mock Turtles, dozens of impartial-game variants all derive from Nim.

For other strategy games, try Tic-Tac-Toe, Connect Four, Checkers, or Gomoku.