Play Nim against a Sprague-Grundy AI and explore game trees visually
Combinatorial game theory studies two-player games with perfect information, no chance moves, and a guaranteed winner. The central example is Nim: players take turns removing objects from heaps, and the player who takes the last object wins (or loses, depending on the variant).
Charles Bouton solved Nim completely in 1901 with a beautiful result: a position is a winning position if and only if the XOR (binary exclusive-or) of all heap sizes is non-zero. This is the foundation of the Sprague-Grundy theorem, which extends the analysis to any combinatorial game.
Click a stone to remove it and everything to its right in that heap. The AI uses the XOR strategy — it plays optimally when possible. Enable the Sprague-Grundy panel to see the binary analysis and understand why the AI makes each move.
| Heap | Size | Binary |
|---|---|---|
| Heap 1 | 3 | 011 |
| Heap 2 | 4 | 100 |
| Heap 3 | 5 | 101 |
| XOR | 2 | 010 |
Winning position (XOR ≠ 0) — there exists an optimal move.
The XOR strategy: Compute the XOR of all heap sizes. If it's non-zero, you can always find a move that makes it zero — leaving your opponent in a losing position. If it's already zero, any move you make will leave it non-zero, giving your opponent a winning position.
Every position in a combinatorial game can be assigned a non-negative integer called its Grundy number (or nimber). The key result:
For standard Nim, the Grundy number of a single heap of size n is simply n. The XOR of all heap sizes gives the Grundy number of the full position — which is exactly Bouton's 1901 result, now seen as a special case of a far more general theory.