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). Named and fully analysed by Charles L. Bouton in 1901, 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).
• On Dinogame.gg: click a stone to select it and every stone to its right in that heap, then press Take Selected. Heaps start as 3-5-7, 4-5-6-7 or 1-3-5-7, and you always move first. Pick vs CPU (Easy plays at random, Hard plays the Nim-sum strategy) or 2 Players, and Normal or Misère rules.

The Nim-sum strategy

The mathematical solution by Charles Bouton (1901): 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

• 1901 — Charles Bouton: publishes “Nim, A Game with a Complete Mathematical Theory.”
• 1935 and 1939 — Sprague and Grundy: Roland Sprague and Patrick Grundy independently show every impartial game is equivalent to a Nim heap.
• 1982 — combinatorial game theory: Berlekamp, Conway and Guy publish “Winning Ways” using Nim as a foundation.

FAQ

• Q: Can I always win? A: Only if the Nim-sum at your move is non-zero. The 3-5-7 start (Nim-sum 1) is a forced win for you; the 4-5-6-7 and 1-3-5-7 starts have Nim-sum 0, so a perfect opponent wins them.
• 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.