每日算法 — 使用java实现贪吃蛇：Q-Learning强化学习与ε-贪心探索策略

贪吃蛇是游戏史上最具影响力的经典益智游戏之一。本文将跳出传统路径搜索的框架，引入强化学习（Reinforcement Learning）范式，使用 Q-Learning 算法 训练一条能够自主决策的贪吃蛇。核心难点在于状态空间的合理抽象与奖励函数的设计——我们将结合 ε-贪心（ε-Greedy）探索策略，让蛇在”利用已知最优动作”与”探索未知动作”之间动态权衡，最终学会高效觅食与躲避危险。

一、问题建模：马尔可夫决策过程

将贪吃蛇游戏抽象为 马尔可夫决策过程（MDP），其五元组为 (S, A, P, R, γ)：

• 状态空间 S：蛇头相对食物的方向、障碍物（自身/墙壁）分布、当前运动方向等。
• 动作空间 A：{上, 下, 左, 右}，每一步选择其中一个动作。
• 转移概率 P：环境确定，给定状态和动作，下一状态唯一。
• 奖励函数 R：吃到食物给予正奖励、撞墙或撞自身给予负奖励、存活给予微小负奖励（鼓励尽快吃食物）。
• 折扣因子 γ：控制未来奖励的衰减程度，通常取 0.9。

Q-Learning 的目标是学习一个动作价值函数 Q(s, a)，表示在状态 s 下执行动作 a 后能获得的累积期望回报。

二、状态空间设计：平衡维度与信息量

状态空间若过于庞大，会导致训练缓慢甚至无法收敛；若过于简单，则蛇无法学到有效策略。本文采用以下11维布尔状态向量：

这种设计将连续坐标离散化为相对关系，状态总数约为 2^11 = 2048，既保证信息量，又使 Q-Table 可存于内存。

三、奖励函数设计：从”生存”到”觅食”

奖励函数是强化学习的灵魂。本文采用分层奖励设计：

吃到食物：   +10.0
撞墙/撞自身： -10.0
每走一步：   -0.1  （避免无限绕圈）
朝向食物移动： +0.1 （引导性奖励）
远离食物移动： -0.1 （惩罚性反馈）

每步 -0.1 的存活惩罚迫使蛇尽快找到食物，避免原地打转；方向性奖励加速前期收敛。

四、Q-Learning 更新与 ε-贪心策略

4.1 Q值更新公式

Q-Learning 是离策略（Off-Policy）时序差分控制算法，其更新规则为：

Q(s, a) = Q(s, a) + α * [r + γ * max_a' Q(s', a') - Q(s, a)]

其中 α 为学习率，γ 为折扣因子，max_a' Q(s', a') 表示下一状态的最大 Q 值。

4.2 ε-贪心探索

训练初期 Q-Table 全为 0，若总是选择当前最优动作，将陷入局部最优。ε-贪心策略以概率 ε 随机探索，以概率 1-ε 选择最优动作：

if (Math.random() < epsilon) {
    action = randomAction();      // 探索
} else {
    action = argMaxQ(state);      // 利用
}

训练过程中 ε 从 1.0 逐渐衰减至 0.01，实现”先广探、后精修”。

五、完整 Java 实现

项目采用 Swing 做可视化渲染，核心逻辑封装于 SnakeQLearning 类。

5.1 项目结构

src/
├── SnakeGame.java          // Swing 渲染主类
├── SnakeQLearning.java     // Q-Learning 决策引擎
└── GameState.java          // 状态编码工具

5.2 GameState.java：状态编码

public class GameState {
    // 将相对位置与危险信息编码为状态索引 [0, 2047]
    public static int encode(boolean dangerLeft, boolean dangerStraight, boolean dangerRight,
                              boolean foodLeft, boolean foodRight,
                              boolean foodUp, boolean foodDown,
                              boolean dirLeft, boolean dirUp, boolean dirRight,
                              boolean longBody) {
        int state = 0;
        state |= (dangerLeft ? 1 : 0) << 0;
        state |= (dangerStraight ? 1 : 0) << 1;
        state |= (dangerRight ? 1 : 0) << 2;
        state |= (foodLeft ? 1 : 0) << 3;
        state |= (foodRight ? 1 : 0) << 4;
        state |= (foodUp ? 1 : 0) << 5;
        state |= (foodDown ? 1 : 0) << 6;
        state |= (dirLeft ? 1 : 0) << 7;
        state |= (dirUp ? 1 : 0) << 8;
        state |= (dirRight ? 1 : 0) << 9;
        state |= (longBody ? 1 : 0) << 10;
        return state;
    }
}

5.3 SnakeQLearning.java：决策引擎

import java.util.Random;

public class SnakeQLearning {
    private static final int STATE_COUNT = 2048;  // 2^11
    private static final int ACTION_COUNT = 3;    // 0=直行, 1=左转, 2=右转
    private static final double ALPHA = 0.1;      // 学习率
    private static final double GAMMA = 0.9;      // 折扣因子
    private static final double EPSILON_START = 1.0;
    private static final double EPSILON_END = 0.01;
    private static final int DECAY_EPISODES = 2000;

    private final double[][] qTable = new double[STATE_COUNT][ACTION_COUNT];
    private final Random random = new Random();
    private int episodeCount = 0;

    // 根据当前 ε 选择动作
    public int chooseAction(int state) {
        double epsilon = getCurrentEpsilon();
        if (random.nextDouble() < epsilon) {
            return random.nextInt(ACTION_COUNT);
        }
        return argMax(qTable[state]);
    }

    // 获取当前探索率（线性衰减）
    private double getCurrentEpsilon() {
        if (episodeCount >= DECAY_EPISODES) return EPSILON_END;
        return EPSILON_START - (EPSILON_START - EPSILON_END) * episodeCount / DECAY_EPISODES;
    }

    // 更新 Q 值
    public void update(int state, int action, double reward, int nextState) {
        double maxNext = qTable[nextState][argMax(qTable[nextState])];
        qTable[state][action] += ALPHA * (reward + GAMMA * maxNext - qTable[state][action]);
    }

    // 标记一回合结束，用于 ε 衰减
    public void endEpisode() {
        episodeCount++;
    }

    // 返回数组最大值的索引
    private int argMax(double[] arr) {
        int best = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[best]) best = i;
        }
        return best;
    }

    public int getEpisodeCount() { return episodeCount; }
}

5.4 SnakeGame.java：主循环与渲染

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class SnakeGame extends JPanel implements ActionListener {
    private static final int TILE_SIZE = 20;
    private static final int WIDTH = 20;   // 20x20 网格
    private static final int HEIGHT = 20;
    private static final int DELAY = 50;   // 毫秒/帧

    private final SnakeQLearning agent = new SnakeQLearning();
    private final LinkedList<Point> snake = new LinkedList<>();
    private Point food;
    private int direction = 1; // 0=左,1=上,2=右,3=下
    private int score = 0;
    private int highScore = 0;
    private boolean running = true;
    private final javax.swing.Timer timer;

    public SnakeGame() {
        setPreferredSize(new Dimension(WIDTH * TILE_SIZE, HEIGHT * TILE_SIZE));
        setBackground(Color.BLACK);
        setFocusable(true);
        initGame();
        timer = new javax.swing.Timer(DELAY, this);
        timer.start();
    }

    private void initGame() {
        snake.clear();
        snake.add(new Point(WIDTH / 2, HEIGHT / 2));
        direction = 1;
        score = 0;
        spawnFood();
        running = true;
    }

    private void spawnFood() {
        Random r = new Random();
        do {
            food = new Point(r.nextInt(WIDTH), r.nextInt(HEIGHT));
        } while (snake.contains(food));
    }

    @Override
    public void actionPerformed(ActionEvent e) {
        if (!running) {
            agent.endEpisode();
            if (score > highScore) highScore = score;
            initGame();
            return;
        }

        int state = getCurrentState();
        int action = agent.chooseAction(state); // 0=直行,1=左转,2=右转

        // 将相对动作映射为绝对方向
        if (action == 1) direction = (direction + 3) % 4;      // 左转
        else if (action == 2) direction = (direction + 1) % 4; // 右转
        // action==0 保持原方向

        Point head = snake.getFirst();
        Point next = new Point(head);
        switch (direction) {
            case 0: next.x--; break;
            case 1: next.y--; break;
            case 2: next.x++; break;
            case 3: next.y++; break;
        }

        double reward = -0.1; // 存活惩罚
        boolean ate = false;

        // 碰撞检测
        if (next.x < 0 || next.x >= WIDTH || next.y < 0 || next.y >= HEIGHT || snake.contains(next)) {
            reward = -10.0;
            running = false;
        } else {
            snake.addFirst(next);
            if (next.equals(food)) {
                reward = 10.0;
                score++;
                ate = true;
                spawnFood();
            } else {
                snake.removeLast();
                // 方向性奖励：朝向食物移动则奖励，远离则惩罚
                double oldDist = Math.abs(head.x - food.x) + Math.abs(head.y - food.y);
                double newDist = Math.abs(next.x - food.x) + Math.abs(next.y - food.y);
                if (newDist < oldDist) reward += 0.1;
                else reward -= 0.1;
            }
        }

        int nextState = getCurrentState();
        agent.update(state, action, reward, nextState);
        repaint();
    }

    // 将当前游戏局面编码为状态索引
    private int getCurrentState() {
        Point head = snake.getFirst();
        boolean dirLeft = direction == 0;
        boolean dirUp = direction == 1;
        boolean dirRight = direction == 2;

        // 计算左前、正前、右前三个方向的坐标
        int[][] dirs = {{0,-1},{1,0},{0,1},{-1,0}}; // 上右下左
        int dirIdx = direction; // 0=左? 修正：direction定义需与dirs对齐
        // direction: 0=左,1=上,2=右,3=下
        // 前方向量
        int fx = 0, fy = 0;
        switch (direction) {
            case 0: fx = -1; break;
            case 1: fy = -1; break;
            case 2: fx = 1; break;
            case 3: fy = 1; break;
        }
        // 左方向量（相对当前方向左转90度）
        int lx = 0, ly = 0;
        switch (direction) {
            case 0: ly = -1; break; // 左→上
            case 1: fx = 0; fy = -1; lx = -1; ly = 0; break; // 上→左
            case 2: ly = 1; break;  // 右→下
            case 3: fx = 0; fy = 1; lx = 1; ly = 0; break;  // 下→右
        }
        // 简化：用绝对方向直接计算三个探测点
        int leftDir = (direction + 3) % 4;
        int rightDir = (direction + 1) % 4;
        Point left = move(head, leftDir);
        Point straight = move(head, direction);
        Point right = move(head, rightDir);

        boolean dangerLeft = isDanger(left);
        boolean dangerStraight = isDanger(straight);
        boolean dangerRight = isDanger(right);

        boolean foodLeft = food.x < head.x;
        boolean foodRight = food.x > head.x;
        boolean foodUp = food.y < head.y;
        boolean foodDown = food.y > head.y;

        boolean longBody = snake.size() > 15;

        return GameState.encode(dangerLeft, dangerStraight, dangerRight,
                                 foodLeft, foodRight, foodUp, foodDown,
                                 dirLeft, dirUp, dirRight, longBody);
    }

    private Point move(Point p, int dir) {
        Point n = new Point(p);
        switch (dir) {
            case 0: n.x--; break;
            case 1: n.y--; break;
            case 2: n.x++; break;
            case 3: n.y++; break;
        }
        return n;
    }

    private boolean isDanger(Point p) {
        return p.x < 0 || p.x >= WIDTH || p.y < 0 || p.y >= HEIGHT || snake.contains(p);
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        // 绘制网格
        g.setColor(Color.DARK_GRAY);
        for (int i = 0; i <= WIDTH; i++) g.drawLine(i * TILE_SIZE, 0, i * TILE_SIZE, HEIGHT * TILE_SIZE);
        for (int i = 0; i <= HEIGHT; i++) g.drawLine(0, i * TILE_SIZE, WIDTH * TILE_SIZE, i * TILE_SIZE);

        // 绘制食物
        g.setColor(Color.RED);
        g.fillOval(food.x * TILE_SIZE + 2, food.y * TILE_SIZE + 2, TILE_SIZE - 4, TILE_SIZE - 4);

        // 绘制蛇
        for (int i = 0; i < snake.size(); i++) {
            Point p = snake.get(i);
            g.setColor(i == 0 ? Color.GREEN : Color.CYAN);
            g.fillRect(p.x * TILE_SIZE + 1, p.y * TILE_SIZE + 1, TILE_SIZE - 2, TILE_SIZE - 2);
        }

        // 绘制信息
        g.setColor(Color.WHITE);
        g.drawString("Score: " + score + "  High: " + highScore + "  Episode: " + agent.getEpisodeCount(), 5, 15);
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame("Snake Q-Learning");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new SnakeGame());
        frame.pack();
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }
}

六、训练观察与参数调优

在 20×20 的网格上训练约 3000 回合后，蛇的行为会经历以下阶段：

若训练后蛇频繁进入死胡同，可尝试：
1. 增大网格尺寸：30×30 给予更多迂回空间。
2. 调整奖励：将存活惩罚从 -0.1 改为 -0.01，避免蛇因恐惧而贴墙不动。
3. 引入蛇尾方向状态：让蛇感知尾巴位置，主动为自身让路。

七、复杂度分析

与传统 A* 寻路相比，Q-Learning 无需预先知道食物位置的全局地图，完全基于局部感知做决策，更贴近”生物本能”式学习。

八、扩展方向

1. Deep Q-Network（DQN）：当状态空间引入全局坐标时，传统 Q-Table 会爆炸，此时可用神经网络近似 Q 函数。
2. Double DQN / Dueling DQN：缓解 Q 值过估计问题，提升策略稳定性。
3. 优先经验回放（PER）：将”吃到食物”或”撞墙”的关键转移样本赋予更高学习权重。
4. 多蛇对抗：引入竞争机制，使用独立 Q-Learning 或博弈论框架训练多条蛇。

九、总结

本文以贪吃蛇为实验平台，完整实现了基于 Q-Learning 的强化学习智能体。核心创新点在于：

• 11维布尔状态编码：将复杂连续游戏空间压缩为可管理的离散状态。
• 分层奖励函数：结合即时反馈（吃食物/撞墙）与引导性奖励（朝向/远离食物），加速收敛。
• ε-贪心动态衰减：从纯随机探索平滑过渡到贪婪利用，兼顾学习效率与策略最优性。

完整代码可直接编译运行，观察蛇从”跌跌撞撞”到”游刃有余”的进化过程，是理解强化学习入门原理的绝佳实践。