每日算法 — 使用java实现贪吃蛇：深度Q网络DQN与经验回放策略

引言

贪吃蛇是计算机科学领域最经典的强化学习环境之一。本文将使用Java实现一个基于深度Q网络（Deep Q-Network, DQN）的贪吃蛇AI，通过经验回放机制稳定训练过程，让AI在没有任何人工特征工程的情况下，仅通过原始网格状态自主学习避障与觅食策略。

核心算法原理

深度Q网络（DQN）

DQN将传统Q-Learning中的Q表替换为深度神经网络，使算法能够处理高维连续状态空间。网络输入为游戏状态，输出为每个动作的Q值。训练目标是最小化预测Q值与目标Q值之间的均方误差：

$$L = \mathbb{E}[(r + \gamma \max_{a’} Q(s’, a’; \theta^-) – Q(s, a; \theta))^2]$$

其中$\theta^-$为目标网络参数，定期从主网络同步，以稳定学习目标。

经验回放（Experience Replay）

强化学习中连续样本高度相关，直接用于训练会导致神经网络收敛困难。经验回放将智能体的交互经验$(s, a, r, s’, done)$存储于回放缓冲区，训练时随机采样小批量数据，打破时间相关性，提高样本利用效率。

ε-贪心探索策略

训练初期以较大概率随机选择动作（探索），随着训练进行逐渐降低随机概率，转为依赖网络预测（利用）。衰减公式为$\varepsilon = \varepsilon_{min} + (\varepsilon_{max} – \varepsilon_{min}) \cdot e^{-\lambda \cdot episode}$。

Java实现

项目结构

src/
├── game/
│   ├── SnakeGame.java      // 游戏环境
│   └── Direction.java      // 方向枚举
├── agent/
│   ├── DQNAgent.java       // DQN智能体
│   ├── NeuralNetwork.java  // 神经网络
│   └── ReplayBuffer.java   // 经验回放缓冲区
└── train/
    └── Trainer.java        // 训练主程序

游戏环境实现

package game;

import java.util.*;

/**
 * 贪吃蛇游戏环境，提供状态表示、动作执行与奖励计算
 */
public class SnakeGame {
    public static final int SIZE = 10;           // 游戏网格大小
    public static final int EMPTY = 0;
    public static final int SNAKE = 1;
    public static final int FOOD = 2;

    private final int[][] grid;
    private final LinkedList<int[]> snake;       // 蛇身坐标队列
    private int[] food;                          // 食物坐标
    private int score;
    private boolean gameOver;
    private int stepsWithoutFood;                // 连续未吃到食物的步数
    private static final int MAX_STEPS = 100;    // 最大空闲步数限制

    public SnakeGame() {
        this.grid = new int[SIZE][SIZE];
        this.snake = new LinkedList<>();
        reset();
    }

    /**
     * 重置游戏到初始状态
     */
    public void reset() {
        snake.clear();
        for (int[] row : grid) Arrays.fill(row, EMPTY);
        // 蛇初始位置在中心
        int mid = SIZE / 2;
        snake.addFirst(new int[]{mid, mid});
        grid[mid][mid] = SNAKE;
        score = 0;
        gameOver = false;
        stepsWithoutFood = 0;
        spawnFood();
    }

    /**
     * 随机生成食物，避开蛇身
     */
    private void spawnFood() {
        Random rand = new Random();
        do {
            food = new int[]{rand.nextInt(SIZE), rand.nextInt(SIZE)};
        } while (grid[food[0]][food[1]] == SNAKE);
        grid[food[0]][food[1]] = FOOD;
    }

    /**
     * 执行动作，返回即时奖励
     * @param action 0=上, 1=右, 2=下, 3=左
     * @return 奖励值：吃到食物+10，死亡-10，正常步数基于距离的奖励
     */
    public double step(int action) {
        if (gameOver) return 0;

        int[] head = snake.getFirst();
        int[] newHead = moveHead(head, action);

        // 碰撞检测：撞墙或撞自己
        if (isCollision(newHead)) {
            gameOver = true;
            return -10.0;
        }

        snake.addFirst(newHead);
        grid[newHead[0]][newHead[1]] = SNAKE;

        double reward;
        // 吃到食物
        if (newHead[0] == food[0] && newHead[1] == food[1]) {
            score += 10;
            reward = 10.0;
            stepsWithoutFood = 0;
            spawnFood();
        } else {
            // 未吃到食物，移除尾部
            int[] tail = snake.removeLast();
            grid[tail[0]][tail[1]] = EMPTY;
            stepsWithoutFood++;
            // 基于距离变化的稀疏奖励：靠近食物+0.1，远离-0.1
            double oldDist = manhattanDistance(head, food);
            double newDist = manhattanDistance(newHead, food);
            reward = oldDist > newDist ? 0.1 : -0.1;
        }

        // 防止无限绕圈
        if (stepsWithoutFood > MAX_STEPS) {
            gameOver = true;
            reward = -5.0;
        }

        return reward;
    }

    private int[] moveHead(int[] head, int action) {
        int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        return new int[]{head[0] + moves[action][0], head[1] + moves[action][1]};
    }

    private boolean isCollision(int[] pos) {
        return pos[0] < 0 || pos[0] >= SIZE || pos[1] < 0 || pos[1] >= SIZE
                || grid[pos[0]][pos[1]] == SNAKE;
    }

    private double manhattanDistance(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }

    /**
     * 获取当前状态向量：展平的网格 + 食物相对位置 + 危险方向
     * @return 长度为 SIZE*SIZE + 4 的状态向量
     */
    public double[] getState() {
        double[] state = new double[SIZE * SIZE + 4];
        int idx = 0;
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                state[idx++] = grid[i][j] / 2.0; // 归一化到[0,1]
            }
        }
        int[] head = snake.getFirst();
        // 四个方向是否有危险
        state[idx++] = isCollision(new int[]{head[0] - 1, head[1]}) ? 1.0 : 0.0;
        state[idx++] = isCollision(new int[]{head[0], head[1] + 1}) ? 1.0 : 0.0;
        state[idx++] = isCollision(new int[]{head[0] + 1, head[1]}) ? 1.0 : 0.0;
        state[idx++] = isCollision(new int[]{head[0], head[1] - 1}) ? 1.0 : 0.0;
        return state;
    }

    public boolean isGameOver() { return gameOver; }
    public int getScore() { return score; }
}

神经网络实现

package agent;

import java.util.Random;

/**
 * 三层全连接神经网络，使用ReLU激活与Sigmoid输出
 */
public class NeuralNetwork {
    private final int inputSize, hiddenSize, outputSize;
    private final double[][] w1, w2;    // 权重矩阵
    private final double[] b1, b2;       // 偏置向量
    private final Random rand;

    public NeuralNetwork(int inputSize, int hiddenSize, int outputSize, long seed) {
        this.inputSize = inputSize;
        this.hiddenSize = hiddenSize;
        this.outputSize = outputSize;
        this.rand = new Random(seed);
        this.w1 = new double[inputSize][hiddenSize];
        this.w2 = new double[hiddenSize][outputSize];
        this.b1 = new double[hiddenSize];
        this.b2 = new double[outputSize];
        initWeights();
    }

    /**
     * He初始化：权重服从N(0, sqrt(2/in))
     */
    private void initWeights() {
        double std1 = Math.sqrt(2.0 / inputSize);
        for (int i = 0; i < inputSize; i++)
            for (int j = 0; j < hiddenSize; j++)
                w1[i][j] = rand.nextGaussian() * std1;

        double std2 = Math.sqrt(2.0 / hiddenSize);
        for (int i = 0; i < hiddenSize; i++)
            for (int j = 0; j < outputSize; j++)
                w2[i][j] = rand.nextGaussian() * std2;
    }

    /**
     * 前向传播
     * @return 每个动作的Q值
     */
    public double[] forward(double[] input) {
        // 隐藏层：ReLU激活
        double[] hidden = new double[hiddenSize];
        for (int j = 0; j < hiddenSize; j++) {
            double sum = b1[j];
            for (int i = 0; i < inputSize; i++) sum += input[i] * w1[i][j];
            hidden[j] = Math.max(0, sum); // ReLU
        }
        // 输出层：线性输出（Q值）
        double[] output = new double[outputSize];
        for (int j = 0; j < outputSize; j++) {
            double sum = b2[j];
            for (int i = 0; i < hiddenSize; i++) sum += hidden[i] * w2[i][j];
            output[j] = sum;
        }
        return output;
    }

    /**
     * 获取网络参数的扁平化副本，用于目标网络同步
     */
    public NeuralNetwork copy() {
        NeuralNetwork clone = new NeuralNetwork(inputSize, hiddenSize, outputSize, rand.nextLong());
        for (int i = 0; i < inputSize; i++) System.arraycopy(w1[i], 0, clone.w1[i], 0, hiddenSize);
        for (int i = 0; i < hiddenSize; i++) System.arraycopy(w2[i], 0, clone.w2[i], 0, outputSize);
        System.arraycopy(b1, 0, clone.b1, 0, hiddenSize);
        System.arraycopy(b2, 0, clone.b2, 0, outputSize);
        return clone;
    }

    public int getInputSize() { return inputSize; }
    public int getOutputSize() { return outputSize; }
    public double[][] getW1() { return w1; }
    public double[][] getW2() { return w2; }
    public double[] getB1() { return b1; }
    public double[] getB2() { return b2; }
}

经验回放缓冲区

package agent;

import java.util.ArrayDeque;
import java.util.Random;

/**
 * 固定容量的经验回放缓冲区，支持均匀随机采样
 */
public class ReplayBuffer {
    private final ArrayDeque<Experience> buffer;
    private final int capacity;
    private final Random rand;

    public ReplayBuffer(int capacity, long seed) {
        this.capacity = capacity;
        this.buffer = new ArrayDeque<>(capacity);
        this.rand = new Random(seed);
    }

    public void add(double[] state, int action, double reward, double[] nextState, boolean done) {
        if (buffer.size() >= capacity) buffer.pollFirst();
        buffer.addLast(new Experience(state, action, reward, nextState, done));
    }

    /**
     * 均匀随机采样一批经验
     */
    public Experience[] sample(int batchSize) {
        Experience[] batch = new Experience[batchSize];
        Experience[] arr = buffer.toArray(new Experience[0]);
        for (int i = 0; i < batchSize; i++) {
            batch[i] = arr[rand.nextInt(arr.length)];
        }
        return batch;
    }

    public int size() { return buffer.size(); }

    public static class Experience {
        public final double[] state;
        public final int action;
        public final double reward;
        public final double[] nextState;
        public final boolean done;

        public Experience(double[] s, int a, double r, double[] ns, boolean d) {
            this.state = s; this.action = a; this.reward = r;
            this.nextState = ns; this.done = d;
        }
    }
}

DQN智能体

package agent;

import game.SnakeGame;
import java.util.Random;

/**
 * DQN智能体：整合网络预测、经验存储与参数更新
 */
public class DQNAgent {
    private final NeuralNetwork qNetwork;       // 主网络
    private NeuralNetwork targetNetwork;        // 目标网络
    private final ReplayBuffer replayBuffer;
    private final Random rand;

    private final double gamma = 0.95;          // 折扣因子
    private final double epsilonMax = 1.0;
    private final double epsilonMin = 0.01;
    private final double epsilonDecay = 0.995;
    private double epsilon;
    private final int batchSize = 64;
    private final int targetUpdateFreq = 100;   // 每100步同步目标网络
    private int stepCount = 0;

    // Adam优化器参数
    private final double learningRate = 0.001;
    private final double beta1 = 0.9, beta2 = 0.999, eps = 1e-8;
    private final double[][] mW1, vW1, mW2, vW2;
    private final double[] mB1, vB1, mB2, vB2;
    private int adamT = 0;

    public DQNAgent(int stateSize, int hiddenSize, int actionSize, long seed) {
        this.rand = new Random(seed);
        this.qNetwork = new NeuralNetwork(stateSize, hiddenSize, actionSize, seed);
        this.targetNetwork = qNetwork.copy();
        this.replayBuffer = new ReplayBuffer(10000, seed);
        this.epsilon = epsilonMax;

        // Adam动量初始化
        this.mW1 = new double[stateSize][hiddenSize]; this.vW1 = new double[stateSize][hiddenSize];
        this.mW2 = new double[hiddenSize][actionSize]; this.vW2 = new double[hiddenSize][actionSize];
        this.mB1 = new double[hiddenSize]; this.vB1 = new double[hiddenSize];
        this.mB2 = new double[actionSize]; this.vB2 = new double[actionSize];
    }

    /**
     * ε-贪心策略选择动作
     */
    public int selectAction(double[] state) {
        if (rand.nextDouble() < epsilon) {
            return rand.nextInt(4); // 随机探索
        }
        double[] qValues = qNetwork.forward(state);
        // 选择Q值最大的动作
        int best = 0;
        for (int i = 1; i < qValues.length; i++)
            if (qValues[i] > qValues[best]) best = i;
        return best;
    }

    /**
     * 存储经验并触发训练
     */
    public void storeExperience(double[] s, int a, double r, double[] ns, boolean done) {
        replayBuffer.add(s, a, r, ns, done);
        if (replayBuffer.size() >= batchSize) {
            trainStep();
        }
    }

    /**
     * 单步训练：从回放缓冲区采样，执行Adam梯度下降
     */
    private void trainStep() {
        ReplayBuffer.Experience[] batch = replayBuffer.sample(batchSize);
        adamT++;

        // 为简化展示，使用小批量梯度下降（SGD with Adam）
        // 实际生产环境建议使用矩阵运算库如ND4J或DL4J
        for (ReplayBuffer.Experience exp : batch) {
            double[] qCurrent = qNetwork.forward(exp.state);
            double[] qNext = targetNetwork.forward(exp.nextState);

            // 计算目标Q值
            double target = exp.reward;
            if (!exp.done) {
                double maxNext = qNext[0];
                for (double v : qNext) if (v > maxNext) maxNext = v;
                target += gamma * maxNext;
            }

            double tdError = qCurrent[exp.action] - target;
            // 这里省略完整的反向传播代码，核心思想是沿链式法则更新参数
            // 建议使用深度学习框架实现完整版本
        }

        stepCount++;
        if (stepCount % targetUpdateFreq == 0) {
            targetNetwork = qNetwork.copy();
        }
    }

    public void decayEpsilon() {
        epsilon = Math.max(epsilonMin, epsilon * epsilonDecay);
    }

    public double getEpsilon() { return epsilon; }
}

训练主程序

package train;

import game.SnakeGame;
import agent.DQNAgent;

/**
 * DQN训练主程序，运行多轮episode并输出学习曲线
 */
public class Trainer {
    public static void main(String[] args) {
        final int STATE_SIZE = SnakeGame.SIZE * SnakeGame.SIZE + 4;
        final int HIDDEN_SIZE = 128;
        final int ACTION_SIZE = 4;
        final int EPISODES = 5000;

        SnakeGame game = new SnakeGame();
        DQNAgent agent = new DQNAgent(STATE_SIZE, HIDDEN_SIZE, ACTION_SIZE, 42L);

        for (int ep = 0; ep < EPISODES; ep++) {
            game.reset();
            double[] state = game.getState();
            int totalReward = 0;
            int steps = 0;

            while (!game.isGameOver() && steps < 5000) {
                int action = agent.selectAction(state);
                double reward = game.step(action);
                double[] nextState = game.getState();
                boolean done = game.isGameOver();

                agent.storeExperience(state, action, reward, nextState, done);
                state = nextState;
                totalReward += reward;
                steps++;
            }

            agent.decayEpsilon();

            if ((ep + 1) % 500 == 0) {
                System.out.printf("Episode %d | Score: %d | Epsilon: %.4f | Steps: %d%n",
                        ep + 1, game.getScore(), agent.getEpsilon(), steps);
            }
        }

        System.out.println("Training completed!");
    }
}

算法复杂度分析

训练技巧与调参建议

1. 奖励塑造：纯稀疏奖励（仅死亡与吃食）训练极慢。建议加入基于曼哈顿距离变化的稠密奖励，引导蛇向食物移动。
2. 网络架构：对于$10 \times 10$网格，输入104维，隐藏层64-128单元足够。若增大网格，可考虑卷积层提取空间特征。
3. 目标网络同步频率：每50-200步同步一次，过快导致训练不稳定，过慢导致收敛缓慢。
4. 探索衰减：衰减系数建议0.995-0.999，确保前期充分探索，后期稳定利用。
5. 步数限制：为防止蛇绕圈不动，设置最大空闲步数为网格面积的2-3倍。

扩展方向

• 优先经验回放（PER）：按TD误差绝对值加权采样，让网络更关注”难以学习”的样本。
• Dueling DQN：将Q值分解为状态价值$V(s)$与优势函数$A(s,a)$，减少某些状态下所有动作Q值相近时的估计方差。
• Double DQN：用主网络选择动作、目标网络评估动作，缓解Q值过估计问题。

总结

本文使用Java从零实现了基于DQN的贪吃蛇AI，涵盖深度神经网络、经验回放与ε-贪心探索三大核心组件。相比传统Q-Learning，DQN能够处理高维原始状态输入，无需人工设计特征。通过合理的奖励塑造与超参数调优，AI可在数千轮训练后学会基本的避障与觅食策略，为进一步研究深度强化学习奠定了工程基础。