Nim & Sprague–Grundy Theory

The Sprague–Grundy theorem: every impartial game is equivalent to a Nim heap. G(position) = mex of reachable positions.

Play Nim vs AI

Your turn — click stones to remove, then confirm.

Nim-sum (XOR): 0 |

Grundy Values Visualizer

G(n) = mex{G(0),...,G(n−1)} for single pile of n

Game:

k for Nim-k: 3

Sprague–Grundy Theorem (1935/1939): Every position in an impartial game has a Grundy value G = mex(reachable Grundy values). mex = minimum excludant (smallest non-negative integer not in the set). A position is a P-position (previous player wins = current player loses) iff G = 0. For a sum of games: G(G₁+G₂+...+Gₙ) = G₁ ⊕ G₂ ⊕ ... ⊕ Gₙ (XOR / nim-sum). Nim winning strategy: move to make nim-sum = 0. With 3 piles (a,b,c): if a⊕b⊕c = 0, you lose; otherwise reduce a pile to make XOR = 0.