Game Theory / Sprague-Grundy Ladder¶
This ladder covers impartial normal-play games where:
- positions are finite
mex-defined Grundy values make sense- independent components combine by xor
Use it when a game problem has moved beyond:
- plain parity
- one interval minimax DP
- one direct Nim formula you can quote from memory
Recommended Route¶
- single-component winning/losing subtraction game
- exact SG precompute for one move set
- xor of multiple heaps / independent components
- pattern-heavy or arithmetic SG tasks only after the route above feels routine
Anchor Problems¶
- S-Nim: the repo's exact first route, with one subtraction set and many multi-heap positions
Retrieval / Build Path¶
- topic page -> Game Theory / Sprague-Grundy
- hot sheet -> Sprague-Grundy hot sheet
- starter -> sprague-grundy-subtract-set.cpp
Compare Points¶
- CSES Stick Game: single-heap win/lose doorway before xor of heaps matters
- CSES Nim Game II: same lane, but with a closed-form SG pattern instead of a bounded precompute
- CSES Grundy's Game: pattern-heavy split game; do not expect the starter to solve it unchanged
- Removal Game: anti-cue when the statement sounds like game theory but the reusable route is score-difference DP
Exit Criteria¶
You are ready to leave this ladder when you can:
- define
SG(state)without hesitation - tell when xor across components is legal
- spot when a game is actually score DP or misere and should leave this lane
- use a small SG table or observed pattern without mixing up the two routes