每日算法 — 使用java实现贪吃蛇：蒙特卡洛树搜索与UCT决策算法

贪吃蛇是承载无数人童年记忆的经典益智游戏。传统的贪吃蛇AI通常依赖A星寻路计算最短路径，但在复杂局面下容易陷入”贪吃陷阱”——为了吃到眼前的食物而将自己逼入死胡同。本文将引入一种源自围棋AI AlphaGo的决策框架蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS），结合UCB1公式（Upper Confidence Bound）构建一棵决策树，让蛇在多步前瞻中自主评估”这条路线能活多久”，从而做出更长寿的决策。全文以Java实现，包含可直接编译运行的完整代码与复杂度分析。

一、为什么需要MCTS？A星的局限

A星算法在贪吃蛇中的核心逻辑是：计算蛇头到食物的最短曼哈顿路径，然后沿路径移动。这个策略在空旷地图上表现优异，但当蛇身逐渐填满网格时，A星给出的”最短路径”往往会让蛇头钻入由自己身体围成的封闭区域，最终无处可去。

MCTS的核心思想截然不同：它不直接求解一条确定路径，而是通过大量随机模拟来统计”在当前局面下走某一步后，最终能存活多少步/获得多少分”。得分最高的动作被选为当前步的决策。这种基于统计的决策方式天然具有”前瞻性”，能规避很多局部最优陷阱。

二、MCTS的四步循环

MCTS算法围绕一棵不断生长的搜索树进行，每次决策包含四个阶段，循环执行直到计算预算耗尽：

2.1 选择（Selection）

从根节点（当前游戏状态）出发，递归选择子节点，直到到达一个”未完全扩展”的节点。节点选择依据UCT公式：

$$\text{UCT} = \frac{w_i}{n_i} + C \cdot \sqrt{\frac{\ln N}{n_i}}$$

其中：
– $w_i$：第 $i$ 个子节点的累计奖励值
– $n_i$：第 $i$ 个子节点的访问次数
– $N$：父节点的总访问次数
– $C$：探索常数，通常取 $\sqrt{2}$

UCT公式的前半部分是利用项（exploitation），倾向于选择胜率高的节点；后半部分是探索项（exploration），保证访问次数少的节点也有机会被选中，避免过早陷入局部最优。

2.2 扩展（Expansion）

当选择阶段抵达一个尚未穷举所有合法动作的节点时，为其创建一个新的子节点，对应一个尚未被探索的动作。

2.3 模拟（Simulation / Rollout）

从新扩展的节点出发，不再使用UCT选择，而是以随机策略（或简单的启发式策略）快速走完整局游戏，直到蛇死亡。记录本局游戏的最终得分（通常用存活步数或吃到的食物数量衡量）。

2.4 反向传播（Backpropagation）

将模拟得到的奖励值，沿着从扩展节点到根节点的路径逐层回传，更新路径上每个节点的 $w_i$ 和 $n_i$。

三、Java核心实现

3.1 游戏状态建模

import java.util.*;

/**
 * 贪吃蛇游戏状态
 * 包含蛇身、食物、地图大小，以及动作执行与胜负判定
 */
public class GameState {
    // 地图尺寸
    public final int width;
    public final int height;

    // 蛇身：头部在列表末尾，尾部在列表开头
    public final LinkedList<int[]> snake;

    // 食物位置
    public int[] food;

    // 已存活步数（用于奖励计算）
    public int stepsAlive;

    // 自上次吃食物以来经过的步数（用于检测死循环）
    public int stepsSinceLastFood;

    // 四个方向：上、下、左、右
    public static final int[][] DIRECTIONS = {
        {0, -1}, {0, 1}, {-1, 0}, {1, 0}
    };

    public GameState(int width, int height) {
        this.width = width;
        this.height = height;
        this.snake = new LinkedList<>();
        // 初始蛇位于地图中央，长度为1
        int startX = width / 2;
        int startY = height / 2;
        this.snake.add(new int[]{startX, startY});
        this.stepsAlive = 0;
        this.stepsSinceLastFood = 0;
        spawnFood();
    }

    // 私有构造方法，用于生成子状态
    private GameState(int width, int height, LinkedList<int[]> snake, 
                      int[] food, int stepsAlive, int stepsSinceLastFood) {
        this.width = width;
        this.height = height;
        this.snake = new LinkedList<>();
        for (int[] p : snake) {
            this.snake.add(new int[]{p[0], p[1]});
        }
        this.food = new int[]{food[0], food[1]};
        this.stepsAlive = stepsAlive;
        this.stepsSinceLastFood = stepsSinceLastFood;
    }

    /**
     * 随机生成食物，确保不与蛇身重叠
     */
    private void spawnFood() {
        Random rand = new Random();
        boolean valid;
        do {
            valid = true;
            int fx = rand.nextInt(width);
            int fy = rand.nextInt(height);
            for (int[] p : snake) {
                if (p[0] == fx && p[1] == fy) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                food = new int[]{fx, fy};
            }
        } while (!valid);
    }

    /**
     * 执行一个方向动作，返回新的游戏状态（深拷贝）
     * @param dirIndex 方向索引 0=上 1=下 2=左 3=右
     * @return 新状态，若动作导致死亡则返回null
     */
    public GameState applyAction(int dirIndex) {
        int[] head = snake.getLast();
        int nx = head[0] + DIRECTIONS[dirIndex][0];
        int ny = head[1] + DIRECTIONS[dirIndex][1];

        // 边界检测
        if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
            return null; // 撞墙死亡
        }

        // 自身碰撞检测（尾部即将移动，所以头部进入原尾部位置不算碰撞）
        boolean willEat = (nx == food[0] && ny == food[1]);
        for (int i = 0; i < snake.size() - (willEat ? 0 : 1); i++) {
            int[] p = snake.get(i);
            if (p[0] == nx && p[1] == ny) {
                return null; // 撞到自己的身体
            }
        }

        // 创建新状态
        GameState next = new GameState(width, height, snake, food, 
                                       stepsAlive + 1, stepsSinceLastFood + 1);
        next.snake.add(new int[]{nx, ny});

        if (willEat) {
            // 吃到食物，长度增加，重置饥饿计数器
            next.stepsSinceLastFood = 0;
            next.spawnFood();
        } else {
            // 未吃到食物，移除尾部
            next.snake.removeFirst();
        }

        // 饥饿保护：如果太久没吃到食物，判定死亡（避免无限绕圈）
        if (next.stepsSinceLastFood > width * height * 2) {
            return null;
        }

        return next;
    }

    /**
     * 判断游戏是否结束
     */
    public boolean isTerminal() {
        // 由applyAction返回null表示结束，这里仅作补充
        return false;
    }

    /**
     * 获取当前状态下所有合法动作
     */
    public List<Integer> getLegalActions() {
        List<Integer> actions = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            if (applyAction(i) != null) {
                actions.add(i);
            }
        }
        return actions;
    }

    /**
     * 计算奖励值：存活步数 + 长度 * 100
     */
    public double getReward() {
        return stepsAlive + snake.size() * 100.0;
    }
}

3.2 MCTS节点

/**
 * MCTS树节点
 * 每个节点对应一个游戏状态，以及到达该状态所采取的动作
 */
public class MCTSNode {
    // 父节点
    public MCTSNode parent;

    // 到达此节点所执行的动作（根节点为-1）
    public int action;

    // 当前节点对应的游戏状态
    public GameState state;

    // 子节点列表
    public List<MCTSNode> children;

    // 访问次数
    public int visits;

    // 累计奖励值
    public double totalReward;

    // 尚未扩展的合法动作
    public List<Integer> untriedActions;

    // UCT探索常数
    public static final double C = Math.sqrt(2);

    public MCTSNode(GameState state, int action, MCTSNode parent) {
        this.state = state;
        this.action = action;
        this.parent = parent;
        this.children = new ArrayList<>();
        this.visits = 0;
        this.totalReward = 0.0;
        this.untriedActions = state.getLegalActions();
    }

    /**
     * 使用UCT公式选择最优子节点
     */
    public MCTSNode selectChild() {
        MCTSNode best = null;
        double bestValue = Double.NEGATIVE_INFINITY;

        for (MCTSNode child : children) {
            // UCT = 平均奖励 + C * sqrt(ln(父访问次数) / 子访问次数)
            double exploitation = child.totalReward / child.visits;
            double exploration = C * Math.sqrt(Math.log(this.visits) / child.visits);
            double uctValue = exploitation + exploration;

            if (uctValue > bestValue) {
                bestValue = uctValue;
                best = child;
            }
        }
        return best;
    }

    /**
     * 判断是否完全扩展（所有合法动作都已有对应子节点）
     */
    public boolean isFullyExpanded() {
        return untriedActions.isEmpty();
    }

    /**
     * 扩展一个未尝试的动作，创建新子节点
     */
    public MCTSNode expand() {
        int action = untriedActions.remove(untriedActions.size() - 1);
        GameState nextState = state.applyAction(action);
        if (nextState == null) {
            return null; // 理论上不应发生，因为untriedActions已过滤非法动作
        }
        MCTSNode child = new MCTSNode(nextState, action, this);
        children.add(child);
        return child;
    }

    /**
     * 更新节点的统计信息
     */
    public void update(double reward) {
        this.visits++;
        this.totalReward += reward;
    }
}

3.3 MCTS核心算法

import java.util.*;

/**
 * 贪吃蛇MCTS决策引擎
 */
public class SnakeMCTS {

    private final Random random = new Random();

    /**
     * 根据当前状态，运行MCTS算法返回最优动作
     * @param rootState 当前游戏状态
     * @param iterations 模拟迭代次数（预算）
     * @return 最优动作方向索引
     */
    public int search(GameState rootState, int iterations) {
        MCTSNode root = new MCTSNode(rootState, -1, null);

        for (int i = 0; i < iterations; i++) {
            MCTSNode node = root;

            // ---- 1. 选择（Selection）----
            // 从根节点出发，递归选择UCT值最大的子节点，直到叶子节点
            while (node.isFullyExpanded() && !node.children.isEmpty()) {
                node = node.selectChild();
            }

            // ---- 2. 扩展（Expansion）----
            // 如果当前节点还有未尝试的动作，则扩展一个新子节点
            if (!node.isFullyExpanded()) {
                MCTSNode expanded = node.expand();
                if (expanded != null) {
                    node = expanded;
                }
            }

            // ---- 3. 模拟（Simulation / Rollout）----
            // 从当前节点状态开始，随机走子直到游戏结束
            double reward = rollout(node.state);

            // ---- 4. 反向传播（Backpropagation）----
            // 将奖励沿路径回传，更新所有祖先节点
            while (node != null) {
                node.update(reward);
                node = node.parent;
            }
        }

        // 返回访问次数最多的子节点对应的动作（最稳健的选择）
        MCTSNode bestChild = null;
        int bestVisits = -1;
        for (MCTSNode child : root.children) {
            if (child.visits > bestVisits) {
                bestVisits = child.visits;
                bestChild = child;
            }
        }

        return bestChild != null ? bestChild.action : 0;
    }

    /**
     * 随机模拟（Rollout）
     * 从给定状态开始，采用完全随机策略走完整局，返回最终奖励
     */
    private double rollout(GameState state) {
        GameState simState = deepCopy(state);

        // 设定最大模拟步数，防止无限循环
        int maxSteps = simState.width * simState.height * 3;

        for (int step = 0; step < maxSteps; step++) {
            List<Integer> actions = simState.getLegalActions();
            if (actions.isEmpty()) {
                break; // 无路可走，游戏结束
            }

            // 完全随机选择动作
            int action = actions.get(random.nextInt(actions.size()));
            GameState next = simState.applyAction(action);
            if (next == null) {
                break; // 死亡
            }
            simState = next;
        }

        return simState.getReward();
    }

    /**
     * 深拷贝游戏状态（用于模拟，不影响真实游戏）
     */
    private GameState deepCopy(GameState original) {
        // 利用GameState的私有构造方法逻辑，这里通过applyAction链重建
        // 为简化，直接在GameState中添加clone方法更佳
        // 这里使用序列化思路的简化版：手动复制
        return original.cloneState();
    }
}

3.4 完善GameState的克隆方法

为了让上述代码能够完整编译运行，需要在 GameState 类中补充 cloneState 方法：

    /**
     * 深度克隆当前游戏状态
     */
    public GameState cloneState() {
        GameState copy = new GameState(width, height, snake, food, 
                                       stepsAlive, stepsSinceLastFood);
        return copy;
    }

将之前 GameState 中 private 的构造方法改为 public 或在同一个包内访问即可。

3.5 主程序与游戏循环

/**
 * 贪吃蛇MCTS主程序
 * 纯命令行运行，可观察AI自动进行游戏
 */
public class SnakeGameMCTS {

    public static void main(String[] args) {
        // 地图尺寸
        int width = 10;
        int height = 10;

        // MCTS迭代次数：越大AI越强，但决策越慢
        int iterations = 2000;

        GameState state = new GameState(width, height);
        SnakeMCTS mcts = new SnakeMCTS();

        System.out.println("=== 贪吃蛇 MCTS AI ===");
        System.out.println("地图大小: " + width + "x" + height);
        System.out.println("MCTS迭代次数: " + iterations);
        System.out.println();

        while (true) {
            printBoard(state);

            List<Integer> actions = state.getLegalActions();
            if (actions.isEmpty()) {
                System.out.println("\n游戏结束！最终得分: " + state.getReward());
                System.out.println("存活步数: " + state.stepsAlive);
                System.out.println("蛇身长度: " + state.snake.size());
                break;
            }

            // MCTS决策
            int bestAction = mcts.search(state, iterations);

            String[] dirNames = {"上", "下", "左", "右"};
            System.out.println("AI决策: " + dirNames[bestAction] + "\n");

            GameState next = state.applyAction(bestAction);
            if (next == null) {
                System.out.println("\n游戏结束！最终得分: " + state.getReward());
                break;
            }
            state = next;

            // 为便于观察，每步暂停一小段时间
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

    /**
     * 打印当前游戏面板到控制台
     */
    private static void printBoard(GameState state) {
        char[][] board = new char[state.height][state.width];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }

        // 绘制食物
        board[state.food[1]][state.food[0]] = '*';

        // 绘制蛇身
        for (int i = 0; i < state.snake.size(); i++) {
            int[] p = state.snake.get(i);
            if (i == state.snake.size() - 1) {
                board[p[1]][p[0]] = 'H'; // 头部
            } else {
                board[p[1]][p[0]] = 'o'; // 身体
            }
        }

        System.out.println("步数: " + state.stepsAlive + " | 长度: " + state.snake.size());
        for (char[] row : board) {
            for (char c : row) {
                System.out.print(c + " ");
            }
            System.out.println();
        }
    }
}

四、模拟策略的优化空间

上述实现中的 rollout 采用完全随机策略，这是MCTS最基础的版本。在实际应用中，可以通过以下方式提升AI强度：

1. 引入启发式rollout：模拟阶段优先选择朝向食物的方向，或避开狭窄空间，让单次模拟的质量更高。
2. 结合A星进行混合决策：在模拟阶段用A星寻找食物路径，仅在A星无路可走时随机探索。
3. RAVE（Rapid Action Value Estimation）：跨兄弟节点共享动作价值信息，加速收敛。
4. 渐进式扩展（Progressive Widening）：在节点访问次数较低时只扩展部分动作，避免早期过度分散搜索资源。

五、时间复杂度分析

空间复杂度为 $O(K \cdot D)$，即迭代过程中创建的节点总数乘以节点大小。由于MCTS只保留一棵树，不存储所有模拟轨迹，内存开销可控。

六、总结

本文以Java完整实现了基于蒙特卡洛树搜索的贪吃蛇AI。与A星寻路不同，MCTS不追求”到食物的最短路径”，而是通过统计大量随机模拟的结果，在多步前瞻中寻找”最可能活得久”的动作。UCT公式在”利用已知好策略”与”探索未知新策略”之间取得了数学上的最优平衡。

读者可以动手调整两个关键参数来观察AI行为变化：
– 迭代次数 iterations：从500提升到10000，AI的存活时间通常会显著增长。
– 探索常数 C：增大C会让AI更愿意探索冷门路线，减小C则会让AI更保守地坚持当前最优路线。

通过这种统计驱动的决策框架，即使是看似简单的贪吃蛇，也能展现出令人惊讶的策略深度。