每日算法 — 使用java实现贪吃蛇：MCTS蒙特卡洛树搜索与UCT探索利用均衡

可莉爸爸 AI算法

引言

贪吃蛇是一款经典的街机游戏，玩家控制蛇在网格中移动并吃掉食物。本文将使用Java实现一个基于蒙特卡洛树搜索（MCTS）的贪吃蛇AI，通过UCT（Upper Confidence Bound applied to Trees）公式在探索未知路径与利用已知优势之间取得平衡，让蛇在复杂局面下做出长远决策。

算法核心思想

蒙特卡洛树搜索四阶段

MCTS通过迭代执行以下四个阶段来构建搜索树：

  1. 选择（Selection）：从根节点出发，使用UCT公式选择子节点，直到到达未完全展开的节点
  2. 扩展（Expansion）：为选中的节点添加一个或多个子节点
  3. 模拟（Simulation）：从新节点出发进行随机模拟（ rollout ）直到游戏结束
  4. 回溯（Backpropagation）：将模拟结果反向传播，更新路径上所有节点的统计值

UCT公式

$$UCT = \frac{w_i}{n_i} + c \sqrt{\frac{\ln N}{n_i}}$$

其中 $w_i$ 是胜利次数，$n_i$ 是访问次数，$N$ 是父节点访问次数，$c$ 是探索常数。

Java实现

核心数据结构

import java.util.*;

public class MCTSSnakeAI {
    // 方向定义：上、右、下、左
    private static final int[][] DIRS = {{-1,0}, {0,1}, {1,0}, {0,-1}};
    private static final int GRID_SIZE = 10;
    private static final double EXPLORATION_CONSTANT = 1.414;

    // 游戏状态
    static class GameState {
        Set<String> snakeBody = new LinkedHashSet<>(); // 保持顺序
        int headRow, headCol;
        int foodRow, foodCol;
        int score;
        boolean gameOver;

        GameState() {
            snakeBody.add("5,5");
            headRow = 5; headCol = 5;
            spawnFood();
            score = 0;
        }

        GameState(GameState other) {
            this.snakeBody = new LinkedHashSet<>(other.snakeBody);
            this.headRow = other.headRow;
            this.headCol = other.headCol;
            this.foodRow = other.foodRow;
            this.foodCol = other.foodCol;
            this.score = other.score;
            this.gameOver = other.gameOver;
        }

        void spawnFood() {
            Random rand = new Random();
            do {
                foodRow = rand.nextInt(GRID_SIZE);
                foodCol = rand.nextInt(GRID_SIZE);
            } while (snakeBody.contains(foodRow + "," + foodCol));
        }

        boolean isValid(int r, int c) {
            return r >= 0 && r < GRID_SIZE && c >= 0 && c < GRID_SIZE 
                && !snakeBody.contains(r + "," + c);
        }

        // 执行动作，返回是否吃到食物
        boolean step(int dirIdx) {
            if (gameOver) return false;
            int nr = headRow + DIRS[dirIdx][0];
            int nc = headCol + DIRS[dirIdx][1];

            if (!isValid(nr, nc)) {
                gameOver = true;
                return false;
            }

            String newPos = nr + "," + nc;
            snakeBody.add(newPos);
            headRow = nr; headCol = nc;

            boolean ate = (nr == foodRow && nc == foodCol);
            if (!ate) {
                // 移除尾部
                Iterator<String> it = snakeBody.iterator();
                it.next();
                it.remove();
            } else {
                score += 10;
                spawnFood();
            }
            return ate;
        }

        List<Integer> getLegalActions() {
            List<Integer> acts = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                int nr = headRow + DIRS[i][0];
                int nc = headCol + DIRS[i][1];
                if (nr >= 0 && nr < GRID_SIZE && nc >= 0 && nc < GRID_SIZE 
                    && !snakeBody.contains(nr + "," + nc)) {
                    acts.add(i);
                }
            }
            return acts;
        }
    }

    // MCTS节点
    static class MCTSNode {
        GameState state;
        MCTSNode parent;
        Map<Integer, MCTSNode> children = new HashMap<>();
        int visits = 0;
        double totalReward = 0;
        int action; // 到达该节点的动作
        List<Integer> untriedActions;

        MCTSNode(GameState state, MCTSNode parent, int action) {
            this.state = new GameState(state);
            this.parent = parent;
            this.action = action;
            this.untriedActions = state.getLegalActions();
        }

        boolean isFullyExpanded() {
            return untriedActions.isEmpty();
        }

        double uctValue() {
            if (visits == 0) return Double.MAX_VALUE;
            double exploitation = totalReward / visits;
            double exploration = EXPLORATION_CONSTANT * Math.sqrt(Math.log(parent.visits) / visits);
            return exploitation + exploration;
        }

        MCTSNode bestChild() {
            MCTSNode best = null;
            double bestVal = -Double.MAX_VALUE;
            for (MCTSNode child : children.values()) {
                double val = child.uctValue();
                if (val > bestVal) {
                    bestVal = val;
                    best = child;
                }
            }
            return best;
        }
    }
}

MCTS搜索主逻辑

    /**
     * 执行MCTS搜索，返回最优动作
     */
    public int search(GameState rootState, int iterations) {
        MCTSNode root = new MCTSNode(rootState, null, -1);

        for (int i = 0; i < iterations; i++) {
            // 阶段1&2：选择与扩展
            MCTSNode node = treePolicy(root);
            // 阶段3：模拟
            double reward = defaultPolicy(node.state);
            // 阶段4：回溯
            backup(node, reward);
        }

        // 选择访问次数最多的动作（更稳健）
        int bestAction = -1;
        int maxVisits = -1;
        for (Map.Entry<Integer, MCTSNode> e : root.children.entrySet()) {
            if (e.getValue().visits > maxVisits) {
                maxVisits = e.getValue().visits;
                bestAction = e.getKey();
            }
        }
        return bestAction;
    }

    /**
     * 树策略：选择+扩展
     */
    private MCTSNode treePolicy(MCTSNode node) {
        while (!node.state.gameOver) {
            if (!node.isFullyExpanded()) {
                return expand(node);
            } else if (node.children.isEmpty()) {
                break;
            } else {
                node = node.bestChild();
            }
        }
        return node;
    }

    /**
     * 扩展节点：随机选择一个未尝试的动作
     */
    private MCTSNode expand(MCTSNode node) {
        int action = node.untriedActions.remove(
            new Random().nextInt(node.untriedActions.size()));
        GameState nextState = new GameState(node.state);
        nextState.step(action);
        MCTSNode child = new MCTSNode(nextState, node, action);
        node.children.put(action, child);
        return child;
    }

    /**
     * 默认策略：随机模拟直到游戏结束
     * 返回值归一化到 [0,1]
     */
    private double defaultPolicy(GameState state) {
        GameState sim = new GameState(state);
        Random rand = new Random();
        int steps = 0;
        final int MAX_STEPS = 500;

        while (!sim.gameOver && steps < MAX_STEPS) {
            List<Integer> legal = sim.getLegalActions();
            if (legal.isEmpty()) break;
            // 优先向食物方向移动的贪婪随机策略
            int bestDir = legal.get(rand.nextInt(legal.size()));
            double bestDist = Double.MAX_VALUE;
            for (int d : legal) {
                int nr = sim.headRow + DIRS[d][0];
                int nc = sim.headCol + DIRS[d][1];
                double dist = Math.abs(nr - sim.foodRow) + Math.abs(nc - sim.foodCol);
                if (dist < bestDist && rand.nextDouble() < 0.7) {
                    bestDist = dist;
                    bestDir = d;
                }
            }
            sim.step(bestDir);
            steps++;
        }

        // 奖励函数：得分 + 生存步数归一化 + 剩余空间奖励
        double spaceReward = sim.snakeBody.size() / (double)(GRID_SIZE * GRID_SIZE);
        return (sim.score * 0.1 + steps / 500.0 + spaceReward) / 3.0;
    }

    /**
     * 回溯更新统计值
     */
    private void backup(MCTSNode node, double reward) {
        while (node != null) {
            node.visits++;
            node.totalReward += reward;
            node = node.parent;
        }
    }

运行入口

    public static void main(String[] args) {
        MCTSSnakeAI ai = new MCTSSnakeAI();
        GameState state = new GameState();
        int totalMoves = 0;

        while (!state.gameOver && totalMoves < 1000) {
            int action = ai.search(state, 800); // 每次决策800次迭代
            if (action < 0) break;
            String[] dirNames = {"上", "右", "下", "左"};
            System.out.printf("第%d步: 向%s移动 | 得分:%d | 长度:%d%n", 
                totalMoves + 1, dirNames[action], state.score, state.snakeBody.size());
            state.step(action);
            totalMoves++;
        }
        System.out.println("游戏结束! 最终得分: " + state.score + ", 总步数: " + totalMoves);
    }

复杂度分析

阶段 时间复杂度 空间复杂度
选择 $O(d)$，$d$为树深度 $O(N)$，$N$为节点数
扩展 $O(1)$ $O(1)$每节点
模拟 $O(k)$，$k$为模拟步数 $O(1)$
总搜索 $O(I \cdot (d + k))$，$I$为迭代次数 $O(I)$

算法优化建议

  1. 渐进式拓宽（Progressive Widening）：当节点访问次数超过阈值时，才允许扩展更多子节点
  2. RAVE（Rapid Action Value Estimation）：利用兄弟节点的统计信息加速收敛
  3. 虚拟损失（Virtual Loss）：并行化时防止多个线程同时探索同一路径
  4. 策略网络引导：用轻量级神经网络替代随机模拟，提升模拟质量

总结

本文通过Java实现了基于MCTS的贪吃蛇AI，核心亮点包括：完整的UCT搜索树构建、贪婪偏向的随机模拟策略、以及综合考虑得分与生存空间的奖励函数。MCTS无需显式评估函数，仅通过自我对弈即可学习策略，非常适合状态空间复杂、难以设计精确评估函数的游戏场景。

Tagged with: