引言
俄罗斯方块（Tetris）是史上最经典的益智游戏之一。由于游戏状态空间巨大，传统的搜索算法难以应对。本文使用Java实现Pierre Dellacherie算法——这是目前已知最强的传统俄罗斯方块AI之一，通过6维特征向量的线性加权评估，在每一步选择最优的方块落点与旋转姿态。
算法核心思想
动作空间定义
俄罗斯方块的决策不仅包括移动方向，还包括旋转角度和最终落点。一个完整的动作定义为：
– 旋转次数（0~3）
– 水平偏移量（左移/右移格数）
– 硬降（直接落到底部）
Pierre Dellacherie评估函数
算法使用以下6个核心特征评估局面：
| 特征 | 符号 | 说明 |
|---|---|---|
| Landing Height | $LH$ | 方块落点中心的高度 |
| Eroded Piece Cells | $EPC$ | 消除行时属于当前方块的格子数 |
| Row Transitions | $RT$ | 行内空→满/满→空的切换次数 |
| Column Transitions | $CT$ | 列内空→满/满→空的切换次数 |
| Holes | $H$ | 被方块覆盖的空洞数量 |
| Board Wells | $BW$ | 井深之和（两侧有方块支撑的空列） |
总评分：$Score = \sum_{i} w_i \cdot f_i$
Java实现
游戏板与方块定义
import java.util.*;
public class TetrisDellacherie {
static final int ROWS = 20;
static final int COLS = 10;
// 7种经典方块的旋转形态（以4x4矩阵表示）
static final int[][][][] PIECES = {
// I-piece
{{{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}}},
// O-piece
{{{0,1,1,0},{0,1,1,0},{0,0,0,0},{0,0,0,0}}},
// T-piece
{{{0,1,0,0},{1,1,1,0},{0,0,0,0},{0,0,0,0}},
{{0,1,0,0},{0,1,1,0},{0,1,0,0},{0,0,0,0}},
{{0,0,0,0},{1,1,1,0},{0,1,0,0},{0,0,0,0}},
{{0,1,0,0},{1,1,0,0},{0,1,0,0},{0,0,0,0}}},
// S-piece
{{{0,1,1,0},{1,1,0,0},{0,0,0,0},{0,0,0,0}},
{{0,1,0,0},{0,1,1,0},{0,0,1,0},{0,0,0,0}}},
// Z-piece
{{{1,1,0,0},{0,1,1,0},{0,0,0,0},{0,0,0,0}},
{{0,0,1,0},{0,1,1,0},{0,1,0,0},{0,0,0,0}}},
// J-piece
{{{1,0,0,0},{1,1,1,0},{0,0,0,0},{0,0,0,0}},
{{0,1,1,0},{0,1,0,0},{0,1,0,0},{0,0,0,0}},
{{0,0,0,0},{1,1,1,0},{0,0,1,0},{0,0,0,0}},
{{0,1,0,0},{0,1,0,0},{1,1,0,0},{0,0,0,0}}},
// L-piece
{{{0,0,1,0},{1,1,1,0},{0,0,0,0},{0,0,0,0}},
{{0,1,0,0},{0,1,0,0},{0,1,1,0},{0,0,0,0}},
{{0,0,0,0},{1,1,1,0},{1,0,0,0},{0,0,0,0}},
{{1,1,0,0},{0,1,0,0},{0,1,0,0},{0,0,0,0}}}
};
static final String[] PIECE_NAMES = {"I","O","T","S","Z","J","L"};
// Dellacherie原始权重（经大量实验调优）
static final double[] WEIGHTS = {
-4.500158825082766, // Landing Height
3.4181268101392694, // Eroded Piece Cells
-3.2178882868487753, // Row Transitions
-9.348695305445199, // Column Transitions
-7.899265427351652, // Holes
-3.3855972247263626 // Board Wells
};
int[][] board = new int[ROWS][COLS];
int totalLines = 0;
int totalPieces = 0;
Random rand = new Random();
特征计算
/**
* 计算Landing Height：当前方块落点中心到板底的距离
*/
double computeLandingHeight(int pieceIdx, int rotation, int col, int landingRow) {
int[][] shape = PIECES[pieceIdx][rotation];
int minR = 3, maxR = 0;
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
if (shape[r][c] == 1) {
minR = Math.min(minR, r);
maxR = Math.max(maxR, r);
}
}
}
// 中心高度 = 落点行 + 形态中心偏移
return ROWS - (landingRow + minR) - (maxR - minR) / 2.0;
}
/**
* 计算Eroded Piece Cells：当前方块参与消除的格子数
*/
int computeErodedCells(int[][] tempBoard, int pieceIdx, int rotation,
int landingRow, int col, int linesCleared) {
if (linesCleared == 0) return 0;
int[][] shape = PIECES[pieceIdx][rotation];
int count = 0;
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
if (shape[r][c] == 1) {
int br = landingRow + r;
int bc = col + c;
// 检查该格子所在行是否被消除
boolean rowFull = true;
for (int cc = 0; cc < COLS; cc++) {
if (tempBoard[br][cc] == 0) {
rowFull = false;
break;
}
}
if (rowFull) count++;
}
}
}
return count * linesCleared;
}
/**
* 计算Row Transitions
*/
int computeRowTransitions(int[][] b) {
int transitions = 0;
for (int r = 0; r < ROWS; r++) {
int prev = 1; // 边界视为已填充
for (int c = 0; c < COLS; c++) {
int cell = b[r][c] != 0 ? 1 : 0;
if (cell != prev) transitions++;
prev = cell;
}
if (prev == 0) transitions++; // 右边界
}
return transitions;
}
/**
* 计算Column Transitions
*/
int computeColTransitions(int[][] b) {
int transitions = 0;
for (int c = 0; c < COLS; c++) {
int prev = 1; // 顶部边界视为已填充
for (int r = 0; r < ROWS; r++) {
int cell = b[r][c] != 0 ? 1 : 0;
if (cell != prev) transitions++;
prev = cell;
}
}
return transitions;
}
/**
* 计算Holes：空洞是被方块覆盖的空单元格
*/
int computeHoles(int[][] b) {
int holes = 0;
for (int c = 0; c < COLS; c++) {
boolean blockFound = false;
for (int r = 0; r < ROWS; r++) {
if (b[r][c] != 0) blockFound = true;
else if (blockFound) holes++;
}
}
return holes;
}
/**
* 计算Board Wells：井是两侧有方块支撑的空列段
*/
int computeWells(int[][] b) {
int wellSum = 0;
for (int c = 0; c < COLS; c++) {
for (int r = 0; r < ROWS; r++) {
if (b[r][c] == 0) {
boolean leftBlocked = (c == 0) || (b[r][c-1] != 0);
boolean rightBlocked = (c == COLS-1) || (b[r][c+1] != 0);
if (leftBlocked && rightBlocked) {
// 计算井深
int depth = 1;
for (int rr = r + 1; rr < ROWS && b[rr][c] == 0; rr++) {
boolean lb = (c == 0) || (b[rr][c-1] != 0);
boolean rb = (c == COLS-1) || (b[rr][c+1] != 0);
if (lb && rb) depth++;
else break;
}
wellSum += depth;
}
}
}
}
return wellSum;
}
动作模拟与最优决策
/**
* 模拟放置方块，返回(临时棋盘, 落点行, 消除行数)
*/
Object[] simulatePlace(int pieceIdx, int rotation, int col) {
int[][] temp = new int[ROWS][COLS];
for (int r = 0; r < ROWS; r++)
System.arraycopy(board[r], 0, temp[r], 0, COLS);
int[][] shape = PIECES[pieceIdx][rotation];
// 找到落点行
int landingRow = -1;
for (int startRow = 0; startRow <= ROWS - 4; startRow++) {
boolean canPlace = true;
for (int r = 0; r < 4 && canPlace; r++) {
for (int c = 0; c < 4; c++) {
if (shape[r][c] == 1) {
int br = startRow + r, bc = col + c;
if (br < 0 || br >= ROWS || bc < 0 || bc >= COLS || temp[br][bc] != 0) {
canPlace = false;
break;
}
}
}
}
if (canPlace) landingRow = startRow;
else break;
}
if (landingRow < 0) return null; // 无法放置
// 放置方块
for (int r = 0; r < 4; r++) {
for (int c = 0; c < 4; c++) {
if (shape[r][c] == 1) {
temp[landingRow + r][col + c] = pieceIdx + 1;
}
}
}
// 消除满行
int linesCleared = 0;
for (int r = ROWS - 1; r >= 0; r--) {
boolean full = true;
for (int c = 0; c < COLS; c++) {
if (temp[r][c] == 0) { full = false; break; }
}
if (full) {
linesCleared++;
// 下移行
for (int rr = r; rr > 0; rr--)
System.arraycopy(temp[rr-1], 0, temp[rr], 0, COLS);
Arrays.fill(temp[0], 0);
r++; // 重新检查当前行
}
}
return new Object[]{temp, landingRow, linesCleared};
}
/**
* 评估一个动作，返回分数（越高越好）
*/
double evaluateMove(int pieceIdx, int rotation, int col) {
Object[] result = simulatePlace(pieceIdx, rotation, col);
if (result == null) return Double.NEGATIVE_INFINITY;
int[][] temp = (int[][]) result[0];
int landingRow = (int) result[1];
int linesCleared = (int) result[2];
double lh = computeLandingHeight(pieceIdx, rotation, col, landingRow);
double epc = computeErodedCells(temp, pieceIdx, rotation, landingRow, col, linesCleared);
double rt = computeRowTransitions(temp);
double ct = computeColTransitions(temp);
double h = computeHoles(temp);
double bw = computeWells(temp);
return WEIGHTS[0] * lh + WEIGHTS[1] * epc + WEIGHTS[2] * rt
+ WEIGHTS[3] * ct + WEIGHTS[4] * h + WEIGHTS[5] * bw;
}
/**
* 寻找当前方块的最优放置方案
*/
int[] findBestMove(int pieceIdx) {
double bestScore = Double.NEGATIVE_INFINITY;
int bestRot = 0, bestCol = 0;
int rotations = PIECES[pieceIdx].length;
for (int rot = 0; rot < rotations; rot++) {
for (int col = -3; col < COLS; col++) {
double score = evaluateMove(pieceIdx, rot, col);
if (score > bestScore) {
bestScore = score;
bestRot = rot;
bestCol = col;
}
}
}
return new int[]{bestRot, bestCol};
}
游戏主循环
void playGame(int maxPieces) {
System.out.println("=== Tetris Dellacherie AI ===");
for (int i = 0; i < maxPieces; i++) {
int piece = rand.nextInt(7);
int[] move = findBestMove(piece);
Object[] result = simulatePlace(piece, move[0], move[1]);
if (result == null) {
System.out.println("游戏结束! 总消除行数: " + totalLines + ", 总方块数: " + totalPieces);
return;
}
board = (int[][]) result[0];
int lines = (int) result[2];
totalLines += lines;
totalPieces++;
if (lines > 0) {
System.out.printf("放置 %s, 消除 %d 行, 累计 %d 行%n",
PIECE_NAMES[piece], lines, totalLines);
}
}
System.out.println("完成! 总消除行数: " + totalLines + ", 总方块数: " + totalPieces);
}
public static void main(String[] args) {
TetrisDellacherie game = new TetrisDellacherie();
game.playGame(1000);
}
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 特征计算 | $O(ROWS \times COLS)$ | 遍历整个棋盘 |
| 单动作评估 | $O(ROWS \times COLS)$ | 模拟放置+特征提取 |
| 单方块决策 | $O(4 \times COLS \times ROWS \times COLS)$ | 最多4种旋转×10列 |
| 实际运行 | 约 $O(1)$ | 棋盘尺寸固定为20×10 |
总结
Pierre Dellacherie算法的精髓在于将复杂的俄罗斯方块决策问题转化为6维线性回归问题。通过精心设计的特征工程（Landing Height、Row Transitions等），算法无需前瞻搜索即可获得顶尖水平。读者可以在此基础上引入特征权重自适应调整（如CEM交叉熵方法）或结合深度强化学习，进一步提升AI的上限。
