Basic Game Theory Concepts

Game theory studies mathematical models of strategic interaction between rational decision-makers. In competitive programming, we focus on two-player, zero-sum, perfect information games.

Determining Winning/Losing Positions

// Basic game state analysis
bool isWinning(int state, vector<int>& memo) {
    if(memo[state] != -1) return memo[state];
    
    // Check if this is a terminal (losing) state
    if(isTerminal(state)) {
        return memo[state] = false;
    }
    
    // Try all possible moves
    vector<int> nextStates = getNextStates(state);
    
    for(int nextState : nextStates) {
        // If any move leads to a losing position for opponent, this is winning
        if(!isWinning(nextState, memo)) {
            return memo[state] = true;
        }
    }
    
    // All moves lead to winning positions for opponent, so this is losing
    return memo[state] = false;
}
                    

The Nim Game

Nim is a fundamental game where players take turns removing objects from piles. The player who takes the last object wins.

Basic Nim Strategy

The key insight: A position is losing if and only if the XOR (nim-sum) of all pile sizes is 0.

// Determine if current Nim position is winning
bool isNimWinning(vector<int>& piles) {
    int nimSum = 0;
    for(int pile : piles) {
        nimSum ^= pile;
    }
    return nimSum != 0; // Non-zero nim-sum means winning position
}

// Find optimal move in Nim
pair<int, int> findNimMove(vector<int>& piles) {
    int nimSum = 0;
    for(int pile : piles) {
        nimSum ^= pile;
    }
    
    if(nimSum == 0) return {-1, -1}; // Already losing position
    
    // Find a pile where pile XOR nimSum < pile
    for(int i = 0; i < piles.size(); i++) {
        int newSize = piles[i] ^ nimSum;
        if(newSize < piles[i]) {
            return {i, piles[i] - newSize}; // Pile index, amount to remove
        }
    }
    
    return {-1, -1}; // Should not reach here
}
                    

Sprague-Grundy Theorem

The Sprague-Grundy theorem allows us to analyze complex games by computing the Grundy number (nimber) of each position.

Computing Grundy Numbers

// Calculate Grundy number for a game state
int grundyNumber(int state, vector<int>& memo) {
    if(memo[state] != -1) return memo[state];
    
    // Terminal states have Grundy number 0
    if(isTerminal(state)) {
        return memo[state] = 0;
    }
    
    // Get all possible next states
    vector<int> nextStates = getNextStates(state);
    set<int> reachableGrundy;
    
    // Collect Grundy numbers of all reachable states
    for(int nextState : nextStates) {
        reachableGrundy.insert(grundyNumber(nextState, memo));
    }
    
    // Grundy number is the minimum excludant (mex)
    int mex = 0;
    while(reachableGrundy.count(mex)) {
        mex++;
    }
    
    return memo[state] = mex;
}

// For combined games, XOR the Grundy numbers
int combinedGrundy(vector<int>& gameStates, vector<vector<int>>& memos) {
    int result = 0;
    for(int i = 0; i < gameStates.size(); i++) {
        result ^= grundyNumber(gameStates[i], memos[i]);
    }
    return result;
}
                    

Minimax Algorithm

Minimax is used to find the optimal move in two-player games by assuming both players play optimally.

// Minimax algorithm for two-player games
int minimax(GameState state, int depth, bool isMaximizing) {
    // Terminal state or depth limit reached
    if(isTerminal(state) || depth == 0) {
        return evaluate(state); // Return game evaluation
    }
    
    vector<GameState> nextStates = getNextStates(state);
    
    if(isMaximizing) {
        int maxEval = INT_MIN;
        for(GameState nextState : nextStates) {
            int eval = minimax(nextState, depth - 1, false);
            maxEval = max(maxEval, eval);
        }
        return maxEval;
    } else {
        int minEval = INT_MAX;
        for(GameState nextState : nextStates) {
            int eval = minimax(nextState, depth - 1, true);
            minEval = min(minEval, eval);
        }
        return minEval;
    }
}

// Alpha-beta pruning optimization
int alphaBeta(GameState state, int depth, int alpha, int beta, bool isMaximizing) {
    if(isTerminal(state) || depth == 0) {
        return evaluate(state);
    }
    
    vector<GameState> nextStates = getNextStates(state);
    
    if(isMaximizing) {
        int maxEval = INT_MIN;
        for(GameState nextState : nextStates) {
            int eval = alphaBeta(nextState, depth - 1, alpha, beta, false);
            maxEval = max(maxEval, eval);
            alpha = max(alpha, eval);
            if(beta <= alpha) break; // Beta cutoff
        }
        return maxEval;
    } else {
        int minEval = INT_MAX;
        for(GameState nextState : nextStates) {
            int eval = alphaBeta(nextState, depth - 1, alpha, beta, true);
            minEval = min(minEval, eval);
            beta = min(beta, eval);
            if(beta <= alpha) break; // Alpha cutoff
        }
        return minEval;
    }
}
                    

Common Game Types

Subtraction Games

Players can remove 1, 2, or 3 objects from a pile:

// Subtraction game with allowed moves {1, 2, 3}
bool isSubtractionWinning(int n, vector<int>& memo) {
    if(memo[n] != -1) return memo[n];
    
    if(n == 0) return memo[n] = false; // Terminal losing state
    
    vector<int> moves = {1, 2, 3};
    for(int move : moves) {
        if(n >= move && !isSubtractionWinning(n - move, memo)) {
            return memo[n] = true; // Found winning move
        }
    }
    
    return memo[n] = false; // All moves lead to winning positions
}
                    

Green Hackenbush

A game played on trees where players remove edges:

// Calculate Grundy number for Green Hackenbush on trees
int hackenbushGrundy(int node, vector<vector<int>>& adj, vector<int>& memo, int parent = -1) {
    if(memo[node] != -1) return memo[node];
    
    int result = 0;
    
    // XOR Grundy numbers of all subtrees
    for(int child : adj[node]) {
        if(child != parent) {
            result ^= (hackenbushGrundy(child, adj, memo, node) + 1);
        }
    }
    
    return memo[node] = result;
}
                    

Advanced Game Theory

Partizan Games

Games where the set of available moves depends on which player is moving:

// Example: Domineering (players place dominoes differently)
struct GameValue {
    int left, right; // Values for left and right players
    
    bool isWinningForLeft() {
        return left >= 0;
    }
    
    bool isWinningForRight() {
        return right <= 0;
    }
};

// Combine partizan game values
GameValue combinePartizan(GameValue a, GameValue b) {
    return {a.left + b.left, a.right + b.right};
}