game_theory_patterns.cpp

/*
Game Theory & Minimax Patterns
Mathematical Foundation: Zero-sum games, optimal play assumption
Minimax: min(max(outcomes)) for adversarial games
Nim games: XOR properties, Grundy numbers
Applications: Tic-tac-toe, stone games, competitive scenarios
*/

#include <bits/stdc++.h>
using namespace std;

// Stone Game
// LeetCode: 877. Stone Game
// https://leetcode.com/problems/stone-game/
bool stoneGame(vector<int>& piles) {
    int n = piles.size();
    vector<vector<int>> dp(n, vector<int>(n));
    
    // Base case: single pile
    for (int i = 0; i < n; i++) dp[i][i] = piles[i];
    
    // Fill DP table
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
        }
    }
    
    return dp[0][n-1] > 0;
}

// Stone Game II
// LeetCode: 1140. Stone Game II
// https://leetcode.com/problems/stone-game-ii/
int stoneGameII(vector<int>& piles) {
    int n = piles.size();
    vector<int> suffix(n);
    suffix[n-1] = piles[n-1];
    for (int i = n-2; i >= 0; i--) {
        suffix[i] = suffix[i+1] + piles[i];
    }
    
    vector<vector<int>> memo(n, vector<int>(n+1, -1));
    
    function<int(int, int)> dp = [&](int i, int M) -> int {
        if (i >= n) return 0;
        if (memo[i][M] != -1) return memo[i][M];
        
        int maxStones = 0;
        for (int X = 1; X <= 2*M && i+X <= n; X++) {
            int opponent = dp(i+X, max(M, X));
            maxStones = max(maxStones, suffix[i] - opponent);
        }
        
        return memo[i][M] = maxStones;
    };
    
    return dp(0, 1);
}

// Nim Game
// LeetCode: 292. Nim Game
// https://leetcode.com/problems/nim-game/
bool canWinNim(int n) {
    return n % 4 != 0;
}

// Predict the Winner
// LeetCode: 486. Predict the Winner
// https://leetcode.com/problems/predict-the-winner/
bool PredictTheWinner(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n));
    
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
        }
    }
    
    return dp[0][n-1] >= 0;
}

// Minimax with Alpha-Beta Pruning
// Generic implementation for game trees
class GameState {
public:
    virtual vector<GameState*> getChildren() = 0;
    virtual int evaluate() = 0; // Positive favors maximizing player
    virtual bool isTerminal() = 0;
    virtual bool isMaximizing() = 0;
};

int minimax(GameState* state, int depth, int alpha, int beta) {
    if (depth == 0 || state->isTerminal()) {
        return state->evaluate();
    }
    
    if (state->isMaximizing()) {
        int maxEval = INT_MIN;
        for (GameState* child : state->getChildren()) {
            int eval = minimax(child, depth - 1, alpha, beta);
            maxEval = max(maxEval, eval);
            alpha = max(alpha, eval);
            if (beta <= alpha) break; // Alpha-beta pruning
        }
        return maxEval;
    } else {
        int minEval = INT_MAX;
        for (GameState* child : state->getChildren()) {
            int eval = minimax(child, depth - 1, alpha, beta);
            minEval = min(minEval, eval);
            beta = min(beta, eval);
            if (beta <= alpha) break; // Alpha-beta pruning
        }
        return minEval;
    }
}

// Tic-Tac-Toe Winner Detection
// LeetCode: 1275. Find Winner on a Tic Tac Toe Game
// https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/
string tictactoe(vector<vector<int>>& moves) {
    vector<vector<char>> board(3, vector<char>(3, ' '));
    
    for (int i = 0; i < moves.size(); i++) {
        char player = (i % 2 == 0) ? 'X' : 'O';
        int row = moves[i][0], col = moves[i][1];
        board[row][col] = player;
        
        // Check if current player wins
        bool win = true;
        // Check row
        for (int c = 0; c < 3; c++) {
            if (board[row][c] != player) { win = false; break; }
        }
        if (win) return (player == 'X') ? "A" : "B";
        
        // Check column
        win = true;
        for (int r = 0; r < 3; r++) {
            if (board[r][col] != player) { win = false; break; }
        }
        if (win) return (player == 'X') ? "A" : "B";
        
        // Check diagonal
        if (row == col) {
            win = true;
            for (int k = 0; k < 3; k++) {
                if (board[k][k] != player) { win = false; break; }
            }
            if (win) return (player == 'X') ? "A" : "B";
        }
        
        // Check anti-diagonal
        if (row + col == 2) {
            win = true;
            for (int k = 0; k < 3; k++) {
                if (board[k][2-k] != player) { win = false; break; }
            }
            if (win) return (player == 'X') ? "A" : "B";
        }
    }
    
    return (moves.size() == 9) ? "Draw" : "Pending";
}

// Can I Win
// LeetCode: 464. Can I Win
// https://leetcode.com/problems/can-i-win/
bool canIWin(int maxChoosableInteger, int desiredTotal) {
    if (maxChoosableInteger >= desiredTotal) return true;
    if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
    
    unordered_map<int, bool> memo;
    
    function<bool(int, int)> canWin = [&](int mask, int total) -> bool {
        if (memo.count(mask)) return memo[mask];
        
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (mask & (1 << i)) continue; // Already used
            
            if (total + i >= desiredTotal || !canWin(mask | (1 << i), total + i)) {
                return memo[mask] = true;
            }
        }
        
        return memo[mask] = false;
    };
    
    return canWin(0, 0);
}

// Flip Game II
// LeetCode: 294. Flip Game II
// https://leetcode.com/problems/flip-game-ii/
bool canWin(string s) {
    unordered_map<string, bool> memo;
    
    function<bool(string)> canWinHelper = [&](string state) -> bool {
        if (memo.count(state)) return memo[state];
        
        for (int i = 0; i < state.size() - 1; i++) {
            if (state[i] == '+' && state[i+1] == '+') {
                string next = state;
                next[i] = next[i+1] = '-';
                if (!canWinHelper(next)) {
                    return memo[state] = true;
                }
            }
        }
        
        return memo[state] = false;
    };
    
    return canWinHelper(s);
}

// Grundy Numbers for Nim-like Games
class NimGame {
public:
    // Calculate Grundy number for a game position
    static int grundy(int n, vector<int>& moves, vector<int>& memo) {
        if (memo[n] != -1) return memo[n];
        
        set<int> reachable;
        for (int move : moves) {
            if (n >= move) {
                reachable.insert(grundy(n - move, moves, memo));
            }
        }
        
        // Find mex (minimum excludant)
        int mex = 0;
        while (reachable.count(mex)) mex++;
        
        return memo[n] = mex;
    }
    
    // Check if position is winning
    static bool isWinning(vector<int>& piles, vector<int>& moves) {
        int n = *max_element(piles.begin(), piles.end());
        vector<int> memo(n + 1, -1);
        memo[0] = 0; // Base case
        
        int xorSum = 0;
        for (int pile : piles) {
            xorSum ^= grundy(pile, moves, memo);
        }
        
        return xorSum != 0;
    }
};

// Optimal Strategy for a Game
// Classical problem: Two players pick from ends of array
int optimalStrategyGame(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n));
    
    // Base case: single element
    for (int i = 0; i < n; i++) dp[i][i] = arr[i];
    
    // Fill table for all possible lengths
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1]);
        }
    }
    
    return dp[0][n-1];
}

// Game of Life (Cellular Automaton)
// LeetCode: 289. Game of Life
// https://leetcode.com/problems/game-of-life/
void gameOfLife(vector<vector<int>>& board) {
    int m = board.size(), n = board[0].size();
    
    auto countNeighbors = [&](int r, int c) {
        int count = 0;
        for (int i = max(0, r-1); i <= min(m-1, r+1); i++) {
            for (int j = max(0, c-1); j <= min(n-1, c+1); j++) {
                if ((i != r || j != c) && (board[i][j] & 1)) count++;
            }
        }
        return count;
    };
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int neighbors = countNeighbors(r, c);
            if (board[r][c] && (neighbors == 2 || neighbors == 3)) {
                board[r][c] |= 2; // Will be alive
            } else if (!board[r][c] && neighbors == 3) {
                board[r][c] |= 2; // Will be alive
            }
        }
    }
    
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            board[r][c] >>= 1;
        }
    }
}