贪吃蛇是检验AI进化能力的经典沙盒。本文用Java实现一套完整的神经进化系统：蛇的”大脑”是一个前馈神经网络，根据环境感知决定移动方向；网络权重不依赖反向传播，而是通过遗传算法在种群中逐代进化——优胜者保留、交叉重组、随机变异。你会看到几十条蛇如何从随机乱撞，逐渐学会避墙、追食物、防自咬。
一、问题分析：为什么神经进化适合贪吃蛇
传统强化学习（如Q-Learning）需要大量离散状态存储，而贪吃蛇的状态空间随蛇身长度指数增长。神经进化（Neuroevolution）的直觉是：把策略参数化为神经网络权重，用遗传算法直接搜索最优权重向量。
优势在于：
– 状态输入可以是连续的（蛇头到障碍距离、食物方向等），无需离散化。
– 不需要梯度计算，避开反向传播的复杂性和局部最优问题。
– 遗传算法天然支持并行评估，适合种群级搜索。
二、神经网络设计：蛇的”大脑”
蛇的感知包括8个方向（上、下、左、右、左上、右上、左下、右下），每个方向探测三类信息：到墙的距离、到自身身体的距离、到食物的距离。共24维输入。隐藏层12个神经元，输出层3个神经元分别对应”直行””左转””右转”。
import java.util.Random;
/**
* 前馈神经网络：感知层 -> 隐藏层 -> 输出层
* 激活函数使用Sigmoid，输出经Softmax转为概率分布
*/
public class NeuralNetwork {
private final int inputSize;
private final int hiddenSize;
private final int outputSize;
// 权重矩阵
private final double[][] w1; // inputSize x hiddenSize
private final double[][] w2; // hiddenSize x outputSize
// 偏置
private final double[] b1;
private final double[] b2;
private final Random rand = new Random();
public NeuralNetwork(int inputSize, int hiddenSize, int outputSize) {
this.inputSize = inputSize;
this.hiddenSize = hiddenSize;
this.outputSize = outputSize;
this.w1 = new double[inputSize][hiddenSize];
this.w2 = new double[hiddenSize][outputSize];
this.b1 = new double[hiddenSize];
this.b2 = new double[outputSize];
randomize();
}
/** 用Xavier初始化权重，避免早期饱和 */
private void randomize() {
double limit1 = Math.sqrt(6.0 / (inputSize + hiddenSize));
for (int i = 0; i < inputSize; i++) {
for (int j = 0; j < hiddenSize; j++) {
w1[i][j] = (rand.nextDouble() * 2 - 1) * limit1;
}
}
double limit2 = Math.sqrt(6.0 / (hiddenSize + outputSize));
for (int i = 0; i < hiddenSize; i++) {
for (int j = 0; j < outputSize; j++) {
w2[i][j] = (rand.nextDouble() * 2 - 1) * limit2;
}
}
// 偏置初始化为小随机数
for (int j = 0; j < hiddenSize; j++) b1[j] = rand.nextDouble() * 0.2 - 0.1;
for (int j = 0; j < outputSize; j++) b2[j] = rand.nextDouble() * 0.2 - 0.1;
}
/** 前向传播，返回三个动作的得分 */
public double[] predict(double[] inputs) {
// 隐藏层
double[] hidden = new double[hiddenSize];
for (int j = 0; j < hiddenSize; j++) {
double sum = b1[j];
for (int i = 0; i < inputSize; i++) {
sum += inputs[i] * w1[i][j];
}
hidden[j] = sigmoid(sum);
}
// 输出层
double[] output = new double[outputSize];
for (int k = 0; k < outputSize; k++) {
double sum = b2[k];
for (int j = 0; j < hiddenSize; j++) {
sum += hidden[j] * w2[j][k];
}
output[k] = sum; // 原始logits，后续Softmax
}
return softmax(output);
}
private double sigmoid(double x) {
return 1.0 / (1.0 + Math.exp(-x));
}
private double[] softmax(double[] logits) {
double max = logits[0];
for (double v : logits) if (v > max) max = v;
double sum = 0.0;
double[] exp = new double[logits.length];
for (int i = 0; i < logits.length; i++) {
exp[i] = Math.exp(logits[i] - max);
sum += exp[i];
}
for (int i = 0; i < logits.length; i++) exp[i] /= sum;
return exp;
}
/** 将网络所有参数展平为一维数组，用于遗传编码 */
public double[] getGenome() {
int genomeSize = inputSize * hiddenSize + hiddenSize * outputSize + hiddenSize + outputSize;
double[] genome = new double[genomeSize];
int idx = 0;
for (int i = 0; i < inputSize; i++) {
for (int j = 0; j < hiddenSize; j++) {
genome[idx++] = w1[i][j];
}
}
for (int i = 0; i < hiddenSize; i++) {
for (int j = 0; j < outputSize; j++) {
genome[idx++] = w2[i][j];
}
}
for (int j = 0; j < hiddenSize; j++) genome[idx++] = b1[j];
for (int j = 0; j < outputSize; j++) genome[idx++] = b2[j];
return genome;
}
/** 从一维基因组恢复网络参数 */
public void setGenome(double[] genome) {
int idx = 0;
for (int i = 0; i < inputSize; i++) {
for (int j = 0; j < hiddenSize; j++) {
w1[i][j] = genome[idx++];
}
}
for (int i = 0; i < hiddenSize; i++) {
for (int j = 0; j < outputSize; j++) {
w2[i][j] = genome[idx++];
}
}
for (int j = 0; j < hiddenSize; j++) b1[j] = genome[idx++];
for (int j = 0; j < outputSize; j++) b2[j] = genome[idx++];
}
public int getGenomeSize() {
return inputSize * hiddenSize + hiddenSize * outputSize + hiddenSize + outputSize;
}
}
三、环境感知：24维特征向量
蛇看不见整个棋盘，只能”感知”周围。8个方向各探测3个值（归一化到0~1），构成神经网络的输入。
/**
* 环境传感器：为神经网络提取24维特征
*/
public class SnakeSensor {
// 8个探测方向：上、右上、右、右下、下、左下、左、左上
private static final int[][] DIRS = {
{0, -1}, {1, -1}, {1, 0}, {1, 1},
{0, 1}, {-1, 1}, {-1, 0}, {-1, -1}
};
/**
* 提取特征向量，长度固定24
* 每方向3个值：到墙距离/最大距离、到身体距离/最大距离(无则1)、食物是否在此方向(0/1)
*/
public double[] getFeatures(SnakeGame game) {
double[] features = new double[24];
int w = game.getWidth();
int h = game.getHeight();
int hx = game.getHeadX();
int hy = game.getHeadY();
int fx = game.getFoodX();
int fy = game.getFoodY();
for (int d = 0; d < 8; d++) {
int dx = DIRS[d][0];
int dy = DIRS[d][1];
// 到墙的距离
int distWall = 0;
int cx = hx + dx;
int cy = hy + dy;
while (cx >= 0 && cx < w && cy >= 0 && cy < h) {
distWall++;
cx += dx;
cy += dy;
}
double maxDist = Math.max(w, h);
features[d * 3] = distWall / maxDist;
// 到身体的距离
int distBody = Integer.MAX_VALUE;
cx = hx + dx;
cy = hy + dy;
int step = 0;
while (cx >= 0 && cx < w && cy >= 0 && cy < h) {
step++;
if (game.isBody(cx, cy)) {
distBody = step;
break;
}
cx += dx;
cy += dy;
}
features[d * 3 + 1] = (distBody == Integer.MAX_VALUE) ? 1.0 : distBody / maxDist;
// 食物方向指示
int foodDir = 0;
if (fx != hx || fy != hy) {
// 检查食物是否大致在此方向
int fdx = Integer.compare(fx, hx);
int fdy = Integer.compare(fy, hy);
// 简化：只看正交4方向的食物相对位置
if (d % 2 == 0) { // 正方向
if (dx == fdx && dy == fdy) foodDir = 1;
}
}
features[d * 3 + 2] = foodDir;
}
return features;
}
}
四、游戏引擎：蛇的移动与规则
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
/**
* 贪吃蛇游戏引擎
* 坐标系：左上角为(0,0)，x向右，y向下
*/
public class SnakeGame {
private final int width;
private final int height;
private final Deque<int[]> body = new ArrayDeque<>();
private final Set<String> bodySet = new HashSet<>();
private int foodX, foodY;
private int direction; // 0=上,1=右,2=下,3=左
private boolean alive = true;
private int score = 0;
private int movesLeft = 100; // 每吃一个食物重置，防止原地打转
private final Random rand = new Random();
public SnakeGame(int width, int height) {
this.width = width;
this.height = height;
int sx = width / 2;
int sy = height / 2;
body.addLast(new int[]{sx, sy});
bodySet.add(key(sx, sy));
direction = 0;
spawnFood();
}
private String key(int x, int y) {
return x + "," + y;
}
private void spawnFood() {
do {
foodX = rand.nextInt(width);
foodY = rand.nextInt(height);
} while (bodySet.contains(key(foodX, foodY)));
}
/**
* 执行动作：0=直行,1=右转,2=左转
* 返回是否存活
*/
public boolean step(int action) {
if (!alive) return false;
// 更新方向
if (action == 1) direction = (direction + 1) % 4; // 右转
else if (action == 2) direction = (direction + 3) % 4; // 左转
// action==0 直行，方向不变
int dx = 0, dy = 0;
switch (direction) {
case 0: dy = -1; break;
case 1: dx = 1; break;
case 2: dy = 1; break;
case 3: dx = -1; break;
}
int[] head = body.peekFirst();
int nx = head[0] + dx;
int ny = head[1] + dy;
// 撞墙
if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
alive = false;
return false;
}
// 撞自己（排除尾部，因为会移动）
String nk = key(nx, ny);
if (bodySet.contains(nk)) {
alive = false;
return false;
}
// 移动
body.addFirst(new int[]{nx, ny});
bodySet.add(nk);
if (nx == foodX && ny == foodY) {
score += 10;
movesLeft += 50; // 奖励额外步数
spawnFood();
} else {
int[] tail = body.pollLast();
bodySet.remove(key(tail[0], tail[1]));
movesLeft--;
}
if (movesLeft <= 0) alive = false;
return alive;
}
public int evaluateFitness() {
// fitness = 得分 * 100 + 移动步数 + 存活长度奖励
int len = body.size();
return score * 100 + Math.max(0, movesLeft) + len * len * 10;
}
public boolean isAlive() { return alive; }
public int getHeadX() { return body.peekFirst()[0]; }
public int getHeadY() { return body.peekFirst()[1]; }
public int getFoodX() { return foodX; }
public int getFoodY() { return foodY; }
public int getWidth() { return width; }
public int getHeight() { return height; }
public boolean isBody(int x, int y) { return bodySet.contains(key(x, y)); }
public int getSnakeLength() { return body.size(); }
}
五、遗传算法：选择、交叉与变异
核心思想：用神经网络的基因组作为”染色体”，fitness作为生存标准。
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
/**
* 遗传算法引擎
*/
public class GeneticAlgorithm {
private final int populationSize;
private final double mutationRate;
private final double crossoverRate;
private final Random rand = new Random();
private final int genomeSize;
private Individual[] population;
public GeneticAlgorithm(int populationSize, int genomeSize,
double mutationRate, double crossoverRate) {
this.populationSize = populationSize;
this.genomeSize = genomeSize;
this.mutationRate = mutationRate;
this.crossoverRate = crossoverRate;
this.population = new Individual[populationSize];
for (int i = 0; i < populationSize; i++) {
population[i] = new Individual(genomeSize);
}
}
/** 评估种群中每个个体的适应度 */
public void evaluate(SnakeGame prototype, int maxSteps) {
for (Individual ind : population) {
SnakeGame game = new SnakeGame(prototype.getWidth(), prototype.getHeight());
NeuralNetwork nn = new NeuralNetwork(24, 12, 3);
nn.setGenome(ind.genome);
SnakeSensor sensor = new SnakeSensor();
int steps = 0;
while (game.isAlive() && steps < maxSteps) {
double[] features = sensor.getFeatures(game);
double[] probs = nn.predict(features);
// 选择概率最大的动作
int action = 0;
if (probs[1] > probs[0] && probs[1] > probs[2]) action = 1;
else if (probs[2] > probs[0] && probs[2] > probs[1]) action = 2;
game.step(action);
steps++;
}
ind.fitness = game.evaluateFitness();
}
}
/** 生成下一代：保留精英 + 交叉 + 变异 */
public void evolve() {
Arrays.sort(population, Comparator.comparingInt((Individual a) -> a.fitness).reversed());
Individual[] nextGen = new Individual[populationSize];
int eliteCount = Math.max(1, populationSize / 10); // 保留前10%
for (int i = 0; i < eliteCount; i++) {
nextGen[i] = new Individual(population[i]);
}
for (int i = eliteCount; i < populationSize; i++) {
Individual parent1 = tournamentSelect(3);
Individual parent2 = tournamentSelect(3);
Individual child = crossover(parent1, parent2);
mutate(child);
nextGen[i] = child;
}
population = nextGen;
}
/** 锦标赛选择：从k个随机个体中选最优 */
private Individual tournamentSelect(int k) {
Individual best = population[rand.nextInt(populationSize)];
for (int i = 1; i < k; i++) {
Individual cand = population[rand.nextInt(populationSize)];
if (cand.fitness > best.fitness) best = cand;
}
return best;
}
/** 均匀交叉：逐基因随机选择来自哪个父代 */
private Individual crossover(Individual p1, Individual p2) {
Individual child = new Individual(genomeSize);
for (int i = 0; i < genomeSize; i++) {
child.genome[i] = (rand.nextDouble() < 0.5) ? p1.genome[i] : p2.genome[i];
}
return child;
}
/** 高斯变异：以mutationRate概率对每个基因添加小扰动 */
private void mutate(Individual ind) {
for (int i = 0; i < genomeSize; i++) {
if (rand.nextDouble() < mutationRate) {
ind.genome[i] += rand.nextGaussian() * 0.3;
// 限制权重范围，防止数值爆炸
ind.genome[i] = Math.max(-5.0, Math.min(5.0, ind.genome[i]));
}
}
}
public Individual getBest() {
return Arrays.stream(population)
.max(Comparator.comparingInt(a -> a.fitness))
.orElse(population[0]);
}
public double getAverageFitness() {
return Arrays.stream(population).mapToInt(a -> a.fitness).average().orElse(0);
}
static class Individual {
double[] genome;
int fitness;
Individual(int size) {
this.genome = new double[size];
Random r = new Random();
for (int i = 0; i < size; i++) genome[i] = r.nextDouble() * 2 - 1;
}
Individual(Individual other) {
this.genome = other.genome.clone();
this.fitness = other.fitness;
}
}
}
六、主程序：进化循环
/**
* 贪吃蛇神经进化主程序
*/
public class SnakeNeuroevolution {
public static void main(String[] args) {
final int POP_SIZE = 200;
final int GENOME_SIZE = new NeuralNetwork(24, 12, 3).getGenomeSize();
final int GENERATIONS = 500;
final int BOARD_W = 10;
final int BOARD_H = 10;
final int MAX_STEPS_PER_GAME = 200;
GeneticAlgorithm ga = new GeneticAlgorithm(POP_SIZE, GENOME_SIZE, 0.05, 0.7);
SnakeGame prototype = new SnakeGame(BOARD_W, BOARD_H);
System.out.println("=== 贪吃蛇神经进化开始 ===");
System.out.println("种群大小: " + POP_SIZE);
System.out.println("基因组长度: " + GENOME_SIZE);
System.out.println("变异率: 5%, 交叉率: 70%");
for (int gen = 1; gen <= GENERATIONS; gen++) {
ga.evaluate(prototype, MAX_STEPS_PER_GAME);
GeneticAlgorithm.Individual best = ga.getBest();
double avg = ga.getAverageFitness();
if (gen % 20 == 0 || gen == 1) {
System.out.printf("Generation %4d | Best Fitness: %6d | Avg Fitness: %8.1f%n",
gen, best.fitness, avg);
}
ga.evolve();
}
// 展示最优个体
System.out.println("\n=== 最优策略演示 ===");
GeneticAlgorithm.Individual champion = ga.getBest();
runDemo(champion.genome, BOARD_W, BOARD_H);
}
private static void runDemo(double[] genome, int w, int h) {
SnakeGame game = new SnakeGame(w, h);
NeuralNetwork nn = new NeuralNetwork(24, 12, 3);
nn.setGenome(genome);
SnakeSensor sensor = new SnakeSensor();
int steps = 0;
while (game.isAlive() && steps < 500) {
double[] feat = sensor.getFeatures(game);
double[] probs = nn.predict(feat);
int action = 0;
if (probs[1] > probs[0] && probs[1] > probs[2]) action = 1;
else if (probs[2] > probs[0] && probs[2] > probs[1]) action = 2;
game.step(action);
steps++;
}
System.out.println("演示结束 | 最终长度: " + game.getSnakeLength() + " | 存活步数: " + steps);
}
}
七、关键技巧：加速收敛的三个工程细节
1. 步数惩罚与奖励重置
引入movesLeft机制：每吃一个食物奖励额外步数，耗尽则死亡。这强制蛇必须积极寻找食物，而不是在安全区域无限绕圈。
2. 锦标赛选择替代轮盘赌
使用3人锦标赛选择而非轮盘赌，避免了早期超级个体垄断基因池的问题，保持种群多样性。
3. 权重截断与高斯变异
将权重限制在[-5, 5]范围内，配合N(0, 0.3)的高斯变异，既保证搜索空间足够大，又避免数值爆炸导致Sigmoid饱和。
八、复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 神经网络前向 | O(I·H + H·O) | I=24输入, H=12隐藏, O=3输出 |
| 单局模拟 | O(S·(I·H + H·O)) | S为最大步数 |
| 单代评估 | O(P·S·(I·H + H·O)) | P为种群大小 |
| 基因组长度 | O(I·H + H·O + H + O) | 约24×12+12×3+12+3=327 |
| 存储空间 | O(P·G) | G为基因组长度 |
九、扩展方向
- 引入精英保存与多样性维护：使用物种形成（Speciation）或新颖性搜索（Novelty Search），防止种群过早收敛到局部最优。
- 改进网络结构：尝试循环神经网络（RNN/LSTM），让蛇”记住”之前的路径，避免重复绕圈。
- 多目标进化：同时优化”吃食物速度”和”存活时间”，获得更稳健的策略。
- 可视化进化过程：用JavaFX或Swing渲染每一代最优蛇的行为，直观观察策略演变。
