Game theory, at its core, is about strategic decision-making. While many of us might think of complex scenarios with hidden information, there’s a fascinating subset known as combinatorial game theory that deals with games of perfect information, no chance, and alternating moves. If you’ve ever wondered how to consistently win games like Nim, or analyze seemingly complex turn-based games, the Sprague-Grundy Theorem is your key.
This theorem provides a powerful framework to analyze a vast class of games, reducing them to a single, fundamental concept: Nim piles. By the end of this post, you’ll understand its mechanics, how to apply it, and even implement it in code to find winning strategies.
What is an Impartial Game?
Before we dive into the theorem, we need to understand the type of games it applies to: impartial games.
An impartial game is characterized by:
- Perfect Information: Both players know everything about the game state.
- No Chance: No dice rolls, no shuffled cards. Outcomes are purely deterministic based on moves.
- Alternating Turns: Players take turns making moves.
- Same Moves for Both Players: The available moves depend only on the state of the game, not on whose turn it is.
- Finite Positions: The game must eventually end.
- Normal Play Convention: The last player to make a move wins. (The opposite is “misere play”, where the last player to move loses).
Classic examples include Nim, Dawson’s Kayles, and various “takeaway” games. Chess, poker, and tic-tac-toe are not impartial games because moves depend on the player (e.g., White moves white pieces, Black moves black pieces).
P-Positions and N-Positions
In combinatorial game theory, every game position can be classified into one of two types under the normal play convention:
- P-position (Previous player winning): A position from which the previous player (the one who just moved) has a winning strategy, assuming optimal play from both sides. This means any move from a P-position leads to an N-position for the next player.
- N-position (Next player winning): A position from which the next player (the one whose turn it is) has a winning strategy, assuming optimal play from both sides. This means there is at least one move from an N-position that leads to a P-position for the next player.
A game ends when no moves are possible. Under normal play, the player who cannot move loses. Therefore, a position where no moves are possible is always a P-position.
Grundy Numbers (or Nim-values)
This is where the magic begins. Every impartial game position can be assigned a Grundy number (also called a Nim-value). This number represents the size of a single Nim pile that is equivalent to the current game position.
The Grundy number of a game position x, denoted g(x), is defined recursively as the Minimum Excluded (mex) value of the Grundy numbers of all positions reachable from x.
Let’s break down mex:
The mex Function
The mex (Minimum Excluded) function for a set of non-negative integers is the smallest non-negative integer not present in the set.
Examples:
mex({}) = 0(0 is the smallest non-negative integer, and it’s not in the empty set)mex({0}) = 1(0 is in the set, 1 is not)mex({1}) = 0(0 is not in the set)mex({0, 1, 3}) = 2(0 is in, 1 is in, 2 is not)mex({0, 1, 2, 3, 4}) = 5
Python implementation of mex:
def mex(s: set) -> int:
"""Calculates the Minimum Excluded (mex) value of a set of non-negative integers."""
i = 0
while i in s:
i += 1
return i
# --- Sample Usage ---
print(f"mex({{}}) = {mex(set())}")
print(f"mex({{0}}) = {mex({0})}")
print(f"mex({{1}}) = {mex({1})}")
print(f"mex({{0, 1, 3}}) = {mex({0, 1, 3})}")
print(f"mex({{0, 1, 2, 3, 4}}) = {mex({0, 1, 2, 3, 4})}")mex({}) = 0
mex({0}) = 1
mex({1}) = 0
mex({0, 1, 3}) = 2
mex({0, 1, 2, 3, 4}) = 5Now, back to Grundy numbers:
g(x) = mex({ g(y) | y is a position reachable from x in one move })
A position x is an N-position if g(x) > 0, and a P-position if g(x) = 0. This makes intuitive sense: if g(x) = 0, it means all reachable positions y must have g(y) > 0 (because mex returned 0, so 0 was not among g(y) values), meaning all moves lead to N-positions for the next player, making x a P-position for the current player.
The Sprague-Grundy Theorem
The theorem states:
Every impartial game under the normal play convention is equivalent to a Nim pile of a certain size.
Furthermore, the sum of several impartial games is equivalent to a single Nim pile whose size is the XOR sum of the Grundy numbers of the individual games.
Let G1, G2, ..., Gk be k impartial games. If g(G1), g(G2), ..., g(Gk) are their respective Grundy numbers, then the game consisting of the sum of these k games (where a move consists of choosing one game and making a move in it) has a Grundy number equal to:
g(G1 + G2 + ... + Gk) = g(G1) ^ g(G2) ^ ... ^ g(Gk)
where ^ denotes the bitwise XOR operation.
This theorem is incredibly powerful because it allows us to analyze complex games by breaking them down into simpler components. If the XOR sum of the Grundy numbers is non-zero, the first player (the one whose turn it is) has a winning strategy. If it’s zero, the second player has a winning strategy.
Example: Simple Nim Pile Grundy Numbers
Let’s start with the simplest impartial game: Nim. A single Nim pile of size n. A player can remove any number of items from the pile (but not zero).
g(0): No moves possible from a pile of 0. Set of reachable Grundy values is{}.g(0) = mex({}) = 0.g(1): Can move to0. Set of reachable Grundy values is{g(0)} = {0}.g(1) = mex({0}) = 1.g(2): Can move to0, 1. Set of reachable Grundy values is{g(0), g(1)} = {0, 1}.g(2) = mex({0, 1}) = 2.g(3): Can move to0, 1, 2. Set of reachable Grundy values is{g(0), g(1), g(2)} = {0, 1, 2}.g(3) = mex({0, 1, 2}) = 3.
It quickly becomes clear that for a single Nim pile of size n, its Grundy number g(n) is simply n. This confirms why Nim strategy relies on XORing pile sizes directly.
Python code to calculate Grundy numbers for Nim piles up to N:
def mex(s: set) -> int:
i = 0
while i in s:
i += 1
return i
def calculate_nim_grundy_numbers(n_max: int) -> list[int]:
"""Calculates Grundy numbers for single Nim piles from 0 to n_max."""
grundy_values = [0] * (n_max + 1)
grundy_values[0] = 0 # Base case: no moves from 0 items
for n in range(1, n_max + 1):
reachable_grundy_values = set()
# From a pile of size n, you can move to any pile of size m < n
for m in range(n):
reachable_grundy_values.add(grundy_values[m])
grundy_values[n] = mex(reachable_grundy_values)
return grundy_values
# --- Sample Usage ---
max_pile_size = 10
nim_grundy = calculate_nim_grundy_numbers(max_pile_size)
print(f"Grundy numbers for Nim piles up to {max_pile_size}:")
for i, g_val in enumerate(nim_grundy):
print(f"g({i}) = {g_val}")Grundy numbers for Nim piles up to 10:
g(0) = 0
g(1) = 1
g(2) = 2
g(3) = 3
g(4) = 4
g(5) = 5
g(6) = 6
g(7) = 7
g(8) = 8
g(9) = 9
g(10) = 10Nim with Multiple Piles (The Classic Example)
Consider a Nim game with piles of sizes A, B, C. According to the Sprague-Grundy Theorem, the game is equivalent to a single Nim pile of size A ^ B ^ C.
If A ^ B ^ C != 0, the first player wins. If A ^ B ^ C == 0, the second player wins.
Example Scenario: Three Nim piles of sizes 3, 4, and 5.
pile_a = 3
pile_b = 4
pile_c = 5
nim_sum = pile_a ^ pile_b ^ pile_c
print(f"Piles: {pile_a}, {pile_b}, {pile_c}")
print(f"Nim-sum (XOR sum of Grundy numbers): {nim_sum}")
if nim_sum != 0:
print("This is an N-position (Next player wins).")
print("Finding a winning move:")
# A winning move means changing one pile's size 'p' to 'p_prime' such that
# p_prime ^ (other_piles_xor_sum) = 0
# or, (p ^ other_piles_xor_sum) ^ p ^ p_prime = 0 ^ p ^ p_prime
# So, nim_sum ^ p ^ p_prime = 0
# This implies p_prime = nim_sum ^ p
initial_piles = [pile_a, pile_b, pile_c]
for i, pile_size in enumerate(initial_piles):
# Calculate the target Grundy number for this pile to make the total XOR sum 0
target_grundy = nim_sum ^ pile_size
# Check if we can reduce the current pile to this target_grundy size
if target_grundy < pile_size:
items_to_remove = pile_size - target_grundy
print(f" Remove {items_to_remove} from pile {i+1} (size {pile_size}). New pile size: {target_grundy}")
# Verify the new nim_sum
new_piles = list(initial_piles)
new_piles[i] = target_grundy
new_nim_sum = new_piles[0] ^ new_piles[1] ^ new_piles[2]
print(f" New Nim-sum: {new_nim_sum} (should be 0)")
break # Found a winning move, no need to check others
else:
print("This is a P-position (Previous player wins, current player loses).")Piles: 3, 4, 5
Nim-sum (XOR sum of Grundy numbers): 2
This is an N-position (Next player wins).
Finding a winning move:
Remove 1 from pile 3 (size 5). New pile size: 4
New Nim-sum: 0 (should be 0)In this example, the Nim-sum is 2. The first player has a winning move. One such move is to change the pile of size 5 to a pile of size 4 (by removing 1 item). The new pile sizes are 3, 4, 4. Their XOR sum is 3 ^ 4 ^ 4 = 3 ^ (4^4) = 3 ^ 0 = 3. Wait, something is wrong.
Let’s re-evaluate the winning move calculation.
We have current_nim_sum = g1 ^ g2 ^ g3.
We want g1' ^ g2 ^ g3 = 0.
So, g1' = g2 ^ g3.
We also know g2 ^ g3 = current_nim_sum ^ g1.
Therefore, g1' = current_nim_sum ^ g1.
The move is valid if g1' < g1.
Corrected winning move logic:
Let N = nim_sum. We want to change one pile_size (say, P) to P' such that (N ^ P) ^ P' = 0. This implies P' = N ^ P.
The move is valid if P' < P.
Let’s re-run with pile_a=3, pile_b=4, pile_c=5.
nim_sum = 3 ^ 4 ^ 5 = (011 ^ 100) ^ 101 = 111 ^ 101 = 010 (binary) = 2.
- For pile A (3):
target_grundy = nim_sum ^ pile_a = 2 ^ 3 = 1. Since1 < 3, we can change pile A from 3 to 1 (remove 2 items). New piles:1, 4, 5. New Nim-sum:1 ^ 4 ^ 5 = 5 ^ 5 = 0. This is a valid winning move! - For pile B (4):
target_grundy = nim_sum ^ pile_b = 2 ^ 4 = 6. Since6is not< 4, this is not a valid move for pile B. - For pile C (5):
target_grundy = nim_sum ^ pile_c = 2 ^ 5 = 7. Since7is not< 5, this is not a valid move for pile C.
The original code snippet for finding the winning move was correct; my mental trace was off. The first found move was “Remove 2 from pile 1 (size 3). New pile size: 1”. This is correct.
pile_a = 3
pile_b = 4
pile_c = 5
initial_piles = [pile_a, pile_b, pile_c]
nim_sum = initial_piles[0] ^ initial_piles[1] ^ initial_piles[2]
print(f"Piles: {initial_piles}")
print(f"Nim-sum: {nim_sum}")
if nim_sum != 0:
print("This is an N-position (Next player wins).")
print("Finding a winning move:")
for i, pile_size in enumerate(initial_piles):
# Calculate the target Grundy number for this pile to make the total XOR sum 0
# If new_grundy = current_nim_sum ^ pile_size, then
# new_grundy ^ (current_nim_sum ^ pile_size) = 0
# (new_grundy for this pile) ^ (other_piles_xor_sum) = 0
# current_nim_sum = pile_size ^ other_piles_xor_sum
# So, new_grundy = current_nim_sum ^ pile_size
target_grundy = nim_sum ^ pile_size
# A move is valid if the new pile size is less than the original pile size
if target_grundy < pile_size:
items_to_remove = pile_size - target_grundy
print(f" Remove {items_to_remove} from pile {i+1} (size {pile_size}). New pile size: {target_grundy}")
# Verify the new nim_sum
new_piles = list(initial_piles)
new_piles[i] = target_grundy
new_nim_sum = new_piles[0] ^ new_piles[1] ^ new_piles[2]
print(f" New Nim-sum: {new_nim_sum} (should be 0)")
break # Found a winning move, no need to check others
else:
print("This is a P-position (Previous player wins, current player loses).")Piles: [3, 4, 5]
Nim-sum: 2
This is an N-position (Next player wins).
Finding a winning move:
Remove 2 from pile 1 (size 3). New pile size: 1
New Nim-sum: 0 (should be 0)Great, the code and logic align now.
More Complex Example: Game of Subtraction
Let’s consider a game where we have a pile of N items. Players can remove k items, where k must be from a predefined set S = {s1, s2, ..., sm}. The player who takes the last item wins (i.e., makes the pile 0).
Let S = {1, 2, 4}. We need to find g(n) for a pile of size n.
g(0) = mex({}) = 0(No moves from 0)g(1) = mex({g(1-1)}) = mex({g(0)}) = mex({0}) = 1g(2) = mex({g(2-1), g(2-2)}) = mex({g(1), g(0)}) = mex({1, 0}) = 2g(3) = mex({g(3-1), g(3-2)}) = mex({g(2), g(1)}) = mex({2, 1}) = 0g(4) = mex({g(4-1), g(4-2), g(4-4)}) = mex({g(3), g(2), g(0)}) = mex({0, 2, 0}) = mex({0, 2}) = 1g(5) = mex({g(5-1), g(5-2), g(5-4)}) = mex({g(4), g(3), g(1)}) = mex({1, 0, 1}) = mex({0, 1}) = 2g(6) = mex({g(6-1), g(6-2), g(6-4)}) = mex({g(5), g(4), g(2)}) = mex({2, 1, 2}) = mex({1, 2}) = 0g(7) = mex({g(7-1), g(7-2), g(7-4)}) = mex({g(6), g(5), g(3)}) = mex({0, 2, 0}) = mex({0, 2}) = 1
Notice a pattern: 0, 1, 2, 0, 1, 2, 0, 1… The Grundy numbers are periodic with a period of 3! g(n) = n % 3. This is a common occurrence in games with a fixed set of moves.
Python code to calculate Grundy numbers for the Subtraction Game:
def mex(s: set) -> int:
i = 0
while i in s:
i += 1
return i
# Note: Memoization (using a dictionary or list) is crucial for efficiency
# when calculating Grundy numbers for larger N, as it avoids redundant calculations.
grundy_memo = {}
def calculate_subtraction_grundy(n: int, moves: set) -> int:
"""
Calculates the Grundy number for a subtraction game with N items.
Moves is a set of integers representing allowed subtractions.
"""
if n < 0:
return 0 # Should not happen with valid moves, but for safety
if n == 0:
return 0 # Base case: no moves from 0 items
if n in grundy_memo:
return grundy_memo[n]
reachable_grundy_values = set()
for move in moves:
if n - move >= 0:
reachable_grundy_values.add(calculate_subtraction_grundy(n - move, moves))
grundy_val = mex(reachable_grundy_values)
grundy_memo[n] = grundy_val
return grundy_val
# --- Sample Usage ---
allowed_moves = {1, 2, 4}
max_n = 20
print(f"Grundy numbers for Subtraction Game (moves={allowed_moves}) up to N={max_n}:")
subtraction_grundy_values = []
for i in range(max_n + 1):
subtraction_grundy_values.append(calculate_subtraction_grundy(i, allowed_moves))
print(f"g({i}) = {subtraction_grundy_values[-1]}")
# Reset memo for new calculations if needed
grundy_memo.clear()Grundy numbers for Subtraction Game (moves={1, 2, 4}) up to N=20:
g(0) = 0
g(1) = 1
g(2) = 2
g(3) = 0
g(4) = 1
g(5) = 2
g(6) = 0
g(7) = 1
g(8) = 2
g(9) = 0
g(10) = 1
g(11) = 2
g(12) = 0
g(13) = 1
g(14) = 2
g(15) = 0
g(16) = 1
g(17) = 2
g(18) = 0
g(19) = 1
g(20) = 2The pattern 0, 1, 2 repeating confirms our manual calculation.
Playing the Subtraction Game
If you have a pile of N items and the Grundy number g(N) is:
0: It’s a P-position. You lose if your opponent plays optimally.> 0: It’s an N-position. You win if you play optimally.
To find a winning move from an N-position (where g(N) > 0): Find a move k (from S) such that g(N - k) = 0. Because g(N) is mex({g(N-k) for k in S}), and g(N) > 0, it means 0 must be present in the set of reachable Grundy values. So, there is always at least one k that leads to g(N-k) = 0.
Example: You have 10 items, S = {1, 2, 4}.
From our output, g(10) = 1. This is an N-position, so the current player (you) can win.
We need to find a k from {1, 2, 4} such that g(10 - k) = 0.
- Try
k=1:g(10-1) = g(9) = 0. Found it! Removing 1 item leads to a pile of 9, which is a P-position. - Try
k=2:g(10-2) = g(8) = 2. Not 0. - Try
k=4:g(10-4) = g(6) = 0. Another one! Removing 4 items leads to a pile of 6, which is also a P-position.
So, from 10 items, you can either take 1 item (leaving 9) or take 4 items (leaving 6) to win.
Sum of Games Example
Let’s say we’re playing a game composed of two independent instances of the Subtraction Game (from the previous example):
- Game A: A pile of
N_Aitems, allowed movesS_A = {1, 2, 4}. - Game B: A pile of
N_Bitems, allowed movesS_B = {1, 3}.
The player chooses one of the two games, makes a valid move in it, and passes the turn. The last player to move wins.
Let N_A = 10 and N_B = 5.
First, we need the Grundy numbers for both types of games. We already have g_A (for S_A={1,2,4}). Let’s calculate g_B (for S_B={1,3}).
Calculating g_B for moves {1, 3}:
g_B(0) = 0g_B(1) = mex({g_B(0)}) = mex({0}) = 1g_B(2) = mex({g_B(1), g_B(0)}) = mex({1, 0}) = 2g_B(3) = mex({g_B(2), g_B(0)}) = mex({2, 0}) = 1(Note: not 0 this time)g_B(4) = mex({g_B(3), g_B(1)}) = mex({1, 1}) = mex({1}) = 0g_B(5) = mex({g_B(4), g_B(2)}) = mex({0, 2}) = 1g_B(6) = mex({g_B(5), g_B(3)}) = mex({1, 1}) = mex({1}) = 0
Python code for g_B and combined game strategy:
def mex(s: set) -> int:
i = 0
while i in s:
i += 1
return i
# Memoization dictionaries for different game types
grundy_memo_A = {}
grundy_memo_B = {}
def calculate_subtraction_grundy(n: int, moves: set, memo: dict) -> int:
if n < 0: return 0
if n == 0: return 0
if n in memo: return memo[n]
reachable_grundy_values = set()
for move in moves:
if n - move >= 0:
reachable_grundy_values.add(calculate_subtraction_grundy(n - move, moves, memo))
grundy_val = mex(reachable_grundy_values)
memo[n] = grundy_val
return grundy_val
# --- Game Setup ---
# Game A: N_A items, moves {1, 2, 4}
moves_A = {1, 2, 4}
N_A = 10
# Game B: N_B items, moves {1, 3}
moves_B = {1, 3}
N_B = 5
# Calculate Grundy number for Game A's current state
g_A = calculate_subtraction_grundy(N_A, moves_A, grundy_memo_A)
print(f"Current Grundy for Game A (N={N_A}, moves={moves_A}): g({N_A}) = {g_A}")
# Calculate Grundy number for Game B's current state
g_B = calculate_subtraction_grundy(N_B, moves_B, grundy_memo_B)
print(f"Current Grundy for Game B (N={N_B}, moves={moves_B}): g({N_B}) = {g_B}")
# Calculate the Nim-sum for the combined game
combined_nim_sum = g_A ^ g_B
print(f"\nCombined Game Nim-sum: g_A ^ g_B = {g_A} ^ {g_B} = {combined_nim_sum}")
if combined_nim_sum != 0:
print("\nThis is an N-position for the combined game (Next player wins).")
print("Finding a winning move:")
# Check for winning move in Game A
for move_val in moves_A:
if N_A - move_val >= 0:
# Calculate new Grundy for Game A if this move is made
new_g_A = calculate_subtraction_grundy(N_A - move_val, moves_A, grundy_memo_A)
# Check if this move makes the total Nim-sum zero
if (new_g_A ^ g_B) == 0:
print(f" Winning move: In Game A, remove {move_val} items.")
print(f" New N_A = {N_A - move_val}, new g_A = {new_g_A}")
print(f" New combined Nim-sum: {new_g_A} ^ {g_B} = 0")
break # Found a winning move
# Check for winning move in Game B (only if no winning move was found in A)
else: # This 'else' block executes if the 'for' loop in Game A finishes without a 'break'
for move_val in moves_B:
if N_B - move_val >= 0:
# Calculate new Grundy for Game B if this move is made
new_g_B = calculate_subtraction_grundy(N_B - move_val, moves_B, grundy_memo_B)
# Check if this move makes the total Nim-sum zero
if (g_A ^ new_g_B) == 0:
print(f" Winning move: In Game B, remove {move_val} items.")
print(f" New N_B = {N_B - move_val}, new g_B = {new_g_B}")
print(f" New combined Nim-sum: {g_A} ^ {new_g_B} = 0")
break # Found a winning move
else:
print("\nThis is a P-position for the combined game (Previous player wins, current player loses).")Current Grundy for Game A (N=10, moves={1, 2, 4}): g(10) = 1
Current Grundy for Game B (N=5, moves={1, 3}): g(5) = 1
Combined Game Nim-sum: g_A ^ g_B = 1 ^ 1 = 0
This is a P-position for the combined game (Previous player wins, current player loses).In this specific example (N_A=10, N_B=5), the combined Nim-sum is 0. This means the first player (you) is in a P-position and will lose if the opponent plays optimally.
Let’s change N_A to 8 to demonstrate a winning move.
N_A = 8, moves_A = {1, 2, 4}. g_A = g(8) = 2.
N_B = 5, moves_B = {1, 3}. g_B = g(5) = 1.
combined_nim_sum = g_A ^ g_B = 2 ^ 1 = 3.
Since 3 != 0, this is an N-position for the first player. A winning move exists.
We need to make a move such that the new combined Nim-sum is 0.
Let G_total = g_A ^ g_B. We want g_A' ^ g_B = 0 or g_A ^ g_B' = 0.
This means g_A' = G_total ^ g_B or g_B' = G_total ^ g_A.
-
Consider Game A:
g_A = 2. We needg_A'such thatg_A' ^ g_B = 0, sog_A' = g_B = 1. Can we make a move in Game A fromN_A=8to reach a state with Grundy number 1? Fromg(8) = 2, reachable states are:g(8-1)=g(7)=1. Yes! Take 1 fromN_A. NewN_Ais7.g(7)=1.g(8-2)=g(6)=0.g(8-4)=g(4)=1. Yes! Take 4 fromN_A. NewN_Ais4.g(4)=1.
So, if we take 1 from Game A,
N_Abecomes7,g_Abecomes1. New total Nim-sum1 ^ 1 = 0. This is a winning move. Or, if we take 4 from Game A,N_Abecomes4,g_Abecomes1. New total Nim-sum1 ^ 1 = 0. Also a winning move.
Let’s modify the code for this scenario:
# --- Game Setup (Modified) ---
# Game A: N_A items, moves {1, 2, 4}
moves_A = {1, 2, 4}
N_A = 8 # Changed from 10
# Game B: N_B items, moves {1, 3}
moves_B = {1, 3}
N_B = 5
# Clear memos for fresh calculation
grundy_memo_A.clear()
grundy_memo_B.clear()
# Calculate Grundy number for Game A's current state
g_A = calculate_subtraction_grundy(N_A, moves_A, grundy_memo_A)
print(f"Current Grundy for Game A (N={N_A}, moves={moves_A}): g({N_A}) = {g_A}")
# Calculate Grundy number for Game B's current state
g_B = calculate_subtraction_grundy(N_B, moves_B, grundy_memo_B)
print(f"Current Grundy for Game B (N={N_B}, moves={moves_B}): g({N_B}) = {g_B}")
# Calculate the Nim-sum for the combined game
combined_nim_sum = g_A ^ g_B
print(f"\nCombined Game Nim-sum: g_A ^ g_B = {g_A} ^ {g_B} = {combined_nim_sum}")
if combined_nim_sum != 0:
print("\nThis is an N-position for the combined game (Next player wins).")
print("Finding a winning move:")
# Iterate through possible moves in Game A
for move_val in moves_A:
if N_A - move_val >= 0:
new_g_A = calculate_subtraction_grundy(N_A - move_val, moves_A, grundy_memo_A)
if (new_g_A ^ g_B) == 0:
print(f" Winning move: In Game A, remove {move_val} items.")
print(f" New N_A = {N_A - move_val}, new g_A = {new_g_A}")
print(f" New combined Nim-sum: {new_g_A} ^ {g_B} = 0")
return # Exit after finding the first winning move
# If no winning move found in Game A, iterate through possible moves in Game B
for move_val in moves_B:
if N_B - move_val >= 0:
new_g_B = calculate_subtraction_grundy(N_B - move_val, moves_B, grundy_memo_B)
if (g_A ^ new_g_B) == 0:
print(f" Winning move: In Game B, remove {move_val} items.")
print(f" New N_B = {N_B - move_val}, new g_B = {new_g_B}")
print(f" New combined Nim-sum: {g_A} ^ {new_g_B} = 0")
return # Exit after finding the first winning move
else:
print("\nThis is a P-position for the combined game (Previous player wins, current player loses).")Current Grundy for Game A (N=8, moves={1, 2, 4}): g(8) = 2
Current Grundy for Game B (N=5, moves={1, 3}): g(5) = 1
Combined Game Nim-sum: g_A ^ g_B = 2 ^ 1 = 3
This is an N-position for the combined game (Next player wins).
Finding a winning move:
Winning move: In Game A, remove 1 items.
New N_A = 7, new g_A = 1
New combined Nim-sum: 1 ^ 1 = 0Success! The code correctly identified a winning move.
Limitations and Nuances
While incredibly powerful, the Sprague-Grundy Theorem has its boundaries:
- Impartial Games Only: It doesn’t apply to games where moves depend on the player (like Chess) or where chance is involved (like Poker).
- Normal Play Convention: The theorem is typically stated for normal play (last player wins). Misere play (last player loses) can behave very differently, especially for small Grundy numbers, and often requires separate analysis (e.g., Bouton’s theorem for Nim, or a case-by-case analysis for other games).
- Computational Complexity: Calculating Grundy numbers can be computationally intensive for games with large state spaces or complex move sets.
- Memoization is Key: As shown in the Python examples, using a dictionary or array to store previously calculated Grundy numbers (
grundy_memo) is absolutely essential to avoid redundant calculations and make recursive solutions efficient. Without it, you’d be recomputing the same sub-problems over and over, leading to exponential time complexity. - State Representation: For games with multiple parameters (e.g., two piles of different types), the “state” becomes a tuple, and the memoization key needs to reflect that tuple.
- Memoization is Key: As shown in the Python examples, using a dictionary or array to store previously calculated Grundy numbers (
- Finding the Move vs. Winning Strategy: The theorem tells you if you can win, and the XOR sum helps identify winning moves. However, for a human player, it might still require a lot of calculation to apply it in real-time if the Grundy values aren’t trivial.
Conclusion
The Sprague-Grundy Theorem is a cornerstone of combinatorial game theory. It elegantly unifies a vast array of impartial games by proving their equivalence to the simple game of Nim. By understanding and applying Grundy numbers and the mex function, you can:
- Determine if a given impartial game position is a winning (N) or losing (P) position.
- Devise optimal strategies for complex impartial games by breaking them down into components and using the XOR sum property.
- Reduce the problem of playing many different impartial games simultaneously to playing a single game of Nim.
While the math might seem abstract at first, the practical applications in competitive programming, AI game playing, and even just understanding the structure of games are immense. So go forth, calculate some Grundy numbers, and conquer those impartial games!