Decoding Impartial Combinatorial Games: Analysis of P and N States in Game Theory

Core Logic and Mathematical Principles

Game Theory is a branch of discrete mathematics that studies decision-making interactions with adversarial properties. In the NOIP competition, the focus is heavily on Impartial Combinatorial Games (ICG).

1. Characteristics of Impartial Combinatorial Games (ICG)

A game is classified as an impartial combinatorial game if it satisfies the following stringent constraints:

The game involves two players who take turns making decisions.
In any given game state (State), the set of legal moves (Legal Moves) depends solely on the state itself, independent of which player's turn it is (for example, chess does not qualify as ICG, since the black player can only move black pieces, and the red player can only move red pieces).
The game must end in a finite number of steps, and meaningless cycles are not allowed.
Typically follows the Normal Play Convention: the player who makes the last legal move wins (i.e., the player who cannot move is considered to lose).

2. State Space Division: P-position and N-position

In the topological graph of the state space of ICG, all game states can be strictly and uniquely divided into two categories:

P-position (Previous-position): a losing state. This means that the player who just made the last move (the previous player) is in a winning position, and the player whose turn it is now will lose if both players play optimally.
N-position (Next-position): a winning state. This means that the player who is about to make a move (the next player) has a strategy to ensure victory.

Three Axioms for State Determination

Based on backward induction, the essence of the state is locked by the following three foundational logics:

Terminal states must be P states: All terminal states that cannot make any legal moves are P-positions (according to the rule that the player who cannot move loses).
Reachable P must be N: If from the current state there exists at least one legal move that can transition to a P-position, then the current state is an N-position (the current player simply needs to decisively pass this losing state to the opponent to win).
All successors being N must be P: If from the current state, regardless of the legal move made, all resulting successor states are N-positions, then the current state is a P-position (no matter how the current player struggles, the opponent faces winning states).

Algorithm Derivation and State Design

Topological Memoization Search of State Graphs

For relatively simple games where states can be quantified numerically, we can abstract all possible game states as nodes on a directed acyclic graph (DAG), with legal moves abstracted as directed edges.

State Design: Define a one-dimensional or multi-dimensional state array f[state], with the values defined as:
0: indicates that the state is a P-position (losing state).
1: indicates that the state is a N-position (winning state).
State Transition Equation:

$$f[u] = \bigvee_{(u, v) \in E} \big( f[v] == 0 \big)$$

Algebraically, this means performing a logical OR operation over all successor nodes $v$ of node $u$. If at least one of the successors is a losing state ($f[v]==0$), then the current state is a winning state ($f[u]=1$); if all successors are winning states, then the current state is a losing state.

Computation Sequence: Use memoization. Since the game must end in a finite number of steps, this DAG naturally possesses the acyclic property. Starting from the initial state and searching downwards, when encountering a terminal state with an out-degree of $0$, return 0 directly, and backtrack layer by layer.

C++ Standard Source Code

The following source code demonstrates how to determine P/N states in a typical game state graph using memoization.

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

const int MAXS = 10000;
int f[MAXS + 5]; // State memoization array: -1 indicates uncalculated, 0 indicates P-position, 1 indicates N-position

// Get all legal successor states for the current state (example: can subtract 1, 3, or 4 each time)
std::vector<int> get_next_states(int state) {
    std::vector<int> next_states;
    if (state >= 1) next_states.push_back(state - 1);
    if (state >= 3) next_states.push_back(state - 3);
    if (state >= 4) next_states.push_back(state - 4);
    return next_states;
}

// Memoization search to determine P/N states
int judge_position(int state) {
    if (f[state] != -1) return f[state]; // Intercept already calculated states

    std::vector<int> next_moves = get_next_states(state);

    // Boundary axiom 1: terminal states that cannot move must be P-position
    if (next_moves.empty()) {
        f[state] = 0;
        return 0;
    }

    // Iterate through all possible successor moves
    for (int next_state : next_moves) {
        // Axiom 2: if there exists a losing state (P) among successor states, the current state becomes a winning state (N)
        if (judge_position(next_state) == 0) {
            f[state] = 1;
            return 1;
        }
    }

    // Axiom 3: if all successor moves lead to winning states, the current player has no escape, the current state is a losing state (P)
    f[state] = 0;
    return 0;
}

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

    std::memset(f, -1, sizeof(f)); // Initialize state table to -1

    int t;
    if (std::cin >> t) {
        while (t--) {
            int initial_state;
            std::cin >> initial_state;

            if (judge_position(initial_state) == 1) {
                std::cout << "First player wins (N-position)\n";
            } else {
                std::cout << "Second player wins (P-position)\n";
            }
        }
    }
    return 0;
}

NOIP Practical Pitfall Guide

Confusing P states (losing) with N states (winning) in algebraic conclusions When writing game theory searches, participants often mistakenly reverse judgment conditions. It is imperative to remember: it is N only if successors include P. Many contestants incorrectly write "all successors must be P for it to be N", which completely flips the victory and defeat logic of the entire game tree.
Forgetting to reset or incorrectly resetting the memoization array under multiple queries If the rules of the game (e.g., the set of stones that can be taken each time) change between different input data, then the f array state obtained from the last query must not be reused in the next query. It is essential to use std::memset(f, -1, sizeof(f)) to thoroughly reset the array for each test input; otherwise, serious cross-data state contamination may occur.

Classic NOIP/Luogu Problems

1. Luogu P1290 Golden Ratio Game

Problem Description: There are two positive integers $(a, b)$, with $a \ge b$. Two players take turns to operate, each time they can subtract any positive integer multiple of the smaller number from the larger number, and the result cannot be negative. The player who first reduces one of the numbers to $0$ wins. Determine whether the first player is guaranteed to win.
Essence of the Problem: An Euclidean game model with decision branches.
Core Solution Idea: The form of this problem is very similar to the Euclidean algorithm. Let the current state be $(a, b)$.
If $a < 2b$, the current player has only one unique legal move, which is to change to $(b, a - b)$, and directly recurse down to determine.
If $a \ge 2b$, the current player faces a large decision-making power. They can choose to transition to $(b, a \bmod b)$ or $(b, a \bmod b + b)$. Among these two successive states, there must exist one P state and one N state. The first player with the choice simply needs to decisively throw the P state to the opponent to secure victory. Therefore, whoever first encounters the situation $a \ge 2b$ locks in victory.

2. Luogu P2148 [SDOI2009] E&D

Problem Description: The game has several piles of stones, each represented by two positive integers $(x, y)$. Each time, a player can choose a pile $(x, y)$, eliminate it, and then split the remaining stones into two new piles $(x_1, y_1)$ and $(x_2, y_2)$, such that $x_1+x_2=x$ and $y_1+y_2=y$. The player who cannot make a move loses.
Essence of the Problem: Game analysis under state decomposition (the SG function will be introduced later, but its foundation still relies on P/N determination).
Core Solution Idea: By running the memoization search code provided above on a small range of data, one can print the P/N state table for small $(x,y)$. By observing the matrix shapes generated, one can clearly capture the patterns: the winning and losing state patterns have a strong algebraic mapping with the lowest bit of $(x-1) \mid (y-1)$ (the lowbit). During the competition, using the P/N determination code to perform small-scale tabulation to find patterns is the most efficient scoring method for solving complex game theory problems.