Everything you need to solve game theory problems in CP -- from Nim and Sprague-Grundy fundamentals to minimax, alpha-beta pruning, and classic competition problems. Full code in C++ and Python with proofs and visual examples.
Combinatorial game theory (CGT) studies two-player games with perfect information where both players know the entire game state at all times. These are not the "game theory" from economics (Nash equilibria, mixed strategies) -- these are deterministic, sequential games where the last player to move either wins or loses.
A game qualifies as a combinatorial game if it satisfies all of the following:
1. Two players -- they alternate turns.
2. Perfect information -- both players see the entire game state. No hidden cards, no fog of war.
3. No randomness -- no dice, no shuffling, no probability. The outcome is entirely determined by player choices.
4. Finite -- the game must end in a finite number of moves. No infinite loops.
5. Normal play convention -- the player who cannot move loses. (The misère convention reverses this -- the player who cannot move wins.)
Examples that fit: Nim, Chess (abstractly), Go, Tic-Tac-Toe. Examples that do NOT fit: Poker (hidden info), Backgammon (dice), Rock-Paper-Scissors (simultaneous moves).
An impartial game is one where both players have the exact same set of available moves from any position. Nim is impartial -- either player can take stones from any pile. A partisan game is one where players have different move sets. Chess is partisan -- you can only move your own pieces.
Almost all game theory problems in competitive programming are impartial games under normal play convention. This is great news because it means we can use the Sprague-Grundy theorem to solve them systematically.
Every combinatorial game can be modeled as a directed acyclic graph (DAG). Each node is a game state, and each edge is a valid move. Terminal nodes (no outgoing edges) are positions where the current player loses (under normal play). Because the game is finite and has no cycles, we can always do backward induction from the terminal states.
The foundation of all game theory in CP: classifying every position as either a winning position or a losing position for the player whose turn it is.
Rule 1: A terminal position (no moves available) is a P-position (the current player loses because they cannot move).
Rule 2: A position is an N-position if there exists at least one move to a P-position (the current player can move to a state where the opponent loses).
Rule 3: A position is a P-position if every move leads to an N-position (no matter what the current player does, the opponent will be in a winning state).
Consider a game with a pile of n stones. On each turn, a player can remove 1, 2, or 3 stones. The player who takes the last stone wins.
n=0: No moves → P-position (current player loses)
n=1: Can move to 0 (P) → N-position (take 1, win)
n=2: Can move to 1(N) or 0(P) → N-position (take 2, win)
n=3: Can move to 2(N), 1(N), or 0(P) → N-position (take 3, win)
n=4: Can move to 3(N), 2(N), 1(N) → all N-positions → P-position!
n=5: Can move to 4(P) → N-position
Pattern: P-positions are exactly the multiples of 4: {0, 4, 8, 12, ...}
Python
def classify_positions(n, moves):
# Classify all positions 0..n as P or N
# pos[i] = True means N-position (current player wins)
pos = [False] * (n + 1) # pos[0] = False (P-position)
for i in range(1, n + 1):
for m in moves:
if i >= m and not pos[i - m]:
pos[i] = True # Found a move to a P-position
break
return pos
# Subtraction game with moves {1, 2, 3}
positions = classify_positions(20, [1, 2, 3])
for i in range(21):
print(f"n={i}: {'N' if positions[i] else 'P'}")C++
#include <bits/stdc++.h>
using namespace std;
vector<bool> classifyPositions(int n, vector<int>& moves) {
vector<bool> pos(n + 1, false); // pos[0] = false (P-position)
for (int i = 1; i <= n; i++) {
for (int m : moves) {
if (i >= m && !pos[i - m]) {
pos[i] = true; // move to a P-position exists
break;
}
}
}
return pos;
}
int main() {
vector<int> moves = {1, 2, 3};
auto pos = classifyPositions(20, moves);
for (int i = 0; i <= 20; i++)
cout << "n=" << i << ": " << (pos[i] ? "N" : "P") << "\n";
}When you see a game theory problem, always start by computing positions for small values (n=0 through n=20 or so). Look for a pattern. Most CP game theory problems have a clean mathematical pattern that you can prove and then compute in O(1).
Nim is the most fundamental game in combinatorial game theory. Understanding Nim is the key to understanding virtually every game theory problem in CP.
There are k piles of stones with sizes n1, n2, ..., nk. Two players alternate turns. On each turn, a player must choose one pile and remove at least one stone from it (they can remove the entire pile). The player who takes the last stone wins (normal play).
We prove three things:
(1) Terminal position has nim-sum 0. The only terminal position is all piles empty: 0 ⊕ 0 ⊕ ... ⊕ 0 = 0. This is indeed a P-position.
(2) From any position with nim-sum ≠ 0, there exists a move to a position with nim-sum 0. Let S = n1 ⊕ ... ⊕ nk ≠ 0. Let d be the position of the highest set bit in S. There exists some pile ni that has this bit set (otherwise the XOR would not have it). Now ni ⊕ S < ni (because we cleared the highest bit and possibly set lower ones). So we can reduce pile i from ni to ni ⊕ S. After this move, the new XOR is S ⊕ ni ⊕ (ni ⊕ S) = 0.
(3) From any position with nim-sum 0, every move leads to a position with nim-sum ≠ 0. If we change pile i from ni to ni′ where ni′ < ni, then ni ≠ ni′, so ni ⊕ ni′ ≠ 0. The new XOR is 0 ⊕ ni ⊕ ni′ = ni ⊕ ni′ ≠ 0.
Together: P-positions (nim-sum 0) and N-positions (nim-sum ≠ 0) satisfy our classification rules exactly.
Python
def nim_winner(piles):
"""Return 'First' if the first player wins, 'Second' otherwise."""
xor_sum = 0
for p in piles:
xor_sum ^= p
return "First" if xor_sum != 0 else "Second"
def nim_winning_move(piles):
"""Find a winning move: return (pile_index, new_size) or None."""
xor_sum = 0
for p in piles:
xor_sum ^= p
if xor_sum == 0:
return None # losing position, no winning move
for i, p in enumerate(piles):
target = p ^ xor_sum
if target < p:
return (i, target) # reduce pile i to target
return None
# Example: piles = [3, 4, 5]
# XOR = 3^4^5 = 2 != 0, so first player wins
print(nim_winner([3, 4, 5])) # "First"
print(nim_winning_move([3, 4, 5])) # (2, 7) -- reduce pile 2 from 5 to 7? No...
# Actually: 3^4^5 = 010 XOR 100 XOR 101 = 011 = 2
# Pile 0: 3^2 = 1 < 3? Yes! Reduce pile 0 from 3 to 1.
# New state: [1, 4, 5], XOR = 1^4^5 = 0. Winning move!C++
#include <bits/stdc++.h>
using namespace std;
string nimWinner(vector<int>& piles) {
int xorSum = 0;
for (int p : piles) xorSum ^= p;
return xorSum ? "First" : "Second";
}
pair<int, int> nimWinningMove(vector<int>& piles) {
int xorSum = 0;
for (int p : piles) xorSum ^= p;
if (xorSum == 0) return {-1, -1}; // losing
for (int i = 0; i < piles.size(); i++) {
int target = piles[i] ^ xorSum;
if (target < piles[i])
return {i, target};
}
return {-1, -1};
}
int main() {
vector<int> piles = {3, 4, 5};
cout << nimWinner(piles) << "\n";
auto [idx, val] = nimWinningMove(piles);
cout << "Reduce pile " << idx << " to " << val << "\n";
}In misère Nim the player who takes the last stone loses. The strategy changes slightly: if all piles have size ≤ 1, the losing position is when there is an odd number of piles. Otherwise, the XOR strategy is the same as normal Nim but you aim to leave an odd number of piles of size 1 when all piles are reduced to ≤ 1. Specifically: a misère Nim position is losing if and only if the XOR of all pile sizes is 0 AND all piles have size ≤ 1, or the XOR is nonzero AND at least one pile has size > 1.
The Sprague-Grundy theorem is the single most powerful tool in combinatorial game theory. It reduces every impartial game to a single non-negative integer -- the Grundy number (also called the nimber or SG-value) -- which tells you everything about the position.
A position is a P-position (losing for current player) if and only if its Grundy number is 0. A position is an N-position (winning) if and only if its Grundy number is nonzero. But Grundy numbers give us MORE than just win/lose -- they tell us how the game "behaves" when combined with other games.
Python
def compute_grundy(n, moves):
"""Compute Grundy numbers for positions 0..n in a subtraction game."""
grundy = [0] * (n + 1)
for i in range(1, n + 1):
reachable = set()
for m in moves:
if i >= m:
reachable.add(grundy[i - m])
# mex: smallest non-negative integer not in reachable
mex = 0
while mex in reachable:
mex += 1
grundy[i] = mex
return grundy
# Subtraction game with moves {1, 2, 3}
g = compute_grundy(16, [1, 2, 3])
for i in range(17):
print(f"G({i}) = {g[i]}")
# Output: 0,1,2,3,0,1,2,3,0,1,2,3,... (period 4)C++
#include <bits/stdc++.h>
using namespace std;
vector<int> computeGrundy(int n, vector<int>& moves) {
vector<int> grundy(n + 1, 0);
for (int i = 1; i <= n; i++) {
set<int> reachable;
for (int m : moves)
if (i >= m)
reachable.insert(grundy[i - m]);
int mex = 0;
while (reachable.count(mex)) mex++;
grundy[i] = mex;
}
return grundy;
}
int main() {
vector<int> moves = {1, 2, 3};
auto g = computeGrundy(16, moves);
for (int i = 0; i <= 16; i++)
cout << "G(" << i << ") = " << g[i] << "\n";
}Let us compute Grundy numbers for this less obvious case:
G(0) = mex({}) = 0
G(1) = mex({G(0)}) = mex({0}) = 1
G(2) = mex({G(1)}) = mex({1}) = 0 (can only remove 1)
G(3) = mex({G(2), G(0)}) = mex({0, 0}) = mex({0}) = 1
G(4) = mex({G(3), G(1), G(0)}) = mex({1, 1, 0}) = mex({0, 1}) = 2
G(5) = mex({G(4), G(2), G(1)}) = mex({2, 0, 1}) = 3
G(6) = mex({G(5), G(3), G(2)}) = mex({3, 1, 0}) = 2
G(7) = mex({G(6), G(4), G(3)}) = mex({2, 2, 1}) = mex({1, 2}) = 0
Pattern: 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, ... (period 7)
For subtraction games with a finite move set, Grundy numbers are eventually periodic. This is known as the Sprague-Grundy periodicity. In CP, compute enough values to spot the period, then answer any query in O(1).
The real power of Sprague-Grundy: when a game consists of multiple independent sub-games, the Grundy number of the combined game is the XOR of the Grundy numbers of the individual sub-games.
Each sub-game is equivalent to a Nim pile of its Grundy number. So the combined game is equivalent to a multi-pile Nim game with those pile sizes. And we already know how to solve multi-pile Nim -- XOR everything.
Suppose we have 3 independent piles of sizes 5, 8, 13 and the allowed moves in each pile are to remove 1, 3, or 4 stones (the S={1,3,4} subtraction game from above).
Grundy values for S = {1, 3, 4} repeat with period 7: [0, 1, 0, 1, 2, 3, 2]
G(5) = 3, G(8) = G(8 mod 7) = G(1) = 1, G(13) = G(13 mod 7) = G(6) = 2
Combined Grundy = 3 ⊕ 1 ⊕ 2 = 0
Result: Second player wins (P-position).
Python
def solve_combined_game(pile_sizes, moves):
"""Solve a game with multiple independent subtraction sub-games."""
# Compute enough Grundy values to find the period
max_val = max(moves) * 2 + max(pile_sizes) + 1
grundy = compute_grundy(max_val, moves)
# XOR all Grundy values
xor_sum = 0
for s in pile_sizes:
xor_sum ^= grundy[s]
return "First" if xor_sum != 0 else "Second"
print(solve_combined_game([5, 8, 13], [1, 3, 4])) # "Second"C++
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> moves = {1, 3, 4};
vector<int> piles = {5, 8, 13};
int maxVal = *max_element(piles.begin(), piles.end());
auto grundy = computeGrundy(maxVal, moves);
int xorSum = 0;
for (int p : piles) xorSum ^= grundy[p];
cout << (xorSum ? "First" : "Second") << "\n";
}The XOR rule only works when the sub-games are truly independent -- a move in one sub-game does not affect any other sub-game. If the sub-games interact (e.g., you can move stones between piles), you cannot simply XOR Grundy values. This is a common trap in CP problems.
While Sprague-Grundy handles impartial games elegantly, many CP and interview problems involve partisan games or games with scores (not just win/lose). For these, we use the minimax algorithm.
In a two-player game, one player (the maximizer) tries to maximize the score, while the other (the minimizer) tries to minimize it. At each node of the game tree:
Python
def check_winner(board):
"""Return 'X', 'O', or None."""
lines = [
[0,1,2], [3,4,5], [6,7,8], # rows
[0,3,6], [1,4,7], [2,5,8], # cols
[0,4,8], [2,4,6] # diagonals
]
for a, b, c in lines:
if board[a] == board[b] == board[c] and board[a] != '.':
return board[a]
return None
def minimax(board, is_maximizer):
"""X is maximizer (+1), O is minimizer (-1). Return best score."""
winner = check_winner(board)
if winner == 'X': return 1
if winner == 'O': return -1
if '.' not in board: return 0 # draw
if is_maximizer:
best = float('-inf')
for i in range(9):
if board[i] == '.':
board[i] = 'X'
best = max(best, minimax(board, False))
board[i] = '.'
return best
else:
best = float('inf')
for i in range(9):
if board[i] == '.':
board[i] = 'O'
best = min(best, minimax(board, True))
board[i] = '.'
return best
def best_move(board, is_maximizer):
"""Return the index of the best move."""
best_score = float('-inf') if is_maximizer else float('inf')
best_idx = -1
mark = 'X' if is_maximizer else 'O'
for i in range(9):
if board[i] == '.':
board[i] = mark
score = minimax(board, not is_maximizer)
board[i] = '.'
if is_maximizer and score > best_score:
best_score = score
best_idx = i
elif not is_maximizer and score < best_score:
best_score = score
best_idx = i
return best_idx
# Empty board, X goes first (maximizer)
board = list('.........')
print(minimax(board, True)) # 0 (draw with perfect play)C++
#include <bits/stdc++.h>
using namespace std;
char checkWinner(vector<char>& b) {
int lines[8][3] = {
{0,1,2},{3,4,5},{6,7,8},
{0,3,6},{1,4,7},{2,5,8},
{0,4,8},{2,4,6}
};
for (auto& l : lines)
if (b[l[0]] == b[l[1]] && b[l[1]] == b[l[2]] && b[l[0]] != '.')
return b[l[0]];
return '.';
}
int minimax(vector<char>& b, bool isMax) {
char w = checkWinner(b);
if (w == 'X') return 1;
if (w == 'O') return -1;
bool hasEmpty = false;
for (char c : b) if (c == '.') hasEmpty = true;
if (!hasEmpty) return 0;
int best = isMax ? -2 : 2;
for (int i = 0; i < 9; i++) {
if (b[i] == '.') {
b[i] = isMax ? 'X' : 'O';
int val = minimax(b, !isMax);
b[i] = '.';
best = isMax ? max(best, val) : min(best, val);
}
}
return best;
}
int main() {
vector<char> board(9, '.');
cout << minimax(board, true) << "\n"; // 0 (draw)
}Minimax without memoization explores the same game states repeatedly. For tic-tac-toe, there are 9! = 362880 possible game sequences but only ~5478 unique board states. Use a hash map to cache results. For larger games, this is the difference between TLE and AC.
Alpha-beta pruning optimizes minimax by eliminating branches that cannot possibly affect the final decision. It maintains two values, alpha and beta, representing the best options already available to the maximizer and minimizer respectively.
Alpha = the best (highest) value the maximizer can guarantee so far along the path.
Beta = the best (lowest) value the minimizer can guarantee so far along the path.
Prune when alpha ≥ beta. This means the maximizer already has a better option elsewhere, so the minimizer would never allow this branch to be reached (or vice versa).
Python
def alpha_beta(board, depth, alpha, beta, is_maximizer):
"""Minimax with alpha-beta pruning."""
winner = check_winner(board)
if winner == 'X': return 1
if winner == 'O': return -1
if '.' not in board: return 0
if is_maximizer:
max_eval = float('-inf')
for i in range(9):
if board[i] == '.':
board[i] = 'X'
val = alpha_beta(board, depth + 1, alpha, beta, False)
board[i] = '.'
max_eval = max(max_eval, val)
alpha = max(alpha, val)
if beta <= alpha:
break # Beta cutoff -- minimizer won't allow this
return max_eval
else:
min_eval = float('inf')
for i in range(9):
if board[i] == '.':
board[i] = 'O'
val = alpha_beta(board, depth + 1, alpha, beta, True)
board[i] = '.'
min_eval = min(min_eval, val)
beta = min(beta, val)
if beta <= alpha:
break # Alpha cutoff -- maximizer won't allow this
return min_eval
# Usage: alpha_beta(board, 0, float('-inf'), float('inf'), True)C++
int alphaBeta(vector<char>& b, int alpha, int beta, bool isMax) {
char w = checkWinner(b);
if (w == 'X') return 1;
if (w == 'O') return -1;
bool hasEmpty = false;
for (char c : b) if (c == '.') hasEmpty = true;
if (!hasEmpty) return 0;
if (isMax) {
int maxEval = -2;
for (int i = 0; i < 9; i++) {
if (b[i] == '.') {
b[i] = 'X';
maxEval = max(maxEval, alphaBeta(b, alpha, beta, false));
b[i] = '.';
alpha = max(alpha, maxEval);
if (beta <= alpha) break;
}
}
return maxEval;
} else {
int minEval = 2;
for (int i = 0; i < 9; i++) {
if (b[i] == '.') {
b[i] = 'O';
minEval = min(minEval, alphaBeta(b, alpha, beta, true));
b[i] = '.';
beta = min(beta, minEval);
if (beta <= alpha) break;
}
}
return minEval;
}
}
// Usage: alphaBeta(board, -2, 2, true)Alpha-beta pruning is most effective when the best moves are examined first. In chess engines, moves are ordered by captures, checks, and killer heuristics. In CP, if you can order moves from most promising to least, you can get close to the optimal O(bd/2) performance. Random ordering gives about O(b3d/4).
Many CP problems model games on directed graphs (DAGs). A token starts at some node, and players alternately move it along edges. The player who cannot move loses.
For a game on a DAG, we compute Grundy numbers via topological order. Nodes with no outgoing edges (sinks) have Grundy number 0. Then we process nodes in reverse topological order.
Python
def grundy_on_dag(adj, n):
"""Compute Grundy numbers for a game on a DAG with nodes 0..n-1."""
# Topological sort (Kahn's algorithm)
in_deg = [0] * n
for u in range(n):
for v in adj[u]:
in_deg[v] += 1
# Process in reverse topological order (sinks first)
grundy = [0] * n
order = []
q = []
for u in range(n):
if in_deg[u] == 0:
q.append(u)
# Actually, we need reverse topo -- process sinks first
# Use DFS-based approach instead
visited = [False] * n
computed = [False] * n
def dfs(u):
if computed[u]:
return grundy[u]
visited[u] = True
reachable = set()
for v in adj[u]:
reachable.add(dfs(v))
mex = 0
while mex in reachable:
mex += 1
grundy[u] = mex
computed[u] = True
return mex
for u in range(n):
if not computed[u]:
dfs(u)
return grundy
# Example DAG: 0->1, 0->2, 1->3, 2->3 (sinks: {3})
adj = [[1, 2], [3], [3], []]
g = grundy_on_dag(adj, 4)
print(g) # [2, 1, 1, 0]C++
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[100005];
int grundy[100005];
bool computed[100005];
int dfs(int u) {
if (computed[u]) return grundy[u];
computed[u] = true;
set<int> reachable;
for (int v : adj[u])
reachable.insert(dfs(v));
int mex = 0;
while (reachable.count(mex)) mex++;
grundy[u] = mex;
return mex;
}
int main() {
cin >> n;
int m; cin >> m;
while (m--) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
}
memset(computed, false, sizeof(computed));
for (int i = 0; i < n; i++)
if (!computed[i]) dfs(i);
// Now grundy[start] tells you if first player wins from 'start'
}If there are multiple tokens on the same DAG and each turn a player picks one token and moves it, this is a sum of independent games. The answer is the XOR of the Grundy numbers at each token's position.
DAG with nodes 0-5. Tokens at positions {1, 3, 4}.
If G(1)=2, G(3)=1, G(4)=3, then combined Grundy = 2 ⊕ 1 ⊕ 3 = 0.
Second player wins.
Staircase Nim is a beautiful variant that appears frequently in disguise in CP problems.
There are n stairs (indexed 0, 1, 2, ..., n-1) each containing some number of stones. On each turn, a player picks any stair i > 0 and moves any positive number of stones from stair i down to stair i-1. The player who cannot move loses (equivalently, the game ends when all stones are on stair 0).
Key insight: Moving stones from an even stair to an odd stair is essentially a "free" move that the opponent can mirror. If player A moves k stones from stair 2i to stair 2i-1, player B can immediately move those same k stones from stair 2i-1 to stair 2i-2, "canceling" the move. Stones on even stairs are irrelevant -- only odd stairs matter.
Since moves on odd stairs behave exactly like Nim (removing stones from an odd stair by moving them to the even stair below), the game reduces to standard Nim on the odd-indexed piles.
Python
def staircase_nim(stairs):
"""Return 'First' if first player wins, 'Second' otherwise."""
xor_sum = 0
for i in range(1, len(stairs), 2): # odd indices only
xor_sum ^= stairs[i]
return "First" if xor_sum != 0 else "Second"
# stairs[0]=3, stairs[1]=5, stairs[2]=1, stairs[3]=4
# XOR of odd indices: 5 ^ 4 = 1 != 0 -> First wins
print(staircase_nim([3, 5, 1, 4])) # "First"C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> stairs(n);
for (int i = 0; i < n; i++) cin >> stairs[i];
int xorSum = 0;
for (int i = 1; i < n; i += 2)
xorSum ^= stairs[i];
cout << (xorSum ? "First" : "Second") << "\n";
}Many CP problems are staircase Nim in disguise. Any time you see a game where moves shift resources "downward" through a sequence of positions, think staircase Nim. The classic example: Turning Turtles, where flipping coins on a line reduces to staircase Nim with binary encoding.
Wythoff's game is a two-pile Nim variant with an elegant connection to the golden ratio.
Two piles of stones (a, b). On each turn, a player can either:
The player who takes the last stone wins.
The P-positions of Wythoff's game partition the positive integers. Each positive integer appears exactly once among all the ak and bk values. This is a consequence of Beatty's theorem: if α and β are positive irrationals with 1/α + 1/β = 1, then the sequences ⌊nα⌋ and ⌊nβ⌋ partition the positive integers. Since 1/φ + 1/φ2 = 1, we get this beautiful partition.
Python
import math
def wythoff_is_losing(a, b):
"""Check if position (a, b) is a P-position (losing for current player)."""
if a > b:
a, b = b, a # ensure a <= b
phi = (1 + math.sqrt(5)) / 2
k = b - a # the difference determines k
return a == int(k * phi)
# Test first few P-positions
phi = (1 + 5 ** 0.5) / 2
for k in range(10):
a = int(k * phi)
b = int(k * phi * phi)
print(f"k={k}: ({a}, {b}) -- losing={wythoff_is_losing(a, b)}")
# Verify some N-positions
print(wythoff_is_losing(2, 3)) # False (N-position)
print(wythoff_is_losing(3, 5)) # True (P-position)C++
#include <bits/stdc++.h>
using namespace std;
bool wythoffIsLosing(long long a, long long b) {
if (a > b) swap(a, b);
double phi = (1.0 + sqrt(5.0)) / 2.0;
long long k = b - a;
return a == (long long)(k * phi);
}
int main() {
// First 10 P-positions
double phi = (1.0 + sqrt(5.0)) / 2.0;
for (int k = 0; k < 10; k++) {
long long a = (long long)(k * phi);
long long b = (long long)(k * phi * phi);
cout << "(" << a << ", " << b << ")\n";
}
}For large values of a and b, floating-point computation of ⌊kφ⌋ can give wrong results. For CP problems with a, b up to 1018, use the identity k = b - a and check a == ⌊kφ⌋ using integer arithmetic. One approach: compute k * phi using 128-bit integers or check that a = ⌊k * (1 + sqrt(5)) / 2⌋ by verifying a * 2 ≤ k * (1 + sqrt(5)) < (a+1) * 2 with careful integer square root computation.
Problem: Alice and Bob take turns. Given n, a player picks x where 0 < x < n and n % x == 0, then replaces n with n - x. The player who cannot move loses. Alice goes first. Does Alice win?
n=1: Alice cannot move, loses. P-position.
n=2: Alice picks x=1, leaves n=1 (P). N-position.
n=3: Only divisor < 3 is 1. Leaves n=2 (N). P-position.
n=4: Pick x=1 leaves 3(P). N-position.
Pattern: Alice wins if and only if n is even.
Proof: If n is even, Alice picks x=1 (always a divisor), leaving n-1 which is odd. If n is odd, all divisors of n are odd, so n-x is even. So even positions can always move to odd, and odd positions can only move to even. Since n=1 (odd) is losing, all odd positions are losing and all even positions are winning.
Python
def divisorGame(n):
return n % 2 == 0C++
bool divisorGame(int n) {
return n % 2 == 0;
}Problem: Piles of stones in a row. Alice and Bob alternate. Each turn, take the entire first or last pile. Alice goes first. Both play optimally. Does Alice win?
This is a classic interval DP problem. Let dp[i][j] = maximum score difference (current player minus opponent) when piles[i..j] remain.
dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
Base case: dp[i][i] = piles[i]
Alice wins if dp[0][n-1] > 0.
Fun fact: With an even number of piles, Alice ALWAYS wins (she can choose all even-indexed or all odd-indexed piles, whichever sum is larger).
Python
def stoneGame(piles):
"""Return True if Alice (first player) wins."""
n = len(piles)
# dp[i][j] = best score diff for current player on piles[i..j]
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = piles[i]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = max(piles[i] - dp[i+1][j],
piles[j] - dp[i][j-1])
return dp[0][n-1] > 0
print(stoneGame([5, 3, 4, 5])) # True (Alice: 5+4=9 vs Bob: 3+5=8)C++
#include <bits/stdc++.h>
using namespace std;
bool stoneGame(vector<int>& piles) {
int n = piles.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = piles[i];
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = max(piles[i] - dp[i+1][j],
piles[j] - dp[i][j-1]);
}
}
return dp[0][n-1] > 0;
}Problem: Piles in a row. On each turn, take the first 1 to 2M piles (M starts at 1, updated to max(M, x) after taking x piles). Maximize your stones.
Python
from functools import lru_cache
def stoneGameII(piles):
n = len(piles)
# suffix sums for quick range sum
suffix = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suffix[i] = suffix[i + 1] + piles[i]
@lru_cache(maxsize=None)
def dp(i, m):
# Max stones current player can get from piles[i:] with parameter M=m
if i >= n:
return 0
if i + 2 * m >= n:
return suffix[i] # take everything
best = 0
for x in range(1, 2 * m + 1):
# Take x piles, opponent gets dp(i+x, max(m,x))
# We get: total remaining - what opponent gets
best = max(best, suffix[i] - dp(i + x, max(m, x)))
return best
return dp(0, 1)C++
#include <bits/stdc++.h>
using namespace std;
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector<int> suffix(n + 1, 0);
for (int i = n - 1; i >= 0; i--)
suffix[i] = suffix[i + 1] + piles[i];
// dp[i][m] = max stones for current player from piles[i:] with M=m
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
for (int i = n - 1; i >= 0; i--) {
for (int m = n; m >= 1; m--) {
if (i + 2 * m >= n) {
dp[i][m] = suffix[i];
} else {
for (int x = 1; x <= 2 * m; x++)
dp[i][m] = max(dp[i][m], suffix[i] - dp[i + x][max(m, x)]);
}
}
}
return dp[0][1];
}Problem: Single pile of n stones. On the first turn, take 1 to n-1 stones. On subsequent turns, take 1 to 2k stones, where k is the number your opponent just took. Losing positions are Fibonacci numbers.
Python
def is_fibonacci(n):
"""Check if n is a Fibonacci number."""
if n <= 0:
return n == 0
a, b = 1, 1
while b < n:
a, b = b, a + b
return b == n
def fibonacci_nim(n):
"""First player wins iff n is NOT a Fibonacci number."""
return "Second" if is_fibonacci(n) else "First"
def zeckendorf(n):
"""Return Zeckendorf representation (list of Fibonacci numbers)."""
fibs = [1, 2]
while fibs[-1] < n:
fibs.append(fibs[-1] + fibs[-2])
result = []
for f in reversed(fibs):
if f <= n:
result.append(f)
n -= f
return result
print(zeckendorf(20)) # [13, 5, 2] -- first move: take 2 stonesC++
#include <bits/stdc++.h>
using namespace std;
bool isFibonacci(long long n) {
long long a = 1, b = 1;
while (b < n) { long long t = b; b = a + b; a = t; }
return b == n;
}
vector<long long> zeckendorf(long long n) {
vector<long long> fibs = {1, 2};
while (fibs.back() < n)
fibs.push_back(fibs[fibs.size()-1] + fibs[fibs.size()-2]);
vector<long long> result;
for (int i = fibs.size() - 1; i >= 0; i--) {
if (fibs[i] <= n) {
result.push_back(fibs[i]);
n -= fibs[i];
}
}
return result;
}Another common variant: Nim where you can also add stones to a pile (but not to a pile you just added to). Surprisingly, the analysis does not change -- the optimal player never adds, because adding just gives the opponent more options.
Step 1: Compute results for small cases (n=0 to ~20).
Step 2: Look for a pattern. Common patterns: modular (n%k), powers of 2, Fibonacci, etc.
Step 3: Prove the pattern using the P/N-position rules (backward induction).
Step 4: If no simple pattern, compute Grundy numbers and look for periodicity.
Step 5: If the game has multiple independent components, XOR the Grundy numbers.
Organized by difficulty. Start from the top and work your way down.
LeetCode 292 - Nim Game: Single pile, remove 1-3 stones. Classic modular analysis. Answer: n%4 != 0.
LeetCode 1025 - Divisor Game: Remove a divisor. Answer: n is even.
LeetCode 877 - Stone Game: Interval DP or parity argument.
Codeforces 768B - Code For 1: Recursive game on binary representation.
SPOJ GNYR09F - Game of Nim: Direct Nim XOR application.
LeetCode 1140 - Stone Game II: DP with parameter M.
LeetCode 1406 - Stone Game III: Take 1-3 piles from the front, maximize score.
Codeforces 850C - Arpa and a game with Mojtaba: Grundy values on digit transformations.
Codeforces 768E - Game of Stones: Multi-pile Nim variant with Grundy analysis.
SPOJ MATGAME - A game with matrices: Sprague-Grundy on a matrix game.
AtCoder ABC206E - Divide Both: Game on number pairs.
Codeforces 1823F - LCT: Game theory on trees with Grundy values.
Codeforces 1498F - Christmas Game: Nim on a tree -- combine staircase Nim with tree DP.
LeetCode 1510 - Stone Game IV: Square number removal -- compute Grundy values.
LeetCode 1563 - Stone Game V: Split-and-choose with DP.
Codeforces 603C - Lieges of Legendre: Misère Nim variant on odd/even analysis.
AtCoder ABC255G - Constrained Nim: Nim with forbidden positions -- Sprague-Grundy with modified mex.
Codeforces 1149E - Election Promises: Game on a DAG with Grundy on XOR of outgoing values.
IOI 2019 - Shoes: A game-theoretic sorting problem.
USACO Platinum - Game: Multi-dimensional game state with Sprague-Grundy.
Codeforces 1442E - Black, White and Grey Tree: Binary search + game theory on trees.
1. Master basic Nim and the XOR trick (problems should take seconds).
2. Learn to compute Grundy numbers for subtraction games.
3. Practice identifying independent sub-games and combining with XOR.
4. Study staircase Nim and Wythoff's game for variant recognition.
5. Learn minimax + alpha-beta for interview-style game problems.
6. For hard CP: recognize hidden game structures (tree games, graph games, disguised Nim).
1. Forgetting optimal play. Both players play perfectly. Do not simulate greedy strategies.
2. Wrong base case. Terminal position (no moves) is a LOSING position under normal play. Double-check misère conventions.
3. Assuming independence. Only XOR Grundy values when sub-games are truly independent.
4. Floating point in Wythoff. Use integer checks for large values.
5. Not looking for patterns. Always compute small cases first. The pattern is almost always there.