本文由 简悦 SimpRead 转码， 原文地址 zhuanlan.zhihu.com

（封面截图系统在线访问地址：https://open.hoyt-tian.com/Tetris/evolution.html）

不少同学都写过俄罗斯方块作为练手项目，本文整理了与俄罗斯方块实现相关的算法。

与 AI 相关的算法相对复杂一些，其他的算法则是跟游戏主流程相关。

名词解释

不妨将俄罗斯方块中，组成各个砖块的最小正方形基本单元称为方块（Tile）；

由若干个方块（Tile）组成的形状，称为砖块（Tetris）。

被玩家或 AI 操控的砖块（Tetris），称为活动砖块（Active Tetris）。

Tetris（砖块）旋转

砖块旋转是俄罗斯方块中非常基础的操作，玩家通过按键，可以实现砖块顺时针 / 逆时针的旋转行为。一般来说，Tetris 是由 Tile 组成的二维数组，Tetris 的旋转，就是对二维数组的元素进行转置操作。

对于任意的二维矩阵 A，A 中包含 m+1 行 n+1 列元素。

$$A = \left[ \begin{matrix} a{00} & a{01} & ... & a{0n} \ a{10} & a{11} & ... & a{1n} \ ... & ... & ... & ... \ a{m0} & a{m1} & ... & a_{mn} \ \end{matrix} \right] \tag{0}$$

其顺时针旋转，就是将现有矩阵转置后，原先的第 m 行作为第 0 列，原来的第 0 行作为旋转后的第 m 列元素。其逆时针旋转后，第 0 行作为第 0 列，第 m 行作为第 m 列。

举个例子，对于 L 形状的 Tetris，可以用二维矩阵表示为如（1），其中 1 表示 Tile，0 表示空

$$L = \left[ \begin{matrix} 1 & 0 \ 1 & 0 \ 1 & 1 \end{matrix} \right] \tag{1}$$

其顺时针旋转后的结果为 (2)

$$L = \left[ \begin{matrix} 1 & 1 & 1 \ 1 & 0 & 0 \end{matrix} \right] \tag{2}$$

逆时针旋转的结果为 (3)

$$L = \left[ \begin{matrix} 0 & 0 & 1 \ 1 & 1 & 1 \end{matrix} \right] \tag{3}$$

故旋转部分的伪代码如下：

  //顺时针旋转
    clockwise(){
        let w = this.width(), h = this.height();
        let ndata = buildMatrix(w, h);
        for(let row = 0; row < h; row++){
            for(let col = 0; col < w; col++){
                ndata[col][h-1-row] = this.data[row][col];
            }
        }
        return ndata;
    }
    // 逆时针旋转
    anticlockwise(){
        let w = this.width(), h = this.height();
        let ndata = buildMatrix(w, h);
        for(let row = 0; row < h; row++){
            for(let col = 0; col < w; col++){
                ndata[w-col-1][row] = this.data[row][col];
            }
        }
        return ndata;      
    }

但是，在实际游戏实现时，在准备执行旋转之前，还需要进行碰撞检测，如果碰撞检测不通过，则不能进行旋转操作。

碰撞检测

几乎所有的玩家操作，都需要进行碰撞检测，检测通过才能执行玩家输入的命令。可以将当前的俄罗斯方块局势信息保存在一个二维数组 (matrix) 中，活动砖块（Active Tetris）的任何移动操作，都需要先比对残局中的数据，防止产生碰撞。

碰撞检测除了检测方块之间的重合，还要考虑边界的情况。碰撞检测的伪代码如下:

testCollsion(matrix, tetris){
        for(let row = 0; row < tetris.height(); row++){
            for(let col = 0; col < tetris.width(); col++){
                if( (tetris.row + row >= matrix.length ) || (tetris.col + col >= matrix[0].length) || (matrix[tetris.row + row][tetris.col + col] !== null && tetris.getTile( row, col) !== null)){
                    return true;
                }
            }
        }
        return false;
    }

消除判断

当活动砖块落下后，需要判断此时是否形成了可消除行。可消除行需要被方块填充满，因此只有活动砖块穿插的行，才可能形成可消除行。其判断算法也比较简单。只要 matrix 中任意一行元素为 null，则不是可消除行，其伪代码实现如下：

isFullLine(matrix, line, cols){
        for(let i=0; i<cols; i++){
            if(matrix[line][i] == null) return false;
        }
        return true;
    }

悬空坠落

当一行或多行产生消除后，需要将被消除行的上方元素向下移动。若第 n 行被消除时，其上一行是第 n-1 行，从第 n-1 行到第 1 行，都需要依次直接拷贝其前一行的数据以覆盖本行数据，而第 0 行则生成一个空行。其伪代码实现如下

clearLine(line){
        for(let i=line; i > 0; i--){
            for(let j = 0; j<this.cols; j++){
                this.state.data[i][j] = this.state.data[i-1][j];
            }
        }
        this.state.data[0].fill(null);
    }

得分计算

最简单的，每消除一行得一分；稍微复杂一点，可以根据连续消除的行数进行额外奖励。

游戏结束判断

当 Tetris 落下后，若组成它的砖块落到了第 0 行的外面，可以认为游戏结束。最好在游戏结束的地方留一个回调，以方便 AI 训练。

上面涉及到的算法都还比较简单，如果要给俄罗斯方块增加 AI 相关支持，就需要用到几个相对复杂一点的算法了。

路径规划

AI 在进行操作时，需要对砖块的路径进行规划。路径规划的算法基础，可以参考一道 lintcode 上的算法题：不同的路径。这道题求的是机器人到达网格右下角的可行路径数量，基于它稍作改进就可以实现从起始点到目标点的动态规划。

更加复杂的路径规划，还需要考虑躲避障碍物、变形移动等情况。当然，路径规划做的简单一点也没关系，演示系统中并没有使用特别复杂的路径规划算法，但这并不妨碍训练出存活能力强的 AI，毕竟这个游戏在训练时，砖块是随机降落的，存活能力高的 AI 本身就会避免需要躲避障碍、变形移动的这些情况尽量少发生。相比于路径规划，AI 对局势分析的能力显得更为重要。

局势评分

对 AI 进行训练时，AI 通过局势评分，来判断当前活动砖块的最佳放置点。AI 可以尝试不同的落至点，并对各个落至结果进行评分，最后将评分最高的结果，作为实际的执行步骤，按照该路径进行操作即可。

最简单的局势分析，只需要考虑当前砖块和当前局势即可；更复杂的，还可以考虑下一个即将落下的砖块，一并分析。

局势评分最重要的，是评分指标的建立。指标的选择并不是唯一的。在借鉴了现有俄罗斯方块 AI 设计和我自身的实践经验，我使用的评价指标包括：

• 消除行数，新砖块下落后能消除多少行
• 平均高度，新砖块下落后，当前局势的平均高度（刨去将被消除的行）
• 空洞数，新砖块下落后，当前局势有多少个空洞（刨去将被消除的行）
• 平整度，新砖块下落后，各列之间的高度差绝对值之和（刨去将被消除的行）

通过这四个指标，AI 就有能力对当前局势进行分析、比较。然而，这四个指标应当如何选取合适的权重值呢？为了解决这个问题，此时就需要引入非常经典的算法——遗传算法。

遗传算法

为了给这些指标找到合适的权重值，我们可以先随机的生成一批种子权重值。尝试使用这些权重值去训练 AI，同时将表现结果好（得分在排名靠前的某个区间）的权重保留下来，继续训练。为了不至于陷入局部最优解，在重复训练的过程中，可以模拟生物进化的过程，对这些候选结果进行杂交，甚至突变。经过若干轮的训练，逐步就会出现一些比较优秀的结果。更多关于 ai 训练的内容，可以查看专题 俄罗斯方块的 React 实现 （三）AI 算法及其实现

附录

示例 AI 训练系统在线演示地址：https://open.hoyt-tian.com/Tetris/evolution.html

更多关于俄罗斯方块的 React 实现细节：Tetris - 田浩的博客

Github：hoyt-tian/tetris