In-depth Analysis of SG Function and mex Operations in Combinatorial Game Theory

Core Logic and Mathematical Principles

The SG function (Sprague-Grundy Function) is the ultimate weapon in combinatorial game theory. It abstracts and maps all impartial combinatorial games (ICG) into values on directed acyclic graphs (DAG), transforming any complex game rules into the XOR operations of the classical Nim game.

1. mex Operation (Minimum Excludant)

The mex operation is a special algebraic operator for sets of non-negative integers. It is defined as $ ext{mex}(S)$, the smallest non-negative integer not in the set $S$.

$$ ext{mex}(S) = ext{min} ig{ x ext{ in } ext{N} ig| x otin S ig\} $$

• $ ext{mex}(\\{1, 2, 3\ ext{)} = 0$
• $ ext{mex}(\\{0, 1, 3\ ext{)} = 2$
• $ ext{mex}(\\emptyset) = 0$

2. Definition of SG Function

For any given position (state) $x$ in the game, let the set of successor states reachable by a legal move be $ ext{Successors}(x) = \\{y_1, y_2, \\dots, y_k\\ ext{)}$. The SG function value for this state is defined as:

$$ ext{SG}(x) = ext{mex}ig( \{ ext{SG}(y) ig| y ext{ in } ext{Successors}(x) \} ig) $$

Mathematical Features and Mapping of P/N States

The SG function values exhibit strong and intricate algebraic physical features:

• $ ext{SG}(x) = 0 ext{ if and only if } x$ is a P-position (losing position).
• $ ext{SG}(x) > 0 ext{ if and only if } x$ is an N-position (winning position).

Its internal logic perfectly converges with the three fundamental axioms of games:

1. Terminal State: If $x$ is a terminal state with no legal moves, its successor set is empty $ ext{emptyset}$, then $ ext{SG}(x) = ext{mex}( ext{emptyset}) = 0$ (losing).
2. From 0 to Non-0: If $ ext{SG}(x) = 0$, then its successor set cannot possibly contain $0$. This means that starting from a losing position, no matter how you move, the SG values of the successor states must be greater than $0$ (all successors are winning positions).
3. From Non-0 to 0: If $ ext{SG}(x) = k > 0$, based on the definition of mex, in its successor set, there must exist at least one successor state $y$ such that $ ext{SG}(y) = 0$. This means that starting from a winning position, one can always shed the advantage in one move, leaving a losing position for the opponent.

3. SG Theorem (Sprague-Grundy Theorem)

If a game is composed of $n$ independent and non-interfering sub-games (for example: there are $n$ piles of stones in the game, and each move can only operate on one of the piles, with the same rules but independent quantities), then the global SG state value of the entire composite game is directly equal to the bitwise XOR sum of the SG values of all sub-games:

$$ ext{SG}_{ ext{global}} = ext{SG}(x_1) igoplus ext{SG}(x_2) igoplus \dots igoplus ext{SG}(x_n) $$

This is why academia claims that "all impartial combinatorial games are essentially Nim games".

Algorithm Derivation and State Design

1. SG Linear Table for Independent Single-Pile Situations

For conventional single-pile games with restricted moves (e.g., one can only take stones from the set $S=\\{1, 3, 4\ ext{)}$), we use a one-dimensional array sg[i] to record the SG value when the number of stones is i.

We utilize bucket sorting (Vis marking array) to achieve efficient mex operations:

• State Design: sg[i] represents the game value when the current number of stones is $i$.
• Transition Equation:

$$ ext{sg}[i] = ext{mex}ig(\{ ext{sg}[i - k] ig| k ext{ in } S ext{ and } i ext{ >= } k \} ig) $$

2. XOR Decoupling of Game Composition

When multiple piles of stones are given, since the sub-games are completely independent, we absolutely do not need to open multi-dimensional arrays to maintain global states. We only need to linearly compute the sg array within the maximum range of a single pile in $O(N)$, and then directly look up the initial quantity $a_i$ for each pile of stones, XORing the retrieved sg[a_i] values together. Finally, we check whether the XOR sum is $0$.

C++ Standard Source Code

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

const int MAXN = 10000;
int sg[MAXN + 5];

// Precompute SG values for single piles of stones under specific rules (f set)
void precompute_sg(const std::vector<int>& f, int max_stone) {
    std::memset(sg, 0, sizeof(sg)); // Implicitly includes boundary: sg[0] = 0

    // Temporary marking array for simulating mex operation set determination
    std::vector<bool> vis(max_stone + 5, false);

    for (int i = 1; i <= max_stone; ++i) {
        // Reset marking bucket
        std::fill(vis.begin(), vis.end(), false);

        // Scan all legal move strategies
        for (int move : f) {
            if (i >= move) {
                vis[sg[i - move]] = true; // Mark that the SG value of the successor state has appeared
            }
        }

        // Execute mex operation: find the smallest unmarked non-negative integer
        int m = 0;
        while (vis[m]) {
            m++;
        }
        sg[i] = m; // Lock the state
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int k; // Size of the move limit set
    if (std::cin >> k) {
        std::vector<int> f(k);
        for (int i = 0; i < k; ++i) {
            std::cin >> f[i];
        }

        // Preprocess the table, assuming the maximum scale of stones in the problem is 10000
        precompute_sg(f, MAXN);

        int m; // Number of game situations to inquire
        if (std::cin >> m) {
            while (m--) {
                int n; // Number of stone piles in the current game
                std::cin >> n;
                int global_sg_sum = 0;

                for (int i = 0; i < n; ++i) {
                    int stones;
                    std::cin >> stones;
                    global_sg_sum ^= sg[stones]; // Core: forcibly XOR SG values of multiple sub-games
                }

                if (global_sg_sum != 0) {
                    std::cout << "W"; // First player wins
                } else {
                    std::cout << "L"; // First player loses
                }
            }
            std::cout << "\n";
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

1. The vis array in the mex operation is not cleared layer by layer or the clearing range is incorrect In the inner loop before calculating sg[i], the vis marking array must be reset. Some contestants, in an attempt to save effort, make vis global, only clearing up to the size of the set $f$, which will lead to residual markings from the previous state contaminating the current mex determination, resulting in values that deviate from the correct mex trajectory.
2. Incorrectly forcing SG XOR on "non-independent" games The premise of using the SG theorem is that each sub-game is independent, and each operation can only interfere with one sub-game. If the problem modifies the rules to allow "removing the same number of stones from two piles simultaneously", a strong causal coupling is generated between these two piles, and the sub-games are no longer independent. In this case, directly XORing sg[u] ^ sg[v] will lead to a complete logical breakdown.

Classic NOIP/Luogu Real Questions

1. Luogu P2189 Little Z's Game / Similar to Luogu P5663 [CSP-J2019] Processing Parts Topological Evolution

• Problem Description: Given a directed acyclic graph, certain nodes contain chess pieces. Two players take turns moving pieces, and each time can choose any piece to move along directed edges to adjacent successor nodes. The player unable to move loses.
• Core of the Problem: The application of SG theorem on multi-sub-games on DAG topological grids.
• Core Solving Idea: Each piece moves independently in the DAG, which fully conforms to the characteristics of independent sub-games. We first perform a reverse topological sort (or memoized search) on the entire DAG to determine the single-point sg[u] values for each node:

$$ ext{sg}[u] = ext{mex}ig({ ext{sg}[v] ig| (u,v) ext{ in } E } \big) $$

After preprocessing all node SG values, we read in the initial node numbers where each piece is located and XOR all these node SG values together. If the XOR sum is non-zero, the first player wins; otherwise, the second player wins.

2. Luogu P2147 [SDOI2009] E&D (Deep Variant)

• Problem Description: Multiple piles of stones, each pile has two numbers $(x,y)$. Each operation destroys a pile and splits it into two piles $(x_1, y_1)$ and $(x_2, y_2)$ such that $x_1+x_2=x, y_1+y_2=y$.
• Core of the Problem: SG function operations with split (game branch) characteristics.
• Core Solving Idea: The operation in this problem splits a game state into two independent sub-games. According to the SG theorem, the SG value of the successor state after a state splits is equal to the XOR sum of the SG values of the two newly generated states. In other words, the successor set of the state $(x,y)$ is not a single value, but a composite value of the form $ ext{SG}(x_1, y_1) igoplus ext{SG}(x_2, y_2)$. When writing memoized searches or tables, the transition equation should be modified to:

$$ ext{SG}(x,y) = ext{mex}igg(ig{ ext{SG}(x_1, y_1) igoplus ext{SG}(x_2, y_2) ig} igg) $$

This demonstrates that the SG theorem can not only be used for the final sum but can also be directly embedded in the Mexican recursive tree of state splitting.