Pattern 15: Game Theory DP

The Adversarial Pattern: Optimal play when two players compete. Minimax strategy, Nim games, Grundy numbers.

---

The Core Pattern

THE MENTAL MODEL

Imagine two players taking turns trying to win:

1. Two players: maximizer (wants max score) and minimizer (wants min score)
2. Players play optimally - always make best move for themselves
3. Use minimax: maximize your gain while assuming opponent minimizes it
4. State tracks: whose turn, game configuration
5. Answer depends on both players' best strategies

Key Insight: A winning position is one where you have at least one move that puts your opponent in a losing position.

---

Pattern Recognition

WHEN YOU SEE THIS PATTERN

Keywords: "two players", "optimal play", "winner", "game", "turns", "minimax", "both play optimally"

Structure:

• Two competing players
• Turn-based gameplay
• Both play optimally (crucial!)
• Need to determine winner or optimal score

State:

• dp[state][turn] = "best outcome from this state for current player"
• Turn alternates between players

Transitions:

• Your turn: You win if ANY move puts opponent in losing position
• Opponent's turn: They will choose their best move (your worst outcome)

---

General Templates

Template 1: Win/Lose Games

public boolean canWin(State state, boolean isMyTurn) {
    // Base case: terminal state
    if (isTerminal(state)) {
        return determineWinner(state, isMyTurn);
    }

    if (isMyTurn) {
        // I win if ANY move leads to opponent losing
        for (Move move : getPossibleMoves(state)) {
            State nextState = applyMove(state, move);
            if (!canWin(nextState, false)) {
                return true;  // Found a winning move!
            }
        }
        return false;  // All moves lead to opponent winning
    } else {
        // Opponent plays optimally
        // I win only if ALL their moves lead to my winning
        for (Move move : getPossibleMoves(state)) {
            State nextState = applyMove(state, move);
            if (canWin(nextState, true)) {
                return true;  // Opponent has a winning move
            }
        }
        return false;  // All opponent moves lead to my win
    }
}

---

Template 2: Score Maximization Games

public int getMaxScore(State state, boolean isMyTurn) {
    // Base case
    if (isTerminal(state)) {
        return getScore(state);
    }

    if (isMyTurn) {
        // Maximize my score
        int maxScore = Integer.MIN_VALUE;
        for (Move move : getPossibleMoves(state)) {
            State nextState = applyMove(state, move);
            int score = getMaxScore(nextState, false);
            maxScore = Math.max(maxScore, score);
        }
        return maxScore;
    } else {
        // Opponent minimizes my score
        int minScore = Integer.MAX_VALUE;
        for (Move move : getPossibleMoves(state)) {
            State nextState = applyMove(state, move);
            int score = getMaxScore(nextState, true);
            minScore = Math.min(minScore, score);
        }
        return minScore;
    }
}

---

Key Insights

🎯 Understanding Game States

1. Winning State: You have at least one move that puts opponent in a losing state
2. Losing State: All your moves put opponent in a winning state
3. Terminal State: Game is over, winner is determined

🎯 Return Logic Patterns

// Pattern 1: OR logic (win if ANY move wins)
return move1Wins || move2Wins || move3Wins;

// Pattern 2: Negation (win if opponent loses)
return !oppWinsAfterMove1 || !oppWinsAfterMove2 || !oppWinsAfterMove3;

// Pattern 3: De Morgan's Law (equivalent to Pattern 2)
return !(oppWinsAfterMove1 && oppWinsAfterMove2 && oppWinsAfterMove3);

🎯 Common Mistake: Perspective Confusion

// WRONG: "I win if opponent wins from any move"
return opponentWins1 || opponentWins2 || opponentWins3;

// CORRECT: "I win if ANY move makes opponent lose"
return !opponentWins1 || !opponentWins2 || !opponentWins3;

Key: Recursive calls return result from opponent's perspective. You need to negate!

---

Problem-Solving Framework

Step 1: Define the Game State

• What information do you need to track?
• Whose turn is it?
• What's the game configuration?

Step 2: Identify Base Cases

• What are the terminal states?
• Who wins in each terminal state?

Step 3: Define State Transitions

• What moves are available from current state?
• How does each move change the state?

Step 4: Choose Return Logic

• Win/Lose: Do I have ANY winning move?
• Score: What's the best score I can achieve?

Step 5: Add Memoization

• Cache: dp[state][turn]
• Key: unique representation of game state

Step 6: Optimize (If Possible)

• Look for mathematical patterns
• Check for symmetries
• Consider space optimization

---

Complexity Analysis

Approach	Time	Space	Notes
Naive Recursion	O(k^n)	O(n)	k = branching factor
Memoization	O(states × moves)	O(states)	Polynomial time
Bottom-Up DP	O(states × moves)	O(states)	Iterative version
Mathematical	O(1)	O(1)	Only for special cases

---

Common LeetCode Problems

By Category

Nim-like Games:

• Nim Game (Easy) - LC 292
• Stone Game IV (Hard) - LC 1510

Stone Games (Pick from Array):

• Stone Game (Medium) - LC 877
• Stone Game II (Medium) - LC 1140
• Stone Game III (Hard) - LC 1406

Number Selection Games:

• Can I Win (Medium) - LC 464
• Predict the Winner (Medium) - LC 486

String Games:

• Flip Game II (Medium) - LC 294

Other:

• Guess Number Higher or Lower II (Medium) - LC 375

---

Advanced Topics

Grundy Numbers (Sprague-Grundy Theorem)

For multi-pile Nim games, use XOR of Grundy numbers:

int calculateGrundy(int n) {
    if (n == 0) return 0;

    Set<Integer> reachable = new HashSet<>();
    for (int move : possibleMoves(n)) {
        reachable.add(calculateGrundy(n - move));
    }

    // MEX (Minimal Excludant): smallest non-negative integer not in set
    int mex = 0;
    while (reachable.contains(mex)) {
        mex++;
    }
    return mex;
}

Property: XOR of Grundy numbers for independent games gives winning strategy.

---

Summary Checklist

✅ Draw game tree for small inputs ✅ Identify base cases correctly (who wins in terminal states?) ✅ Understand what recursive calls represent (opponent's perspective!) ✅ Use correct return logic: !opp_wins_1 || !opp_wins_2 || ... ✅ Cache both states: your turn AND opponent's turn ✅ Look for mathematical patterns before implementing full DP

---

Resources

• Sprague-Grundy Theorem: For complex Nim-like games
• Minimax Algorithm: Foundation for game theory
• Alpha-Beta Pruning: Optimization for game trees
• Nash Equilibrium: For non-zero-sum games

---

Remember: In game theory DP, you're not just optimizing for yourself - you're optimizing while assuming your opponent also plays optimally! This dual perspective is what makes the pattern unique.