Fundamentals of Combinatorial Game Theory Using SG Functions: A Complete Guide

The Sprague-Grundy (SG) function assigns every position in an impartial game a non-negative integer using the minimum excluded value (mex), allowing complex games to be reduced to equivalent Nim heaps and solved via bitwise XOR.

Combinatorial game theory provides the mathematical framework for analyzing two-player, perfect-information games without chance elements. This guide explores the fundamentals of combinatorial game theory using SG functions, based on the educational resources found in the hzwer/shareoi repository—a comprehensive collection of competitive programming materials used in Olympiad in Informatics (OI) training.

What Is the Sprague-Grundy Function?

The Sprague-Grundy function (or SG function) is the cornerstone of impartial game analysis. It maps every game position to a Grundy number (or nimber), effectively converting any impartial game into an equivalent Nim heap.

Formal Definition Using the Mex Operation

For any position $P$, let $M(P)$ denote the set of all positions reachable from $P$ in one legal move. The SG value is defined as:

$$ \text{SG}(P) = \text{mex}{\text{SG}(Q) \mid Q \in M(P)} $$

Here, mex (minimum excluded value) returns the smallest non-negative integer not present in the set. This recursive definition ensures that positions with no available moves (terminal positions) receive $\text{SG} = 0$.

Terminal Positions and Zero SG Values

When $M(P)$ is empty (no legal moves remain), $\text{mex}(\emptyset) = 0$. Therefore, terminal positions always have SG value 0, representing losing positions for the player about to move. This property serves as the base case for recursive SG computation in graph-based games.

The Sprague-Grundy Theorem and Nim Equivalence

The power of SG functions lies in the Sprague-Grundy theorem, which states that every impartial game is equivalent to a Nim heap whose size equals the game's SG value.

Nim Heap Equivalence

In the game of Nim, a heap of size $k$ has $\text{SG}(k) = k$. The theorem generalizes this: any impartial game position with SG value $g$ behaves identically to a Nim heap of size $g$ when combined with other games.

Combining Games with Bitwise XOR

When analyzing the disjoint sum of multiple independent games (where a player moves in exactly one subgame per turn), the combined SG value is the bitwise XOR of individual SG values:

$$ \text{SG}_{\text{total}} = \text{SG}_1 \oplus \text{SG}_2 \oplus \cdots \oplus \text{SG}_n $$

P-Positions vs. N-Positions

The XOR result determines the game outcome under optimal play:

• P-positions (Previous player wins): XOR equals 0. The player who just moved has a winning strategy.
• N-positions (Next player wins): XOR is non-zero. The player about to move can force a win by moving to a P-position.

Computing SG Values for Classic Games

Different game structures produce characteristic SG value patterns. The hzwer/shareoi repository documents several fundamental classes used in competitive programming.

Subtraction Games

In take-away games where players remove between 1 and $m$ objects from a heap, the SG values follow a cyclic pattern:

$$ \text{SG}(i) = i \bmod (m+1) $$

For example, if players may remove 1, 3, or 4 stones (as implemented in the repository examples), the SG sequence exhibits periodic behavior after an initial transient.

Wythoff's Game

In Wythoff's game, players may remove any number of tokens from one heap or equal numbers from both heaps. The P-positions follow Beatty sequences related to the golden ratio $\phi = \frac{1+\sqrt{5}}{2}$. The SG function for this game requires more sophisticated analysis involving cold positions and the mex operation over two-dimensional state spaces.

Kayles and Graph-Based Games

Kayles (a bowling pin game where players knock down single pins or adjacent pairs) demonstrates how SG values are computed via dynamic programming over game states. For graph-based impartial games where positions form a directed acyclic graph (DAG), topological sorting enables bottom-up SG computation from terminal nodes upward.

Practical Implementation in Python

The following implementations follow the algorithmic patterns documented in 数学/博弈论和SG函数_方泓杰.pdf and 数学/组合游戏略述——浅谈SG游戏的若干拓展及变形_贾志豪.ppt from the repository.

The Mex Function

def mex(s):
    """Return the minimum excluded non-negative integer from set s."""
    i = 0
    while i in s:
        i += 1
    return i

Recursive SG Computation with Memoization

def sg_state(state, moves_func, memo):
    """
    Compute SG value for a given state using memoized recursion.
    
    Args:
        state: Current game position (hashable)
        moves_func: Function returning list of next states
        memo: Dictionary caching computed SG values
    """
    if state in memo:
        return memo[state]
    
    next_states = moves_func(state)
    next_sgs = {sg_state(ns, moves_func, memo) for ns in next_states}
    
    g = mex(next_sgs)
    memo[state] = g
    return g

Subtraction Game Example (1, 3, 4)

def moves_subtraction(n):
    """Generate moves for subtraction game allowing removal of 1, 3, or 4."""
    return [n - k for k in (1, 3, 4) if n >= k]

# Compute SG values for states 0 through 20

memo = {}
sg_values = [sg_state(n, moves_subtraction, memo) for n in range(21)]

print("n : SG(n)")
for n, sg in enumerate(sg_values):
    print(f"{n:2d}: {sg}")

Nim-Sum Evaluation for Combined Games

from functools import reduce
import operator

def evaluate_nim_position(piles):
    """
    Determine if current Nim position is winning or losing.
    Returns (is_winning, xor_value)
    """
    xor_sum = reduce(operator.xor, piles, 0)
    return xor_sum != 0, xor_sum

# Example: Three heaps of size 3, 4, 5

piles = [3, 4, 5]
is_winning, xor_val = evaluate_nim_position(piles)

print(f"XOR sum: {xor_val}")
print(f"Position type: {'N-position (Next player wins)' if is_winning else 'P-position (Previous player wins)'}")

Learning Resources from the hzwer/shareoi Repository

The hzwer/shareoi repository contains authoritative educational materials on combinatorial game theory fundamentals using SG functions, specifically curated for competitive programming training.

Core Theoretical Documents

• 数学/博弈论和SG函数_方泓杰.pdf: Comprehensive lecture notes covering the Sprague-Grundy theorem, formal proofs, and foundational examples. This document establishes the mathematical rigor behind mex calculations and Nim equivalence.

• 数学/组合游戏略述——浅谈SG游戏的若干拓展及变形_贾志豪.ppt: Presentation slides exploring extensions including subtraction games, graph-based impartial games, and multi-dimensional SG calculations. This resource bridges theory with OI competition problem-solving strategies.

Supplementary Materials

• 数学/组合计数问题_方泓杰.pdf: While primarily focused on combinatorial counting, this document contains sections illustrating the intersection of counting principles and SG function applications in complex game states.

These materials collectively provide the theoretical foundation and practical algorithms necessary for implementing SG function solutions in algorithmic competitions.

Summary

• Sprague-Grundy functions convert any impartial game position into a non-negative integer (Grundy number) using the mex (minimum excluded value) operation.
• The Sprague-Grundy theorem establishes that every impartial game is equivalent to a Nim heap of size equal to its SG value.
• Game sums are evaluated by computing the bitwise XOR of individual SG values; a zero result indicates a P-position (losing for the next player), while non-zero indicates an N-position (winning for the next player).
• Subtraction games, Wythoff's game, and Kayles demonstrate specific SG computation patterns using dynamic programming and recursive memoization.
• The hzwer/shareoi repository provides definitive educational resources including 数学/博弈论和SG函数_方泓杰.pdf and 数学/组合游戏略述——浅谈SG游戏的若干拓展及变形_贾志豪.ppt for mastering these concepts in competitive programming contexts.

Frequently Asked Questions

What is the mex function in combinatorial game theory?

The mex (minimum excluded) function returns the smallest non-negative integer not present in a given set of numbers. In SG function calculations, mex(S) identifies the least non-negative integer missing from the set of SG values of all reachable next positions. For example, mex({0, 1, 3}) returns 2, while mex({}) returns 0 for terminal positions.

How do you calculate the Sprague-Grundy value for a game sum?

To calculate the SG value for a disjoint sum of independent games, compute the SG value for each individual subgame using recursive mex operations, then apply the bitwise XOR operation across all values. If you have three games with SG values of 3, 4, and 5, the combined value is 3 ^ 4 ^ 5 = 2. This reduction works because of the Sprague-Grundy theorem, which guarantees that any impartial game behaves equivalently to a Nim heap of matching size.

What is the difference between P-positions and N-positions?

P-positions (Previous player winning) are game states where the player who just moved has a winning strategy, assuming optimal play from this point forward. These positions have a combined SG value of zero (XOR of all subgames equals 0). N-positions (Next player winning) are states where the player about to move can force a win by transitioning to a P-position; these have non-zero combined SG values. In practical terms, if you face an N-position, you should move to make the XOR sum zero; if you face a P-position, any move you make will give the opponent a winning opportunity.

Where can I find practice problems for SG function applications?

The hzwer/shareoi repository contains curated competitive programming materials specifically designed for mastering SG functions, including the PDF 数学/博弈论和SG函数_方泓杰.pdf which provides theoretical foundations and example problems, and the PowerPoint 数学/组合游戏略述——浅谈SG游戏的若干拓展及变形_贾志豪.ppt which covers extensions like subtraction games, Wythoff's game, and graph-based impartial games commonly found in OI contests. These resources bridge the gap between mathematical theory and algorithmic implementation, offering both proof-based understanding and concrete coding exercises.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}