Algorithms
Game Theory
Difficulty: Advanced
Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero....
Game Theory
Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero. That is Nim, and the surprise is not that it has a strategy but that the strategy is so compact. The Sprague-Grundy theorem extends the same idea to every impartial combinatorial game.
Game Theory introduces the algorithmic side of two-player game analysis. You will work through Nim and its XOR strategy, then see how the Sprague-Grundy theorem assigns a Grundy number (nimber) to every position and how XOR-of-nimbers solves any sum of games. The lesson then moves to general game trees: minimax for optimal play, alpha-beta pruning for cutting branches that cannot affect the result, and move ordering for better pruning. You will analyze game states using DP, classifying positions as winning or losing by computing backward from terminal states, and meet retrograde analysis as a complete-game-state technique.
In Dynamic Programming (Intro), you learned to recurse on subproblems and cache results. Recursion Fundamentals gave you the call-stack model behind minimax and Grundy computation. Game theory recasts those tools as adversarial search.
Next, Randomized Algorithms turns to a different way of taming worst-case inputs.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Determine the winning strategy in Nim using the XOR of pile sizes.
Compute Grundy numbers for simple game positions and combine games using the Sprague-Grundy theorem.
Implement the Minimax algorithm for two-player zero-sum games.
Apply Alpha-Beta pruning to reduce the Minimax search space.
Classify game positions as winning or losing using dynamic programming on game states.
Why This Matters
01
The Nim game and Sprague-Grundy theorem provide a complete mathematical framework for analyzing any impartial combinatorial game -- understanding them unlocks an entire class of competitive programming problems.
02
Minimax is the foundation of game-playing AI, from chess engines to Go programs. Alpha-Beta pruning makes it practical by eliminating branches that cannot affect the outcome.
03
Game state analysis using DP teaches you to think backward from terminal states -- a powerful problem-solving technique that extends to many optimization problems.
04
Combinatorial game theory problems appear regularly in competitive programming contests and occasionally in advanced coding interviews.
Key Terms
6 terms you'll encounter in this lesson
Nim
A two-player game where players take turns removing objects from piles. The player who takes the last object wins (normal play). The winning strategy is based on the XOR of all pile sizes.
Grundy Number (Nimber)
A non-negative integer assigned to each game position. The Grundy number equals the minimum excludant (mex) of the Grundy numbers of all positions reachable in one move. A position with Grundy number 0 is a losing position.
Minimum Excludant (mex)
The smallest non-negative integer NOT in a given set. For example, mex({0, 1, 3}) = 2. Used to compute Grundy numbers.
Sprague-Grundy Theorem
Any impartial game position is equivalent to a Nim heap of size equal to its Grundy number. The Grundy number of a combination of independent games is the XOR of their individual Grundy numbers.
Minimax
An algorithm for two-player zero-sum games. The maximizing player picks the move with the highest value; the minimizing player picks the move with the lowest value. Both play optimally.
Alpha-Beta Pruning
An optimization of Minimax that skips branches that cannot affect the final decision. Alpha is the best value the maximizer can guarantee; beta is the best value the minimizer can guarantee. Prune when alpha >= beta.
Heads Up
Common misconceptions to watch out for
"In Nim, the player who goes first always wins"
The first player wins only if the XOR of all pile sizes is nonzero. If the XOR is 0, the second player has the winning strategy. The starting position determines who wins, not who moves first.
"Alpha-Beta pruning changes the result of Minimax"
Alpha-Beta pruning returns exactly the same result as full Minimax -- it only skips branches that are provably irrelevant. It is a pure optimization, not an approximation.
"Grundy numbers only work for Nim"
The Sprague-Grundy theorem applies to all impartial combinatorial games (games where both players have the same moves). Nim is just the simplest example. The theorem lets you reduce any such game to an equivalent Nim position.