游戏介绍
俄罗斯方块（Tetris）是1984年诞生的经典益智游戏，七种不同形状的方块（I、O、T、S、Z、J、L）从顶部下落，玩家可以旋转和左右移动方块，目标是填满整行以消除得分。本文用Java实现俄罗斯方块的AI自动玩家，核心是使用贪心策略评估每个落点的得分。
核心算法
状态评估函数
AI决策的关键是评估每个可能的落点状态，选取评分最高的动作。评估函数综合考虑以下因素：
1. ** Landing Height：方块落点高度（越低越好）
2. Eroded Piece Cells：消行时贡献的方块数（越多越好）
3. Row Transitions：行中空到填的转换次数（越少越好）
4. Column Transitions：列中空到填的转换次数（越少越好）
5. Holes：被覆盖的空洞数（越少越好）
6. Well Sums**：井的深度之和（越少越好）
贪心搜索
对每个新方块，枚举所有旋转和水平位置，模拟下落到底部，计算评估分数，选择最优落点。
Java实现
import java.util.*;
public class TetrisAI {
// 游戏板：宽10高20
static final int BOARD_WIDTH = 10;
static final int BOARD_HEIGHT = 20;
// 七种方块形状（以4x4矩阵表示）
static final int[][][][] SHAPES = {
// I
{{{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
{{{0,0,0,0}, {0,1,1,0}, {0,1,1,0}, {0,0,0,0}}},
// T
{{{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}},
{{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}}},
// S
{{{0,0,0,0}, {0,1,1,0}, {1,1,0,0}, {0,0,0,0}},
{{1,0,0,0}, {1,1,0,0}, {0,1,0,0}, {0,0,0,0}}},
// Z
{{{0,0,0,0}, {1,1,0,0}, {0,1,1,0}, {0,0,0,0}},
{{0,1,0,0}, {1,1,0,0}, {1,0,0,0}, {0,0,0,0}}},
// J
{{{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}},
{{1,0,0,0}, {1,1,1,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}}},
// L
{{{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}},
{{0,0,1,0}, {1,1,1,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}}}
};
// 评估权重（基于Pierre Dellacherie算法）
static final double W_LANDING_HEIGHT = -4.500158825082766;
static final double W_ERODED_CELLS = 3.4181268101392694;
static final double W_ROW_TRANSITIONS = -3.2178882868487753;
static final double W_COL_TRANSITIONS = -9.348695305445199;
static final double W_HOLES = -7.899265427351652;
static final double W_WELL_SUMS = -3.3855972247263626;
Random rand = new Random();
boolean[][] board = new boolean[BOARD_HEIGHT][BOARD_WIDTH];
int score = 0;
int lines = 0;
// 获取方块的某旋转状态下的有效单元格
List<int[]> getCells(int shapeIdx, int rot) {
List<int[]> cells = new ArrayList<>();
int[][] shape = SHAPES[shapeIdx][rot];
for (int y = 0; y < 4; y++) {
for (int x = 0; x < 4; x++) {
if (shape[y][x] == 1) cells.add(new int[]{x, y});
}
}
return cells;
}
// 模拟放置方块，返回（新棋盘，消除行数，落点高度）
Result simulatePlace(boolean[][] currentBoard, int shapeIdx, int rot, int offsetX) {
List<int[]> cells = getCells(shapeIdx, rot);
boolean[][] newBoard = copyBoard(currentBoard);
// 找到能放置的最低y位置
int minY = BOARD_HEIGHT;
for (int[] c : cells) {
int x = c[0] + offsetX;
if (x < 0 || x >= BOARD_WIDTH) return null; // 越界
// 从顶部开始向下找碰撞
for (int y = 0; y <= BOARD_HEIGHT; y++) {
int by = c[1] + y;
if (by >= BOARD_HEIGHT || currentBoard[by][x]) {
minY = Math.min(minY, y - 1);
break;
}
}
}
if (minY < 0) return null; // 无法放置
// 放置方块
int landingHeight = 0;
for (int[] c : cells) {
int x = c[0] + offsetX;
int y = c[1] + minY;
if (y < 0) return null;
newBoard[y][x] = true;
landingHeight = Math.max(landingHeight, BOARD_HEIGHT - y);
}
// 消除满行
int cleared = 0;
int erodedCells = 0;
for (int y = BOARD_HEIGHT - 1; y >= 0; y--) {
boolean full = true;
for (int x = 0; x < BOARD_WIDTH; x++) {
if (!newBoard[y][x]) { full = false; break; }
}
if (full) {
// 统计这行中被刚放置的方块数（简化：不精确追踪，用总消除行数估算）
erodedCells += 4; // 估算
cleared++;
// 下移所有行
for (int dy = y; dy > 0; dy--) {
System.arraycopy(newBoard[dy - 1], 0, newBoard[dy], 0, BOARD_WIDTH);
}
Arrays.fill(newBoard[0], false);
y++; // 重新检查当前行
}
}
return new Result(newBoard, cleared, landingHeight, erodedCells);
}
// 评估棋盘状态
double evaluate(boolean[][] b) {
// 1. Row Transitions
int rowTrans = 0;
for (int y = 0; y < BOARD_HEIGHT; y++) {
boolean prev = true; // 左边界外视为已填充
for (int x = 0; x < BOARD_WIDTH; x++) {
boolean curr = b[y][x];
if (curr != prev) rowTrans++;
prev = curr;
}
if (!prev) rowTrans++; // 右边界
}
// 2. Column Transitions
int colTrans = 0;
for (int x = 0; x < BOARD_WIDTH; x++) {
boolean prev = true; // 上边界外视为已填充
for (int y = 0; y < BOARD_HEIGHT; y++) {
boolean curr = b[y][x];
if (curr != prev) colTrans++;
prev = curr;
}
if (!prev) colTrans++; // 下边界
}
// 3. Holes（空洞：上方有填充但当前为空）
int holes = 0;
for (int x = 0; x < BOARD_WIDTH; x++) {
boolean filledAbove = false;
for (int y = 0; y < BOARD_HEIGHT; y++) {
if (b[y][x]) filledAbove = true;
else if (filledAbove) holes++;
}
}
// 4. Well Sums（井：两侧都被填充的连续空列段）
int wellSums = 0;
for (int x = 0; x < BOARD_WIDTH; x++) {
for (int y = 0; y < BOARD_HEIGHT; y++) {
if (!b[y][x]) {
boolean left = (x == 0) || b[y][x - 1];
boolean right = (x == BOARD_WIDTH - 1) || b[y][x + 1];
if (left && right) {
int depth = 1;
for (int dy = y + 1; dy < BOARD_HEIGHT && !b[dy][x]; dy++) {
boolean l = (x == 0) || b[dy][x - 1];
boolean r = (x == BOARD_WIDTH - 1) || b[dy][x + 1];
if (l && r) depth++;
else break;
}
wellSums += depth;
}
}
}
}
// 组合评分
return W_LANDING_HEIGHT * 0 +
W_ROW_TRANSITIONS * rowTrans +
W_COL_TRANSITIONS * colTrans +
W_HOLES * holes +
W_WELL_SUMS * wellSums;
}
// AI选择最佳动作
Move findBestMove(int shapeIdx) {
Move best = null;
double bestScore = Double.NEGATIVE_INFINITY;
int rotations = SHAPES[shapeIdx].length;
for (int rot = 0; rot < rotations; rot++) {
for (int x = -3; x < BOARD_WIDTH; x++) {
Result r = simulatePlace(board, shapeIdx, rot, x);
if (r == null) continue;
double score = evaluate(r.board);
// 奖励消行
score += W_ERODED_CELLS * r.cleared * 4;
score += W_LANDING_HEIGHT * (BOARD_HEIGHT - r.landingHeight);
if (score > bestScore) {
bestScore = score;
best = new Move(rot, x, r);
}
}
}
return best;
}
// 执行一步
boolean playStep() {
int shapeIdx = rand.nextInt(7);
Move move = findBestMove(shapeIdx);
if (move == null) return false; // 游戏结束
board = move.result.board;
lines += move.result.cleared;
score += move.result.cleared * move.result.cleared * 100;
return true;
}
// 打印棋盘
void printBoard() {
for (int y = 0; y < BOARD_HEIGHT; y++) {
for (int x = 0; x < BOARD_WIDTH; x++) {
System.out.print(board[y][x] ? "[]" : " .");
}
System.out.println();
}
System.out.println("Score: " + score + " Lines: " + lines);
System.out.println();
}
boolean[][] copyBoard(boolean[][] src) {
boolean[][] c = new boolean[BOARD_HEIGHT][BOARD_WIDTH];
for (int y = 0; y < BOARD_HEIGHT; y++) {
System.arraycopy(src[y], 0, c[y], 0, BOARD_WIDTH);
}
return c;
}
// 数据结构
static class Result {
boolean[][] board;
int cleared;
int landingHeight;
int erodedCells;
Result(boolean[][] b, int c, int h, int e) {
board = b; cleared = c; landingHeight = h; erodedCells = e;
}
}
static class Move {
int rotation, offsetX;
Result result;
Move(int r, int x, Result res) {
rotation = r; offsetX = x; result = res;
}
}
public static void main(String[] args) {
TetrisAI ai = new TetrisAI();
int steps = 0;
while (ai.playStep() && steps < 10000) {
steps++;
if (steps % 100 == 0) {
System.out.println("Step " + steps + " Lines: " + ai.lines);
}
}
System.out.println("Game Over! Steps: " + steps + " Lines: " + ai.lines + " Score: " + ai.score);
}
}
复杂度分析
- 单次评估时间：$O(WIDTH \times HEIGHT)$，即 $O(200)$
- 每方块搜索空间：最多4种旋转 $\times$ 约13个水平位置 = 52种放置方式
- 每步总复杂度：$O(52 \times WH) \approx O(10^4)$，现代计算机可轻松实时计算
- 整体游戏复杂度：随高度增加，搜索空间不变，评估效率恒定
总结
本文实现了基于Pierre Dellacherie评估函数的俄罗斯方块AI，通过六维特征评分选择最优落点。读者可以尝试调整权重参数、加入搜索深度（如lookahead多步）或使用遗传算法优化权重，进一步提升AI表现。
