Two players take turns removing stones from a pile. You go first. Can you guarantee a win, no matter what your opponent does? At first glance, this seems like it requires simulating every possible sequence of moves. But with the right mathematical insight, you can often determine the winner in O(1) time, before a single stone is removed.

Game theory problems in coding interviews are deceptive. They look like brute-force simulation problems, but they almost always have elegant mathematical solutions. The key ideas, Nim values, XOR tricks, and Grundy numbers, form a small toolkit that covers a surprisingly wide range of problems. Once you learn to recognize the patterns, these problems become some of the fastest solves in an interview.

In this chapter, we will start with the fundamental concepts of winning and losing positions, work through the classic Nim game and its XOR-based solution, then build up to the Sprague-Grundy theorem, which generalizes these ideas to virtually any combinatorial game. By the end, you will have the tools to tackle any game theory problem that shows up in an interview.

Game theory problems appear regularly on LeetCode and in interviews at top companies. Problems like "Nim Game," "Stone Game," "Predict the Winner," "Can I Win," and "Flip Game II" all require game-theoretic thinking. They test whether you can identify mathematical structure instead of brute-forcing through game states.

Interview Insight: Interviewers use game theory problems to separate candidates who simulate from those who analyze. A candidate who recognizes that a Nim game reduces to a single XOR operation demonstrates strong mathematical problem-solving, which is exactly what these questions are designed to test.

Beyond interviews, combinatorial game theory has applications in AI (game-playing agents), economics (strategic decision-making), and algorithm design (adversarial analysis). The Sprague-Grundy theorem in particular is one of the most beautiful results in combinatorics, and understanding it gives you a powerful lens for reasoning about any turn-based game.

Winning and Losing Positions

Every game theory problem in interviews is built on one fundamental idea: every game state is either a winning position (W) or a losing position (L) for the player whose turn it is.

The rules are simple:

Think of it this way. If you are in a losing position, no matter what you do, your opponent ends up in a good spot. If you are in a winning position, there is at least one smart move that puts your opponent in a bad spot.

This recursive definition is the foundation of everything else in this chapter.

The diagram above shows a simple game where players take 1, 2, or 3 stones. Position 0 is a loss (no moves). Positions 1, 2, 3 are wins (you can take all remaining stones). Position 4 is a loss (every move leaves 1, 2, or 3 stones for your opponent, which are all winning positions). Position 5 is a win (take 1 to leave your opponent at position 4, a loss).

This pattern repeats: every multiple of 4 is a losing position. That is not a coincidence. It is the structure of the game.

The Nim Game and the XOR Trick

Nim is the most important game in combinatorial game theory. The setup is simple: there are several piles of stones. Two players alternate turns. On each turn, a player picks any one pile and removes any positive number of stones from it. The player who takes the last stone wins.

The solution to Nim is remarkably elegant. Compute the XOR (exclusive or) of all pile sizes. If the result is non-zero, the first player wins. If it is zero, the first player loses.

Why does this work? The key insight is that XOR has special properties:

When the XOR of all piles is zero, any move you make on a pile changes its value and makes the overall XOR non-zero. So your opponent is now in a non-zero XOR state. When the XOR is non-zero, there always exists a move that brings it back to zero. The winning strategy is to always leave your opponent facing a XOR of zero.

The terminal state (all piles empty) has a XOR of 0, which is a losing position for the player to move. So the chain of reasoning works: keep forcing XOR = 0 onto your opponent, and eventually they face all-empty piles with no moves.

Interview Insight: The Nim game XOR trick is a favorite interview question. LeetCode 292 (Nim Game) is the simplified single-pile version where you can take 1-3 stones. The answer is just checking if n % 4 != 0. But the multi-pile version uses XOR, and understanding why it works shows deep mathematical reasoning.

Sprague-Grundy Theorem and Grundy Numbers

What happens when the game is not standard Nim? What if the moves are restricted, or the game has a different structure? This is where the Sprague-Grundy theorem comes in, and it is one of the most powerful results in combinatorial game theory.

The theorem states that every impartial game (a game where both players have the same moves available from any position) is equivalent to a Nim pile of some size. That size is called the Grundy number (or nimber) of the position.

The Grundy number of a position is defined as:

where mex (minimum excludant) is the smallest non-negative integer NOT in the set. For example:

A position with Grundy number 0 is a losing position. A position with Grundy number greater than 0 is a winning position. This aligns perfectly with the W/L framework we established earlier.

The beauty of Grundy numbers goes further: when you have a game composed of independent sub-games (like multiple Nim piles), the Grundy number of the combined game is the XOR of the individual Grundy numbers. This is why XOR works for Nim: each pile is an independent sub-game, and the Grundy number of a pile of size n in standard Nim is simply n.

How to Compute Grundy Values

Computing Grundy numbers for a game follows a bottom-up approach, similar to dynamic programming.

This process is essentially filling in a DP table from the base case upward. For many games, the Grundy values follow a repeating pattern, which allows you to compute them in O(1) after discovering the cycle.

Minimax Approach

Some game theory problems cannot be reduced to Nim or Grundy numbers, particularly when the game is not impartial (meaning the two players have different objectives, like maximizing vs. minimizing a score). For these problems, the minimax approach is the standard technique.

The idea is straightforward: the maximizing player picks the move that maximizes the outcome, and the minimizing player picks the move that minimizes it. You can implement this with recursion and memoization.

Problems like "Stone Game" and "Predict the Winner" on LeetCode use this pattern. The state is typically represented as a range [i, j] of remaining elements, and you recurse on all possible moves (take from left or right), alternating between maximizing and minimizing.

Interview Insight: When you see a game problem where players choose optimally and the goal involves scores or values (not just win/lose), think minimax with memoization. When you see a game where the goal is simply "can the first player win?" and moves are symmetric, think Grundy numbers or direct W/L analysis.

Identifying Game Theory Problems in Interviews

Game theory problems share a few telltale signs:

The word "optimally" is your biggest clue. When a problem says "both players play optimally," it is telling you that brute-force simulation will not work because you need to account for the best possible play from both sides.

Once you identify a game theory problem, the next question is: which technique applies?

Building Game State Graphs

For problems where the state space is small enough, you can model the game as a directed graph. Each node is a game state, and each edge is a move. Terminal nodes (no outgoing edges) are losing positions for the player whose turn it is.

Once you build this graph, you can label every node as W or L using the rules from the Core Concepts section, working backward from the terminal states. This is essentially a BFS/DFS from the terminal nodes.

A position is W (winning) if at least one of its edges leads to an L (losing) position. A position is L if all of its edges lead to W positions. In the diagram, state 4 is a losing position because all three moves (take 1, 2, or 3) lead to states 3, 2, or 1, which are all winning positions for the opponent.

Computing Grundy Numbers Step by Step

Let us walk through computing Grundy numbers for a subtraction game. In this game, there is one pile of stones, and on each turn you can remove 1, 2, or 3 stones. The player who takes the last stone wins.

The move set is S = {1, 2, 3}.

We build the Grundy table from the bottom up:

The pattern is clear: G(n) = n % 4. This is the same result we got from the W/L analysis earlier, but now we have actual Grundy numbers, not just win/lose labels. The Grundy number tells us more: it tells us the "size" of the equivalent Nim pile, which matters when combining sub-games.

Combining Independent Sub-Games

The real power of Grundy numbers appears when you have a game made of independent sub-games. Suppose you have three piles with a subtraction game (remove 1, 2, or 3) played independently on each pile. The Grundy number of the combined game is:

If the combined Grundy number is non-zero, the first player wins. If it is zero, the second player wins. This is exactly the same as standard Nim, but now each "pile" might have a non-standard Grundy value due to restricted moves.

Dynamic Programming Approach to Game Problems

For problems like "Stone Game" or "Predict the Winner," where players take turns selecting from the ends of an array and the goal is to maximize their total score, the approach is interval DP.

The state is dp[i][j] representing the maximum score advantage the current player can achieve from the subarray arr[i..j]. On their turn, the current player either takes arr[i] or arr[j], and then becomes the "opponent" for the remaining subarray.

The subtraction is because after the current player takes a value, the opponent gets to play optimally on the remaining range, and dp[i+1][j] represents the opponent's advantage. The current player's net advantage is what they took minus the opponent's future advantage.

The base case is dp[i][i] = arr[i] (only one element left, the current player takes it).

The first player wins if dp[0][n-1] >= 0.

Example 1: Classic Nim Game

Problem: Three piles of stones with sizes [3, 4, 5]. Players alternate turns, removing any number of stones from a single pile. The player who takes the last stone wins. Does the first player win?

Solution using XOR:

But how does the first player actually win? They need to make a move that brings the XOR to zero.

The first player removes 2 stones from the pile of 3, leaving [1, 4, 5]. Now the XOR is 0, and no matter what the second player does, the XOR becomes non-zero again, and the first player can always restore it to zero. This continues until all piles are empty.

Example 2: Subtraction Game with Grundy Numbers

Problem: There are two independent piles with 5 and 7 stones respectively. From each pile, a player can remove 1, 2, or 3 stones. Players alternate turns (choosing any one pile per turn). Who wins?

Solution using Grundy numbers:

First, compute the Grundy number for each pile size. From our earlier analysis, for the subtraction game with moves {1, 2, 3}, we know G(n) = n % 4.

Now suppose the move set was {1, 3, 4} instead. We would need to recompute the Grundy values:

With move set {1, 3, 4}, G(5) = 3 and G(7) = 0. The combined Grundy number is 3 XOR 0 = 3, which is non-zero. The first player still wins, but through a different strategy.

Notice how changing the move set completely changes the Grundy values. This is why you cannot blindly apply the n % k shortcut. You need to compute the Grundy numbers from the actual move set.

Below are implementations of two core game theory algorithms: the Nim game solver (XOR-based) and Grundy number computation for a subtraction game.

Nim Game Solver

Determines whether the first player wins in a multi-pile Nim game by computing the XOR of all pile sizes.

Java

Python

C++

C#

JavaScript

TypeScript

Grundy Number Computation

Computes Grundy numbers for a subtraction game where players can remove any number of stones in a given move set.

Java

Python

C++

C#

JavaScript

TypeScript

Where:

The Nim game solver is extremely efficient because XOR reduces the entire game to a single bitwise operation per pile. Grundy number computation is essentially dynamic programming over the game states, with each state examining all possible moves. For interview problems, the state space is typically small enough that either approach runs well within time limits.

1. Confusing "First Player Wins" with "Current Player Wins"

Many candidates mix up the perspective. When computing whether a game state is winning, it is always from the perspective of the player whose turn it is at that state, not the first player globally. In a recursive solution, this means the "winning" player alternates at each level of recursion.

The fix: Always define your W/L labels or Grundy numbers relative to the "current player." When the problem asks "does the first player win?", evaluate the initial state and check if it is a winning position for the current player (who happens to be player 1).

2. Forgetting That Grundy Values Depend on the Move Set

A common mistake is assuming that the Grundy number of a pile of size n is always n (as it is in standard Nim). This is only true when you can remove any number of stones from 1 to n. If the move set is restricted (e.g., you can only remove 1, 2, or 3), the Grundy values change entirely.

The fix: Always compute Grundy numbers from the specific move set of the problem. Do not assume G(n) = n unless the game is standard Nim.

3. Not Recognizing Independent Sub-Games

The Sprague-Grundy theorem only applies when sub-games are truly independent, meaning a move in one sub-game does not affect any other sub-game. Some problems disguise this: for example, a game played on a grid might decompose into independent row games. Missing this decomposition means you cannot apply the XOR trick and end up with an exponential brute-force solution.

The fix: Ask yourself, "Can I decompose this game into parts where a move in one part does not affect other parts?" If yes, compute Grundy numbers for each part and XOR them together.

4. Off-by-One Errors in Game State DP

In interval DP problems like Stone Game, a common bug is getting the base case or the recurrence indices wrong. For example, dp[i][j] might represent the subarray from index i to j inclusive, but the recurrence accidentally uses dp[i+1][j] when the subarray should be [i+1, j].

The fix: Be explicit about whether your indices are inclusive or exclusive. Write out the base case (single element) and the simplest non-trivial case (two elements) by hand before coding. Verify your recurrence matches your index convention.

5. Trying to Simulate All Games Instead of Using Mathematical Properties

The instinct to brute-force through all possible game sequences is strong. For a game with n stones and two players, the game tree can be exponential. Candidates who try to simulate every possible game run out of time both in their solution and in the interview.

The fix: Look for mathematical patterns first. Check if the game is Nim or reducible to Nim. Try computing the first 10-20 Grundy values by hand and look for a repeating cycle. Most interview game theory problems have clean mathematical solutions. Simulation is the last resort, not the first.

Q1: In a game of Nim with piles [7, 11, 8, 4], does the first player win? Explain your reasoning.

Compute the XOR of all pile sizes:

The XOR is 0, so the first player loses with optimal play from both sides. The zero XOR means that no matter what move the first player makes, the XOR becomes non-zero, giving the second player a winning position. The second player can always make a move to restore the XOR to zero, maintaining their advantage until the game ends.

Q2: What is the Sprague-Grundy theorem, and why is it useful?

The Sprague-Grundy theorem states that every position in an impartial combinatorial game (one where both players have the same moves available) is equivalent to a Nim pile of some size. That size is the Grundy number, computed as the mex (minimum excludant) of the Grundy numbers of all positions reachable in one move. The theorem is useful because it reduces any impartial game to Nim. For compound games made of independent sub-games, the overall Grundy number is the XOR of the individual Grundy numbers. This means that no matter how complicated the rules of a game are, if it is impartial and decomposable, you can solve it by computing Grundy numbers for each component and XORing them together.

Q3: You have a game where players can remove 1, 4, or 5 stones from a pile. Compute the Grundy numbers for pile sizes 0 through 10.

Working through the mex computation:

The sequence is: 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, ... This has a period of 8 starting from position 0. So for any pile size n, G(n) can be computed from the repeating pattern, making it O(1) after finding the cycle.

Q4: Explain the difference between impartial and partisan games. Which technique applies to each?

In an impartial game, both players have exactly the same moves available from any position. Nim is the classic example: either player can remove stones from any pile. For impartial games, the Sprague-Grundy theorem applies, and you can compute Grundy numbers to determine the winner.

In a partisan game, the two players have different moves or different objectives. Chess is partisan because white and black move different pieces. "Predict the Winner" is partisan because player 1 wants to maximize their score while player 2 wants to maximize theirs. For partisan games, Grundy numbers do not apply. Instead, you use the minimax approach, typically implemented with dynamic programming (often interval DP). The state tracks whose turn it is, and each player makes the move that is optimal from their perspective.

In interviews, the distinction matters because applying the wrong technique wastes time. If the problem says "both players have the same moves" and "the player who cannot move loses," think Grundy. If the problem says "players choose optimally" and involves scores or different objectives, think minimax DP.