一、问题背景
贪吃蛇是一款经典的益智游戏，玩家控制一条蛇在网格中移动，通过吃食物不断增长身体。本文将用Java实现一个基于DQN（Deep Q-Network）深度Q网络的贪吃蛇AI，让蛇通过自我对弈学习最优策略。核心算法包括神经网络近似Q值函数、经验回放池稳定训练、以及ε-贪心策略平衡探索与利用。
二、算法核心思想
2.1 DQN概述
传统Q-Learning使用表格存储每个状态-动作对的Q值，但在高维状态空间下不可行。DQN使用神经网络近似Q函数：
$$Q(s, a; \theta) \approx Q^*(s, a)$$
其中 $\theta$ 为网络参数，通过最小化时序差分误差更新：
$$L(\theta) = \mathbb{E}[(r + \gamma \max_{a’} Q(s’, a’; \theta^-) – Q(s, a; \theta))^2]$$
2.2 经验回放（Experience Replay）
将智能体的经验 $(s, a, r, s’, done)$ 存储在回放缓冲区中，训练时随机采样小批量数据。这打破了数据间的时序相关性，提高样本利用效率。
2.3 ε-贪心策略
以概率 $\varepsilon$ 随机选择动作（探索），以概率 $1-\varepsilon$ 选择Q值最大的动作（利用）。随着训练进行，$\varepsilon$ 逐渐衰减。
三、状态设计与网络结构
3.1 状态表示
将蛇的当前环境编码为11维向量：
– 前方、左侧、右侧是否有危险（3维）
– 当前移动方向（4维one-hot）
– 食物相对位置（左上、右下等，4维）
3.2 神经网络结构
输入层(11) → 隐藏层1(128, ReLU) → 隐藏层2(128, ReLU) → 输出层(3, 线性)
输出3个Q值，分别对应直行、左转、右转。
四、完整Java实现
import java.util.*;
/**
* DQN贪吃蛇AI - 深度Q网络与经验回放
*/
public class SnakeDQN {
// ==================== 神经网络层 ====================
static class NeuralNetwork {
int inputSize, hiddenSize, outputSize;
double[][] W1, W2; // 权重矩阵
double[] b1, b2; // 偏置
double lr; // 学习率
public NeuralNetwork(int inputSize, int hiddenSize, int outputSize, double lr) {
this.inputSize = inputSize;
this.hiddenSize = hiddenSize;
this.outputSize = outputSize;
this.lr = lr;
W1 = new double[inputSize][hiddenSize];
W2 = new double[hiddenSize][outputSize];
b1 = new double[hiddenSize];
b2 = new double[outputSize];
initWeights();
}
/** Xavier初始化权重 */
void initWeights() {
Random rand = new Random(42);
double scale1 = Math.sqrt(2.0 / inputSize);
for (int i = 0; i < inputSize; i++)
for (int j = 0; j < hiddenSize; j++)
W1[i][j] = rand.nextGaussian() * scale1;
double scale2 = Math.sqrt(2.0 / hiddenSize);
for (int i = 0; i < hiddenSize; i++)
for (int j = 0; j < outputSize; j++)
W2[i][j] = rand.nextGaussian() * scale2;
}
/** ReLU激活函数 */
double relu(double x) { return Math.max(0, x); }
/** 前向传播，返回输出层和隐藏层结果 */
double[][] forward(double[] x) {
double[] h = new double[hiddenSize];
for (int j = 0; j < hiddenSize; j++) {
double sum = b1[j];
for (int i = 0; i < inputSize; i++) sum += x[i] * W1[i][j];
h[j] = relu(sum);
}
double[] out = new double[outputSize];
for (int j = 0; j < outputSize; j++) {
double sum = b2[j];
for (int i = 0; i < hiddenSize; i++) sum += h[i] * W2[i][j];
out[j] = sum; // 线性输出
}
return new double[][]{out, h};
}
/** 反向传播更新参数 */
void backward(double[] x, double[] h, double[] out, double[] target) {
// 输出层梯度
double[] dOut = new double[outputSize];
for (int i = 0; i < outputSize; i++) dOut[i] = 2 * (out[i] - target[i]) / outputSize;
// 隐藏层梯度
double[] dH = new double[hiddenSize];
for (int i = 0; i < hiddenSize; i++) {
double sum = 0;
for (int j = 0; j < outputSize; j++) sum += dOut[j] * W2[i][j];
dH[i] = h[i] > 0 ? sum : 0; // ReLU导数
}
// 更新W2, b2
for (int i = 0; i < hiddenSize; i++)
for (int j = 0; j < outputSize; j++)
W2[i][j] -= lr * dOut[j] * h[i];
for (int j = 0; j < outputSize; j++) b2[j] -= lr * dOut[j];
// 更新W1, b1
for (int i = 0; i < inputSize; i++)
for (int j = 0; j < hiddenSize; j++)
W1[i][j] -= lr * dH[j] * x[i];
for (int j = 0; j < hiddenSize; j++) b1[j] -= lr * dH[j];
}
}
// ==================== 经验回放缓冲区 ====================
static class ReplayBuffer {
List<Experience> buffer = new ArrayList<>();
int capacity;
Random rand = new Random();
public ReplayBuffer(int capacity) { this.capacity = capacity; }
void add(double[] state, int action, double reward, double[] nextState, boolean done) {
if (buffer.size() >= capacity) buffer.remove(0);
buffer.add(new Experience(state, action, reward, nextState, done));
}
List<Experience> sample(int batchSize) {
List<Experience> batch = new ArrayList<>();
int n = Math.min(batchSize, buffer.size());
for (int i = 0; i < n; i++)
batch.add(buffer.get(rand.nextInt(buffer.size())));
return batch;
}
int size() { return buffer.size(); }
}
static class Experience {
double[] state, nextState;
int action;
double reward;
boolean done;
Experience(double[] s, int a, double r, double[] ns, boolean d) {
state = s; action = a; reward = r; nextState = ns; done = d;
}
}
// ==================== 贪吃蛇环境 ====================
static class SnakeEnv {
int width = 10, height = 10;
int[] head; // 蛇头位置 [x, y]
List<int[]> body; // 蛇身
int[] food; // 食物位置
int direction; // 0:上 1:右 2:下 3:左
int score;
boolean gameOver;
Random rand = new Random();
public SnakeEnv() { reset(); }
void reset() {
head = new int[]{width / 2, height / 2};
body = new ArrayList<>();
body.add(new int[]{head[0], head[1]});
direction = 1;
score = 0;
gameOver = false;
spawnFood();
}
void spawnFood() {
do {
food = new int[]{rand.nextInt(width), rand.nextInt(height)};
} while (isOnSnake(food));
}
boolean isOnSnake(int[] pos) {
for (int[] p : body) if (p[0] == pos[0] && p[1] == pos[1]) return true;
return false;
}
/** 执行动作：0=直行, 1=左转, 2=右转 */
double step(int action) {
if (gameOver) return 0;
// 更新方向
if (action == 1) direction = (direction + 3) % 4; // 左转
else if (action == 2) direction = (direction + 1) % 4; // 右转
int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}}; // 上右下左
int nx = head[0] + dirs[direction][0];
int ny = head[1] + dirs[direction][1];
// 撞墙或撞自己
if (nx < 0 || nx >= height || ny < 0 || ny >= width || isOnSnake(new int[]{nx, ny})) {
gameOver = true;
return -10; // 死亡惩罚
}
head = new int[]{nx, ny};
body.add(0, new int[]{nx, ny});
double reward = -0.1; // 每步小惩罚，鼓励快速吃食物
if (nx == food[0] && ny == food[1]) {
score++;
reward = 10; // 吃食物奖励
spawnFood();
} else {
body.remove(body.size() - 1); // 未吃食物则去尾
}
return reward;
}
/** 获取11维状态向量 */
double[] getState() {
double[] state = new double[11];
int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
int leftDir = (direction + 3) % 4;
int rightDir = (direction + 1) % 4;
// 前方、左侧、右侧是否有危险
int fx = head[0] + dirs[direction][0], fy = head[1] + dirs[direction][1];
int lx = head[0] + dirs[leftDir][0], ly = head[1] + dirs[leftDir][1];
int rx = head[0] + dirs[rightDir][0], ry = head[1] + dirs[rightDir][1];
state[0] = isDanger(fx, fy) ? 1 : 0;
state[1] = isDanger(lx, ly) ? 1 : 0;
state[2] = isDanger(rx, ry) ? 1 : 0;
// 当前移动方向
for (int i = 0; i < 4; i++) state[3 + i] = (direction == i) ? 1 : 0;
// 食物相对位置
state[7] = (food[0] < head[0]) ? 1 : 0; // 食物在上
state[8] = (food[0] > head[0]) ? 1 : 0; // 食物在下
state[9] = (food[1] < head[1]) ? 1 : 0; // 食物在左
state[10] = (food[1] > head[1]) ? 1 : 0; // 食物在右
return state;
}
boolean isDanger(int x, int y) {
return x < 0 || x >= height || y < 0 || y >= width || isOnSnake(new int[]{x, y});
}
}
// ==================== DQN训练主循环 ====================
public static void main(String[] args) {
final int STATE_SIZE = 11;
final int ACTION_SIZE = 3;
final int HIDDEN_SIZE = 128;
final double LR = 0.001;
final double GAMMA = 0.95;
final double EPSILON_START = 1.0;
final double EPSILON_END = 0.01;
final double EPSILON_DECAY = 0.995;
final int BATCH_SIZE = 64;
final int MEMORY_SIZE = 10000;
final int EPISODES = 2000;
NeuralNetwork policyNet = new NeuralNetwork(STATE_SIZE, HIDDEN_SIZE, ACTION_SIZE, LR);
NeuralNetwork targetNet = new NeuralNetwork(STATE_SIZE, HIDDEN_SIZE, ACTION_SIZE, LR);
// 复制参数到目标网络
copyWeights(policyNet, targetNet);
ReplayBuffer buffer = new ReplayBuffer(MEMORY_SIZE);
SnakeEnv env = new SnakeEnv();
double epsilon = EPSILON_START;
Random rand = new Random();
List<Double> scores = new ArrayList<>();
for (int ep = 0; ep < EPISODES; ep++) {
env.reset();
double[] state = env.getState();
double totalReward = 0;
int steps = 0;
final int MAX_STEPS = 500;
while (!env.gameOver && steps < MAX_STEPS) {
// ε-贪心选择动作
int action;
if (rand.nextDouble() < epsilon) {
action = rand.nextInt(ACTION_SIZE);
} else {
double[][] out = policyNet.forward(state);
action = argMax(out[0]);
}
double reward = env.step(action);
double[] nextState = env.getState();
boolean done = env.gameOver;
totalReward += reward;
buffer.add(state, action, reward, nextState, done);
state = nextState;
steps++;
// 经验回放训练
if (buffer.size() >= BATCH_SIZE) {
List<Experience> batch = buffer.sample(BATCH_SIZE);
for (Experience e : batch) {
double[][] out = policyNet.forward(e.state);
double[] target = out[0].clone();
double[][] nextOut = targetNet.forward(e.nextState);
double maxNextQ = max(nextOut[0]);
double tdTarget = e.done ? e.reward : e.reward + GAMMA * maxNextQ;
target[e.action] = tdTarget;
policyNet.backward(e.state, out[1], out[0], target);
}
}
}
scores.add((double) env.score);
epsilon = Math.max(EPSILON_END, epsilon * EPSILON_DECAY);
// 每50回合同步目标网络
if (ep % 50 == 0) copyWeights(policyNet, targetNet);
if (ep % 200 == 0) {
double avgScore = scores.subList(Math.max(0, scores.size() - 100), scores.size())
.stream().mapToDouble(Double::doubleValue).average().orElse(0);
System.out.printf("Episode %d, AvgScore(100)=%.2f, Epsilon=%.3f%n", ep, avgScore, epsilon);
}
}
System.out.println("训练完成！最终测试:");
testAgent(policyNet);
}
static void copyWeights(NeuralNetwork src, NeuralNetwork dst) {
for (int i = 0; i < src.W1.length; i++) System.arraycopy(src.W1[i], 0, dst.W1[i], 0, src.W1[i].length);
for (int i = 0; i < src.W2.length; i++) System.arraycopy(src.W2[i], 0, dst.W2[i], 0, src.W2[i].length);
System.arraycopy(src.b1, 0, dst.b1, 0, src.b1.length);
System.arraycopy(src.b2, 0, dst.b2, 0, src.b2.length);
}
static int argMax(double[] arr) {
int idx = 0;
for (int i = 1; i < arr.length; i++) if (arr[i] > arr[idx]) idx = i;
return idx;
}
static double max(double[] arr) {
double m = arr[0];
for (double v : arr) if (v > m) m = v;
return m;
}
static void testAgent(NeuralNetwork net) {
SnakeEnv env = new SnakeEnv();
double[] state = env.getState();
int steps = 0;
while (!env.gameOver && steps < 200) {
double[][] out = net.forward(state);
int action = argMax(out[0]);
env.step(action);
state = env.getState();
steps++;
}
System.out.println("测试得分: " + env.score + ", 步数: " + steps);
}
}
五、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 前向传播 | $O(H \cdot (I + O))$ | $O(H)$ |
| 经验回放训练（每步） | $O(B \cdot H \cdot (I + O))$ | $O(M \cdot S)$ |
| 环境模拟 | $O(L)$（L为蛇长） | $O(L)$ |
其中 $I=11$ 为输入维度，$H=128$ 为隐藏层大小，$O=3$ 为动作数，$B=64$ 为批量大小，$M=10000$ 为缓冲区容量，$S=25$ 为每条经验大小。
六、总结
本文实现了基于DQN的贪吃蛇AI，核心要点包括：
– 状态抽象：将复杂游戏局面压缩为11维向量，降低网络输入维度
– 经验回放：随机采样打破数据相关性，提升训练稳定性
– 目标网络：延迟更新减少自举偏差，加速收敛
– ε-贪心：平衡探索与利用，逐步从随机策略过渡到最优策略
通过2000回合训练，智能体能够学会绕开障碍物、朝向食物移动的基本策略。读者可以在此基础上扩展：增加更多网络层、使用优先经验回放、或引入Dueling DQN等改进结构。
