每日算法 — 使用java实现Chomp：组合博弈论必败态策略分析

引言

Chomp（巧克力游戏）是组合博弈论中的经典两人游戏：一块 m×n 的巧克力棋盘，左上角格子有毒。两名玩家轮流选择一块巧克力格子 (i,j)，吃掉该格子及其右下方所有格子。被迫吃掉毒格子的玩家输掉游戏。

本文将用 Java 实现 Chomp 游戏及其 AI 求解器，核心算法基于Sprague-Grundy 理论与必败态（P-position）分析，揭示这个看似简单却蕴含深刻数学的游戏。

问题建模

游戏状态

用单调不增序列表示棋盘边界：

状态 = [h0, h1, ..., hn-1]

其中 hi 表示第 i 列剩余的高度（从底部算起），且 h0 ≥ h1 ≥ … ≥ hn-1。

游戏规则

选择第 i 列并减少到高度 h’（0 ≤ h’ < hi，且保持单调性），即更新 hi = h’ 并确保 hi ≥ hi+1。

关键性质

定理：在 m×n 的 Chomp 游戏中，先手必胜（除了 1×1 的平凡情况）。

证明思路：假设后手有必胜策略，先手可以第一步吃掉右下角 (m-1, n-1) 成为”伪后手”，如果这是必胜策略则矛盾；如果不是，则原后手的必胜策略不存在。这个策略窃取论证证明了先手必胜，但没有给出具体必胜策略。

核心算法：Sprague-Grundy 数 + 记忆化搜索

对于小棋盘，可以计算每个状态的 Grundy 数：
– Grundy(终止态) = 0
– Grundy(状态) = mex{ Grundy(所有后继状态) }

其中 mex（最小排斥值）是不在集合中的最小非负整数。

完整 Java 实现

import java.util.*;

/**
 * Chomp（巧克力游戏）求解器
 * 基于Sprague-Grundy理论的组合博弈分析
 */
public class ChompSolver {

    // 记忆化Grundy数：状态->Grundy值
    private final Map<String, Integer> grundyCache;
    // 记忆化最优移动
    private final Map<String, Move> bestMoveCache;

    public ChompSolver() {
        this.grundyCache = new HashMap<>();
        this.bestMoveCache = new HashMap<>();
    }

    /**
     * 游戏状态类
     * 用单调不增序列表示每列高度
     */
    static class State {
        final int[] heights;
        final int rows; // 最大行数（用于显示）

        State(int[] heights, int rows) {
            this.heights = heights.clone();
            this.rows = rows;
            // 确保单调性
            for (int i = 1; i < this.heights.length; i++) {
                if (this.heights[i] > this.heights[i - 1]) {
                    throw new IllegalArgumentException("高度必须单调不增");
                }
            }
        }

        /**
         * 从棋盘尺寸创建初始状态
         */
        static State createInitial(int rows, int cols) {
            int[] heights = new int[cols];
            Arrays.fill(heights, rows);
            return new State(heights, rows);
        }

        /**
         * 生成所有合法后继状态
         * 选择第col列，将其高度减少为newHeight
         */
        List<State> getSuccessors() {
            List<State> successors = new ArrayList<>();
            int cols = heights.length;

            for (int col = 0; col < cols; col++) {
                if (heights[col] == 0) continue;

                // 可以尝试将该列减少到 0 ~ heights[col]-1
                // 但要保持单调性：heights[col] >= heights[col+1]
                int maxNewHeight = heights[col] - 1;
                int minNewHeight = (col + 1 < cols) ? heights[col + 1] : 0;

                for (int newHeight = minNewHeight; newHeight <= maxNewHeight; newHeight++) {
                    int[] newHeights = heights.clone();
                    newHeights[col] = newHeight;
                    successors.add(new State(newHeights, rows));
                }
            }

            return successors;
        }

        /**
         * 检查是否为终止状态（只剩毒格子）
         */
        boolean isTerminal() {
            return heights[0] == 0;
        }

        /**
         * 执行移动，返回新状态
         */
        State applyMove(Move move) {
            int[] newHeights = heights.clone();
            newHeights[move.col] = move.newHeight;
            // 确保右侧列不超过当前列
            for (int i = move.col + 1; i < newHeights.length; i++) {
                if (newHeights[i] > newHeights[i - 1]) {
                    newHeights[i] = newHeights[i - 1];
                }
            }
            return new State(newHeights, rows);
        }

        String key() {
            return Arrays.toString(heights);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof State)) return false;
            State state = (State) o;
            return Arrays.equals(heights, state.heights);
        }

        @Override
        public int hashCode() {
            return Arrays.hashCode(heights);
        }

        /**
         * 打印棋盘状态
         */
        void printBoard() {
            System.out.println("棋盘状态 (" + rows + "x" + heights.length + "):");
            for (int r = rows - 1; r >= 0; r--) {
                for (int c = 0; c < heights.length; c++) {
                    if (r == rows - 1 && c == 0) {
                        System.out.print("☠ "); // 毒格子
                    } else if (r < heights[c]) {
                        System.out.print("■ "); // 巧克力
                    } else {
                        System.out.print("· "); // 已吃掉
                    }
                }
                System.out.println();
            }
            System.out.println("高度: " + Arrays.toString(heights));
        }
    }

    /**
     * 移动类
     */
    static class Move {
        final int col;      // 选择的列
        final int newHeight; // 新高度

        Move(int col, int newHeight) {
            this.col = col;
            this.newHeight = newHeight;
        }

        @Override
        public String toString() {
            return String.format("将第%d列高度改为%d", col, newHeight);
        }
    }

    /**
     * 计算状态的Sprague-Grundy数
     * 使用记忆化搜索
     * 时间复杂度: O(状态数 × 合法移动数)
     */
    public int computeGrundy(State state) {
        String key = state.key();

        if (grundyCache.containsKey(key)) {
            return grundyCache.get(key);
        }

        if (state.isTerminal()) {
            grundyCache.put(key, 0);
            return 0;
        }

        // 计算所有后继状态的Grundy数
        Set<Integer> reachable = new HashSet<>();
        for (State succ : state.getSuccessors()) {
            reachable.add(computeGrundy(succ));
        }

        // mex = 最小排斥值
        int grundy = 0;
        while (reachable.contains(grundy)) {
            grundy++;
        }

        grundyCache.put(key, grundy);
        return grundy;
    }

    /**
     * 查找最优移动（移动到Grundy数为0的状态）
     */
    public Move findBestMove(State state) {
        String key = state.key();

        if (bestMoveCache.containsKey(key)) {
            return bestMoveCache.get(key);
        }

        int currentGrundy = computeGrundy(state);

        if (currentGrundy == 0) {
            // 当前是P-position（必败态），没有必胜移动
            // 随机选择一个移动
            List<State> succs = state.getSuccessors();
            if (succs.isEmpty()) return null;
            State randomSucc = succs.get(0);
            // 重建移动
            Move move = reconstructMove(state, randomSucc);
            bestMoveCache.put(key, move);
            return move;
        }

        // 寻找使后继状态Grundy数为0的移动
        for (State succ : state.getSuccessors()) {
            if (computeGrundy(succ) == 0) {
                Move move = reconstructMove(state, succ);
                bestMoveCache.put(key, move);
                return move;
            }
        }

        return null;
    }

    /**
     * 从前后状态重建移动
     */
    private Move reconstructMove(State from, State to) {
        for (int i = 0; i < from.heights.length; i++) {
            if (from.heights[i] != to.heights[i]) {
                return new Move(i, to.heights[i]);
            }
        }
        return null;
    }

    /**
     * 判断是否为P-position（前一个玩家获胜，即当前玩家必败）
     */
    public boolean isPPosition(State state) {
        return computeGrundy(state) == 0;
    }

    /**
     * 判断是否为N-position（下一个玩家获胜，即当前玩家必胜）
     */
    public boolean isNPosition(State state) {
        return computeGrundy(state) != 0;
    }

    /**
     * 运行一局完整游戏（AI vs AI 或 AI vs 人类）
     */
    public void playGame(int rows, int cols, boolean aiVsAi) {
        State state = State.createInitial(rows, cols);
        Scanner scanner = aiVsAi ? null : new Scanner(System.in);
        int player = 1;

        System.out.println("=== Chomp 游戏开始 ===");
        System.out.println("规则：选择一块巧克力，吃掉该格子及其右下方所有格子");
        System.out.println("被迫吃掉毒格子(☠)的玩家输！\n");

        while (!state.isTerminal()) {
            state.printBoard();
            System.out.println("\n玩家 " + player + " 的回合");
            System.out.println("Grundy数: " + computeGrundy(state));
            System.out.println("当前状态: " + (isPPosition(state) ? "P-position（必败）" : "N-position（必胜）"));

            Move move;
            if (aiVsAi || player == 1) {
                move = findBestMove(state);
                if (move == null) {
                    // 没有必胜移动，随便走一步
                    List<State> succs = state.getSuccessors();
                    move = reconstructMove(state, succs.get(0));
                }
                System.out.println("AI选择: " + move);
            } else {
                System.out.print("输入列号和高度（如: 1 2）: ");
                int col = scanner.nextInt();
                int h = scanner.nextInt();
                move = new Move(col, h);
            }

            state = state.applyMove(move);
            player = 3 - player; // 切换玩家 (1->2, 2->1)
        }

        state.printBoard();
        System.out.println("\n游戏结束！玩家 " + player + " 被迫吃掉毒格子，输了！");
        System.out.println("玩家 " + (3 - player) + " 获胜！");
    }

    /**
     * 预计算并输出所有小棋盘的Grundy数
     */
    public void precomputeSmallBoards(int maxRows, int maxCols) {
        System.out.println("=== 预计算小棋盘Grundy数 ===");

        for (int r = 1; r <= maxRows; r++) {
            for (int c = 1; c <= maxCols; c++) {
                State state = State.createInitial(r, c);
                int g = computeGrundy(state);
                String type = (g == 0) ? "P" : "N";
                System.out.printf("%dx%d: Grundy=%d (%s-position)%n", r, c, g, type);
            }
        }
    }

    /**
     * 分析特定棋盘的获胜策略
     */
    public void analyzeBoard(int rows, int cols) {
        State state = State.createInitial(rows, cols);
        System.out.println("\n=== " + rows + "x" + cols + " 棋盘分析 ===");
        state.printBoard();

        int g = computeGrundy(state);
        System.out.println("Grundy数: " + g);
        System.out.println("先手: " + (g != 0 ? "必胜" : "必败"));

        if (g != 0) {
            Move best = findBestMove(state);
            System.out.println("必胜首步: " + best);

            // 展示走法后的状态
            State after = state.applyMove(best);
            System.out.println("\n走法后状态:");
            after.printBoard();
            System.out.println("对手面对Grundy=0的必败态");
        }
    }

    public static void main(String[] args) {
        ChompSolver solver = new ChompSolver();

        // 预计算小棋盘
        solver.precomputeSmallBoards(4, 4);

        // 分析常见棋盘
        solver.analyzeBoard(2, 3);
        solver.analyzeBoard(3, 3);
        solver.analyzeBoard(3, 5);

        // 运行AI对战
        System.out.println("\n=== AI 自我对弈 (3x4) ===");
        solver.playGame(3, 4, true);

        System.out.println("\n缓存状态数: " + solver.grundyCache.size());
    }
}

算法解析

Sprague-Grundy 定理

对于无偏组合游戏（双方可选移动相同），每个状态等价于一个 Nim 堆，其大小由 Grundy 数定义：
– G(终止态) = 0
– G(状态) = mex{ G(所有后继状态) }

状态为 P-position（Previous player wins，前一个玩家获胜）当且仅当 G = 0。
状态为 N-position（Next player wins，下一个玩家获胜）当且仅当 G > 0。

Chomp 的特殊性

Chomp 满足策略窃取论证：先手必胜。但对于非 2×n 的棋盘，没有已知的多项式时间必胜策略。小棋盘可以通过穷举计算，大棋盘目前仍是开放问题。

记忆化的威力

由于 Chomp 状态空间是组合数的，3×5 棋盘就有数百个可达状态。记忆化将指数时间降为线性（相对于状态数）。

复杂度分析

扩展思考

1. 偏序集游戏：Chomp 是偏序集游戏的特例，任何有限偏序集都可以定义类似游戏。
2. 三维 Chomp：m×n×p 的立方体 Chomp，状态空间爆炸更快。
3. 近似策略：对大棋盘，使用蒙特卡洛树搜索（MCTS）寻找近似最优解。

总结

Chomp 是组合博弈论的入门宝石：规则极简却蕴含深刻的数学结构。Sprague-Grundy 理论为分析这类游戏提供了通用框架，而策略窃取论证则展示了存在性证明的优雅。掌握这些工具，可以分析绝大多数无偏组合游戏。