每日算法 — 使用java实现俄罗斯方块：进化策略与协方差矩阵自适应评估

引言

俄罗斯方块（Tetris）是全球最经典的益智游戏之一，玩家需要控制下落的方块并合理摆放以消除完整行。设计一个高分的俄罗斯方块AI，核心在于评估每种落地方位的”局面价值”。本文采用进化策略（Evolution Strategy, ES）中的协方差矩阵自适应（CMA-ES）方法，自动优化局面评估函数的权重参数，让AI在进化中学会识别优质布局。

算法核心思想

传统俄罗斯方块AI通常依赖人工设计的评估特征（如高度、空洞数、平整度等）和固定权重。CMA-ES通过以下方式自动寻找最优权重：

• 参数编码：将评估函数的各项权重编码为实数向量
• 种群采样：根据多元正态分布采样多组权重参数
• 选择更新：保留表现好的样本，更新分布的均值和协方差矩阵
• 自适应步长：自动调整搜索步长，平衡探索与开发
• 协方差学习：通过成功样本的分布学习参数间的相关性

核心数据结构

import java.util.*;

/**
 * CMA-ES 俄罗斯方块AI
 */
public class CMAESTetris {

    // 游戏面板：宽10高20
    private static final int WIDTH = 10;
    private static final int HEIGHT = 20;

    // 七种方块形状（I, O, T, S, Z, J, L）
    private static final int[][][][] SHAPES = {
        // I
        {{{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 final Random random;
    private boolean[][] board;

    // CMA-ES参数
    private final int lambda;      // 后代数量
    private final int mu;          // 父代选择数量
    private final int dim;         // 权重维度（评估特征数）

    public CMAESTetris() {
        this.random = new Random();
        this.board = new boolean[HEIGHT][WIDTH];
        this.dim = 8; // 8个评估特征
        this.lambda = 20 + (int)(3 * Math.log(dim)); // 种群大小
        this.mu = lambda / 2;
    }

    /**
     * 局面评估特征向量
     */
    static class Features {
        double[] values;
        Features(int n) { values = new double[n]; }
    }

    /**
     * CMA-ES 状态
     */
    static class CMAState {
        double[] xmean;      // 分布均值
        double[] sigma;      // 步长（标量，这里简化为每个维度独立）
        double[][] C;        // 协方差矩阵
        double[] pc;         // 进化路径（协方差）
        double[] ps;         // 进化路径（步长）

        CMAState(int dim) {
            xmean = new double[dim];
            sigma = new double[dim];
            C = new double[dim][dim];
            pc = new double[dim];
            ps = new double[dim];
            for (int i = 0; i < dim; i++) {
                sigma[i] = 1.0;
                C[i][i] = 1.0;
            }
        }
    }

局面评估特征提取

    /**
     * 提取局面的8维特征向量
     */
    private Features extractFeatures(boolean[][] b) {
        Features f = new Features(dim);
        int[] heights = new int[WIDTH];

        // 1. 各列高度
        for (int c = 0; c < WIDTH; c++) {
            for (int r = 0; r < HEIGHT; r++) {
                if (b[r][c]) {
                    heights[c] = HEIGHT - r;
                    break;
                }
            }
        }

        // 特征1: 总高度之和（越小越好）
        double sumHeight = 0;
        for (int h : heights) sumHeight += h;
        f.values[0] = sumHeight;

        // 特征2: 最大高度（越小越好）
        double maxHeight = 0;
        for (int h : heights) maxHeight = Math.max(maxHeight, h);
        f.values[1] = maxHeight;

        // 特征3: 高度标准差（越平整越好）
        double avgHeight = sumHeight / WIDTH;
        double varHeight = 0;
        for (int h : heights) varHeight += Math.pow(h - avgHeight, 2);
        f.values[2] = Math.sqrt(varHeight / WIDTH);

        // 特征4: 空洞数量（上方有方块但当前为空）
        int holes = 0;
        for (int c = 0; c < WIDTH; c++) {
            boolean foundBlock = false;
            for (int r = 0; r < HEIGHT; r++) {
                if (b[r][c]) foundBlock = true;
                else if (foundBlock) holes++;
            }
        }
        f.values[3] = holes;

        // 特征5: 凸度/凹陷惩罚（相邻列高度差的绝对值之和）
        double bumpiness = 0;
        for (int c = 0; c < WIDTH - 1; c++) {
            bumpiness += Math.abs(heights[c] - heights[c + 1]);
        }
        f.values[4] = bumpiness;

        // 特征6: 可消除行数
        int completeLines = 0;
        for (int r = 0; r < HEIGHT; r++) {
            boolean complete = true;
            for (int c = 0; c < WIDTH; c++) {
                if (!b[r][c]) { complete = false; break; }
            }
            if (complete) completeLines++;
        }
        f.values[5] = completeLines;

        // 特征7: 井的深度（两侧高中间低的列深度之和）
        double wellDepth = 0;
        for (int c = 0; c < WIDTH; c++) {
            int leftH = (c > 0) ? heights[c - 1] : HEIGHT;
            int rightH = (c < WIDTH - 1) ? heights[c + 1] : HEIGHT;
            int minNeighbor = Math.min(leftH, rightH);
            if (heights[c] < minNeighbor) {
                wellDepth += minNeighbor - heights[c];
            }
        }
        f.values[6] = wellDepth;

        // 特征8: 当前方块放置后的接触面（与已有方块和边界的接触点数）
        // 此特征在评估具体放置时计算，这里预留
        f.values[7] = 0;

        return f;
    }

    /**
     * 使用权重向量评估局面得分
     * 分数越高越好
     */
    private double evaluateBoard(boolean[][] b, double[] weights) {
        Features f = extractFeatures(b);
        double score = 0;
        for (int i = 0; i < dim; i++) {
            score += weights[i] * f.values[i];
        }
        return score;
    }

方块放置模拟与AI决策

    /**
     * 给定当前面板和下落方块，评估所有可能的放置位置
     * @return 最优放置后的新局面和对应的权重评分
     */
    private PlacementResult findBestPlacement(boolean[][] currentBoard, int shapeType, double[] weights) {
        int[][][] rotations = SHAPES[shapeType];
        double bestScore = Double.NEGATIVE_INFINITY;
        boolean[][] bestBoard = null;
        int bestClears = 0;

        for (int rot = 0; rot < rotations.length; rot++) {
            int[][] shape = rotations[rot];
            int sh = shape.length;
            int sw = shape[0].length;

            // 尝试所有水平位置
            for (int col = 0; col <= WIDTH - sw; col++) {
                // 从顶部下落，找到落点
                int row = findDropRow(currentBoard, shape, col);
                if (row < 0 || row + sh > HEIGHT) continue;

                // 模拟放置
                boolean[][] simulated = copyBoard(currentBoard);
                for (int r = 0; r < sh; r++) {
                    for (int c = 0; c < sw; c++) {
                        if (shape[r][c] == 1) {
                            simulated[row + r][col + c] = true;
                        }
                    }
                }

                // 消除完整行
                int clears = clearLines(simulated);

                // 计算评分（消除行给予额外奖励）
                double score = evaluateBoard(simulated, weights) + clears * clears * 100;

                if (score > bestScore) {
                    bestScore = score;
                    bestBoard = simulated;
                    bestClears = clears;
                }
            }
        }

        return new PlacementResult(bestBoard, bestScore, bestClears);
    }

    private int findDropRow(boolean[][] b, int[][] shape, int col) {
        int sh = shape.length;
        int sw = shape[0].length;

        for (int row = 0; row <= HEIGHT - sh; row++) {
            // 检查下一行是否碰撞
            if (row + sh >= HEIGHT) return row;
            boolean collision = false;
            for (int r = 0; r < sh && !collision; r++) {
                for (int c = 0; c < sw; c++) {
                    if (shape[r][c] == 1 && b[row + sh][col + c]) {
                        collision = true;
                        break;
                    }
                }
            }
            if (collision) return row;
        }
        return -1;
    }

    private int clearLines(boolean[][] b) {
        int clears = 0;
        for (int r = HEIGHT - 1; r >= 0; r--) {
            boolean complete = true;
            for (int c = 0; c < WIDTH; c++) {
                if (!b[r][c]) { complete = false; break; }
            }
            if (complete) {
                // 删除该行，上方整体下移
                for (int rr = r; rr > 0; rr--) {
                    b[rr] = b[rr - 1].clone();
                }
                b[0] = new boolean[WIDTH];
                clears++;
                r++; // 重新检查当前行
            }
        }
        return clears;
    }

    private boolean[][] copyBoard(boolean[][] b) {
        boolean[][] copy = new boolean[HEIGHT][WIDTH];
        for (int r = 0; r < HEIGHT; r++) copy[r] = b[r].clone();
        return copy;
    }

    static class PlacementResult {
        boolean[][] board;
        double score;
        int linesCleared;
        PlacementResult(boolean[][] b, double s, int l) {
            board = b; score = s; linesCleared = l;
        }
    }

CMA-ES 进化核心

    /**
     * 使用CMA-ES进化最优权重
     */
    public double[] evolveWeights(int generations) {
        CMAState cma = new CMAState(dim);

        // 初始均值在0附近
        for (int i = 0; i < dim; i++) cma.xmean[i] = random.nextGaussian() * 0.1;

        double bestFitness = Double.NEGATIVE_INFINITY;
        double[] bestWeights = null;

        for (int gen = 0; gen < generations; gen++) {
            // 采样lambda个后代
            double[][] samples = new double[lambda][dim];
            double[] fitnesses = new double[lambda];

            for (int i = 0; i < lambda; i++) {
                // 多元正态分布采样（简化版：各维度独立）
                for (int d = 0; d < dim; d++) {
                    samples[i][d] = cma.xmean[d] + cma.sigma[d] * Math.sqrt(cma.C[d][d]) * random.nextGaussian();
                }
                fitnesses[i] = evaluateWeights(samples[i]);

                if (fitnesses[i] > bestFitness) {
                    bestFitness = fitnesses[i];
                    bestWeights = samples[i].clone();
                }
            }

            // 按适应度排序，选择前mu个
            Integer[] indices = new Integer[lambda];
            for (int i = 0; i < lambda; i++) indices[i] = i;
            Arrays.sort(indices, (a, b) -> Double.compare(fitnesses[b], fitnesses[a]));

            // 更新均值
            double[] oldMean = cma.xmean.clone();
            for (int d = 0; d < dim; d++) {
                cma.xmean[d] = 0;
                for (int i = 0; i < mu; i++) {
                    cma.xmean[d] += samples[indices[i]][d] / mu;
                }
            }

            // 更新协方差矩阵（简化版）
            for (int d1 = 0; d1 < dim; d1++) {
                for (int d2 = 0; d2 < dim; d2++) {
                    double cov = 0;
                    for (int i = 0; i < mu; i++) {
                        double diff1 = samples[indices[i]][d1] - oldMean[d1];
                        double diff2 = samples[indices[i]][d2] - oldMean[d2];
                        cov += diff1 * diff2 / mu;
                    }
                    cma.C[d1][d2] = 0.9 * cma.C[d1][d2] + 0.1 * cov;
                }
            }

            // 更新步长（自适应）
            for (int d = 0; d < dim; d++) {
                double successRate = 0;
                for (int i = 0; i < mu; i++) {
                    if (fitnesses[indices[i]] > bestFitness * 0.95) successRate++;
                }
                successRate /= mu;
                if (successRate > 0.2) {
                    cma.sigma[d] *= 1.1; // 成功率高，扩大搜索
                } else {
                    cma.sigma[d] *= 0.9; // 成功率低，缩小搜索
                }
                cma.sigma[d] = Math.max(0.01, Math.min(cma.sigma[d], 10.0));
            }

            if (gen % 50 == 0) {
                System.out.println("Gen " + gen + ", Best Fitness: " + String.format("%.1f", bestFitness));
            }
        }

        return bestWeights;
    }

    /**
     * 评估一组权重：进行多局游戏取平均得分
     */
    private double evaluateWeights(double[] weights) {
        int games = 3;
        double totalScore = 0;

        for (int g = 0; g < games; g++) {
            boolean[][] gameBoard = new boolean[HEIGHT][WIDTH];
            int score = 0;
            int pieces = 0;
            int maxPieces = 500; // 单局最多落块数

            while (pieces < maxPieces) {
                int shapeType = random.nextInt(SHAPES.length);
                PlacementResult result = findBestPlacement(gameBoard, shapeType, weights);

                if (result.board == null) break; // 无法放置，游戏结束

                gameBoard = result.board;
                score += result.linesCleared * result.linesCleared * 100 + 1;
                pieces++;
            }
            totalScore += score;
        }
        return totalScore / games;
    }

完整游戏演示

    /**
     * 使用最优权重运行完整游戏并展示结果
     */
    public void playWithWeights(double[] weights, int maxPieces) {
        board = new boolean[HEIGHT][WIDTH];
        int totalScore = 0;
        int totalLines = 0;

        System.out.println("=== CMA-ES 俄罗斯方块AI ===");

        for (int p = 0; p < maxPieces; p++) {
            int shapeType = random.nextInt(SHAPES.length);
            PlacementResult result = findBestPlacement(board, shapeType, weights);

            if (result.board == null) {
                System.out.println("Game Over at piece " + p);
                break;
            }

            board = result.board;
            totalScore += result.linesCleared * result.linesCleared * 100;
            totalLines += result.linesCleared;

            if (p % 100 == 99) {
                System.out.println("Pieces: " + (p + 1) + ", Lines: " + totalLines + ", Score: " + totalScore);
                printBoard();
            }
        }

        System.out.println("\nFinal Score: " + totalScore + ", Total Lines: " + totalLines);
        printBoard();
    }

    private void printBoard() {
        System.out.println("+" + "-".repeat(WIDTH) + "+");
        for (int r = 0; r < HEIGHT; r++) {
            System.out.print("|");
            for (int c = 0; c < WIDTH; c++) {
                System.out.print(board[r][c] ? "#" : " ");
            }
            System.out.println("|");
        }
        System.out.println("+" + "-".repeat(WIDTH) + "+");
    }

    public static void main(String[] args) {
        CMAESTetris ai = new CMAESTetris();

        System.out.println("=== 阶段1：CMA-ES进化权重 ===");
        double[] weights = ai.evolveWeights(300);

        System.out.println("\n=== 进化后的权重 ===");
        String[] names = {"总高度","最大高度","平整度","空洞数","凹凸度","可消行","井深度","接触面"};
        for (int i = 0; i < weights.length; i++) {
            System.out.println(names[i] + ": " + String.format("%.3f", weights[i]));
        }

        System.out.println("\n=== 阶段2：使用最优权重游戏 ===");
        ai.playWithWeights(weights, 1000);
    }
}

算法复杂度分析

其中 W=10, H=20, R=旋转数, P=落块数, L=lambda, D=维度, E=进化代数, G=评估局数。

总结

CMA-ES通过协方差矩阵自适应地调整搜索方向，能够高效地探索高维权重空间。在俄罗斯方块中，进化后的权重往往能学到”保持低高度、减少空洞、追求平整”等人类玩家凭直觉掌握的策略。相比手动调参，CMA-ES让AI自动发现最优评估策略，展现出进化计算的强大能力。