每日算法 — 使用java实现俄罗斯方块：穷举落点搜索与多维度启发式评估AI决策

俄罗斯方块（Tetris）是1984年诞生的经典益智游戏，其核心魅力在于无限变化的方块组合与有限空间之间的博弈。本文将抛开遗传算法等进化策略，转而探讨一种确定性AI决策方案：通过穷举当前方块的所有合法落点，结合多维度状态评估函数，让AI在每一帧都能做出”当前最优”的放置决策。你会看到如何将一个看似复杂的游戏AI问题，拆解为可枚举的搜索空间与可量化的评分体系。

一、问题建模：将落点决策转化为搜索问题

俄罗斯方块的AI决策可以抽象为以下步骤：

1. 获取当前方块（7种形状之一，每个形状有4种旋转态）
2. 生成所有合法落点：对方块的每种旋转态，从顶部下落到所有可能的水平位置
3. 评估每个落点后的盘面状态：使用启发式函数给盘面打分
4. 选择评分最高的落点：作为AI的最终决策

穷举搜索的可行性在于：单种方块最多4种旋转 × 10列棋盘 = 40个候选落点。计算量极小，可在毫秒级完成决策。

二、核心数据结构：方块形状与游戏盘面

2.1 方块形状定义（7种经典方块）

每种方块用4×4的布尔矩阵表示，支持0°、90°、180°、270°四种旋转。

/**
 * 俄罗斯方块形状枚举，包含7种经典方块及其旋转矩阵
 * 每个形状用4x4布尔矩阵表示，true表示有方块占据
 */
public enum Tetromino {
    I(new int[][]{
        {0,0,0,0},
        {1,1,1,1},
        {0,0,0,0},
        {0,0,0,0}
    }),
    O(new int[][]{
        {1,1},
        {1,1}
    }),
    T(new int[][]{
        {0,1,0},
        {1,1,1},
        {0,0,0}
    }),
    S(new int[][]{
        {0,1,1},
        {1,1,0},
        {0,0,0}
    }),
    Z(new int[][]{
        {1,1,0},
        {0,1,1},
        {0,0,0}
    }),
    J(new int[][]{
        {1,0,0},
        {1,1,1},
        {0,0,0}
    }),
    L(new int[][]{
        {0,0,1},
        {1,1,1},
        {0,0,0}
    });

    private final int[][] shape;
    private final int size;

    Tetromino(int[][] shape) {
        this.shape = shape;
        this.size = shape.length;
    }

    public int[][] getShape() {
        return shape;
    }

    public int getSize() {
        return size;
    }

    /**
     * 顺时针旋转90度，返回新矩阵
     * 旋转公式：new[i][j] = old[size-1-j][i]
     */
    public static int[][] rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[i][j] = matrix[n - 1 - j][i];
            }
        }
        return rotated;
    }
}

2.2 游戏盘面与状态管理

/**
 * 俄罗斯方块游戏盘面，宽10列、高20行
 * 使用二维int数组表示，0为空，1为已固定方块
 */
public class Board {
    public static final int WIDTH = 10;
    public static final int HEIGHT = 20;
    private final int[][] grid;

    public Board() {
        this.grid = new int[HEIGHT][WIDTH];
    }

    /**
     * 复制构造函数，用于AI模拟落点后评估盘面
     */
    public Board(Board other) {
        this.grid = new int[HEIGHT][WIDTH];
        for (int i = 0; i < HEIGHT; i++) {
            System.arraycopy(other.grid[i], 0, this.grid[i], 0, WIDTH);
        }
    }

    /**
     * 检查指定位置和形状的方块是否与已有方块或边界碰撞
     */
    public boolean isCollision(int[][] shape, int row, int col) {
        int size = shape.length;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (shape[i][j] == 1) {
                    int r = row + i;
                    int c = col + j;
                    if (r < 0 || r >= HEIGHT || c < 0 || c >= WIDTH) {
                        return true; // 越界
                    }
                    if (grid[r][c] == 1) {
                        return true; // 碰撞
                    }
                }
            }
        }
        return false;
    }

    /**
     * 将方块固定到盘面
     */
    public void placePiece(int[][] shape, int row, int col) {
        int size = shape.length;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (shape[i][j] == 1) {
                    grid[row + i][col + j] = 1;
                }
            }
        }
    }

    /**
     * 清除已填满的行，返回清除行数
     */
    public int clearLines() {
        int linesCleared = 0;
        int writeRow = HEIGHT - 1;
        for (int row = HEIGHT - 1; row >= 0; row--) {
            boolean full = true;
            for (int col = 0; col < WIDTH; col++) {
                if (grid[row][col] == 0) {
                    full = false;
                    break;
                }
            }
            if (!full) {
                if (writeRow != row) {
                    System.arraycopy(grid[row], 0, grid[writeRow], 0, WIDTH);
                }
                writeRow--;
            } else {
                linesCleared++;
            }
        }
        // 清空顶部空出的行
        for (int row = writeRow; row >= 0; row--) {
            java.util.Arrays.fill(grid[row], 0);
        }
        return linesCleared;
    }

    /**
     * 找到方块在指定水平位置下的最终落点行
     */
    public int getDropRow(int[][] shape, int col) {
        int row = 0;
        while (!isCollision(shape, row + 1, col)) {
            row++;
        }
        return row;
    }

    public int[][] getGrid() {
        return grid;
    }
}

三、穷举搜索：生成所有合法落点

对于当前方块，AI需要遍历其所有旋转态和所有水平位置，生成候选落点列表。

import java.util.ArrayList;
import java.util.List;

/**
 * 候选落点描述，包含旋转后的形状、最终落点坐标、以及执行的旋转次数
 */
public record CandidateMove(int[][] shape, int finalRow, int finalCol, int rotations) {}

/**
 * 落点生成器：穷举当前方块在游戏盘面上的所有合法落点
 */
public class MoveGenerator {

    /**
     * 生成所有合法落点候选
     * @param board 当前盘面
     * @param piece 当前方块类型
     * @return 候选落点列表
     */
    public static List<CandidateMove> generateAllMoves(Board board, Tetromino piece) {
        List<CandidateMove> candidates = new ArrayList<>();
        int[][] currentShape = piece.getShape();

        // 遍历4种旋转状态
        for (int rot = 0; rot < 4; rot++) {
            int shapeSize = currentShape.length;

            // 遍历所有水平位置（考虑方块宽度可能越界）
            for (int col = -shapeSize + 1; col < Board.WIDTH; col++) {
                // 先检查方块是否能以当前旋转和位置放入顶部
                if (!board.isCollision(currentShape, 0, col)) {
                    int dropRow = board.getDropRow(currentShape, col);
                    candidates.add(new CandidateMove(
                        copyMatrix(currentShape), dropRow, col, rot
                    ));
                }
            }

            // 计算下一种旋转态
            currentShape = Tetromino.rotate(currentShape);

            // 若旋转回到初始状态（如O方块），提前终止
            if (java.util.Arrays.deepEquals(currentShape, piece.getShape())) {
                break;
            }
        }

        return candidates;
    }

    private static int[][] copyMatrix(int[][] src) {
        int[][] dst = new int[src.length][src.length];
        for (int i = 0; i < src.length; i++) {
            System.arraycopy(src[i], 0, dst[i], 0, src.length);
        }
        return dst;
    }
}

四、启发式评估函数：多维度盘面评分

评估函数是AI的”大脑”。本文采用6个维度的加权评分体系，综合衡量盘面的优劣。

4.1 评估指标设计

/**
 * 启发式评估器，对盘面状态进行多维度量化评分
 * 分数越高表示盘面状态越优
 */
public class HeuristicEvaluator {

    // 权重配置（通过调参或训练获得，此处为经验值）
    private static final double WEIGHT_LINES      =  5.0;  // 消行奖励
    private static final double WEIGHT_AGG_HEIGHT = -0.51; // 累计高度惩罚
    private static final double WEIGHT_HOLES      = -0.76; // 洞数惩罚
    private static final double WEIGHT_BUMPINESS  = -0.18; // 不平整惩罚
    private static final double WEIGHT_WELLS      = -0.35; // 井深惩罚
    private static final double WEIGHT_MAX_HEIGHT = -0.20; // 最高列惩罚

    /**
     * 评估盘面状态，返回综合评分
     */
    public static double evaluate(Board board, int linesCleared) {
        int[][] grid = board.getGrid();
        int[] heights = getColumnHeights(grid);

        double score = 0.0;
        score += WEIGHT_LINES * linesCleared;
        score += WEIGHT_AGG_HEIGHT * aggregateHeight(heights);
        score += WEIGHT_HOLES * countHoles(grid, heights);
        score += WEIGHT_BUMPINESS * bumpiness(heights);
        score += WEIGHT_WELLS * wellDepths(heights);
        score += WEIGHT_MAX_HEIGHT * maxHeight(heights);

        return score;
    }

    /**
     * 计算每列的有效高度（从底部向上第一个方块所在的行索引+1）
     */
    private static int[] getColumnHeights(int[][] grid) {
        int[] heights = new int[Board.WIDTH];
        for (int col = 0; col < Board.WIDTH; col++) {
            for (int row = 0; row < Board.HEIGHT; row++) {
                if (grid[row][col] == 1) {
                    heights[col] = Board.HEIGHT - row;
                    break;
                }
            }
        }
        return heights;
    }

    private static int aggregateHeight(int[] heights) {
        int sum = 0;
        for (int h : heights) sum += h;
        return sum;
    }

    private static int maxHeight(int[] heights) {
        int max = 0;
        for (int h : heights) max = Math.max(max, h);
        return max;
    }

    /**
     * 统计盘面中的"洞"：上方有方块覆盖的空格
     */
    private static int countHoles(int[][] grid, int[] heights) {
        int holes = 0;
        for (int col = 0; col < Board.WIDTH; col++) {
            int top = Board.HEIGHT - heights[col];
            for (int row = top + 1; row < Board.HEIGHT; row++) {
                if (grid[row][col] == 0) {
                    holes++;
                }
            }
        }
        return holes;
    }

    /**
     * 计算相邻列高度差的绝对值之和，衡量盘面平整度
     */
    private static int bumpiness(int[] heights) {
        int sum = 0;
        for (int i = 0; i < heights.length - 1; i++) {
            sum += Math.abs(heights[i] - heights[i + 1]);
        }
        return sum;
    }

    /**
     * 计算"井"的深度之和。
     * 井定义为：某一列比左右相邻列都深，差值即为井深。
     * 边界列只与内侧邻居比较。
     */
    private static int wellDepths(int[] heights) {
        int wellSum = 0;
        for (int i = 0; i < heights.length; i++) {
            int left = (i == 0) ? Integer.MAX_VALUE : heights[i - 1];
            int right = (i == heights.length - 1) ? Integer.MAX_VALUE : heights[i + 1];
            int minNeighbor = Math.min(left, right);
            if (heights[i] < minNeighbor) {
                wellSum += minNeighbor - heights[i];
            }
        }
        return wellSum;
    }
}

五、AI决策引擎：搜索+评估的完整闭环

/**
 * 俄罗斯方块AI决策引擎
 * 核心逻辑：穷举所有合法落点 → 模拟放置 → 评估盘面 → 选择最优
 */
public class TetrisAI {

    /**
     * 为当前方块选择最佳落点
     * @param board 当前盘面
     * @param piece 当前方块
     * @return 最佳落点，若无可行落点返回null
     */
    public CandidateMove findBestMove(Board board, Tetromino piece) {
        List<CandidateMove> candidates = MoveGenerator.generateAllMoves(board, piece);

        if (candidates.isEmpty()) {
            return null; // 游戏结束
        }

        CandidateMove bestMove = null;
        double bestScore = Double.NEGATIVE_INFINITY;

        for (CandidateMove move : candidates) {
            // 复制盘面进行模拟
            Board simulated = new Board(board);
            simulated.placePiece(move.shape(), move.finalRow(), move.finalCol());
            int lines = simulated.clearLines();

            // 评估模拟后的盘面
            double score = HeuristicEvaluator.evaluate(simulated, lines);

            if (score > bestScore) {
                bestScore = score;
                bestMove = move;
            }
        }

        return bestMove;
    }
}

六、可运行主程序：AI自动对战演示

import java.util.Random;

/**
 * 俄罗斯方块AI演示主程序
 * AI自动选择方块落点，统计存活步数与总消行数
 */
public class TetrisGame {
    private final Board board;
    private final TetrisAI ai;
    private final Random random;
    private int totalLinesCleared;
    private int stepsSurvived;

    public TetrisGame() {
        this.board = new Board();
        this.ai = new TetrisAI();
        this.random = new Random();
        this.totalLinesCleared = 0;
        this.stepsSurvived = 0;
    }

    /**
     * 执行单步：生成随机方块 → AI决策 → 放置 → 消行
     * @return 是否成功放置（false表示游戏结束）
     */
    public boolean step() {
        Tetromino[] pieces = Tetromino.values();
        Tetromino current = pieces[random.nextInt(pieces.length)];

        CandidateMove bestMove = ai.findBestMove(board, current);
        if (bestMove == null) {
            return false; // 无法放置，游戏结束
        }

        board.placePiece(bestMove.shape(), bestMove.finalRow(), bestMove.finalCol());
        int lines = board.clearLines();
        totalLinesCleared += lines;
        stepsSurvived++;

        return true;
    }

    public void runSimulation(int maxSteps) {
        System.out.println("=== 俄罗斯方块AI自动对战开始 ===\n");
        while (stepsSurvived < maxSteps && step()) {
            if (stepsSurvived % 100 == 0) {
                System.out.printf("步数: %d, 累计消行: %d%n", stepsSurvived, totalLinesCleared);
            }
        }
        System.out.printf("\n游戏结束！存活步数: %d, 总消行数: %d%n", stepsSurvived, totalLinesCleared);
    }

    /**
     * 打印当前盘面状态
     */
    public void printBoard() {
        int[][] grid = board.getGrid();
        System.out.println("+----------+");
        for (int row = 0; row < Board.HEIGHT; row++) {
            System.out.print("|");
            for (int col = 0; col < Board.WIDTH; col++) {
                System.out.print(grid[row][col] == 1 ? "[]" : "  ");
            }
            System.out.println("|");
        }
        System.out.println("+----------+");
    }

    public static void main(String[] args) {
        TetrisGame game = new TetrisGame();
        game.runSimulation(10000);
    }
}

七、权重调参策略

上述权重为经验值，实际效果取决于具体取值。调参思路如下：

1. 消行权重 应显著高于其他正向指标，因为它是游戏的核心目标
2. 洞数惩罚 通常应最严格，因为洞很难被后续消除，会长期恶化盘面
3. 累计高度与最高列 控制整体堆叠高度，防止过早触顶
4. Bumpiness与井深 保证盘面平整，为后续大方块（如I、O）预留放置空间

自动化调参可借助网格搜索或模拟退火：在大量随机对局中，搜索使平均存活步数最长的权重组合。

八、复杂度分析

本方案的优势在于零训练成本：无需预先生成种群、无需交叉变异迭代，每帧独立决策，逻辑透明、结果可复现。

九、进阶方向

1. 前瞻深度扩展：不仅评估当前方块，同时枚举下一个预览方块的落点，使用Minimax或期望极大化处理随机性
2. 动态权重调整：根据当前盘面高度和剩余空间，动态调整各维度权重
3. 模式识别：识别特定危险盘面构型（如”尖塔”、”深井”），施加额外惩罚

总结

本文通过穷举搜索将俄罗斯方块的AI决策问题转化为可控的计算任务，配合多维度启发式评估函数实现了零训练成本的确定性AI。核心代码不足300行，完整展现了搜索空间枚举、状态模拟、启发式评分三大环节。理解这套框架后，你可以轻松将其扩展到其他完美信息博弈游戏的AI设计中。