In competitive programming, many game theory problems fall under the category of impartial combinatorial games (ICG). These games involve two players who take turns making moves according to fixed rules. Crucially, both players have identical move options from any given state, and no randomness or hidden information is involved.

Each possible configuration during gameplay is referred to as a position. A move consists of transitioning from one position to another via a valid action. If a player has no legal moves available when it's their turn, they lose immediately. Positions are classified into two types:

• P-position: The current player will lose if both players play optimally.
• N-position: The current player can force a win with optimal play.

The classification follows recursive logic:

• A position with no outgoing moves is a P-position by definition.
• If at least one move leads to a P-position, the current position is an N-position.
• If all moves lead only to N-positions, then the current position is a P-position.

This framework enables backward induction: starting from terminal states (P-positions), we propagate winning and losing status through the game tree.

A common problem type involves determining whether the initial state is a winning (N) or losing (P) position for the first player. For example, consider a game with n stones where each player removes exactly one stone per turn, and the player taking the last stone wins. Here, the outcome depends on parity: if n is odd, the first player wins; otherwise, they lose.

Another variation allows removing up to m stones per turn. This general case is known as Bash Game. The key insight is that a position is losing (P) if the number of stones is divisible by (m + 1). Otherwise, it’s a winning (N) position. This leads to a direct solution:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (n % (m + 1) == 0)
        cout << "Defeat" << endl;
    else
        cout << "Victory" << endl;
    return 0;
}

This approach leverages periodicity in game states, reducing computation from O(n) to O(1).

Modeling Games as DAGs

Any impartial game can be represented as a directed acyclic graph (DAG), where nodes represent positions and edges represent valid transitions between them. For instance, the Bash Game with m=3 forms a structured DAG where each node connects to its next four predecessors.

In such graphs, the Sprague-Grundy (SG) function provides a powerful tool for analyzing game states. The SG value of a node is defined recursively:

• If a node has no outgoing edges, SG(x) = 0.
• Otherwise, SG(x) = mex{SG(y₁), SG(y₂), ..., SG(yₖ)}, where yᵢ are the immediate successors of x.

The mex (minimum excludant) operation returns the smallest non-negative integer not present in the set.

Examples:

• mex({1,2,3}) = 0
• mex({0,1,2}) = 3
• mex({0,1,3}) = 2

The significance of SG values lies in their ability to classify positions:

• A node with SG(x) = 0 is a P-position.
• A node with SG(x) > 0 is an N-position, since the player can always move to a node with SG = 0.

This property allows efficient evaluation of complex games involving multiple components.

Multi-Component Games and Nim

Consider a game with k tokens placed on different nodes of a DAG. Players alternate moving one token along a directed edge. The player unable to move loses. The overall game state is winning for the first player if and only if the XOR (nim-sum) of all individual token SG values is non-zero.

This result generalizes to the classic Nim game, where there are n piles of stones. On each turn, a player removes any number of stones from a single pile. The last player to remove a stone wins.

The solution relies on computing the nim-sum: XOR all pile sizes. If the result is zero, the first player is in a losing position; otherwise, they can force a win.

For example, with piles [1, 1, 2]:

1 ⊕ 1 ⊕ 2 = 0 → First player loses.

This equivalence arises because each pile behaves independently, and the SG value of a pile of size n is simply n. Thus, the total game state reduces to computing the XOR of all pile sizes.

Using SG theory, even seeming complex games can be decomposed into independant subgames, whose outcomes combine via XOR operations.