Game Theory -- Nim & Sprague-Grundy

Quick Revisit

• USE WHEN: two-player impartial game — "who wins with optimal play?"
• INVARIANT: XOR of all pile sizes (Nim) or Grundy values (general) is 0 ⇔ second player wins
• TIME: O(n) for Nim; O(n × states) for Grundy computation | SPACE: O(states)
• CLASSIC BUG: Grundy value is the MEX (minimum excludant) of reachable states, not max or count of moves
• PRACTICE: 08-ladder-mixed

Combinatorial game theory for competitive programming -- Nim, Grundy values (nimbers), and the Sprague-Grundy theorem for decomposing games into independent sub-games so you can decide the winner in $O(n)$ instead of exploring an exponential game tree.

Difficulty: [Intermediate] Prerequisites: Bit Manipulation

---

Contents

• Intuition
• Visual Intuition (ASCII Art)
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

Two players face three piles of stones with sizes (3, 4, 5). Players alternate; on each turn you pick any pile and remove at least one stone. Whoever takes the last stone wins.

Who wins with optimal play?

Naive approach -- build the full game tree. Each state is a triple $(a,b,c)$ with $0\le a\le 3$, $0\le b\le 4$, $0\le c\le 5$. From $(3,4,5)$ you can reach $(0..2,4,5)$, $(3,0..3,5)$, $(3,4,0..4)$ -- that is $3+4+5=12$ children in just the root. The total number of states is $(3+1)(4+1)(5+1)=120$, and the game tree (counting repeated visits from different move orders) is even larger. For piles up to ${10}^5$, the state space is astronomically large.

  Game tree root: (3, 4, 5)
        /        |           \
  (2,4,5)    (3,3,5)  ...  (3,4,0)      <- 12 children
   / | \      / | \          / | \
  ...  ...   ...  ...       ...  ...     <- branching explodes

Even dynamic programming over $(a,b,c)$ states is $O(a\cdot b\cdot c\cdot (a+b+c))$ when you factor in transitions. With $k$ piles of size up to $n$, that's $O(n^k\cdot kn)$ -- completely impractical.

We're recursing through an exponential game tree just to answer a yes/no question. There has to be a pattern.

"XOR all pile sizes -- if the result is non-zero, the first player wins; if zero, the second player wins. This works because each move can always restore the XOR to zero." (Bouton's theorem, 1901).

Analogy -- balancing a multi-pan scale. Imagine a balance with several pans. Each pan holds stones representing a pile. The "XOR balance" reads zero when the system is in equilibrium. The second player's strategy is to always restore equilibrium after the first player disturbs it. If the game starts balanced (XOR = 0), the first player is forced to unbalance it, and the second player can always rebalance -- so the second player wins. If it starts unbalanced (XOR != 0), the first player unbalances-then-rebalances by making one move that forces XOR to zero, then plays the role of "restorer" from there on.

Where the analogy breaks: Real scales have continuous weights and gravity. XOR is a bitwise operation -- it "balances" each bit position independently. A move that reduces one pile might flip many bits at once, so the restoration isn't as simple as moving one stone to another pan.

Visual Walkthrough

Same game: piles = (3, 4, 5).

Step 1: Compute the XOR

  Pile sizes in binary:

    3 = 0 1 1
    4 = 1 0 0
    5 = 1 0 1
        -----
  XOR = 0 1 0  = 2

XOR = $3\oplus 4\oplus 5=2\ne 0$, so Player 1 wins with optimal play.

Step 2: Find P1's winning move

P1 needs to make one move so the resulting XOR is 0. Look at the XOR result (2 = 010). The highest set bit is bit 1. Find any pile with bit 1 set. Pile of 3 = 011 has bit 1 set. Reduce pile 3 by XORing it with the current XOR: $3\oplus 2=1$. So P1 changes pile 3 from 3 to 1 (removes 2 stones).

  Before P1's move:  (3, 4, 5)   XOR = 2 (P1 wins)

  P1 removes 2 from pile 1:  (1, 4, 5)

  Verify:
    1 = 0 0 1
    4 = 1 0 0
    5 = 1 0 1
        -----
    XOR = 0 0 0  = 0            <-- XOR is now 0 (losing for mover)

Step 3: P2 must disturb the balance

P2 has no choice but to break the XOR = 0 state. Suppose P2 removes 2 from pile of 5, leaving (1, 4, 3):

  After P2's move:  (1, 4, 3)

    1 = 0 0 1
    4 = 1 0 0
    3 = 0 1 1
        -----
    XOR = 1 1 0  = 6            <-- XOR != 0, P1 can restore again

Step 4: P1 restores balance

XOR = 6 = 110. Highest set bit: bit 2. Pile of 4 = 100 has bit 2 set. $4\oplus 6=2$. P1 reduces pile from 4 to 2:

  P1's move:  (1, 2, 3)

    1 = 0 0 1
    2 = 0 1 0
    3 = 0 1 1
        -----
    XOR = 0 0 0  = 0            <-- Balance restored

Step 5: The pattern holds until the end

P2 is always the one forced to unbalance. Eventually the piles shrink to (0, 0, 0) on P2's turn -- but (0, 0, 0) is the terminal losing position (no moves), and XOR = 0, so it's indeed P2 who faces it. P1 wins.

  Summary of play:

  (3,4,5)  XOR=2  P1 moves  -->  (1,4,5)  XOR=0
  (1,4,5)  XOR=0  P2 moves  -->  (1,4,3)  XOR=6
  (1,4,3)  XOR=6  P1 moves  -->  (1,2,3)  XOR=0
  ...
  (0,0,0)  XOR=0  P2 loses  (no moves left)

Bridge: Nim piles are the primitive game units. Bouton's theorem solves Nim because a Nim pile of size $n$ is the simplest impartial game with $n$ available moves, and XOR of pile sizes determines the winner. The Sprague-Grundy theorem extends this: any impartial game state has an equivalent "Grundy value" $g$, and the state behaves exactly like a Nim pile of size $g$. So once you compute Grundy values, an arbitrary impartial game becomes a Nim game over those values — and Bouton's XOR rule applies again.

Now Sprague-Grundy for a non-Nim game. Suppose a single-pile game where you can remove 1, 2, or 3 stones. Compute Grundy values:

  g(0) = 0                           (no moves: losing)
  g(1) = mex({g(0)})       = mex({0})       = 1
  g(2) = mex({g(1),g(0)})  = mex({1,0})     = 2
  g(3) = mex({g(2),g(1),g(0)}) = mex({2,1,0}) = 3
  g(4) = mex({g(3),g(2),g(1)}) = mex({3,2,1}) = 0  <-- cycle!
  g(5) = mex({g(4),g(3),g(2)}) = mex({0,3,2}) = 1
  g(6) = mex({g(5),g(4),g(3)}) = mex({1,0,3}) = 2
  g(7) = mex({g(6),g(5),g(4)}) = mex({2,1,0}) = 3

  Pattern: g(n) = n % 4

With multiple independent sub-games, XOR all their Grundy values -- same theorem.

COMPOSITE GAME -- XOR of Grundy values:

  Game = 3 independent sub-games played simultaneously.
  On your turn, pick ONE sub-game and make a move in it.

  Sub-game A: pile of 3 (take 1 or 2)  -> G(3) = 0
  Sub-game B: pile of 5 (take 1 or 2)  -> G(5) = 2
  Sub-game C: pile of 4 (take 1-3)     -> G(4) = 4... 
  
  Wait -- for take 1-3:
  G(0)=0, G(1)=mex{0}=1, G(2)=mex{0,1}=2, 
  G(3)=mex{0,1,2}=3, G(4)=mex{1,2,3}=0

  So: G(A)=0, G(B)=2, G(C)=0

  Total Grundy = 0 XOR 2 XOR 0 = 2

     0: 0 0 0
     2: 0 1 0
     0: 0 0 0
  XOR:  0 1 0 = 2 != 0  ->  FIRST PLAYER WINS

  Strategy: make a move in sub-game B to change G(B)
  from 2 to 0. Then total = 0 XOR 0 XOR 0 = 0.
  (Reduce pile B from 5 to 3: G(3) = 0. Done.)

The Invariant

+-----------------------------------------------------------------------+
| GRUNDY VALUE: g(state) = mex({g(next) for all reachable next states}) |
|                                                                       |
| For standard Nim: g(pile of size n) = n.                              |
|                                                                       |
| THEOREM (Sprague-Grundy): A composite game of independent sub-games   |
| has Grundy value g(G1) XOR g(G2) XOR ... XOR g(Gk).                  |
| First player wins iff this XOR is non-zero.                           |
+-----------------------------------------------------------------------+

The mex (minimum excludant) of a set $S$ is the smallest non-negative integer not in $S$. It captures "the effective pile size" -- a game position with Grundy value $g$ behaves identically to a Nim pile of size $g$.

Look at the Grundy table above: $g(4)=0$ because from 4 stones you can reach states with Grundy values $\{3,2,1\}$ -- the mex is 0, meaning position 4 is a losing position (like an empty pile), which makes sense: with moves $\{1,2,3\}$, your opponent can always mirror your move to sum to 4.

MEX COMPUTATION -- step by step:

  Game: from pile of n, you can take 1 or 2 stones.

  G(0) = mex({})         = 0     <- no moves: mex of empty = 0
  G(1) = mex({G(0)})     = mex({0}) = 1
  G(2) = mex({G(1),G(0)})= mex({1,0}) = 2
  G(3) = mex({G(2),G(1)})= mex({2,1}) = 0    <- not {0}!
  G(4) = mex({G(3),G(2)})= mex({0,2}) = 1
  G(5) = mex({G(4),G(3)})= mex({1,0}) = 2

  n:    0  1  2  3  4  5  6  7  8  9  ...
  G(n): 0  1  2  0  1  2  0  1  2  0  ...
                 └─ period = 3 ──┘

  ┌────────────────────────────────────────────┐
  │ mex({0,1,2}) = 3                           │
  │ mex({0,2,3}) = 1    <- NOT the min!        │
  │ mex({1,2,3}) = 0    <- smallest MISSING    │
  │ mex({0,1,3,4}) = 2  <- gap at 2            │
  └────────────────────────────────────────────┘

When to Reach for This

Trigger phrases in problem statements:

• "Two players alternating turns" + "optimal play" -> game theory
• "Who wins?" or "first player / second player" -> compute Grundy
• "Nim" or "piles of stones" -> direct XOR
• "Several independent games played simultaneously" -> Sprague-Grundy
• "Remove 1..k objects" / custom move sets -> compute Grundy values, look for cycle

Counter-examples -- when this does NOT apply:

• Games with ties or draws (e.g., Tic-Tac-Toe can end in a draw) -> not a combinatorial game in the Sprague-Grundy sense; SG assumes every game eventually terminates with a winner.
• Games where sub-games interact (e.g., a move in one pile affects another) -> SG theorem requires independence. You need a different approach (game DAG, DP over composite states).
• Games where the last mover loses (Misere Nim) -> XOR logic flips subtly: if XOR != 0 P1 still wins, unless all piles are size 1, in which case the winner depends on parity. This is a common trap.

Insight Gaps

Why XOR works for Nim. The proof uses the strategy: from a position with XOR != 0, there always exists a move that makes XOR = 0. From a position with XOR = 0, every move makes XOR != 0. This bidirectional property is what makes XOR the complete characterization. Understanding the proof -- not just the rule -- makes the strategy unforgettable and helps you recognize when XOR doesn't apply.

Grundy values for non-trivial games require game analysis, not just a formula. For Nim, Grundy(pile of size n) = n. For other games (Wythoff's Nim, Turning Turtles, Nim with restricted moves), the Grundy values must be computed and often have periodic or pattern-based structure. Many contest game-theory problems require finding this pattern experimentally for small values and then proving (or assuming) it holds.

The Sprague-Grundy theorem enables composition. The power of Grundy values is that for a game that is a sum of independent games (disjoint components), the overall Grundy value is the XOR of each component's Grundy value. This is what makes it possible to solve "there are $k$ separate piles/boards/games, who wins?" by XOR-ing sub-game values. Without this composition theorem, you'd need to enumerate the full product state space.

What the Code Won't Teach You

The Grundy-value code computes mex of successors mechanically. What it hides is the strategic thinking: why XOR captures winning/losing, how to decompose a complex game into independent sub-games, and when the whole Sprague-Grundy framework doesn't apply at all.

GAME CLASSIFICATION TREE -- what tool to reach for:

  Is the game impartial?  (both players have same moves)
       │
       ├─ YES
       │    │
       │    ├─ Normal play? (last move wins)
       │    │    ├─ YES -> Sprague-Grundy theorem
       │    │    │    ├─ Pure Nim? -> XOR pile sizes
       │    │    │    └─ Other?   -> compute Grundy values
       │    │    │
       │    │    └─ Misère play? (last move loses)
       │    │         └─ Nim? -> special endgame rule
       │    │
       │    └─ Is the game a SUM of independent games?
       │         ├─ YES -> XOR individual Grundy values
       │         └─ NO  -> analyze as single game
       │
       └─ NO (partisan -- different moves per player)
            └─ Sprague-Grundy does NOT apply
               Use surreal numbers or ad-hoc analysis

The code also won't show you how to find the winning move. Knowing "first player wins" (XOR != 0) is half the battle; the other half is which pile to reduce and to what size. The algorithm: find the pile whose reduction makes the total XOR zero. The code gives you the Grundy value; the strategic insight gives you the move.

FINDING THE WINNING MOVE -- Nim piles (3, 5, 6):

  XOR = 011 ⊕ 101 ⊕ 110 = 010 = 2

  Highest bit of XOR (010) is bit 1.
  Pile with bit 1 set: pile 3 (011), pile 6 (110)

  Option A: reduce pile 3 from 011 to 011 ⊕ 010 = 001 = 1
    New piles: (1, 5, 6)  XOR = 001 ⊕ 101 ⊕ 110 = 010... wrong

  Correct: reduce pile to pile_i XOR total_xor:
    Pile 3: 011 ⊕ 010 = 001 = 1  -> new XOR = 1⊕5⊕6 = 2 (not 0)
    Pile 6: 110 ⊕ 010 = 100 = 4  -> new XOR = 3⊕5⊕4 = 2 (not 0)
    
  Actually: total XOR = 2 (010). For pile p_i:
    new_p_i = p_i XOR total_xor (only if result < p_i)
    Pile 6: 6 XOR 2 = 4 < 6 OK  -> remove 2 from pile 6
    New: (3, 5, 4), XOR = 3⊕5⊕4 = 2... 
    
  Let me recompute: 3=011, 5=101, 6=110
  XOR = 011 ⊕ 101 = 110, 110 ⊕ 110 = 000. Wait:
  011 ⊕ 101 = 110; 110 ⊕ 110 = 000. XOR = 0!
  This is a LOSING position for the current player!

The code also won't teach you how to find the winning move in a composite Sprague-Grundy game. With Nim, you reduce a pile to make the total XOR zero -- straightforward. But in a composite game of non-Nim sub-games, "change a sub-game so the XOR of Grundy values becomes zero" means you need to: (1) identify which sub-game to modify, (2) find a position inside that sub-game with the required Grundy value. Step 2 is the hard part -- a sub-game at Grundy value 5 might need to reach Grundy value 3, but which concrete move in that sub-game achieves this? You need to trace through the Grundy table or BFS the sub-game's state graph to find it.

FINDING A WINNING MOVE IN A COMPOSITE GAME:

  Sub-games:    A (Grundy=5)    B (Grundy=3)    C (Grundy=6)
  XOR:          5 ⊕ 3 ⊕ 6 = 0  ->  P-position (we lose!)

  Suppose instead:  A=5, B=3, C=7  ->  XOR = 5⊕3⊕7 = 1 (N-position)

  Goal: change ONE sub-game so total XOR = 0
  Target for each sub-game:
    Change A to A' where A' ⊕ 3 ⊕ 7 = 0  ->  A' = 3⊕7 = 4  (need A: 5->4)
    Change B to B' where 5 ⊕ B' ⊕ 7 = 0  ->  B' = 5⊕7 = 2  (need B: 3->2)
    Change C to C' where 5 ⊕ 3 ⊕ C' = 0  ->  C' = 5⊕3 = 6  (need C: 7->6)

  Valid move: target < current  (can only reduce Grundy values by moving)
    A: 5->4 OK (4<5)    B: 3->2 OK (2<3)    C: 7->6 OK (6<7)

  Pick sub-game A. Now WITHIN game A, find a position reachable
  from the current state that has Grundy value exactly 4.

  ┌─────────────────────────────────────────────────────────┐
  │  This search through sub-game A is what the code won't  │
  │  do for you -- you must trace the game graph to find a   │
  │  concrete successor state with Grundy(state) = 4.       │
  └─────────────────────────────────────────────────────────┘

Finally, the code won't show you when Sprague-Grundy doesn't apply at all. The framework requires: (1) two players, (2) alternating turns, (3) perfect information, (4) no randomness, (5) impartial (same moves for both players), (6) game must terminate (no infinite play), and (7) normal play convention (last player to move wins). Partisan games (Chess, Go), games with draws, stochastic games, and games allowing infinite play all break the framework. Recognizing these boundaries is a skill the code cannot develop for you.

The decision tree that tells you which tool to use. Before computing anything, classify your game: Is it impartial? Is it normal-play or misère? Is it a single game or a sum of independent sub-games? Each answer narrows the toolbox. The code gives you the mex function and the XOR combiner, but doesn't tell you when NOT to use them -- which is exactly when you need the decision tree most.

GAME THEORY DECISION TREE:

  Is the game impartial?
  ├── NO -> Partisan game theory (Surreal numbers, CGT)
  │        [Beyond most CP -- rare in contests]
  │
  └── YES -> Is it a sum of independent sub-games?
            ├── NO -> Single game: compute G(state) via mex
            │        directly. G = 0 -> lose, G > 0 -> win.
            │
            └── YES -> G(total) = G(game₁) XOR G(game₂) XOR ...
                      │
                      Is it standard Nim?
                      ├── YES -> G(pile) = pile size
                      │         Total XOR = pile₁ XOR pile₂ XOR ...
                      │
                      └── NO -> Compute G(sub-game) for each
                               sub-game via mex on small cases.
                               Look for a period / pattern.

  Is it misère play?
  ├── NO -> Normal play: G = 0 -> current player loses
  └── YES -> Special case only when all sub-games trivial
            (all Grundy <= 1). Otherwise same as normal.

---

Visual Intuition (ASCII Art)

Diagram 1: Nim game state trace

  Piles:  [3]  [4]  [5]         XOR = 3^4^5 = 2 (P1 wins)
          |||  |||| |||||
          |||  |||| |||||

  P1 takes 2 from pile 1:

  Piles:  [1]  [4]  [5]         XOR = 1^4^5 = 0 (P2 must break it)
           |   |||| |||||
               |||| |||||

  P2 takes 2 from pile 3:

  Piles:  [1]  [4]  [3]         XOR = 1^4^3 = 6 (P1 can fix it)
           |   |||| |||
               |||| |||

  P1 takes 2 from pile 2:

  Piles:  [1]  [2]  [3]         XOR = 1^2^3 = 0 (balanced again)
           |   ||   |||
               ||   |||

Caption: Stone piles shrink each turn. P1 always moves to XOR = 0.

Diagram 2: Grundy value computation DAG (remove 1, 2, or 3)

  State:   0     1     2     3     4     5     6     7
  g(n):    0     1     2     3     0     1     2     3

  Move graph (each node can reach up to 3 predecessors):

  +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+
  | 0 |<--| 1 |<--| 2 |<--| 3 |<--| 4 |<--| 5 |<--| 6 |<--| 7 |
  | 0 |   | 1 |   | 2 |   | 3 |   | 0 |   | 1 |   | 2 |   | 3 |
  +---+   +---+   +---+   +---+   +---+   +---+   +---+   +---+
    ^       ^  ^    ^ ^      ^       ^       ^  ^    ^ ^      ^
    |       |  |    | |      |       |       |  |    | |      |
    +-------+--+----+-+------+       +-------+--+----+-+------+
    (arrows show which states each position can reach)

  Cycle length = 4.  Losing positions (g=0): 0, 4, 8, 12, ...

Caption: Grundy values for "remove 1..3" game. Pattern repeats with period 4.

Diagram 3: Sprague-Grundy composite game

  Game A: pile of 3 stones (remove 1..3)    g(A) = 3
  Game B: pile of 5 stones (remove 1..3)    g(B) = 1
  Game C: pile of 7 stones (remove 1..3)    g(C) = 3

  Composite Grundy value:

    g(A)  =  3  =  0 1 1
    g(B)  =  1  =  0 0 1
    g(C)  =  3  =  0 1 1
                   ------
    XOR        =   0 0 1  = 1 != 0

  --> First player wins the composite game.

Caption: XOR of Grundy values determines the composite game winner.

Diagram 4: Game tree for Nim position (1, 2) with Grundy values

                        (1,2)
                        G=3 [W]
                 /         |         \
          take 1       take 1       take 2
         from p1      from p2      from p2
            |             |             |
         (0,2)         (1,1)         (1,0)
         G=2 [W]       G=0 [L]      G=1 [W]
         /     \        /     \         |
     (0,1)   (0,0)  (0,1)   (1,0)   (0,0)
     G=1[W]  G=0[L] G=1[W]  G=1[W]  G=0[L]
       |               |       |
     (0,0)           (0,0)   (0,0)
     G=0[L]          G=0[L]  G=0[L]

  G = Grundy value = XOR of pile sizes
  [W] = Winning (G != 0): current player can force a win
  [L] = Losing  (G == 0): current player loses with optimal play

  Optimal play from (1,2): take 1 from pile 2 -> (1,1) G=0 [L]
  Opponent faces a losing position no matter what.

Caption: Complete game tree for piles (1,2). The first player wins by moving to the unique G=0 child.

Diagram 5: XOR computation -- piles (3, 4, 5) in binary

  PILES (3, 4, 5) -- BITWISE XOR COMPUTATION

              bit2  bit1  bit0
              ----  ----  ----
  Pile 1:  3 =  0     1     1
  Pile 2:  4 =  1     0     0
  Pile 3:  5 =  1     0     1
              ----  ----  ----
  XOR:         0     1     0   =  2

  (Each bit column: count 1s. Even count -> 0, Odd count -> 1)

   bit2: 0+1+1 = 2 (even) -> 0
   bit1: 1+0+0 = 1 (odd)  -> 1
   bit0: 1+0+1 = 2 (even) -> 0

  Result: XOR = 010 = 2 != 0  -->  First player WINS

  +-- Finding the winning move: --------------------------+
  |  Highest set bit of XOR (=2) is bit1.                 |
  |  Find a pile with bit1 set: Pile 1 (3 = 011) OK       |
  |  New pile value = 3 XOR 2 = 1.  Remove 2 stones.     |
  |  New state: (1, 4, 5) -> XOR = 001^100^101 = 000 = 0 |
  |  Opponent now faces a losing position.                |
  +-------------------------------------------------------+

Caption: Binary XOR determines the winner in O(n). The highest set bit guides the winning move.

Diagram 6: Sprague-Grundy decomposition -- three independent sub-games

  SPRAGUE-GRUNDY DECOMPOSITION

  Three independent sub-games, each "subtract {1, 2}" on a pile:

  Grundy table for "subtract {1, 2}":
    n:    0   1   2   3   4   5   6   7   8
    g(n): 0   1   2   0   1   2   0   1   2      Period = 3

    +---+   +---+   +---+   +---+   +---+   +---+
    | 0 |<--| 1 |<--| 2 |<--| 3 |<--| 4 |<--| 5 | ...
    |g=0|   |g=1|   |g=2|   |g=0|   |g=1|   |g=2|
    +---+   +---+   +---+   +---+   +---+   +---+
      ^       ^       ^
      |       |       +--- each node can reach 1 or 2 steps back
      +-------+

  Sub-game A: pile=4  ->  g(4) = 1
  Sub-game B: pile=5  ->  g(5) = 2
  Sub-game C: pile=3  ->  g(3) = 0

    +-------+       +-------+       +-------+
    | Sub-A |       | Sub-B |       | Sub-C |
    | pile=4|       | pile=5|       | pile=3|
    | g = 1 |       | g = 2 |       | g = 0 |
    +---+---+       +---+---+       +---+---+
        \               |               /
         \              |              /
          +------+------+------+------+
                 |             |
                 v    XOR      v
            g(A) = 1 = 0 1
            g(B) = 2 = 1 0
            g(C) = 0 = 0 0
                      -----
            XOR      = 1 1  =  3  !=  0

            --> First player wins the composite game.

Caption: Sprague-Grundy theorem: XOR individual Grundy values (not pile sizes) to solve composite games.

Worked Example: Grundy values for "subtract {1, 3}" game

  GRUNDY COMPUTATION: "subtract {1, 3}" game

  Rules: from pile of n, remove exactly 1 or exactly 3 stones.
         Player who cannot move (n=0) loses.

  g(0) = 0                             (no moves, terminal, L)

  g(1): can subtract 1 -> pos 0
        Reachable Grundy set = {g(0)} = {0}
        g(1) = mex({0}) = 1            [W]

  g(2): can subtract 1 -> pos 1       (can't subtract 3: 2 < 3)
        Reachable = {g(1)} = {1}
        g(2) = mex({1}) = 0            [L]

  g(3): subtract 1 -> pos 2,  subtract 3 -> pos 0
        Reachable = {g(2), g(0)} = {0, 0} = {0}
        g(3) = mex({0}) = 1            [W]

  g(4): subtract 1 -> pos 3,  subtract 3 -> pos 1
        Reachable = {g(3), g(1)} = {1, 1} = {1}
        g(4) = mex({1}) = 0            [L]

  g(5): subtract 1 -> pos 4,  subtract 3 -> pos 2
        Reachable = {g(4), g(2)} = {0, 0} = {0}
        g(5) = mex({0}) = 1            [W]

  g(6): subtract 1 -> pos 5,  subtract 3 -> pos 3
        Reachable = {g(5), g(3)} = {1, 1} = {1}
        g(6) = mex({1}) = 0            [L]

  Summary:
    n:    0   1   2   3   4   5   6
    g(n): 0   1   0   1   0   1   0
          L   W   L   W   L   W   L

    +---+   +---+   +---+   +---+   +---+   +---+   +---+
    | 0 |   | 1 |   | 2 |   | 3 |   | 4 |   | 5 |   | 6 |
    |g=0|   |g=1|   |g=0|   |g=1|   |g=0|   |g=1|   |g=0|
    | L |   | W |   | L |   | W |   | L |   | W |   | L |
    +---+   +---+   +---+   +---+   +---+   +---+   +---+
      ^       ^       ^       ^       ^       ^       ^
      |       |       |       +---+   |       +---+   |
      +--(-1)-+       +--(-1)-+   |   +--(-1)-+   |   |
                                  |               |   |
              +------(-3)---------+   +---(-3)----+   |
              |                       |               |
              +-------(-3)------------+---(-3)--------+

  Pattern: g(n) = n mod 2.  Period = 2.
  Why? Both 1 and 3 are ODD. Every move flips parity.
  Even positions = Losing, Odd positions = Winning.

  Compare with "subtract {1, 2}": g(n) = n mod 3 (period 3).
  Compare with "subtract {1, 2, 3}": g(n) = n mod 4 (period 4).
  General rule for "subtract {1, 2, ..., k}": g(n) = n mod (k+1).

Caption: The subtract {1,3} game has period 2 because both moves are odd. Always compute small cases to spot the pattern.

Diagram 7: Full game tree for Nim (2, 3) -- who wins from each state

GAME TREE -- Nim with piles (2, 3):

                      (2,3) XOR=1 [W]
                    /       |        \
              take 1        take 2    take from
              from p1      from p1     pile 2
                 /           |         |    \     \
           (1,3)          (0,3)     (2,2) (2,1) (2,0)
           XOR=2[W]      XOR=3[W]  XOR=0 XOR=3 XOR=2
                                    [L]   [W]   [W]

Each node shows (pile1, pile2), XOR value, and [W]in/[L]ose. The first player at (2,3) should move to any XOR=0 state. Only (2,2) has XOR=0: remove 1 from pile 2.

Diagram 8: Misère vs Normal Nim -- the endgame difference

MISÈRE vs NORMAL NIM -- piles all <= 1:

  Normal play (last move wins):
    Piles: (1, 1, 1)  XOR = 1  [W for current player]
    Move: take one pile -> (1, 1, 0) XOR=0 [L for opponent]
    Opponent takes one -> (1, 0, 0) XOR=1 [W]
    You take last -> WIN

  Misère play (last move LOSES):
    Piles: (1, 1, 1)  XOR = 1  [L for current player!]
    Any move -> (1, 1, 0) XOR=0 -> opponent takes -> (1,0,0)
    -> you're forced to take last -> LOSE

  Rule difference:
    Normal:  XOR != 0 -> current player WINS
    Misère:  Same as normal EXCEPT when all piles <= 1:
             XOR != 0 -> current player LOSES (odd # of 1s)

Diagram 9: Sprague-Grundy composition -- 3 independent games

COMPOSITE GAME -- three independent "subtract {1,2}" games:

  Game A: pile=4        Game B: pile=2        Game C: pile=5
  g(4) = 4 mod 3 = 1   g(2) = 2 mod 3 = 2   g(5) = 5 mod 3 = 2

  Composite Grundy = g(A) ⊕ g(B) ⊕ g(C) = 1 ⊕ 2 ⊕ 2

    01
  ⊕ 10
  ────
    11
  ⊕ 10
  ────
    01 = 1  != 0  ->  First player WINS

  Note: XOR of GRUNDY values, NOT pile sizes!
  Pile XOR = 4 ⊕ 2 ⊕ 5 = 3 (different number!)

Diagram 10: Mex Computation Visualized

  MEX (Minimum EXcludant) -- visual computation:

  Given a game position P, suppose its successors have Grundy values:
    successors of P -> {Grundy = 0, Grundy = 1, Grundy = 3, Grundy = 4}

  Lay out all non-negative integers, mark which are reachable:

    Value:     0    1    2    3    4    5    6  ...
    Present?   OK    OK    X    OK    OK    X    X
                         ▲
                         │
                    mex = 2  (first gap!)

  Another example -- successors have Grundy values: {1, 2, 4}

    Value:     0    1    2    3    4    5    6  ...
    Present?   X    OK    OK    X    OK    X    X
               ▲
               │
          mex = 0  (0 is not in the set)

  Edge case -- successors have Grundy values: {0, 1, 2, 3}

    Value:     0    1    2    3    4    5    6  ...
    Present?   OK    OK    OK    OK    X    X    X
                                   ▲
                                   │
                              mex = 4  (consecutive 0..3 -> mex is 4)

  ┌──────────────────────────────────────────────────────┐
  │ mex({})      = 0    (no successors = terminal = P)   │
  │ mex({0})     = 1    (can reach 0 -> you can win)      │
  │ mex({1,2,3}) = 0    (can't reach 0 -> you lose!)      │
  │ mex always returns the smallest non-negative integer  │
  │ NOT in the set -- nothing more, nothing less.          │
  └──────────────────────────────────────────────────────┘

Diagram 11: Normal vs Misère Play -- Endgame Comparison

  NORMAL vs MISÈRE NIM -- where they diverge:

  Piles: (1, 1, 1)

  ═══════════════════════════════════════════════════════
  NORMAL PLAY (last move wins):
  ═══════════════════════════════════════════════════════
    XOR = 1⊕1⊕1 = 1 != 0  ->  First player WINS
    Strategy: take one entire pile -> (1, 1, 0)
    Opponent takes a pile -> (1, 0, 0)
    You take the last pile -> (0, 0, 0)  YOU WIN OK

  ═══════════════════════════════════════════════════════
  MISÈRE PLAY (last move loses):
  ═══════════════════════════════════════════════════════
    XOR = 1⊕1⊕1 = 1 != 0  ->  but strategy DIFFERS!
    Strategy: take one entire pile -> (1, 1, 0)
    Opponent takes a pile -> (1, 0, 0)
    You MUST take last pile -> (0, 0, 0)  YOU LOSE X

    Correct misère play: leave OPPONENT with an odd
    number of size-1 piles.
    Take one pile -> (1, 1, 0). Two piles (even). Good!
    Opponent takes -> (1, 0, 0). One pile (odd for them).
    Wait -- you're forced to take. You lose.

    Actually: (1,1,1) under misère is a LOSING position.

  ═══════════════════════════════════════════════════════
  THE MISÈRE RULE (Nim only):
  ═══════════════════════════════════════════════════════
    If all piles <= 1:
      Normal: XOR = 0 -> lose    Misère: XOR = 0 -> WIN
      (Inverted! Want EVEN number of 1-piles in misère)
    If any pile > 1:
      Strategy is IDENTICAL to normal Nim.
      Play normally until you're about to leave all-1s,
      then adjust the last move to leave an ODD count.

  ┌───────────────────────────────────────────────────┐
  │ Misère Nim != "opposite of normal Nim".            │
  │ It's 99% the same -- only the final endgame with   │
  │ all piles <= 1 gets the inverted rule.             │
  └───────────────────────────────────────────────────┘

Diagram 12: Grundy Value Periodicity -- "Subtract {1,3}" Game

  GRUNDY VALUES for "subtract {1,3}" (remove 1 or 3 stones):

  Position n:   0   1   2   3   4   5   6   7   8   9  10  11  12
  Reachable:    -  {0} {1} {0, {1, {2, {1, {2, {3, {2, {3, {0, {3,
                          2}  3}  0}  3}  0}  1}  0}  1}  2}  1}
  Grundy g(n):  0   1   0   1   2   3   0   1   2   3   0   1   2

  How each Grundy value is computed (mex of reachable set):
    g(0) = mex({})           = 0     [terminal position]
    g(1) = mex({g(0)})       = mex({0})       = 1
    g(2) = mex({g(1)})       = mex({1})       = 0
    g(3) = mex({g(2),g(0)})  = mex({0,0})     = mex({0})     = 1
    g(4) = mex({g(3),g(1)})  = mex({1,1})     = mex({1})     = 0... 

  Wait, let me recompute carefully:
    g(4) = mex({g(3), g(1)}) = mex({1, 1}) = mex({1}) = 0
  
  Hmm, that gives period 2 (0,1,0,1,...). Let me redo:
    g(0)=0, g(1)=mex({0})=1, g(2)=mex({1})=0, 
    g(3)=mex({g(2),g(0)})=mex({0,0})=mex({0})=1
    g(4)=mex({g(3),g(1)})=mex({1,1})=mex({1})=0
    g(5)=mex({g(4),g(2)})=mex({0,0})=mex({0})=1
    
  Pattern:  0  1  0  1  0  1  0  1  ...   Period = 2

  ──────────────────────────────────────────────────
  Now compare "subtract {1,4}" -- trickier periodicity:
  ──────────────────────────────────────────────────

    g(0)=0  g(1)=1  g(2)=2  g(3)=3  
    g(4)=mex({g(3),g(0)})=mex({3,0})=1
    g(5)=mex({g(4),g(1)})=mex({1,1})=mex({1})=0
    g(6)=mex({g(5),g(2)})=mex({0,2})=1
    g(7)=mex({g(6),g(3)})=mex({1,3})=0
    g(8)=mex({g(7),g(4)})=mex({0,1})=2
    g(9)=mex({g(8),g(5)})=mex({2,0})=1
    g(10)=mex({g(9),g(6)})=mex({1,1})=0

  n:     0  1  2  3  4  5  6  7  8  9  10  11  12  13 ...
  g(n):  0  1  2  3  1  0  1  0  2  1   0   1   0   2 ...

  Pre-period: 0 1 2 3  (length 4)
  Period:     1 0 1 0 2  (length 5, starts at n=4)

  ┌──────────────────────────────────────────────────────┐
  │ LESSON: Don't assume periodicity starts at n=0.      │
  │ Some games have a "pre-period" of irregular values    │
  │ before the repeating cycle begins.                    │
  │                                                       │
  │ Safe approach:                                        │
  │  1. Compute g(0)..g(K) for large K (e.g., K=1000)    │
  │  2. Look for period P starting at offset S            │
  │  3. Verify: g(n) = g(S + (n-S) mod P) for all n >= S  │
  │  4. For contest: K = max(200, 3x(S+P)) is usually OK  │
  └──────────────────────────────────────────────────────┘

---

C++ STL Reference

Game theory problems rarely need heavy STL. Key utilities:

Function / Class	Header	What it does	Time Complexity
^ (XOR operator)	built-in	Bitwise XOR of integers	$O(1)$
__builtin_ctz(x)	built-in	Count trailing zeros (lowest set bit)	$O(1)$
__builtin_clz(x)	built-in	Count leading zeros (find highest set bit)	$O(1)$
bitset<N>	<bitset>	Fixed-size bit array; useful for large Grundy sets	$O(N/64)$ per op
unordered_set<int>	<unordered_set>	Store reachable Grundy values for mex computation	$O(1)$ avg lookup
vector<int>	<vector>	DP table for Grundy values	$O(1)$ access
set<int>	<set>	Ordered reachable set when you need mex via lower_bound	$O(\log n)$

---

Implementation (Contest-Ready)

Version 1: Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

// Standard Nim: XOR all pile sizes.
void solve_nim() {
    int n; cin >> n;
    int xorSum = 0;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        xorSum ^= a;
    }
    cout << (xorSum ? "First" : "Second") << "\n";
}

// Compute mex of a set of non-negative integers.
int mex(const vector<int>& s) {
    unordered_set<int> st(s.begin(), s.end());
    for (int i = 0; ; i++)
        if (!st.count(i)) return i;
}

// Grundy values for a single-pile game with a given move set.
// moves[] = sorted list of allowed removals (e.g., {1,2,3}).
vector<int> grundy_table(int maxn, const vector<int>& moves) {
    vector<int> g(maxn + 1, 0);
    for (int n = 1; n <= maxn; n++) {
        vector<int> reach;
        for (int m : moves)
            if (n >= m) reach.push_back(g[n - m]);
        g[n] = mex(reach);
    }
    return g;
}

// Sprague-Grundy for multiple independent sub-games.
void solve_sg() {
    int k; cin >> k;
    vector<int> moves;
    int numMoves; cin >> numMoves;
    moves.resize(numMoves);
    for (int& m : moves) cin >> m;

    auto g = grundy_table(100000, moves);

    int games; cin >> games;
    while (games--) {
        int n; cin >> n;
        int xorSum = 0;
        for (int i = 0; i < n; i++) {
            int pile; cin >> pile;
            xorSum ^= g[pile];
        }
        cout << (xorSum ? "First" : "Second") << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve_nim();
    return 0;
}

Version 2: Explained Version

#include <bits/stdc++.h>
using namespace std;

// mex (Minimum EXcludant): smallest non-negative integer NOT in the set.
// Example: mex({0,1,3}) = 2, mex({1,2}) = 0, mex({}) = 0.
int mex(const vector<int>& reachable_grundy) {
    unordered_set<int> seen(reachable_grundy.begin(), reachable_grundy.end());
    // Walk from 0 upward until we find a gap.
    for (int i = 0; ; i++)
        if (!seen.count(i)) return i;
}

// Build a Grundy table for positions 0..maxn.
//
// For each position n, compute g(n) = mex({g(n - m) : m in moves, m <= n}).
// g(0) = 0 by convention (terminal position = losing = Grundy 0).
//
// After computing, look for a cycle. Many games have periodic Grundy values
// after some prefix. If you find a cycle, you can answer arbitrary n in O(1).
vector<int> grundy_table(int maxn, const vector<int>& moves) {
    vector<int> g(maxn + 1, 0);
    for (int n = 1; n <= maxn; n++) {
        vector<int> reach;
        for (int m : moves) {
            if (n >= m) {
                // From position n, removing m stones reaches position n-m.
                // The Grundy value of that successor is g[n-m].
                reach.push_back(g[n - m]);
            }
        }
        g[n] = mex(reach);
    }
    return g;
}

// Detect the cycle in a Grundy sequence.
// Returns {offset, period} such that g[offset + i] == g[offset + period + i]
// for all valid i. Useful for handling n up to 10^9 or 10^18.
pair<int,int> detect_cycle(const vector<int>& g, int minPeriod = 1) {
    int n = (int)g.size();
    // Try each candidate period length.
    for (int p = minPeriod; p <= n / 3; p++) {
        // Check if the last 2*p values form two identical blocks.
        bool ok = true;
        int start = n - 2 * p;
        if (start < 0) continue;
        for (int i = 0; i < p && ok; i++)
            if (g[start + i] != g[start + p + i]) ok = false;
        if (ok) {
            // Find where the cycle starts by scanning backwards.
            int offset = start;
            while (offset > 0 && g[offset - 1] == g[offset - 1 + p])
                offset--;
            return {offset, p};
        }
    }
    return {-1, -1}; // no cycle found in computed range
}

// Solve standard Nim: read pile sizes, XOR them, print winner.
void solve_nim() {
    int n;
    cin >> n;
    int xorSum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        // Bouton's theorem: Grundy value of a Nim pile = pile size.
        // XOR of all Grundy values = XOR of all pile sizes.
        xorSum ^= a;
    }
    // XOR != 0 => current player (first) can force a win.
    // XOR == 0 => current player loses with optimal opponent.
    cout << (xorSum ? "First" : "Second") << "\n";
}

// Solve a Sprague-Grundy composite game:
// Multiple independent sub-games, each is a single-pile game with custom moves.
void solve_sprague_grundy() {
    int numMoves;
    cin >> numMoves;
    vector<int> moves(numMoves);
    for (int& m : moves) cin >> m;

    // Pre-compute Grundy values up to the max pile size.
    // If piles can be up to 10^5, this table suffices.
    auto g = grundy_table(100000, moves);

    int games;
    cin >> games;
    while (games--) {
        int n;
        cin >> n;
        int xorSum = 0;
        for (int i = 0; i < n; i++) {
            int pile;
            cin >> pile;
            // Each sub-game contributes its Grundy value.
            // The composite game's Grundy value is the XOR of all.
            xorSum ^= g[pile];
        }
        cout << (xorSum ? "First" : "Second") << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve_nim();
    return 0;
}

---

Operations Reference

Operation	Time	Space
Standard Nim (XOR of $n$ piles)	$O(n)$	$O(1)$
Grundy table for positions $0..N$ with $k$ moves	$O(Nk)$	$O(N)$
mex of a set of size $k$	$O(k)$	$O(k)$
Cycle detection in Grundy sequence	$O(N)$	$O(N)$
Query with detected cycle (arbitrary $n$)	$O(1)$	$O(\text{period})$
Sprague-Grundy for $m$ games of $n$ piles each	$O(mn)$	$O(N)$ for table

---

Problem Patterns & Tricks

Pattern 1: Pure Nim

Direct application of Bouton's theorem. XOR all pile sizes. If constraints are small, this is the entire solution.

int xorSum = 0;
for (int x : piles) xorSum ^= x;
cout << (xorSum ? "First" : "Second");

Examples: CF 850C, CSES 1730 (Nim Game I)

Pattern 2: Nim with Restricted Moves (Grundy Table)

Allowed removals are a subset $S\subset \{1,2,\dots ,k\}$ instead of "any positive number." Compute Grundy values via DP, find the cycle, then answer queries.

// Subtraction game: can remove elements in set S.
auto g = grundy_table(MAXN, S);
// Often g[] is periodic. Detect cycle for large n.

Examples: CSES 1731 (Nim Game II), CF 305C

Pattern 3: Multi-Game XOR (Sprague-Grundy Decomposition)

The game board consists of several independent sub-games. Compute each sub-game's Grundy value, then XOR them all. This is the most powerful and general pattern.

Key requirement: independence -- a move in sub-game $i$ must not affect sub-game $j$.

Examples: CF 850C, CSES 1734 (Grundy's Game variant)

Pattern 4: Staircase Nim

Piles are arranged on a staircase. On each turn, move any positive number of stones from pile $i$ to pile $i-1$ (pile 0 is a "ground" that doesn't count). Equivalent to playing Nim on only the odd-indexed piles.

int xorSum = 0;
for (int i = 1; i < n; i += 2) // XOR only odd-indexed piles
    xorSum ^= piles[i];

Examples: CF 812E, Lightoj 1199

Pattern 5: Misere Nim

Same as Nim but the last player to move loses. The XOR trick still works, with one twist: if all piles are size $\le 1$, the winner depends on parity (even number of piles = first player wins). Otherwise, the result is the same as normal Nim.

int xorSum = 0;
bool allOnes = true;
for (int x : piles) {
    xorSum ^= x;
    if (x > 1) allOnes = false;
}
if (allOnes)
    cout << (n % 2 == 0 ? "First" : "Second");
else
    cout << (xorSum ? "First" : "Second");

Examples: CSES 1732 (Nim Game variant), CF 305C

Pattern 6: Nim on Graphs / Game on DAG

Each player moves a token on a DAG. The Grundy value of a node is mex of its successors' Grundy values. Terminal node (no outgoing edges) has Grundy value 0. Process in reverse topological order.

// Compute Grundy values on a DAG via topological sort.
vector<int> g(n, 0);
for (int u : reverse_topo_order) {
    unordered_set<int> reachable;
    for (int v : adj[u]) reachable.insert(g[v]);
    g[u] = 0;
    while (reachable.count(g[u])) g[u]++;
}

Examples: CF 1498C, CSES 1733 (Staircase Nim generalization)

Pattern 7: Green Hackenbush / Nim Value of Graph Edges

Each edge in a graph is a "move" that deletes the edge (and any disconnected parts). For trees, the Grundy value of a vertex is the XOR of $(g(\text{child})+1)$ for each child. This transforms tree games into XOR computations.

int grundy_tree(int u, int par, vector<vector<int>>& adj) {
    int g = 0;
    for (int v : adj[u]) if (v != par)
        g ^= (grundy_tree(v, u, adj) + 1);
    return g;
}

Examples: CF 1498C, various Hackenbush problems on SPOJ

---

Contest Cheat Sheet

+----------------------------------------------------------------+
| GAME THEORY -- NIM & SPRAGUE-GRUNDY          CHEAT SHEET       |
+----------------------------------------------------------------+
| WHEN TO USE:                                                    |
|   - Two players, alternating turns, optimal play                |
|   - "Who wins?" with perfect information, no randomness         |
|   - Multiple independent sub-games played simultaneously        |
|                                                                 |
| KEY FORMULAS:                                                   |
|   Nim:     XOR of all pile sizes.  != 0 => P1 wins.            |
|   Grundy:  g(s) = mex({g(t) : t reachable from s})             |
|   Compose: g(G1+G2+...+Gk) = g(G1) ^ g(G2) ^ ... ^ g(Gk)     |
|   Misere:  same as Nim UNLESS all piles <= 1 (check parity)    |
|                                                                 |
| KEY CODE:                                                       |
|   int xorSum = 0;                                               |
|   for (int x : piles) xorSum ^= x;                             |
|   // or: xorSum ^= grundy[pile_size];                           |
|                                                                 |
| COMPLEXITY:                                                     |
|   Nim:    O(n) time, O(1) space                                 |
|   Grundy table: O(N * |moves|) time, O(N) space                |
|   Cycle in Grundy => O(1) per query after O(N*|moves|) precomp |
|                                                                 |
| GOTCHA:                                                         |
|   Misere != normal Nim. Check "all piles <= 1" edge case.      |
|   Sub-games must be INDEPENDENT for SG to apply.                |
+----------------------------------------------------------------+

---

Gotchas & Debugging

1. Misere Nim is NOT "just flip the answer"

A common mistake: "In misere Nim, just invert the normal Nim result." This is wrong. The correct rule: if all piles have size $\le 1$, the player facing an even number of piles wins (they can always leave the last pile for the opponent). If any pile has size $>1$, the result is the same as normal Nim (XOR != 0 means P1 wins). Always check the "all piles $\le 1$" special case.

2. Forgetting that $g(0)=0$

The terminal (no-move) position always has Grundy value 0. If you start your DP from 1 without initializing $g(0)=0$, all subsequent values will be wrong.

3. Move set must be exact

If the problem says "remove between 1 and $k$ stones," the move set is $\{1,2,\dots ,k\}$. If it says "remove any square number," the move set is $\{1,4,9,16,\dots \}$. Reading the move set wrong changes the Grundy values entirely.

4. Sub-game independence

Sprague-Grundy only works when sub-games are independent. If removing from pile A changes the available moves in pile B, you cannot simply XOR. You need DP over the full composite state.

5. Integer overflow in XOR

XOR itself never overflows (it's bitwise), but if you're computing pile sizes or Grundy values that exceed int range, use long long. The XOR of long long values works the same way.

6. Cycle detection off-by-one

When Grundy values are periodic with offset $d$ and period $p$, the value for large $n$ is g[d + (n - d) % p], NOT g[n % p]. The offset matters -- the first few values before the cycle starts may not follow the pattern.

7. mex efficiency

For small move sets (say $|S|\le 20$), the reachable set is small, and a simple loop to find mex is fine. For large move sets, use a bitset or boolean array to avoid $O(k\log k)$ overhead from sorted sets.

8. Debugging tip: print the Grundy table

When your game theory solution gives wrong answers, print the first 20-30 Grundy values manually and check them by hand. Often you'll spot a pattern error or an off-by-one in the move set.

auto g = grundy_table(30, moves);
for (int i = 0; i <= 30; i++)
    cerr << "g(" << i << ") = " << g[i] << "\n";

Mental Traps

"If both players play optimally, the result is determined -- I just need to find the winner." True, but "find the winner" is harder than it sounds. For Nim, the XOR gives you this instantly. For general impartial games, you need Sprague-Grundy theory. For games that are sums of smaller games, you XOR Grundy values. For general combinatorial games, even determining the winner is a research-level problem. Know which class your problem falls into before choosing a technique.

"Grundy value = who wins." Not exactly. Grundy value = the "Nim-equivalence" of the position. A position with Grundy value 0 is a losing position (current player loses). Grundy value > 0 means a winning position. The exact Grundy value matters when combining sub-games (you XOR them), but only the "zero vs. nonzero" distinction matters for a single isolated game.

"All combinatorial games reduce to Nim." All impartial combinatorial games under normal play are equivalent to a Nim pile of some size (by Sprague-Grundy). But partisan games (like Chess) do not reduce to Nim. And "reduce to Nim" means "the Grundy value tells you the winning strategy" -- it doesn't mean the game literally becomes a stone-pile game.

"The XOR is 0 so the position is losing -- I should just output L and move on." When you're in a losing position, every move leads to a winning position for your opponent. In competitive programming, flag this and don't waste time debugging. But in an interactive problem where you must play moves, try to maximize the chance of your opponent making a mistake.

"The Grundy table repeats, so I'll just compute a few values and assume periodicity." Dangerous shortcut. Many subtraction games have short, clean periods (e.g., "subtract {1,2}" -> period 3). But some games have long pre-periods before periodicity kicks in, and others (like Wythoff's game) have no exact periodicity at all. Always verify the period by computing significantly more values than you think you need -- at least 3x the conjectured period -- and confirm the pattern holds. A wrong period assumption silently gives wrong answers for large $n$.

"If XOR = 0, it's drawn / no winner." No. Under normal play convention, XOR = 0 means the current player is in a P-position (Previous player wins, i.e., current player loses). There are no draws in standard combinatorial game theory under normal or misère play. Every position is either a win or a loss. If you see "draw" in a game-theory problem, it's a red flag that the game might not be impartial, or it has a special termination rule -- re-read the problem statement carefully.

P-POSITIONS vs N-POSITIONS -- game graph for "subtract {1,2}":

  Position:  0     1     2     3     4     5     6     7     8
             P     N     N     P     N     N     P     N     N
             L     W     W     L     W     W     L     W     W

  Game graph (arrows = legal moves):

    0 ◄── 1 ◄── 2 ◄── 3 ◄── 4 ◄── 5 ◄── 6 ◄── 7 ◄── 8
    │           │     │           │     │           │
    └───────────┘     └───────────┘     └───────────┘
      (subtract 2)      (subtract 2)      (subtract 2)

  KEY INVARIANTS:
  ┌─────────────────────────────────────────────────┐
  │ • P-position: ALL moves lead to N-positions     │
  │ • N-position: AT LEAST ONE move to a P-position │
  │ • Terminal position (0) is always P (you lose)  │
  │ • No draws exist -- every node is P or N         │
  └─────────────────────────────────────────────────┘

  Grundy values:  0  1  2  0  1  2  0  1  2  <- period 3
  P = Grundy 0, N = Grundy > 0

Trap: "Computing Grundy values by brute force is always O(states x moves)."

For games with large state spaces, brute-force mex computation is too slow. Many games have periodic Grundy values -- after computing the first few hundred values, you find a repeating pattern (the Sprague-Grundy period). In contests, the expected approach is often: compute Grundy values for small cases, spot the period, and extrapolate. If you're brute-forcing Grundy values for $n\le {10}^{18}$, you're missing the pattern.

GRUNDY VALUE PERIODICITY:

  Game: take 1, 3, or 4 stones from a pile of n.

  n:       0  1  2  3  4  5  6  7  8  9  10 11 12 13 ...
  G(n):    0  1  1  2  3  0  1  1  2  3   0  1  1  2 ...
           └──────period = 5───────┘└──period = 5──┘

  For n = 10¹⁸: G(n) = G(n mod 5)

  ┌────────────────────────────────────────────────┐
  │ RECIPE for contest game-theory problems:       │
  │ 1. Compute G(0..200) by brute force            │
  │ 2. Print them, look for a period               │
  │ 3. Prove the period (or trust it for contest)  │
  │ 4. Answer: G(n) = G(n mod period)              │
  └────────────────────────────────────────────────┘

Trap: "Misère Nim is just 'flip the answer' from normal Nim."

Almost, but not quite. In normal Nim, the losing condition is XOR = 0. In misère Nim, the losing condition is also XOR = 0 EXCEPT when all piles are <= 1. When all piles are 0 or 1, the misère winner is the player who faces an odd number of piles (not even, as in normal play). The off-by-one at the boundary trips people up constantly.

MISÈRE vs NORMAL NIM -- the boundary case:

  Piles: [1, 1, 1]     XOR = 1

  Normal Nim:  XOR != 0 -> first player WINS
               Strategy: take 1 stone to make XOR = 0
               -> leaves [0, 1, 1], XOR = 0, second player loses

  Misère Nim:  All piles <= 1 and count is ODD
               -> first player LOSES (must take last stone)
               Wait -- XOR != 0 but first player loses!

  ┌──────────────────────────────────────────────────┐
  │ MISÈRE NIM COMPLETE RULE:                        │
  │                                                  │
  │ If any pile > 1: same as normal Nim              │
  │   (XOR != 0 -> first player wins)                │
  │                                                  │
  │ If ALL piles <= 1:                               │
  │   ODD number of 1s -> first player LOSES          │
  │   EVEN number of 1s -> first player WINS          │
  │                                                  │
  │ This is the ONLY difference from normal Nim.     │
  └──────────────────────────────────────────────────┘

---

Common Mistakes

1. Assuming Grundy values follow a simple formula based on move sizes. The "Nim with moves $\{1,2,3\}$" game has $g(x)=xmod4$ -- tempting to generalize to $g(x)=xmod(max(\text{move})+1)$. But with moves $\{1,3,4\}$, the Grundy sequence is $0,1,0,2,3,1,0,2,3,\dots$ -- not $xmod5$. There is no shortcut: always compute Grundy values via mex and then search for the actual period (which may have a pre-period). Don't pattern-match on move sizes.

Debug Drills

Drill 1. Grundy computation for large $n$.

int grundy[MAXN];
void compute_grundy(vector<int>& moves, int n) {
    grundy[0] = 0;
    for (int i = 1; i <= n; i++) {
        set<int> reachable;
        for (int m : moves) {
            if (i - m >= 0)
                reachable.insert(grundy[i - m]);
        }
        // compute mex
        int mex = 0;
        while (reachable.count(mex)) mex++;
        grundy[i] = mex;
    }
}
// Called with: compute_grundy(moves, 1000000000);

What's wrong?

The code logic is correct, but $n={10}^9$ means this loop runs a billion iterations -- TLE guaranteed. For large $n$, you must find the period of Grundy values (which is usually small for fixed move sets) and use modular arithmetic.

Fix: Compute Grundy values up to a reasonable bound (e.g., 1000), detect the period, then return grundy[n % period] (with care for the pre-period portion).

Drill 2. Nim solver for a Misère problem.

string solve(vector<int>& piles) {
    int xorSum = 0;
    for (int p : piles) xorSum ^= p;
    if (xorSum > 0) return "First";
    else return "Second";
}

// Problem says: "The player who takes the LAST stone LOSES."

What's wrong?

This solves normal Nim (last move wins), but the problem is Misère Nim (last move loses). In Misère Nim, the answer differs when all piles are $\le 1$: if the number of nonempty piles is odd, the second player wins (not the first).

Fix:

bool all_ones = all_of(piles.begin(), piles.end(), [](int p){ return p <= 1; });
if (all_ones) {
    int cnt = count_if(piles.begin(), piles.end(), [](int p){ return p == 1; });
    return (cnt % 2 == 0) ? "First" : "Second";  // opposite of normal Nim
}
return (xorSum > 0) ? "First" : "Second";  // same as normal Nim

Drill 3. Multi-game XOR assumes pile = Grundy.

int ans = 0;
for (int i = 0; i < n; i++) {
    // each sub-game: remove from pile[i], allowed moves = {1, 2, ..., pile[i]}
    ans ^= pile[i];  // using pile size as Grundy value
}
cout << (ans ? "First" : "Second") << endl;

What's wrong?

This assumes the Grundy value of a pile equals its size, which is only true for standard Nim (moves = {1, 2, ..., any amount}). If the game has restricted moves (e.g., take at most $k$ stones), the Grundy value is NOT the pile size -- it's pile[i] % (k+1) for the "take up to $k$" variant, or something else entirely for other rulesets. Always verify what the Grundy function actually is.

Fix: Compute the correct Grundy value for the specific game rules, e.g., ans ^= grundy(pile[i]) where grundy() is determined by the actual move set.

---

Self-Test

Before moving to practice problems, verify you can answer these without looking at the notes above:

1. State the Sprague-Grundy theorem -- for a sum of independent impartial games, the Grundy value of the whole is the ___ of the parts.

2. Define minimum excludant (mex) -- compute mex({0, 1, 3, 4}) by hand.

3. Solve a Nim position -- piles (3, 5, 6). Who wins? What is the first player's winning move?

4. State the misère Nim strategy -- explain precisely how it differs from normal Nim and when the difference matters.

5. Compute Grundy values -- for the game "subtract {1, 2}" with positions 0 through 6. Identify the period.

6. Composite game -- three independent sub-games have Grundy values 5, 3, and 6. Who wins the composite game? What single sub-game Grundy value would you need to change to make the second player win?

7. Identify the game class -- a problem says "two players alternate placing queens on a chessboard so they don't attack each other; the player who cannot place loses." Is this impartial or partisan? Does Sprague-Grundy apply directly?

8. Find the winning move in a composite game -- three sub-games have Grundy values 7, 2, and 4. The total XOR is 1. Which sub-game(s) can you modify to make the XOR zero, and what target Grundy value does each need?

9. Misère endgame detection -- piles are (1, 1, 1, 3). Under misère Nim, is the winning strategy different from normal Nim here? If so, what is the correct move?

10. Periodicity verification -- for "subtract {1, 4, 5}", you compute Grundy values: 0,1,0,1,2,3,2,3,0,1,0,1,2,3,2,3,... Is the period 8 or 4? How many values should you compute to be confident?

• [ ] Compute the Grundy values for the game "take 1, 3, or 4 stones" for $n=0$ to $12$. Identify the period and predict $G(1000)$.
• [ ] Given piles [3, 5, 6] in normal Nim, find the XOR, determine the winner, and specify the optimal first move (which pile to reduce, and to what size).
• [ ] Explain why Sprague-Grundy theory does NOT apply to Chess -- identify which assumption (impartial, normal play, perfect information) fails.
• [ ] Solve misère Nim for piles [1, 1, 1, 1, 1]: compute the XOR, check the all-piles-<=-1 boundary condition, and state the winner.
• [ ] Given a game that is the sum of three sub-games with Grundy values $G_1=3$, $G_2=5$, $G_3=6$, compute the overall Grundy value and determine if the first player wins.

11. Grundy value composition -- game A has Grundy value 0, game B has Grundy value 0. A player must move in exactly one game per turn. Who wins the composite game? What if game A has Grundy value 0 and game B has Grundy value 3?

12. Sprague-Grundy applicability -- a problem says "two players alternately claim edges of a graph; a player who completes a cycle loses." Does Sprague-Grundy apply? What makes this tricky?

Quick self-check -- tick each box when you can do it cold:

• [ ] Given Nim piles $(7,3,5)$, compute the XOR, identify the winning move (which pile to reduce and to what value), and verify the resulting XOR is 0.
• [ ] For the game "subtract $\{1,3\}$", build the Grundy table for $n=0..11$, identify the period and pre-period, and predict $g(100)$.
• [ ] Three independent sub-games have Grundy values $6,4,2$. Determine who wins, then find a move in one sub-game that makes the composite position losing for your opponent.
• [ ] Piles are $(1,1,0,1)$ under misère Nim. Determine whether the strategy differs from normal Nim and state the correct move.
• [ ] A problem says "Alice and Bob take turns removing 1-3 stones from a single pile; the player who takes the last stone loses." Classify: impartial? Normal or misère? Then solve for pile size 7.

---

Practice Problems

CF Rating	What You Should Be Able To Do
1200	Know Nim: XOR all pile sizes; if nonzero, first player wins
1500	Compute Grundy values by hand for small games; recognize "independent sub-games -> XOR"
1800	Implement Grundy DP for games on DAGs; spot Grundy value periodicity in restricted Nim variants
2100	Solve multi-game compositions; handle Misère Nim; combine Sprague-Grundy with other techniques (bitmask DP, segment trees)

#	Problem	Source	Difficulty	Key Idea
1	Nim Game I	CSES	Easy	Pure Nim, XOR of piles
2	Nim Game II	CSES	Easy	Nim with restricted move set, Grundy table
3	Staircase Nim	CSES	Medium	XOR only odd-indexed piles
4	Grundy's Game	CSES	Medium	Split pile into two unequal parts, Grundy values
5	Another Game	CF 305C	Medium	Nim variant, careful with move rules
6	Arpa and a game with Mojtaba	CF 850C	Medium-Hard	Sprague-Grundy on digit-based game
7	Two Gymno	CF 1498C	Medium	Game on planar graph, Grundy on DAG
8	Matching Game	CF 812E	Hard	Staircase Nim reduction
9	Nim Extreme	AtCoder	Hard	Number theory + Nim
10	Sprague-Grundy	YosupoJudge	Easy	Standard Nim verification

---

Further Reading

• cp-algorithms: Sprague-Grundy theorem -- thorough treatment with proofs.
• cp-algorithms: Games on arbitrary graphs -- Grundy values on DAGs.
• Codeforces Blog: Game Theory for CP -- community-curated problem list.
• Thomas Ferguson, "Game Theory" (UCLA) -- rigorous combinatorial game theory reference.
• Winning Ways for Your Mathematical Plays by Berlekamp, Conway, Guy -- the definitive textbook (academic, not a quick read).
• For Misere games beyond Nim, see the Misere Quotient theory -- rarely needed in contests but intellectually deep.

Related Techniques

• Bit Manipulation -- Nim's XOR characterization connects game theory directly to bitwise operations
• DP -- Bitmask -- complex games often require bitmask DP to compute Grundy values
• Inclusion-Exclusion -- counting winning positions sometimes uses PIE over game states

---