每日算法 — 使用java实现俄罗斯方块：贪心评估函数与AI自动下落

可莉爸爸 AI算法

引言

俄罗斯方块（Tetris）是全球最知名的益智游戏之一，玩家通过旋转和移动下落的方块，使其在底部拼成完整的行以消除得分。随着游戏进行，速度逐渐加快，对玩家的反应和策略提出极高要求。本文将使用Java实现一个带AI的俄罗斯方块游戏，核心采用贪心评估函数对每种可能的落点进行打分，自动选择最优旋转位置和水平位移，实现远超人类的长时间存活能力。

问题建模

游戏场地为10列×20行的网格。七种标准方块（I、O、T、S、Z、J、L）从顶部随机生成并下落。每个方块有若干种旋转形态，可左右移动。

AI需要在每个新方块生成时，在有限时间内决策：
1. 选择旋转角度（0°、90°、180°、270°）
2. 选择水平落点（0-9列）
3. 评估该落点对场面的长期影响

核心算法设计

1. 场地状态与方块表示

import java.util.*;

/**
 * 俄罗斯方块游戏场地与状态管理
 */
public class TetrisBoard {
    public static final int COLS = 10;
    public static final int ROWS = 20;

    private int[][] grid; // 0为空，1为已固定方块
    private int score;
    private int linesCleared;

    public TetrisBoard() {
        this.grid = new int[ROWS][COLS];
        this.score = 0;
        this.linesCleared = 0;
    }

    public int[][] getGrid() { return grid; }
    public int getScore() { return score; }
    public int getLinesCleared() { return linesCleared; }

    /**
     * 检查某旋转形态的方块能否放置在指定位置
     */
    public boolean canPlace(Piece piece, int rotation, int col, int row) {
        int[][] shape = piece.getShape(rotation);
        for (int r = 0; r < shape.length; r++) {
            for (int c = 0; c < shape[0].length; c++) {
                if (shape[r][c] == 1) {
                    int nr = row + r;
                    int nc = col + c;
                    if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) {
                        return false;
                    }
                    if (grid[nr][nc] == 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 计算方块从顶部某列下落的最终行位置
     */
    public int getDropRow(Piece piece, int rotation, int col) {
        int row = 0;
        while (canPlace(piece, rotation, col, row + 1)) {
            row++;
        }
        return row;
    }

    /**
     * 将方块固定到场地，并清除完整行
     * @return 消除的行数
     */
    public int placePiece(Piece piece, int rotation, int col, int row) {
        int[][] shape = piece.getShape(rotation);
        for (int r = 0; r < shape.length; r++) {
            for (int c = 0; c < shape[0].length; c++) {
                if (shape[r][c] == 1) {
                    grid[row + r][col + c] = 1;
                }
            }
        }
        return clearLines();
    }

    /**
     * 清除完整行并返回清除数量
     */
    private int clearLines() {
        int cleared = 0;
        int writeRow = ROWS - 1;

        for (int r = ROWS - 1; r >= 0; r--) {
            boolean full = true;
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 0) {
                    full = false;
                    break;
                }
            }
            if (!full) {
                if (writeRow != r) {
                    System.arraycopy(grid[r], 0, grid[writeRow], 0, COLS);
                }
                writeRow--;
            } else {
                cleared++;
            }
        }

        // 清空顶部行
        for (int r = 0; r <= writeRow; r++) {
            Arrays.fill(grid[r], 0);
        }

        linesCleared += cleared;
        score += calculateScore(cleared);
        return cleared;
    }

    private int calculateScore(int lines) {
        switch (lines) {
            case 1: return 100;
            case 2: return 300;
            case 3: return 500;
            case 4: return 800;
            default: return 0;
        }
    }

    /**
     * 创建场地副本（用于AI评估）
     */
    public TetrisBoard copy() {
        TetrisBoard copy = new TetrisBoard();
        for (int r = 0; r < ROWS; r++) {
            System.arraycopy(this.grid[r], 0, copy.grid[r], 0, COLS);
        }
        copy.score = this.score;
        copy.linesCleared = this.linesCleared;
        return copy;
    }
}

/**
 * 方块定义
 */
class Piece {
    private String name;
    private int[][][] rotations; // [rotation][row][col]

    public Piece(String name, int[][][] rotations) {
        this.name = name;
        this.rotations = rotations;
    }

    public String getName() { return name; }
    public int[][] getShape(int rotation) {
        return rotations[rotation % rotations.length];
    }
    public int getRotationCount() { return rotations.length; }

    // 七种标准方块
    public static final Piece I = new Piece("I", new int[][][]{
        {{1,1,1,1}},
        {{1},{1},{1},{1}}
    });
    public static final Piece O = new Piece("O", new int[][][]{
        {{1,1},{1,1}}
    });
    public static final Piece T = new Piece("T", new int[][][]{
        {{0,1,0},{1,1,1}},
        {{1,0},{1,1},{1,0}},
        {{1,1,1},{0,1,0}},
        {{0,1},{1,1},{0,1}}
    });
    public static final Piece S = new Piece("S", new int[][][]{
        {{0,1,1},{1,1,0}},
        {{1,0},{1,1},{0,1}}
    });
    public static final Piece Z = new Piece("Z", new int[][][]{
        {{1,1,0},{0,1,1}},
        {{0,1},{1,1},{1,0}}
    });
    public static final Piece J = new Piece("J", new int[][][]{
        {{1,0,0},{1,1,1}},
        {{1,1},{1,0},{1,0}},
        {{1,1,1},{0,0,1}},
        {{0,1},{0,1},{1,1}}
    });
    public static final Piece L = new Piece("L", new int[][][]{
        {{0,0,1},{1,1,1}},
        {{1,0},{1,0},{1,1}},
        {{1,1,1},{1,0,0}},
        {{1,1},{0,1},{0,1}}
    });

    public static final Piece[] ALL_PIECES = {I, O, T, S, Z, J, L};
}

2. 贪心评估函数

/**
 * 俄罗斯方块AI评估器
 * 基于贪心策略的落点评估
 */
public class TetrisAI {

    // 评估权重（通过大量实验调优）
    private static final double WEIGHT_AGGREGATE_HEIGHT = -0.51;
    private static final double WEIGHT_COMPLETE_LINES = 0.76;
    private static final double WEIGHT_HOLES = -0.36;
    private static final double WEIGHT_BUMPINESS = -0.18;

    /**
     * 为给定场地状态计算综合评分
     * 分数越高表示该状态越优
     */
    public double evaluateBoard(TetrisBoard board) {
        int[][] grid = board.getGrid();

        int aggregateHeight = getAggregateHeight(grid);
        int completeLines = getCompleteLines(grid);
        int holes = getHoles(grid);
        int bumpiness = getBumpiness(grid);

        return WEIGHT_AGGREGATE_HEIGHT * aggregateHeight
             + WEIGHT_COMPLETE_LINES * completeLines
             + WEIGHT_HOLES * holes
             + WEIGHT_BUMPINESS * bumpiness;
    }

    /**
     * 计算所有列高度之和
     */
    private int getAggregateHeight(int[][] grid) {
        int total = 0;
        for (int c = 0; c < TetrisBoard.COLS; c++) {
            total += getColumnHeight(grid, c);
        }
        return total;
    }

    /**
     * 计算单列高度
     */
    private int getColumnHeight(int[][] grid, int col) {
        for (int r = 0; r < TetrisBoard.ROWS; r++) {
            if (grid[r][col] == 1) {
                return TetrisBoard.ROWS - r;
            }
        }
        return 0;
    }

    /**
     * 计算完整行数
     */
    private int getCompleteLines(int[][] grid) {
        int count = 0;
        for (int r = 0; r < TetrisBoard.ROWS; r++) {
            boolean full = true;
            for (int c = 0; c < TetrisBoard.COLS; c++) {
                if (grid[r][c] == 0) {
                    full = false;
                    break;
                }
            }
            if (full) count++;
        }
        return count;
    }

    /**
     * 计算空洞数（上方有方块但自身为空的格子）
     */
    private int getHoles(int[][] grid) {
        int count = 0;
        for (int c = 0; c < TetrisBoard.COLS; c++) {
            boolean blockFound = false;
            for (int r = 0; r < TetrisBoard.ROWS; r++) {
                if (grid[r][c] == 1) {
                    blockFound = true;
                } else if (blockFound) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 计算相邻列高度差的绝对值之和（平滑度）
     */
    private int getBumpiness(int[][] grid) {
        int bumpiness = 0;
        for (int c = 0; c < TetrisBoard.COLS - 1; c++) {
            bumpiness += Math.abs(getColumnHeight(grid, c) - getColumnHeight(grid, c + 1));
        }
        return bumpiness;
    }

    /**
     * 搜索当前方块的最优落点
     * @return 最优决策 [rotation, column]
     */
    public int[] findBestMove(TetrisBoard board, Piece piece) {
        double bestScore = Double.NEGATIVE_INFINITY;
        int bestRotation = 0;
        int bestCol = 0;

        for (int rot = 0; rot < piece.getRotationCount(); rot++) {
            int[][] shape = piece.getShape(rot);
            int pieceWidth = shape[0].length;

            for (int col = 0; col <= TetrisBoard.COLS - pieceWidth; col++) {
                int row = board.getDropRow(piece, rot, col);

                // 无法放置（超出顶部）
                if (row < 0) continue;

                // 模拟放置
                TetrisBoard testBoard = board.copy();
                testBoard.placePiece(piece, rot, col, row);

                // 评估
                double score = evaluateBoard(testBoard);
                if (score > bestScore) {
                    bestScore = score;
                    bestRotation = rot;
                    bestCol = col;
                }
            }
        }

        return new int[]{bestRotation, bestCol};
    }
}

3. AI游戏引擎

/**
 * 俄罗斯方块AI游戏引擎
 */
public class TetrisGameEngine {
    private TetrisBoard board;
    private TetrisAI ai;
    private Random random;
    private int piecesPlaced;

    public TetrisGameEngine() {
        this.board = new TetrisBoard();
        this.ai = new TetrisAI();
        this.random = new Random();
        this.piecesPlaced = 0;
    }

    /**
     * AI自动运行一步
     * @return 游戏是否继续
     */
    public boolean aiStep() {
        Piece piece = Piece.ALL_PIECES[random.nextInt(Piece.ALL_PIECES.length)];
        int[] move = ai.findBestMove(board, piece);
        int rotation = move[0];
        int col = move[1];
        int row = board.getDropRow(piece, rotation, col);

        if (row < 0) {
            System.out.println("Game Over! Pieces placed: " + piecesPlaced);
            System.out.println("Final score: " + board.getScore());
            System.out.println("Lines cleared: " + board.getLinesCleared());
            return false;
        }

        board.placePiece(piece, rotation, col, row);
        piecesPlaced++;
        return true;
    }

    public void printBoard() {
        int[][] grid = board.getGrid();
        System.out.println("+" + "-".repeat(TetrisBoard.COLS * 2 + 1) + "+");
        for (int r = 0; r < TetrisBoard.ROWS; r++) {
            System.out.print("| ");
            for (int c = 0; c < TetrisBoard.COLS; c++) {
                System.out.print(grid[r][c] == 1 ? "■ " : "· ");
            }
            System.out.println("|");
        }
        System.out.println("+" + "-".repeat(TetrisBoard.COLS * 2 + 1) + "+");
        System.out.println("Score: " + board.getScore() + " | Lines: " + board.getLinesCleared());
        System.out.println();
    }

    public static void main(String[] args) {
        TetrisGameEngine game = new TetrisGameEngine();

        while (game.aiStep()) {
            if (game.piecesPlaced % 500 == 0) {
                System.out.println("Pieces placed: " + game.piecesPlaced);
                game.printBoard();
            }
        }

        System.out.println("Final board:");
        game.printBoard();
    }
}

复杂度分析

模块 时间复杂度 空间复杂度
落点评估 O(rotations × cols × rows) O(1)
场地评估（四指标） O(rows × cols) O(1)
每步AI决策 O(rotations × cols × rows) O(rows × cols)
完整游戏模拟 O(pieces × rotations × cols × rows) O(1)

算法优化

  1. 权重参数优化：使用遗传算法或梯度下降自动调优评估权重
  2. 前瞻搜索（Lookahead）：不仅评估当前方块，还考虑下一个方块的最坏情况
  3. 局部分搜索（Beam Search）：保留前K个最优状态，扩展搜索深度
  4. 生存策略：在游戏后期优先保持低高度而非追求消行

总结

本文通过贪心评估函数实现了俄罗斯方块的AI自动游玩。核心思路是将每个可能的落点转化为一个场地状态，然后用多指标线性评估函数打分，选择分数最高的落点。评估函数的四项指标（总高度、完整行数、空洞数、平滑度）覆盖了俄罗斯方块策略的核心要素。这种基于状态评估的贪心方法在经典俄罗斯方块中已能达到数百万分的水平，其核心思想也适用于其他需要实时决策的堆叠类游戏AI设计。

Tagged with: