博弈论算法为何能用数学公式预测胜负从Nim博弈到极大极小算法的完整LeetCode通关指南

class Solution {
    public boolean canWinNim(int n) {
        // 如果石子数是4的倍数，先手必败
        // 否则先手可以取走 n % 4 颗，留给对手4的倍数
        return n % 4 != 0;
    }
}

public int minimax(int depth, boolean isMaximizingPlayer) {
    // 终止条件：达到最大深度或游戏结束
    if (depth == 0 || isGameOver()) {
        return evaluate();
    }
    
    if (isMaximizingPlayer) {
        int maxEval = Integer.MIN_VALUE;
        for (Move move : getAllPossibleMoves()) {
            makeMove(move);
            int eval = minimax(depth - 1, false);
            undoMove(move);
            maxEval = Math.max(maxEval, eval);
        }
        return maxEval;
    } else {
        int minEval = Integer.MAX_VALUE;
        for (Move move : getAllPossibleMoves()) {
            makeMove(move);
            int eval = minimax(depth - 1, true);
            undoMove(move);
            minEval = Math.min(minEval, eval);
        }
        return minEval;
    }
}

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int n = nums.length;
        // dp[i][j] 表示在区间 [i, j] 内先手能获得的最大分数差
        int[][] dp = new int[n][n];
        
        // 基本情况：只有一个数时，先手直接取走
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
        }
        
        // 区间DP：从小区间扩展到大区间
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                // 先手取左端：获得 nums[i]，然后对手在 [i+1, j] 上先手
                // 先手取右端：获得 nums[j]，然后对手在 [i, j-1] 上先手
                // 对手会最大化自己的收益，相当于最小化当前玩家的收益
                dp[i][j] = Math.max(
                    nums[i] - dp[i + 1][j],
                    nums[j] - dp[i][j - 1]
                );
            }
        }
        
        // 先手能获得非负的分数差则获胜
        return dp[0][n - 1] >= 0;
    }
}

public int alphabeta(int depth, int alpha, int beta, boolean isMaximizingPlayer) {
    if (depth == 0 || isGameOver()) {
        return evaluate();
    }
    
    if (isMaximizingPlayer) {
        int maxEval = Integer.MIN_VALUE;
        for (Move move : getAllPossibleMoves()) {
            makeMove(move);
            int eval = alphabeta(depth - 1, alpha, beta, false);
            undoMove(move);
            maxEval = Math.max(maxEval, eval);
            alpha = Math.max(alpha, eval);
            if (beta <= alpha) {
                break;  // 剪枝：MIN玩家不会选择这条路径
            }
        }
        return maxEval;
    } else {
        int minEval = Integer.MAX_VALUE;
        for (Move move : getAllPossibleMoves()) {
            makeMove(move);
            int eval = alphabeta(depth - 1, alpha, beta, true);
            undoMove(move);
            minEval = Math.min(minEval, eval);
            beta = Math.min(beta, eval);
            if (beta <= alpha) {
                break;  // 剪枝：MAX玩家不会选择这条路径
            }
        }
        return minEval;
    }
}

class Solution {
    public boolean stoneGame(int[] piles) {
        // 数学结论：先手总是必胜
        // 因为Alice可以预先选择所有偶数位置或所有奇数位置
        // 两种方案的总和必有一个大于对方
        return true;
    }
}

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(
                    piles[i] - dp[i + 1][j],
                    piles[j] - dp[i][j - 1]
                );
            }
        }
        
        return dp[0][n - 1] > 0;
    }
}

class Solution {
    private int[] prefixSum;
    private Integer[][] memo;
    private int n;
    
    public int stoneGameII(int[] piles) {
        n = piles.length;
        prefixSum = new int[n + 1];
        memo = new Integer[n][n + 1];
        
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + piles[i];
        }
        
        return dfs(0, 1);
    }
    
    private int dfs(int i, int m) {
        // 如果能取走所有剩余石子，直接取走
        if (m * 2 >= n - i) {
            return prefixSum[n] - prefixSum[i];
        }
        
        if (memo[i][m] != null) {
            return memo[i][m];
        }
        
        int result = 0;
        for (int x = 1; x <= 2 * m; x++) {
            // 当前玩家取走前x堆，获得这些石子
            // 对手在剩余石子上的最优收益通过递归计算
            // 当前玩家的总收益 = 取走的石子 + 剩余石子 - 对手的收益
            int currentGain = prefixSum[i + x] - prefixSum[i];
            int remainingStones = prefixSum[n] - prefixSum[i + x];
            int opponentGain = dfs(i + x, Math.max(m, x));
            result = Math.max(result, currentGain + remainingStones - opponentGain);
        }
        
        memo[i][m] = result;
        return result;
    }
}

class Solution {
    public boolean winnerSquareGame(int n) {
        // dp[i] = true 表示剩余 i 颗石子时当前玩家必胜
        boolean[] dp = new boolean[n + 1];
        
        for (int i = 1; i <= n; i++) {
            // 尝试所有可能的完全平方数
            for (int k = 1; k * k <= i; k++) {
                // 如果存在一种取法使得对手必败，则当前玩家必胜
                if (!dp[i - k * k]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}