引言
俄罗斯方块是1984年由苏联科学家阿列克谢·帕基特诺夫发明的经典益智游戏，玩家通过旋转和移动下落的方块，使其在底部形成完整行以消除得分。设计一个强大的俄罗斯方块AI需要在实时性约束下做出最优决策——选择当前方块的最佳落点。本文介绍如何使用粒子群优化（Particle Swarm Optimization, PSO）算法离线训练评估函数的权重参数，让AI学会在多目标之间找到平衡：消除行数、保持平整、减少空洞、控制高度，最终得到一个能够持续生存并获得高分的智能玩家。
算法原理
俄罗斯方块评估指标
一个优秀的俄罗斯方块AI需要综合考虑以下维度：
- 着陆高度（Landing Height）：方块放置后的重心高度，越高越危险
- 消除行数（Rows Cleared）：一次性消除的行数，越多越好
- 行转换（Row Transitions）：同行中从有块到无块或反之的次数，反映平整度
- 列转换（Column Transitions）：同列中的类似转换
- 空洞数（Holes）：被方块覆盖的空格，一旦形成极难消除
- 井深（Well Sums）：深井（两侧高中间低）的累计深度，适度井有利于连续消行
- 最大高度（Max Height）：最高列的高度，过高则接近死亡
综合评估函数：
score = w1 * landingHeight + w2 * rowsCleared + w3 * rowTransitions
+ w4 * colTransitions + w5 * holes + w6 * wellSums + w7 * maxHeight
粒子群优化
PSO是一种群体智能优化算法，模拟鸟群捕食行为：
- 每个粒子代表一组权重参数 (w1, w2, …, w7)
- 粒子在搜索空间中飞行，速度受三个因素影响：
- 惯性：保持当前飞行方向
- 个体经验：向自己历史最优位置靠近
- 群体经验：向全局最优位置靠近
速度更新公式：
v[i] = w * v[i] + c1 * rand() * (pbest[i] - x[i]) + c2 * rand() * (gbest - x[i])
x[i] = x[i] + v[i]
AI决策流程
对于每个下落的方块：
1. 枚举所有可能的落点（所有旋转 × 所有水平位置）
2. 对每个落点，计算放置后的棋盘特征值
3. 使用评估函数计算得分
4. 选择得分最高的落点执行
Java实现
import java.util.*;
/**
* 俄罗斯方块AI - 粒子群优化训练评估函数
*/
public class TetrisPSO {
// 棋盘大小
private static final int BOARD_WIDTH = 10;
private static final int BOARD_HEIGHT = 20;
// 方块形状定义（7种经典方块，4种旋转）
private static final int[][][][] SHAPES = {
// I型
{{{1,1,1,1}},{{1},{1},{1},{1}}},
// O型
{{{1,1},{1,1}}},
// T型
{{{0,1,0},{1,1,1}},{{1,0},{1,1},{1,0}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}}},
// S型
{{{0,1,1},{1,1,0}},{{1,0},{1,1},{0,1}}},
// Z型
{{{1,1,0},{0,1,1}},{{0,1},{1,1},{1,0}}},
// J型
{{{1,0,0},{1,1,1}},{{1,1},{1,0},{1,0}},{{1,1,1},{0,0,1}},{{0,1},{0,1},{1,1}}},
// L型
{{{0,0,1},{1,1,1}},{{1,0},{1,0},{1,1}},{{1,1,1},{1,0,0}},{{1,1},{0,1},{0,1}}}
};
private static final String[] SHAPE_NAMES = {"I","O","T","S","Z","J","L"};
// 评估特征维度
private static final int FEATURE_DIM = 7;
// PSO参数
private static final int PARTICLE_COUNT = 30;
private static final int MAX_ITERATIONS = 100;
private static final double W_INERTIA = 0.7;
private static final double C1 = 1.5; // 个体学习因子
private static final double C2 = 1.5; // 社会学习因子
private static final double V_MAX = 2.0;
private Random random;
public TetrisPSO() {
this.random = new Random();
}
/**
* 表示一个粒子（一组权重参数）
*/
static class Particle {
double[] position; // 权重参数
double[] velocity;
double[] pbest; // 个体最优位置
double pbestScore; // 个体最优得分
Particle(int dim, Random rand) {
position = new double[dim];
velocity = new double[dim];
pbest = new double[dim];
for (int i = 0; i < dim; i++) {
position[i] = rand.nextDouble() * 2 - 1; // [-1, 1]
velocity[i] = rand.nextDouble() * 2 - 1;
pbest[i] = position[i];
}
pbestScore = -Double.MAX_VALUE;
}
}
/**
* 俄罗斯方块游戏模拟器
*/
class GameSimulator {
int[][] board;
int score;
int lines;
boolean gameOver;
GameSimulator() {
board = new int[BOARD_HEIGHT][BOARD_WIDTH];
score = 0;
lines = 0;
gameOver = false;
}
/**
* 复制棋盘
*/
int[][] copyBoard() {
int[][] copy = new int[BOARD_HEIGHT][BOARD_WIDTH];
for (int i = 0; i < BOARD_HEIGHT; i++) {
System.arraycopy(board[i], 0, copy[i], 0, BOARD_WIDTH);
}
return copy;
}
/**
* 检查方块是否可以放置在指定位置
*/
boolean canPlace(int[][] shape, int r, int c) {
for (int i = 0; i < shape.length; i++) {
for (int j = 0; j < shape[0].length; j++) {
if (shape[i][j] == 1) {
int nr = r + i, nc = c + j;
if (nr < 0 || nr >= BOARD_HEIGHT || nc < 0 || nc >= BOARD_WIDTH) {
return false;
}
if (board[nr][nc] == 1) {
return false;
}
}
}
}
return true;
}
/**
* 将方块放置到棋盘
*/
void place(int[][] shape, int r, int c) {
for (int i = 0; i < shape.length; i++) {
for (int j = 0; j < shape[0].length; j++) {
if (shape[i][j] == 1) {
board[r + i][c + j] = 1;
}
}
}
}
/**
* 消除完整行
*/
int clearLines() {
int cleared = 0;
for (int i = BOARD_HEIGHT - 1; i >= 0; i--) {
boolean full = true;
for (int j = 0; j < BOARD_WIDTH; j++) {
if (board[i][j] == 0) {
full = false;
break;
}
}
if (full) {
// 删除该行，顶部添加空行
for (int k = i; k > 0; k--) {
System.arraycopy(board[k - 1], 0, board[k], 0, BOARD_WIDTH);
}
board[0] = new int[BOARD_WIDTH];
cleared++;
i++; // 重新检查当前行
}
}
return cleared;
}
/**
* 找到方块下落的最终行
*/
int dropRow(int[][] shape, int c) {
int r = 0;
while (canPlace(shape, r + 1, c)) {
r++;
}
return r;
}
/**
* 计算评估特征
*/
double[] computeFeatures() {
double[] features = new double[FEATURE_DIM];
// 1. 最大高度
int maxHeight = 0;
for (int j = 0; j < BOARD_WIDTH; j++) {
for (int i = 0; i < BOARD_HEIGHT; i++) {
if (board[i][j] == 1) {
maxHeight = Math.max(maxHeight, BOARD_HEIGHT - i);
break;
}
}
}
features[6] = maxHeight;
// 2. 空洞数
int holes = 0;
for (int j = 0; j < BOARD_WIDTH; j++) {
boolean foundBlock = false;
for (int i = 0; i < BOARD_HEIGHT; i++) {
if (board[i][j] == 1) foundBlock = true;
else if (foundBlock) holes++;
}
}
features[4] = holes;
// 3. 行转换
int rowTransitions = 0;
for (int i = 0; i < BOARD_HEIGHT; i++) {
int prev = 1; // 边界视为有块
for (int j = 0; j < BOARD_WIDTH; j++) {
int curr = board[i][j];
if (curr != prev) rowTransitions++;
prev = curr;
}
if (prev != 1) rowTransitions++; // 右边界
}
features[2] = rowTransitions;
// 4. 列转换
int colTransitions = 0;
for (int j = 0; j < BOARD_WIDTH; j++) {
int prev = 1;
for (int i = 0; i < BOARD_HEIGHT; i++) {
int curr = board[i][j];
if (curr != prev) colTransitions++;
prev = curr;
}
if (prev != 1) colTransitions++;
}
features[3] = colTransitions;
// 5. 井深
int wellSums = 0;
for (int j = 0; j < BOARD_WIDTH; j++) {
for (int i = 0; i < BOARD_HEIGHT; i++) {
if (board[i][j] == 0) {
boolean leftWall = (j == 0) || (board[i][j - 1] == 1);
boolean rightWall = (j == BOARD_WIDTH - 1) || (board[i][j + 1] == 1);
if (leftWall && rightWall) {
int depth = 1;
for (int k = i + 1; k < BOARD_HEIGHT && board[k][j] == 0; k++) {
depth++;
}
wellSums += depth;
}
}
}
}
features[5] = wellSums;
// 着陆高度和消除行数在评估时动态计算
features[0] = 0;
features[1] = 0;
return features;
}
/**
* 使用给定权重评估一个落点
*/
double evaluatePlacement(int[][] shape, int r, int c, double[] weights) {
int[][] backup = copyBoard();
place(shape, r, c);
int cleared = clearLines();
double[] features = computeFeatures();
features[0] = r + shape.length / 2.0; // 着陆高度
features[1] = cleared * cleared * 10; // 消除行数（奖励连消）
double score = 0;
for (int i = 0; i < FEATURE_DIM; i++) {
score += weights[i] * features[i];
}
// 恢复棋盘
board = backup;
return score;
}
/**
* 为当前方块找到最佳落点
*/
int[] findBestMove(int shapeIdx, double[] weights) {
int[][][] rotations = SHAPES[shapeIdx];
double bestScore = -Double.MAX_VALUE;
int bestRot = 0, bestCol = 0;
for (int rot = 0; rot < rotations.length; rot++) {
int[][] shape = rotations[rot];
for (int c = -shape[0].length + 1; c < BOARD_WIDTH; c++) {
if (canPlace(shape, 0, c)) {
int r = dropRow(shape, c);
double score = evaluatePlacement(shape, r, c, weights);
if (score > bestScore) {
bestScore = score;
bestRot = rot;
bestCol = c;
}
}
}
}
return new int[]{bestRot, bestCol};
}
/**
* 执行一步游戏
*/
boolean step(int shapeIdx, double[] weights) {
if (gameOver) return false;
int[] move = findBestMove(shapeIdx, weights);
int[][] shape = SHAPES[shapeIdx][move[0]];
int c = move[1];
int r = dropRow(shape, c);
if (!canPlace(shape, r, c)) {
gameOver = true;
return false;
}
place(shape, r, c);
int cleared = clearLines();
lines += cleared;
score += cleared * cleared * 100;
return true;
}
}
/**
* 使用给定权重模拟一局游戏，返回得分
*/
private double simulateGame(double[] weights, int maxPieces) {
GameSimulator game = new GameSimulator();
int pieces = 0;
while (pieces < maxPieces && !game.gameOver) {
int shapeIdx = random.nextInt(SHAPES.length);
game.step(shapeIdx, weights);
pieces++;
}
// 综合评分：消除行数 + 生存步数 - 高度惩罚
return game.lines * 100 + pieces - game.computeFeatures()[6] * 2;
}
/**
* 粒子群优化训练
*/
public double[] train() {
Particle[] particles = new Particle[PARTICLE_COUNT];
for (int i = 0; i < PARTICLE_COUNT; i++) {
particles[i] = new Particle(FEATURE_DIM, random);
}
double[] gbest = new double[FEATURE_DIM];
double gbestScore = -Double.MAX_VALUE;
for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
for (Particle p : particles) {
// 评估当前位置（多次模拟取平均）
double totalScore = 0;
int games = 3;
for (int g = 0; g < games; g++) {
totalScore += simulateGame(p.position, 500);
}
double avgScore = totalScore / games;
// 更新个体最优
if (avgScore > p.pbestScore) {
p.pbestScore = avgScore;
System.arraycopy(p.position, 0, p.pbest, 0, FEATURE_DIM);
}
// 更新全局最优
if (avgScore > gbestScore) {
gbestScore = avgScore;
System.arraycopy(p.position, 0, gbest, 0, FEATURE_DIM);
}
}
// 更新粒子速度和位置
for (Particle p : particles) {
for (int d = 0; d < FEATURE_DIM; d++) {
double r1 = random.nextDouble();
double r2 = random.nextDouble();
p.velocity[d] = W_INERTIA * p.velocity[d]
+ C1 * r1 * (p.pbest[d] - p.position[d])
+ C2 * r2 * (gbest[d] - p.position[d]);
// 限制速度
p.velocity[d] = Math.max(-V_MAX, Math.min(V_MAX, p.velocity[d]));
p.position[d] += p.velocity[d];
// 限制位置范围
p.position[d] = Math.max(-5, Math.min(5, p.position[d]));
}
}
if (iter % 10 == 0) {
System.out.println("迭代 " + iter + ", 全局最优得分: " + String.format("%.2f", gbestScore));
System.out.println("权重: " + Arrays.toString(gbest));
}
}
System.out.println("训练完成！最优权重: " + Arrays.toString(gbest));
return gbest;
}
/**
* 使用训练好的权重运行完整游戏并可视化
*/
public void playWithWeights(double[] weights, int maxPieces) {
GameSimulator game = new GameSimulator();
int pieces = 0;
System.out.println("=== 俄罗斯方块AI演示 ===");
while (pieces < maxPieces && !game.gameOver) {
int shapeIdx = random.nextInt(SHAPES.length);
game.step(shapeIdx, weights);
pieces++;
if (pieces % 50 == 0) {
System.out.println("已放置 " + pieces + " 个方块，消除行数: " + game.lines);
}
}
System.out.println("\n游戏结束！");
System.out.println("总方块数: " + pieces);
System.out.println("消除行数: " + game.lines);
System.out.println("得分: " + game.score);
printBoard(game.board);
}
/**
* 打印棋盘
*/
private void printBoard(int[][] board) {
System.out.println("+" + "-".repeat(BOARD_WIDTH * 2 + 1) + "+");
for (int i = 0; i < BOARD_HEIGHT; i++) {
System.out.print("|");
for (int j = 0; j < BOARD_WIDTH; j++) {
System.out.print(board[i][j] == 1 ? "[]" : " ");
}
System.out.println("|");
}
System.out.println("+" + "-".repeat(BOARD_WIDTH * 2 + 1) + "+");
}
public static void main(String[] args) {
TetrisPSO tetris = new TetrisPSO();
// 训练阶段
System.out.println("=== PSO训练评估函数权重 ===");
double[] bestWeights = tetris.train();
// 演示阶段
System.out.println("\n=== 使用训练权重运行游戏 ===");
tetris.playWithWeights(bestWeights, 200);
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 落点枚举 | O(r × w) | r为旋转数，w为水平位置数 |
| 特征计算 | O(h × w) | h×w为棋盘大小 |
| 单步决策 | O(r × w × h × w) | 枚举所有落点并评估 |
| PSO迭代 | O(p × g × s) | p为粒子数，g为游戏模拟次数，s为步数 |
| 训练总时间 | 取决于参数 | 通常需要数分钟到数小时 |
PSO训练属于离线过程，实际游戏时仅需执行训练好的评估函数，决策速度极快。对于标准10×20的俄罗斯方块棋盘，每步决策可在毫秒级完成，完全满足实时性要求。
总结
本文展示了如何使用粒子群优化算法训练俄罗斯方块AI的评估函数权重。与传统的手动调参相比，PSO能够自动探索高维参数空间，找到使AI长期生存能力最大化的权重组合。核心设计包括：多维度特征提取（高度、空洞、平整度等）、粒子群的全局和局部搜索平衡、以及通过多次模拟取平均的鲁棒评估。读者可以进一步扩展特征维度（如引入棋盘轮廓方差、列高差异等），或尝试遗传算法、模拟退火等其他元启发式算法进行对比实验。
