Nim and the Grundy Number
Solve impartial games with XOR.
Meet the Game of Nim
In Nim there are several piles of stones. On your turn you remove any number from one pile, and the player who takes the last stone wins. 🪨
The Magic Quantity: XOR
The whole game is decided by the XOR of all pile sizes. That single number tells you who is winning.
All lessons in this course
- Winning & Losing States in Games
- Nim and the Grundy Number
- Meet in the Middle
- Debug Fast: Stress Tests & Triage