一、问题背景
俄罗斯方块（Tetris）是1984年由阿列克谢·帕基特诺夫设计的经典益智游戏。七种不同形状的方块（I、J、L、O、S、T、Z）从顶部下落，玩家通过旋转和水平移动方块，使其在底部堆叠成完整行以消除得分。本文用Java实现一个AI自动玩俄罗斯方块，核心算法为深度神经网络（DNN）评估当前局面优劣，结合列生成启发式指导方块的最佳落点。
二、算法核心思想
2.1 局面特征提取
将当前棋盘状态转换为数值特征向量，供神经网络评估。常用特征包括：
– 列高：每列的堆叠高度
– 空洞数：列中被方块覆盖但下方有空位的格子数
– 平整度：相邻列高度差的绝对值之和（颠簸程度）
– 可消除行数：当前可立即消除的完整行数
– 最深层空洞：最深空洞的深度
– 列高方差：列高度的离散程度
2.2 深度神经网络评估
使用多层感知机（MLP）拟合一个评估函数 $V(s)$，输出当前局面的”价值”分数。网络结构为：
输入层(特征维度) → 隐藏层1(64, ReLU) → 隐藏层2(32, ReLU) → 输出层(1, 线性)
2.3 列生成启发式搜索
对于每个下落方块，枚举所有可能的旋转和水平位置，对每个落点模拟方块落下后的新盘面，用神经网络评估该盘面的价值，选择价值最高的落点：
$$a^* = \arg\max_{a \in A} V(\text{simulate}(s, a))$$
三、完整Java实现
import java.util.*;
/**
* 俄罗斯方块AI - 深度神经网络评估与列生成启发式
*/
public class TetrisDNN {
static final int ROWS = 20; // 棋盘行数
static final int COLS = 10; // 棋盘列数
static final int FEATURE_DIM = 8; // 特征维度
// ==================== 神经网络 ====================
static class NeuralNetwork {
int input, hidden1, hidden2, output;
double[][] W1, W2, W3;
double[] b1, b2, b3;
double lr;
Random rand;
public NeuralNetwork(int input, int h1, int h2, int output, double lr, long seed) {
this.input = input; this.hidden1 = h1; this.hidden2 = h2; this.output = output;
this.lr = lr; this.rand = new Random(seed);
W1 = new double[input][h1]; W2 = new double[h1][h2]; W3 = new double[h2][output];
b1 = new double[h1]; b2 = new double[h2]; b3 = new double[output];
initWeights(W1, input); initWeights(W2, h1); initWeights(W3, h2);
}
void initWeights(double[][] w, int fanIn) {
double scale = Math.sqrt(2.0 / fanIn);
for (int i = 0; i < w.length; i++)
for (int j = 0; j < w[i].length; j++)
w[i][j] = rand.nextGaussian() * scale;
}
double relu(double x) { return Math.max(0, x); }
double forward(double[] x) {
double[] h1 = new double[this.hidden1];
for (int j = 0; j < this.hidden1; j++) {
double sum = b1[j];
for (int i = 0; i < input; i++) sum += x[i] * W1[i][j];
h1[j] = relu(sum);
}
double[] h2 = new double[this.hidden2];
for (int j = 0; j < this.hidden2; j++) {
double sum = b2[j];
for (int i = 0; i < this.hidden1; i++) sum += h1[i] * W2[i][j];
h2[j] = relu(sum);
}
double out = b3[0];
for (int i = 0; i < this.hidden2; i++) out += h2[i] * W3[i][0];
return out;
}
}
// ==================== 方块定义 ====================
static class Piece {
int[][][] shapes; // [旋转][行][列]
char name;
public Piece(char name, int[][][] shapes) { this.name = name; this.shapes = shapes; }
}
static Piece[] PIECES = {
new Piece('I', new int[][][]{
{{0,0,0,0},{1,1,1,1},{0,0,0,0},{0,0,0,0}},
{{0,0,1,0},{0,0,1,0},{0,0,1,0},{0,0,1,0}},
}),
new Piece('O', new int[][][]{
{{1,1},{1,1}}
}),
new Piece('T', new int[][][]{
{{0,1,0},{1,1,1},{0,0,0}},
{{0,1,0},{0,1,1},{0,1,0}},
{{0,0,0},{1,1,1},{0,1,0}},
{{0,1,0},{1,1,0},{0,1,0}},
}),
new Piece('S', new int[][][]{
{{0,1,1},{1,1,0},{0,0,0}},
{{0,1,0},{0,1,1},{0,0,1}},
}),
new Piece('Z', new int[][][]{
{{1,1,0},{0,1,1},{0,0,0}},
{{0,0,1},{0,1,1},{0,1,0}},
}),
new Piece('J', new int[][][]{
{{1,0,0},{1,1,1},{0,0,0}},
{{0,1,1},{0,1,0},{0,1,0}},
{{0,0,0},{1,1,1},{0,0,1}},
{{0,1,0},{0,1,0},{1,1,0}},
}),
new Piece('L', new int[][][]{
{{0,0,1},{1,1,1},{0,0,0}},
{{0,1,0},{0,1,0},{0,1,1}},
{{0,0,0},{1,1,1},{1,0,0}},
{{1,1,0},{0,1,0},{0,1,0}},
}),
};
// ==================== 棋盘与环境 ====================
static class Board {
int[][] grid = new int[ROWS][COLS]; // 0=空, 1=有块
int score = 0;
int lines = 0;
/** 复制棋盘 */
Board copy() {
Board b = new Board();
for (int i = 0; i < ROWS; i++) System.arraycopy(grid[i], 0, b.grid[i], 0, COLS);
b.score = score; b.lines = lines;
return b;
}
/** 检查方块在指定位置是否合法 */
boolean isValid(Piece p, int rot, int row, int col) {
int[][] shape = p.shapes[rot];
for (int r = 0; r < shape.length; r++) {
for (int c = 0; c < shape[r].length; c++) {
if (shape[r][c] == 1) {
int nr = row + r, nc = col + c;
if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) return false;
if (grid[nr][nc] == 1) return false;
}
}
}
return true;
}
/** 将方块放置到棋盘（不检查合法性） */
void place(Piece p, int rot, int row, int col) {
int[][] shape = p.shapes[rot];
for (int r = 0; r < shape.length; r++) {
for (int c = 0; c < shape[r].length; c++) {
if (shape[r][c] == 1) grid[row + r][col + c] = 1;
}
}
}
/** 方块从顶部下落到最低位置 */
int drop(Piece p, int rot, int col) {
int row = 0;
while (isValid(p, rot, row + 1, col)) row++;
return row;
}
/** 模拟放置并消除完整行，返回消除行数 */
int placeAndClear(Piece p, int rot, int row, int col) {
place(p, rot, row, col);
int cleared = 0;
for (int r = ROWS - 1; r >= 0; r--) {
boolean full = true;
for (int c = 0; c < COLS; c++) if (grid[r][c] == 0) { full = false; break; }
if (full) {
// 删除该行，上方整体下移
for (int rr = r; rr > 0; rr--) System.arraycopy(grid[rr - 1], 0, grid[rr], 0, COLS);
Arrays.fill(grid[0], 0);
cleared++;
r++; // 重新检查当前行
}
}
return cleared;
}
/** 提取8维特征向量 */
double[] extractFeatures() {
double[] feat = new double[FEATURE_DIM];
int[] heights = new int[COLS];
for (int c = 0; c < COLS; c++) {
for (int r = 0; r < ROWS; r++) {
if (grid[r][c] == 1) { heights[c] = ROWS - r; break; }
}
}
// 1. 总高度
double totalHeight = 0;
for (int h : heights) totalHeight += h;
feat[0] = totalHeight / ROWS;
// 2. 空洞数
int holes = 0;
for (int c = 0; c < COLS; c++) {
boolean seen = false;
for (int r = 0; r < ROWS; r++) {
if (grid[r][c] == 1) seen = true;
else if (seen) holes++;
}
}
feat[1] = holes / 10.0;
// 3. 颠簸度（相邻列高度差之和）
double bumpiness = 0;
for (int c = 0; c < COLS - 1; c++) bumpiness += Math.abs(heights[c] - heights[c + 1]);
feat[2] = bumpiness / ROWS;
// 4. 最大高度
int maxH = 0;
for (int h : heights) maxH = Math.max(maxH, h);
feat[3] = maxH / (double) ROWS;
// 5. 可消除行数（当前已有完整行数）
int clearable = 0;
for (int r = 0; r < ROWS; r++) {
boolean full = true;
for (int c = 0; c < COLS; c++) if (grid[r][c] == 0) { full = false; break; }
if (full) clearable++;
}
feat[4] = clearable / 4.0;
// 6. 列高方差
double mean = totalHeight / COLS;
double var = 0;
for (int h : heights) var += (h - mean) * (h - mean);
feat[5] = var / (COLS * ROWS * ROWS);
// 7. 最宽空列
int maxEmptyCol = 0;
for (int c = 0; c < COLS; c++) {
int empty = 0;
for (int r = 0; r < ROWS; r++) if (grid[r][c] == 0) empty++;
maxEmptyCol = Math.max(maxEmptyCol, empty);
}
feat[6] = maxEmptyCol / (double) ROWS;
// 8. 井深（两侧高中间低的列深度之和）
double wellSum = 0;
for (int c = 0; c < COLS; c++) {
int leftH = (c > 0) ? heights[c - 1] : ROWS;
int rightH = (c < COLS - 1) ? heights[c + 1] : ROWS;
int well = Math.min(leftH, rightH) - heights[c];
if (well > 0) wellSum += well;
}
feat[7] = wellSum / ROWS;
return feat;
}
/** 检查游戏是否结束（顶部有方块） */
boolean isGameOver() {
for (int c = 0; c < COLS; c++) if (grid[0][c] == 1) return true;
return false;
}
}
// ==================== AI决策器 ====================
static class TetrisAI {
NeuralNetwork net;
Random rand = new Random();
public TetrisAI(NeuralNetwork net) { this.net = net; }
/** 为当前方块选择最佳落点，返回[旋转, 列] */
int[] chooseAction(Board board, Piece piece) {
double bestScore = Double.NEGATIVE_INFINITY;
int bestRot = 0, bestCol = 0;
for (int rot = 0; rot < piece.shapes.length; rot++) {
int width = piece.shapes[rot][0].length;
for (int col = -2; col <= COLS; col++) {
if (!board.isValid(piece, rot, 0, col)) continue;
int row = board.drop(piece, rot, col);
if (!board.isValid(piece, rot, row, col)) continue;
Board sim = board.copy();
int cleared = sim.placeAndClear(piece, rot, row, col);
double[] feat = sim.extractFeatures();
double value = net.forward(feat);
// 加分项：消除的行数带来额外奖励
double bonus = cleared * cleared * 10;
double score = value + bonus;
if (score > bestScore) {
bestScore = score;
bestRot = rot;
bestCol = col;
}
}
}
return new int[]{bestRot, bestCol};
}
}
// ==================== 训练与评估 ====================
public static void main(String[] args) {
// 使用预训练权重（实际训练中可用遗传算法或策略梯度优化网络参数）
// 这里使用手工调优的启发式权重作为基线，演示网络结构
NeuralNetwork net = new NeuralNetwork(FEATURE_DIM, 64, 32, 1, 0.001, 42);
// 手工设置一组表现较好的权重作为演示（实际应通过训练获得）
// 负权重表示惩罚：高度、空洞、颠簸、最大高度都是负面特征
// 消除行、空列、井是正面或中性特征
net.W1[0][0] = -0.5; // 总高度 -> 负面
net.W1[1][0] = -2.0; // 空洞 -> 强负面
net.W1[2][0] = -0.8; // 颠簸 -> 负面
net.W1[3][0] = -1.0; // 最大高度 -> 负面
net.W1[4][0] = 2.0; // 可消除行 -> 正面
net.W1[5][0] = -0.3; // 方差 -> 轻微负面
net.W1[6][0] = 0.2; // 空列 -> 轻微正面
net.W1[7][0] = -0.4; // 井深 -> 轻微负面
// 简单演示：运行一局游戏
Board board = new Board();
TetrisAI ai = new TetrisAI(net);
Random rand = new Random(123);
int totalPieces = 0;
while (!board.isGameOver() && totalPieces < 10000) {
Piece piece = PIECES[rand.nextInt(PIECES.length)];
int[] action = ai.chooseAction(board, piece);
int row = board.drop(piece, action[0], action[1]);
int cleared = board.placeAndClear(piece, action[0], row, action[1]);
board.lines += cleared;
board.score += cleared * cleared * 100;
totalPieces++;
}
System.out.println("游戏结束！");
System.out.println("放置方块数: " + totalPieces);
System.out.println("消除行数: " + board.lines);
System.out.println("最终得分: " + board.score);
printBoard(board);
}
static void printBoard(Board b) {
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++)
System.out.print(b.grid[r][c] == 1 ? "#" : ".");
System.out.println();
}
}
}
四、网络训练策略
上述代码使用手工权重演示网络结构。实际训练中，可通过以下方式获得优质权重：
- 遗传算法进化：将网络权重编码为染色体，通过多代选择、交叉、变异，保留能消除最多行的个体。
- 策略梯度：让AI自我对弈，以最终得分为奖励信号，通过REINFORCE算法更新网络参数。
- 模仿学习：记录人类玩家的操作序列，用监督学习拟合状态到动作的映射。
五、算法复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 特征提取 | $O(R \cdot C)$ | 遍历整个棋盘 |
| 神经网络前向 | $O(H_1 \cdot I + H_2 \cdot H_1)$ | 固定结构，常数时间 |
| 枚举落点 | $O(Rot \cdot C \cdot (R \cdot C))$ | 每种旋转和水平位置 |
| 单行消除 | $O(R \cdot C)$ | 移动上方行 |
其中 $R=20, C=10, Rot \leq 4$，整体每步决策在毫秒级完成。
六、总结
本文实现了基于深度神经网络评估的俄罗斯方块AI：
– 特征工程：提取8维关键特征，将高维棋盘状态压缩为低维向量
– 神经网络：三层MLP拟合局面价值函数，量化当前盘面的优劣
– 列生成搜索：枚举所有合法落点，用网络评估落子后的局面，贪心选择最优
– 扩展方向：可引入CNN自动提取空间特征、或结合MCTS进行多步 lookahead
该框架将传统启发式评估升级为数据驱动的神经网络评估，具备良好的泛化能力。
