Game Theory Basics: Winning Positions, Nim and Minimax DP

Two-player game questions ("both players play optimally; does the first player win?") are DP on the game's state graph. Almost all of them reduce to one of three ideas: winning and losing positions, the XOR rule for Nim and its Sprague-Grundy generalization, and the "score difference" form of minimax.

Intuition

Consider games where two players alternate, both see everything, there is no chance, and the game always ends. If the available moves depend only on the position and not on whose turn it is (an impartial game) and the player who cannot move loses, every position is either:

• losing for the player to move (often called a P-position), or
• winning (an N-position).

Three rules label them all:

1. A position with no moves is losing.
2. A position is winning if some move leads to a losing position.
3. A position is losing if every move leads to a winning position.

Since the game graph has no cycles, a memoized DFS (or a loop in topological order) labels every position. That is already enough for many interview problems; the rest of the theory is about doing it faster.

Nim. Several piles; a move removes any positive number of stones from one pile; whoever takes the last stone wins. A position is losing exactly when the XOR of the pile sizes is 0. From XOR 0, any move changes one pile and makes the XOR non-zero; from a non-zero XOR s, pick a pile a that has a 1 at the highest bit of s and reduce it to a ^ s, which brings the XOR back to 0. The player facing XOR 0 can never take the last stone.

Sprague-Grundy. Every impartial game position behaves like a single Nim pile of size g, its Grundy number: g = mex (smallest non-negative integer not present) of the Grundy numbers of the positions it can move to. A position is losing iff g = 0, and a sum of independent games (move in exactly one of them per turn) has Grundy number equal to the XOR of the parts.

Scores instead of win/lose. When each move earns points and both players maximize their own total, store the best difference "my points minus your points" for the player to move: f(state) = max over moves of (gain - f(next state)). The opponent's optimal play is folded into the subtraction, so there is no separate min step.

When to use it in interviews / OAs

• "Both players play optimally. Return true if the first player wins."
• Taking stones, numbers or cards from piles or from the ends of a row.
• Several independent piles or boards played in parallel (XOR of Grundy numbers).
• "Return the maximum score the first player can get" or "can the first player at least tie": score difference DP.

Template: winning and losing positions

Players alternately pick an unused number from 1..m, adding it to a running total; whoever reaches desired_total wins. The state is the set of used numbers (a bitmask); the remaining target follows from it.

from functools import cache, reduce
from operator import xor


def can_i_win(max_choosable: int, desired_total: int) -> bool:
    if desired_total <= 0:
        return True
    if max_choosable * (max_choosable + 1) // 2 < desired_total:
        return False  # nobody can ever reach the total

    @cache
    def wins(used: int, remaining: int) -> bool:
        # True if the player to move can force a win
        for x in range(1, max_choosable + 1):
            if not used >> x & 1 and (x >= remaining or not wins(used | 1 << x, remaining - x)):
                return True  # reach the total now, or hand the opponent a losing position
        return False

    return wins(0, desired_total)

Template: Nim and Grundy numbers

def nim_winning_move(piles: list[int]) -> tuple[int, int] | None:
    # a move (pile index, new size) that leaves XOR 0, or None if the position is lost
    s = reduce(xor, piles, 0)
    if s == 0:
        return None
    for i, a in enumerate(piles):
        if a ^ s < a:  # this pile has a 1 at the highest set bit of s
            return i, a ^ s


def subtraction_game_first_wins(n: int, k: int) -> bool:
    # one pile, take 1..k stones per move: the multiples of k + 1 are the losing positions
    return n % (k + 1) != 0


def grundy_numbers(n_max: int, moves: list[int]) -> list[int]:
    # g[x] = mex of the Grundy numbers reachable from a pile of size x
    g = [0] * (n_max + 1)
    for x in range(1, n_max + 1):
        reachable = {g[x - m] for m in moves if m <= x}
        mex = 0
        while mex in reachable:
            mex += 1
        g[x] = mex
    return g


def multi_pile_first_wins(piles: list[int], moves: list[int]) -> bool:
    # several independent piles, each move removes an allowed amount from one pile
    g = grundy_numbers(max(piles), moves)
    return reduce(xor, (g[p] for p in piles), 0) != 0

Grundy numbers are usually periodic (for moves 1..k they cycle with period k + 1), so printing the first few dozen values often reveals a closed form.

Template: score difference

Take a number from either end of a row; f[i][j] is the best difference for the player to move on nums[i..j]. The first player wins (or ties) iff f[0][n-1] >= 0. One array, reused in place, is enough because length-L intervals only need length L - 1 ones.

def best_score_difference(nums: list[int]) -> int:
    n = len(nums)
    f = nums[:]  # intervals of length 1: take the only number
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            f[i] = max(nums[i] - f[i + 1], nums[j] - f[i])  # f[i + 1] and f[i] are length - 1
    return f[0]


def take_up_to_three(values: list[int]) -> int:
    # players alternately take the next 1, 2 or 3 values from the front of the row
    n = len(values)
    f = [0] * (n + 1)  # f[i] = best difference for the player to move at position i
    for i in range(n - 1, -1, -1):
        best, taken = float("-inf"), 0
        for k in range(1, 4):
            if i + k > n:
                break
            taken += values[i + k - 1]
            best = max(best, taken - f[i + k])
        f[i] = best
    return f[0]

Complexity

Win/lose labeling is O(states + moves). Nim is O(n). Grundy numbers up to N with m allowed moves cost O(N * m). The interval score game is O(n^2), the front-taking game O(n). Bitmask games cost O(2^m * m).

Common pitfalls

• Perspective: values must always be "for the player to move". Mixing "first player" and "current player" breaks the recursion.
• Normal vs misere play: if the player who takes the last stone loses, the rules change (misere Nim has a special case when all piles are 1). Read the statement twice.
• Applying Sprague-Grundy to a non-impartial game: if the two players have different moves, Grundy numbers do not apply; use minimax on (state, player).
• Forgetting impossible totals: in pick-a-number games, check first whether the target is reachable at all.
• Cycles: if positions can repeat (moving on a graph), plain memoized recursion loops forever; label states backward from terminal positions with a BFS instead.

Interview variations

• Nim game with one pile and moves 1..3: lose iff n % 4 == 0.
• Divisor game: the first player wins iff n is even (prove it with the win/lose rules on small n).
• Stone games: pick from either end (interval difference DP), take from the front with varying limits (suffix difference DP).
• Predict the winner: difference >= 0.
• Can I win: bitmask memoization over used numbers.
• Several piles with restricted moves: XOR of Grundy numbers.
• Chalkboard XOR game: reason directly about the XOR of the whole board and the parity of its length.