Combinatorial Games
Which move guarantees a win?
Study games in which players take turns changing a visible position. Begin with a single pile, build up to Nim and graph games, then use those ideas to analyze sums and rooted structures.
A suggested learning path
Follow the sequence, or jump directly to the question that interests you. Each lab opens in Guided Learning; switch to Sandbox at any time to experiment freely.
- Step 1
Take-Away
Learn winning and losing positions by working backward from the end.
Learning outcome: Classify positions as winning or losing by working backward, then pick a winning move.
- Level
- Introductory
- Time
- About 15 min
- Concepts
- P-positions · N-positions · Backward induction
- Step 2
Nim
Extend the idea to several piles and understand binary XOR.
Learning outcome: Use the binary nim-sum to decide who wins a Nim position and find a winning move.
- Level
- Introductory
- Time
- About 20 min
- Concepts
- Nim-sum (XOR) · Bouton's theorem · Misère play
- Step 3
Graph Games
Describe legal moves with arrows and calculate Sprague–Grundy values.
Learning outcome: Compute Sprague–Grundy values on a directed graph with the minimum-excluded rule.
- Level
- Intermediate
- Time
- About 20 min
- Concepts
- Sprague–Grundy value · mex · Followers
- Step 4
Sum of Games
Combine independent games using their values.
Learning outcome: Combine the Grundy values of independent games with XOR to play their sum.
- Level
- Intermediate
- Time
- About 20 min
- Concepts
- Game sums · Sprague–Grundy theorem · Nim-sum
- Step 5
Hackenbush
Apply the ideas to cuts, connectivity and supported structures.
Learning outcome: Replace rooted Green Hackenbush branches by equivalent Nim heaps and choose a winning cut.
- Level
- Intermediate
- Time
- About 25 min
- Concepts
- Green Hackenbush · Colon principle · Equivalent Nim heap
