Game Theory

1. Minimax Algorithm

Concept	Description	Purpose	Complexity
Minimax	Maximize your minimum gain, minimize opponent's maximum gain	Optimal play for two-player zero-sum games	`O(b^d)` where b=branching factor, d=depth
Max Player	Tries to maximize the score	Your turn	Choose max of children
Min Player	Tries to minimize the score	Opponent's turn	Choose min of children
Terminal State	Game over condition with score	Base case for recursion	Win/loss/draw evaluation

Example: Basic minimax for Tic-Tac-Toe

// Simplified minimax for optimal game play
function minimax(board, depth, isMaximizing) {
    // Check terminal state
    const score = evaluate(board);
    
    // If game is over, return score
    if (score !== null) return score;
    
    // If board is full, it's a tie
    if (isBoardFull(board)) return 0;
    
    if (isMaximizing) {
        let bestScore = -Infinity;
        
        // Try all possible moves
        for (let i = 0; i < 9; i++) {
            if (board[i] === '') {
                board[i] = 'X'; // Make move
                const score = minimax(board, depth + 1, false);
                board[i] = ''; // Undo move
                bestScore = Math.max(bestScore, score);
            }
        }
        return bestScore;
    } else {
        let bestScore = Infinity;
        
        for (let i = 0; i < 9; i++) {
            if (board[i] === '') {
                board[i] = 'O'; // Opponent's move
                const score = minimax(board, depth + 1, true);
                board[i] = ''; // Undo move
                bestScore = Math.min(bestScore, score);
            }
        }
        return bestScore;
    }
}

// Evaluate board: +10 for X win, -10 for O win, null for ongoing
function evaluate(board) {
    const winPatterns = [
        [0,1,2], [3,4,5], [6,7,8], // Rows
        [0,3,6], [1,4,7], [2,5,8], // Columns
        [0,4,8], [2,4,6]           // Diagonals
    ];
    
    for (const [a, b, c] of winPatterns) {
        if (board[a] && board[a] === board[b] && board[a] === board[c]) {
            return board[a] === 'X' ? 10 : -10;
        }
    }
    return null;
}

function isBoardFull(board) {
    return board.every(cell => cell !== '');
}

// Find best move
function findBestMove(board) {
    let bestScore = -Infinity;
    let bestMove = -1;
    
    for (let i = 0; i < 9; i++) {
        if (board[i] === '') {
            board[i] = 'X';
            const score = minimax(board, 0, false);
            board[i] = '';
            
            if (score > bestScore) {
                bestScore = score;
                bestMove = i;
            }
        }
    }
    
    return bestMove;
}

Note: Minimax assumes both players play optimally. The algorithm explores the entire game tree, so it's guaranteed to find the best move but can be slow for complex games. Use alpha-beta pruning to optimize.

2. Alpha Beta Pruning

Parameter	Meaning	Update Rule	Effect
Alpha (α)	Best score maximizer can guarantee	α = max(α, value)	Lower bound for max player
Beta (β)	Best score minimizer can guarantee	β = min(β, value)	Upper bound for min player
Pruning Condition	α ≥ β	Stop exploring this branch	Remaining moves won't be chosen
Optimization	Cuts search tree significantly	Best case: O(b^(d/2))	Can search twice as deep

Example: Minimax with alpha-beta pruning

function minimaxAlphaBeta(board, depth, alpha, beta, isMaximizing) {
    const score = evaluate(board);
    
    if (score !== null) return score;
    if (isBoardFull(board)) return 0;
    
    if (isMaximizing) {
        let maxEval = -Infinity;
        
        for (let i = 0; i < 9; i++) {
            if (board[i] === '') {
                board[i] = 'X';
                const eval = minimaxAlphaBeta(board, depth + 1, alpha, beta, false);
                board[i] = '';
                
                maxEval = Math.max(maxEval, eval);
                alpha = Math.max(alpha, eval);
                
                // Beta cutoff: opponent won't allow this branch
                if (beta <= alpha) {
                    break; // Prune remaining moves
                }
            }
        }
        return maxEval;
    } else {
        let minEval = Infinity;
        
        for (let i = 0; i < 9; i++) {
            if (board[i] === '') {
                board[i] = 'O';
                const eval = minimaxAlphaBeta(board, depth + 1, alpha, beta, true);
                board[i] = '';
                
                minEval = Math.min(minEval, eval);
                beta = Math.min(beta, eval);
                
                // Alpha cutoff: maximizer won't allow this branch
                if (beta <= alpha) {
                    break; // Prune remaining moves
                }
            }
        }
        return minEval;
    }
}

// Initial call with alpha = -∞, beta = +∞
function findBestMoveOptimized(board) {
    let bestScore = -Infinity;
    let bestMove = -1;
    let alpha = -Infinity;
    const beta = Infinity;
    
    for (let i = 0; i < 9; i++) {
        if (board[i] === '') {
            board[i] = 'X';
            const score = minimaxAlphaBeta(board, 0, alpha, beta, false);
            board[i] = '';
            
            if (score > bestScore) {
                bestScore = score;
                bestMove = i;
            }
            alpha = Math.max(alpha, bestScore);
        }
    }
    
    return bestMove;
}

Example: Alpha-beta pruning visualization

// Understanding pruning:
// 
//          Max (α=-∞, β=+∞)
//         /    |    \
//       /      |      \
//     Min     Min     Min
//    / | \   / | \   
//   3  5  2  ...
//
// At first Min node:
// - Evaluates 3: β = min(+∞, 3) = 3
// - Evaluates 5: β stays 3 (min doesn't change)
// - Evaluates 2: β stays 3
// - Returns 2 to Max
// - Max: α = max(-∞, 2) = 2
//
// At second Min node:
// - Evaluates first child, gets 1
// - β = min(+∞, 1) = 1
// - Since β(1) <= α(2), PRUNE!
// - Don't need to check remaining children
// - Max already has better option (2 > 1)

function minimaxWithLogging(board, depth, alpha, beta, isMax) {
    const score = evaluate(board);
    if (score !== null) return score;
    if (isBoardFull(board)) return 0;
    
    const indent = '  '.repeat(depth);
    console.log(`${indent}${isMax ? 'MAX' : 'MIN'} (α=${alpha}, β=${beta})`);
    
    if (isMax) {
        let maxEval = -Infinity;
        for (let i = 0; i < 9; i++) {
            if (board[i] === '') {
                board[i] = 'X';
                const eval = minimaxWithLogging(board, depth + 1, alpha, beta, false);
                board[i] = '';
                
                maxEval = Math.max(maxEval, eval);
                alpha = Math.max(alpha, eval);
                
                if (beta <= alpha) {
                    console.log(`${indent}PRUNE at α=${alpha}, β=${beta}`);
                    break;
                }
            }
        }
        return maxEval;
    } else {
        let minEval = Infinity;
        for (let i = 0; i < 9; i++) {
            if (board[i] === '') {
                board[i] = 'O';
                const eval = minimaxWithLogging(board, depth + 1, alpha, beta, true);
                board[i] = '';
                
                minEval = Math.min(minEval, eval);
                beta = Math.min(beta, eval);
                
                if (beta <= alpha) {
                    console.log(`${indent}PRUNE at α=${alpha}, β=${beta}`);
                    break;
                }
            }
        }
        return minEval;
    }
}

3. Nim Game Pattern

Concept	Description	Winning Condition	Strategy
Nim Game	Remove 1-k items from pile, last to move loses	Leave opponent with multiple of (k+1)	Mathematical pattern
Can Win Formula	`n % (k + 1) !== 0`	If n is not multiple of k+1, first player wins	O(1) solution
Nim Sum (XOR)	For multiple piles: XOR all pile sizes	XOR = 0 means losing position	Sprague-Grundy theorem
Grundy Number	Minimum excludant (mex) of reachable states	Grundy = 0 is losing position	Generalized Nim

Example: Simple Nim game - remove 1, 2, or 3 stones

// Classic Nim: n stones, can remove 1-3, last to move wins
function canWinNim(n) {
    // If n % 4 === 0, you lose (opponent can mirror moves)
    // Otherwise, remove stones to leave opponent with multiple of 4
    return n % 4 !== 0;
}

// Examples:
// n=1: Take 1, you win -> true
// n=2: Take 2, you win -> true
// n=3: Take 3, you win -> true
// n=4: Any move (1,2,3) leaves opponent with 3,2,1 -> false
// n=5: Take 1, leave 4 for opponent -> true
// n=6: Take 2, leave 4 for opponent -> true
// n=7: Take 3, leave 4 for opponent -> true
// n=8: Any move leaves 7,6,5 for opponent -> false

// Strategy: Leave opponent with multiple of 4
function optimalNimMove(n) {
    if (n % 4 === 0) return -1; // No winning move
    return n % 4; // Take this many to leave multiple of 4
}

// Generalized: can remove 1 to k stones
function canWinNimGeneral(n, k) {
    return n % (k + 1) !== 0;
}

// Multiple piles - Nim sum (XOR)
function canWinMultiPileNim(piles) {
    let nimSum = 0;
    for (const pile of piles) {
        nimSum ^= pile;
    }
    // If XOR of all piles is 0, current player loses
    return nimSum !== 0;
}

// Find winning move in multi-pile Nim
function findWinningMove(piles) {
    const nimSum = piles.reduce((xor, pile) => xor ^ pile, 0);
    
    if (nimSum === 0) return null; // No winning move
    
    // Find a pile where removing stones reduces nim sum to 0
    for (let i = 0; i < piles.length; i++) {
        const targetSize = piles[i] ^ nimSum;
        if (targetSize < piles[i]) {
            return { pile: i, remove: piles[i] - targetSize };
        }
    }
}

Note: The Nim game pattern applies to many variations. Key insight: positions where n % (k+1) === 0 are losing positions because any move you make can be mirrored by opponent to return to a multiple of k+1.

4. Stone Game DP

Problem Type	DP State	Transition	Time
Take First/Last	`dp[i][j]` = max score for piles[i..j]	Max of taking first or last	`O(n²)`
Optimal Substructure	Best play in subarray	Assume opponent plays optimally	Minimax DP
Score Difference	Your score - opponent score	Maximize difference	Common pattern
Even-Odd Parity	Some problems have parity tricks	First player wins if total is odd	O(1) for special cases

Example: Stone game - take first or last

function stoneGame(piles) {
    const n = piles.length;
    
    // dp[i][j] = max stones you can get from piles[i..j]
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    // Base case: single pile
    for (let i = 0; i < n; i++) {
        dp[i][i] = piles[i];
    }
    
    // Fill diagonal by diagonal (length 2, 3, ..., n)
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            
            // Calculate total stones in range [i, j]
            let total = 0;
            for (let k = i; k <= j; k++) {
                total += piles[k];
            }
            
            // Take first: piles[i] + (total - piles[i] - dp[i+1][j])
            // Take last:  piles[j] + (total - piles[j] - dp[i][j-1])
            const takeFirst = total - dp[i + 1][j];
            const takeLast = total - dp[i][j - 1];
            
            dp[i][j] = Math.max(takeFirst, takeLast);
        }
    }
    
    const total = piles.reduce((sum, pile) => sum + pile, 0);
    
    // You get dp[0][n-1], opponent gets rest
    return dp[0][n - 1] > total - dp[0][n - 1];
}

// Optimized: Stone game with even number of piles
// First player always wins!
function stoneGameOptimized(piles) {
    // Parity trick: group piles into even and odd indices
    // First player can always take all even or all odd indices
    // One group sum is guaranteed > half total
    return true;
}

// Explanation of why first player wins:
// Piles: [5, 3, 4, 5]
// Even indices (0, 2): 5 + 4 = 9
// Odd indices (1, 3):  3 + 5 = 8
// First player can force taking all even or all odd
// Take from end that starts the better group

Example: Stone game with prefix sum optimization

function stoneGameDP(piles) {
    const n = piles.length;
    
    // Prefix sum for O(1) range sum
    const prefix = [0];
    for (const pile of piles) {
        prefix.push(prefix[prefix.length - 1] + pile);
    }
    
    // Get sum of piles[i..j]
    const rangeSum = (i, j) => prefix[j + 1] - prefix[i];
    
    // dp[i][j] = maximum stones from piles[i..j]
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    for (let i = 0; i < n; i++) {
        dp[i][i] = piles[i];
    }
    
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            const total = rangeSum(i, j);
            
            // If you take piles[i], opponent plays optimally on [i+1, j]
            // You get: piles[i] + remaining stones after opponent's optimal play
            const takeFirst = total - dp[i + 1][j];
            
            // If you take piles[j], opponent plays optimally on [i, j-1]
            const takeLast = total - dp[i][j - 1];
            
            dp[i][j] = Math.max(takeFirst, takeLast);
        }
    }
    
    return dp[0][n - 1];
}

// Memoization approach
function stoneGameMemo(piles) {
    const memo = new Map();
    
    function dp(i, j, total) {
        if (i === j) return piles[i];
        
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key);
        
        const takeFirst = total - dp(i + 1, j, total - piles[i]);
        const takeLast = total - dp(i, j - 1, total - piles[j]);
        
        const result = Math.max(takeFirst, takeLast);
        memo.set(key, result);
        return result;
    }
    
    const total = piles.reduce((a, b) => a + b, 0);
    return dp(0, piles.length - 1, total);
}

5. Predict the Winner

Approach	State	Strategy	Complexity
Minimax DP	`dp[i][j]` = score difference	Maximize your advantage	`O(n²)` time, `O(n²)` space
Score Difference	Your score - opponent's score	Win if difference ≥ 0	Simplifies logic
1D DP Optimization	Rolling array, use current row only	Space optimization	`O(n)` space
Memoization	Top-down with cache	Easier to understand	Same complexity, cleaner code

Example: Predict winner with DP

function predictTheWinner(nums) {
    const n = nums.length;
    
    // dp[i][j] = max score difference (you - opponent) for nums[i..j]
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    // Base case: single element, you take it
    for (let i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }
    
    // Fill for all lengths
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            
            // Take nums[i]: you get +nums[i], opponent gets -dp[i+1][j]
            const takeFirst = nums[i] - dp[i + 1][j];
            
            // Take nums[j]: you get +nums[j], opponent gets -dp[i][j-1]
            const takeLast = nums[j] - dp[i][j - 1];
            
            dp[i][j] = Math.max(takeFirst, takeLast);
        }
    }
    
    // Player 1 wins if score difference >= 0
    return dp[0][n - 1] >= 0;
}

// Example: nums = [1, 5, 2]
// 
// dp[0][0] = 1, dp[1][1] = 5, dp[2][2] = 2
// 
// dp[0][1]: Take 1 -> 1 - dp[1][1] = 1 - 5 = -4
//           Take 5 -> 5 - dp[0][0] = 5 - 1 = 4
//           dp[0][1] = 4
// 
// dp[1][2]: Take 5 -> 5 - dp[2][2] = 5 - 2 = 3
//           Take 2 -> 2 - dp[1][1] = 2 - 5 = -3
//           dp[1][2] = 3
// 
// dp[0][2]: Take 1 -> 1 - dp[1][2] = 1 - 3 = -2
//           Take 2 -> 2 - dp[0][1] = 2 - 4 = -2
//           dp[0][2] = -2
// 
// Result: -2 < 0, so false (Player 2 wins)

Example: Space-optimized and memoization

// 1D DP optimization - O(n) space
function predictTheWinnerOptimized(nums) {
    const n = nums.length;
    let dp = [...nums]; // Previous row
    
    for (let len = 2; len <= n; len++) {
        const newDp = Array(n).fill(0);
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            const takeFirst = nums[i] - dp[i + 1];
            const takeLast = nums[j] - dp[i];
            newDp[i] = Math.max(takeFirst, takeLast);
        }
        dp = newDp;
    }
    
    return dp[0] >= 0;
}

// Memoization approach - cleaner logic
function predictTheWinnerMemo(nums) {
    const memo = new Map();
    
    function maxDiff(i, j) {
        if (i === j) return nums[i];
        
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key);
        
        // Take first: you gain nums[i], lose opponent's best play
        const takeFirst = nums[i] - maxDiff(i + 1, j);
        
        // Take last: you gain nums[j], lose opponent's best play
        const takeLast = nums[j] - maxDiff(i, j - 1);
        
        const result = Math.max(takeFirst, takeLast);
        memo.set(key, result);
        return result;
    }
    
    return maxDiff(0, nums.length - 1) >= 0;
}

// Parity optimization for even-length arrays
function predictTheWinnerParity(nums) {
    // If even length, player 1 can always force a win
    // by choosing to always take from even or odd positions
    if (nums.length % 2 === 0) return true;
    
    // For odd length, need full DP
    return predictTheWinnerMemo(nums);
}

Warning: In game theory DP, track score difference, not absolute scores. When you take a value, your difference increases by that value, but opponent's optimal play on remaining elements decreases your total difference. Formula: `dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])`.

Summary: Game Theory Patterns

Minimax Principle: Maximize your minimum gain, minimize opponent's maximum gain - assumes both players play optimally
Max Player: Choose max of all possible moves - your turn trying to maximize score
Min Player: Choose min of all possible moves - opponent's turn trying to minimize your score
Alpha-Beta Pruning: α = best max can do, β = best min can do - prune when α ≥ β
Pruning Benefit: Reduces O(b^d) to O(b^(d/2)) in best case - allows searching twice as deep
Alpha Cutoff: If min node finds β ≤ α, stop - max already has better option elsewhere
Beta Cutoff: If max node finds α ≥ β, stop - min already has better option elsewhere
Nim Game Pattern: n % (k+1) !== 0 means first player wins - leave opponent with multiple of k+1
Nim Sum (XOR): For multiple piles, XOR all sizes - XOR = 0 is losing position (Sprague-Grundy)
Grundy Number: Mex (minimum excludant) of reachable states - Grundy = 0 is losing position
Stone Game DP: dp[i][j] = max stones from piles[i..j] - transition: max(total - dp[i+1][j], total - dp[i][j-1])
Score Difference: Track (your score - opponent score) instead of absolute - simplifies win condition to ≥ 0
Predict Winner: dp[i][j] = max difference - transition: max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
Parity Trick: Even-length arrays: first player wins by controlling even/odd indices - O(1) solution
Space Optimization: 2D DP can often reduce to 1D - use rolling array for O(n) space
Memoization: Top-down often cleaner than bottom-up for game theory - cache (i, j) states

Related Cheatsheets

Datastructures-algorithms