每日算法 — 使用java实现俄罗斯方块：模拟退火与多维度启发式评估优化

引言

俄罗斯方块（Tetris）是史上最经典的益智游戏之一。除了人类玩家的操作技巧外，如何用算法让AI自动玩好俄罗斯方块，一直是算法竞赛和人工智能领域的热门话题。本文将使用Java实现一个基于模拟退火（Simulated Annealing）优化的俄罗斯方块AI，通过多维度启发式评估函数，让算法在每一轮选择最优的方块落点与旋转姿态。

核心算法思路

模拟退火算法

模拟退火是一种受物理退火过程启发的随机优化算法。其核心思想是：在搜索初期允许接受较差的解，以跳出局部最优；随着”温度”逐渐降低，接受劣解的概率也随之下降，最终收敛到全局最优或近似最优解。

在俄罗斯方块场景中，我们将每个可能的落点与旋转姿态视为一个”解”，通过模拟退火动态调整评估函数的权重，使AI在不同游戏阶段表现出适应性。

多维度启发式评估

一个优秀的俄罗斯方块AI需要综合考虑以下因素：

• ** Landing Height**：方块落点高度，越低越好
• ** Row Transitions**：行内空位与实块的交替次数
• ** Column Transitions**：列内空位与实块的交替次数
• ** Holes**：被方块覆盖的空洞数量
• ** Well Sums**：深井（连续空列）的惩罚
• ** Line Clears**：消除行数的奖励

Java实现

核心数据结构

/**
 * 俄罗斯方块游戏面板
 */
public class TetrisBoard {
    private static final int WIDTH = 10;
    private static final int HEIGHT = 20;
    private boolean[][] board = new boolean[HEIGHT][WIDTH];

    /**
     * 检查某个位置是否合法
     */
    public boolean isValid(int x, int y) {
        return x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT && !board[y][x];
    }

    /**
     * 放置方块并返回消除的行数
     */
    public int placePiece(Piece piece, int offsetX, int offsetY) {
        // 将方块固定到面板
        for (int[] block : piece.getBlocks()) {
            int bx = block[0] + offsetX;
            int by = block[1] + offsetY;
            if (by >= 0 && by < HEIGHT && bx >= 0 && bx < WIDTH) {
                board[by][bx] = true;
            }
        }
        return clearLines();
    }

    /**
     * 消除满行并返回消除数量
     */
    private int clearLines() {
        int linesCleared = 0;
        for (int y = HEIGHT - 1; y >= 0; y--) {
            boolean full = true;
            for (int x = 0; x < WIDTH; x++) {
                if (!board[y][x]) {
                    full = false;
                    break;
                }
            }
            if (full) {
                // 将上方所有行下移
                for (int moveY = y; moveY > 0; moveY--) {
                    System.arraycopy(board[moveY - 1], 0, board[moveY], 0, WIDTH);
                }
                board[0] = new boolean[WIDTH];
                linesCleared++;
                y++; // 重新检查当前行
            }
        }
        return linesCleared;
    }

    /**
     * 复制当前面板状态
     */
    public TetrisBoard copy() {
        TetrisBoard copy = new TetrisBoard();
        for (int y = 0; y < HEIGHT; y++) {
            System.arraycopy(this.board[y], 0, copy.board[y], 0, WIDTH);
        }
        return copy;
    }

    // Getter方法
    public boolean[][] getBoard() { return board; }
    public int getWidth() { return WIDTH; }
    public int getHeight() { return HEIGHT; }
}

/**
 * 方块定义（包含7种基础形状）
 */
public class Piece {
    private int[][] blocks; // 相对坐标
    private int type;

    public static Piece[] getAllPieces() {
        return new Piece[] {
            new Piece(new int[][]{{0,0},{1,0},{2,0},{3,0}}, 0), // I
            new Piece(new int[][]{{0,0},{1,0},{0,1},{1,1}}, 1), // O
            new Piece(new int[][]{{1,0},{0,1},{1,1},{2,1}}, 2), // T
            new Piece(new int[][]{{0,0},{1,0},{1,1},{2,1}}, 3), // S
            new Piece(new int[][]{{1,0},{2,0},{0,1},{1,1}}, 4), // Z
            new Piece(new int[][]{{0,0},{0,1},{1,1},{2,1}}, 5), // J
            new Piece(new int[][]{{2,0},{0,1},{1,1},{2,1}}, 6), // L
        };
    }

    public Piece(int[][] blocks, int type) {
        this.blocks = blocks;
        this.type = type;
    }

    /**
     * 顺时针旋转90度
     */
    public Piece rotate() {
        if (type == 1) return this; // O型不旋转
        int[][] rotated = new int[blocks.length][2];
        for (int i = 0; i < blocks.length; i++) {
            rotated[i][0] = -blocks[i][1];
            rotated[i][1] = blocks[i][0];
        }
        return new Piece(normalize(rotated), type);
    }

    /**
     * 归一化坐标，使最小x,y为0
     */
    private int[][] normalize(int[][] coords) {
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
        for (int[] c : coords) {
            minX = Math.min(minX, c[0]);
            minY = Math.min(minY, c[1]);
        }
        int[][] result = new int[coords.length][2];
        for (int i = 0; i < coords.length; i++) {
            result[i][0] = coords[i][0] - minX;
            result[i][1] = coords[i][1] - minY;
        }
        return result;
    }

    public int[][] getBlocks() { return blocks; }
}

启发式评估函数

/**
 * 多维度启发式评估器
 */
public class HeuristicEvaluator {
    private double[] weights;

    public HeuristicEvaluator(double[] weights) {
        this.weights = weights;
    }

    /**
     * 计算面板得分（越高越好）
     */
    public double evaluate(TetrisBoard board) {
        boolean[][] b = board.getBoard();
        int width = board.getWidth();
        int height = board.getHeight();

        double aggregateHeight = 0;
        int holes = 0;
        int bumpiness = 0;
        int lineClears = 0;
        int maxHeight = 0;

        int[] columnHeights = new int[width];

        // 计算每列高度
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                if (b[y][x]) {
                    columnHeights[x] = height - y;
                    maxHeight = Math.max(maxHeight, columnHeights[x]);
                    break;
                }
            }
        }

        // 计算总高度和不平整度
        for (int x = 0; x < width; x++) {
            aggregateHeight += columnHeights[x];
            if (x > 0) {
                bumpiness += Math.abs(columnHeights[x] - columnHeights[x - 1]);
            }
        }

        // 计算空洞数
        for (int x = 0; x < width; x++) {
            boolean blockFound = false;
            for (int y = 0; y < height; y++) {
                if (b[y][x]) {
                    blockFound = true;
                } else if (blockFound) {
                    holes++;
                }
            }
        }

        // 计算消除行数（通过对比全空行变化来估算）
        // 实际游戏中在placePiece时已记录，此处简化处理

        return weights[0] * aggregateHeight +
               weights[1] * holes +
               weights[2] * bumpiness +
               weights[3] * lineClears +
               weights[4] * maxHeight;
    }

    public double[] getWeights() { return weights; }
    public void setWeights(double[] weights) { this.weights = weights; }
}

模拟退火优化器

import java.util.Random;

/**
 * 模拟退火权重优化器
 */
public class SimulatedAnnealingOptimizer {
    private static final Random random = new Random();
    private double initialTemp = 100.0;
    private double coolingRate = 0.995;
    private int iterations = 10000;

    /**
     * 优化评估权重
     * @param evaluator 当前评估器
     * @param board 测试面板
     * @param pieceSequence 测试方块序列
     * @return 优化后的评估器
     */
    public HeuristicEvaluator optimize(HeuristicEvaluator evaluator, 
                                        TetrisBoard board, 
                                        Piece[] pieceSequence) {
        double[] currentWeights = evaluator.getWeights().clone();
        double[] bestWeights = currentWeights.clone();
        double bestScore = simulateGame(board.copy(), pieceSequence, evaluator);

        double temp = initialTemp;

        for (int i = 0; i < iterations; i++) {
            // 生成邻域解：随机微调权重
            double[] newWeights = perturb(currentWeights);
            evaluator.setWeights(newWeights);
            double newScore = simulateGame(board.copy(), pieceSequence, evaluator);

            double delta = newScore - bestScore;

            // 模拟退火接受准则
            if (delta > 0 || random.nextDouble() < Math.exp(delta / temp)) {
                currentWeights = newWeights;
                if (newScore > bestScore) {
                    bestScore = newScore;
                    bestWeights = newWeights.clone();
                }
            }

            temp *= coolingRate;
        }

        evaluator.setWeights(bestWeights);
        return evaluator;
    }

    /**
     * 随机扰动权重
     */
    private double[] perturb(double[] weights) {
        double[] newWeights = weights.clone();
        int idx = random.nextInt(weights.length);
        newWeights[idx] += (random.nextDouble() - 0.5) * 0.5;
        return newWeights;
    }

    /**
     * 模拟一局游戏，返回得分
     */
    private double simulateGame(TetrisBoard board, Piece[] pieces, HeuristicEvaluator evaluator) {
        int totalLines = 0;
        int moves = 0;

        for (Piece piece : pieces) {
            Move bestMove = findBestMove(board, piece, evaluator);
            if (bestMove == null) break; // 游戏结束

            int lines = board.placePiece(bestMove.getPiece(), bestMove.getX(), bestMove.getY());
            totalLines += lines;
            moves++;
        }

        return totalLines * 100.0 + moves; // 综合评分
    }

    /**
     * 寻找当前方块的最优落点
     */
    private Move findBestMove(TetrisBoard board, Piece piece, HeuristicEvaluator evaluator) {
        Move bestMove = null;
        double bestScore = Double.NEGATIVE_INFINITY;

        // 尝试所有旋转
        for (int rot = 0; rot < 4; rot++) {
            Piece rotated = piece;
            for (int r = 0; r < rot; r++) {
                rotated = rotated.rotate();
            }

            // 尝试所有水平位置
            for (int x = -2; x < board.getWidth() + 2; x++) {
                // 寻找该x位置的最高落点
                int y = findDropPosition(board, rotated, x);
                if (y < 0) continue; // 无法放置

                TetrisBoard testBoard = board.copy();
                testBoard.placePiece(rotated, x, y);
                double score = evaluator.evaluate(testBoard);

                if (score > bestScore) {
                    bestScore = score;
                    bestMove = new Move(rotated, x, y);
                }
            }
        }

        return bestMove;
    }

    /**
     * 计算方块在指定x位置的落点y坐标
     */
    private int findDropPosition(TetrisBoard board, Piece piece, int offsetX) {
        boolean[][] b = board.getBoard();
        int height = board.getHeight();
        int[][] blocks = piece.getBlocks();

        for (int y = -4; y < height; y++) {
            // 检查下一行是否会碰撞
            boolean collision = false;
            for (int[] block : blocks) {
                int bx = block[0] + offsetX;
                int by = block[1] + y + 1;
                if (by >= height || (by >= 0 && bx >= 0 && bx < board.getWidth() && b[by][bx])) {
                    collision = true;
                    break;
                }
            }
            if (collision) {
                // 验证当前位置是否合法
                boolean valid = true;
                for (int[] block : blocks) {
                    int bx = block[0] + offsetX;
                    int by = block[1] + y;
                    if (by >= 0 && (bx < 0 || bx >= board.getWidth() || b[by][bx])) {
                        valid = false;
                        break;
                    }
                }
                return valid ? y : -1;
            }
        }
        return -1;
    }
}

/**
 * 落点动作封装
 */
class Move {
    private Piece piece;
    private int x, y;

    public Move(Piece piece, int x, int y) {
        this.piece = piece;
        this.x = x;
        this.y = y;
    }

    public Piece getPiece() { return piece; }
    public int getX() { return x; }
    public int getY() { return y; }
}

主程序入口

/**
 * 俄罗斯方块AI主程序
 */
public class TetrisAI {
    public static void main(String[] args) {
        // 初始化评估器（初始权重基于经验值）
        double[] initialWeights = {-0.51, -0.76, -0.18, 0.5, -0.35};
        HeuristicEvaluator evaluator = new HeuristicEvaluator(initialWeights);

        // 模拟退火优化
        SimulatedAnnealingOptimizer sa = new SimulatedAnnealingOptimizer();
        TetrisBoard testBoard = new TetrisBoard();
        Piece[] testSequence = generateRandomSequence(500);

        System.out.println("开始模拟退火优化...");
        evaluator = sa.optimize(evaluator, testBoard, testSequence);

        System.out.println("优化后的权重:");
        double[] optimized = evaluator.getWeights();
        System.out.printf("AggregateHeight: %.4f%n", optimized[0]);
        System.out.printf("Holes: %.4f%n", optimized[1]);
        System.out.printf("Bumpiness: %.4f%n", optimized[2]);
        System.out.printf("LineClears: %.4f%n", optimized[3]);
        System.out.printf("MaxHeight: %.4f%n", optimized[4]);

        // 运行一局完整游戏
        TetrisBoard gameBoard = new TetrisBoard();
        Piece[] gameSequence = generateRandomSequence(1000);
        int totalLines = 0;
        int totalMoves = 0;

        for (Piece piece : gameSequence) {
            // 这里简化处理，实际应调用findBestMove
            // 展示AI决策效果
            totalMoves++;
        }

        System.out.println("\n游戏结束！");
        System.out.println("总消除行数: " + totalLines);
        System.out.println("总步数: " + totalMoves);
    }

    private static Piece[] generateRandomSequence(int length) {
        Piece[] allPieces = Piece.getAllPieces();
        Piece[] sequence = new Piece[length];
        Random rand = new Random();
        for (int i = 0; i < length; i++) {
            sequence[i] = allPieces[rand.nextInt(allPieces.length)];
        }
        return sequence;
    }
}

算法复杂度分析

其中：W=10（面板宽度），H=20（面板高度），R=4（旋转次数），S=方块序列长度，I=迭代次数。

总结

本文通过Java实现了基于模拟退火的俄罗斯方块AI，核心要点包括：

• 多维度启发式评估综合考虑高度、空洞、平整度等因素
• 模拟退火动态优化评估权重，使AI适应不同游戏阶段
• 穷举搜索在所有可能的旋转和落点中寻找最优解

读者可以通过调整评估维度、退火参数和搜索策略，进一步优化AI的表现。模拟退火作为一种通用优化框架，也可应用于其他组合优化问题。