腾讯极客挑战赛第四期-鹅罗斯方块 复盘

七月末的时候看到了腾讯极客挑战赛第四期，发现这不是俄罗斯方块嘛，是之前 Botzone 玩过的 AI 游戏，于是决定来玩玩。没想到一玩玩了好几天，最后的程序也和之前在 Botzone 写的 AI 完全不一样了，最后以 1413876 的分数拿到了外网赛道的第一，同时该分数也是内外网赛道的最高分。

这次的赛题叫做「鹅罗斯方块」，名字很有鹅厂风格。其实就是在一个 Web 版俄罗斯方块游戏中尽可能取得最高分。贴心的鹅厂还准备了正常缩进的源代码，查看源代码可以知道方块总数共 10000 个，落完则游戏结束。方块的下落序列则是由一个伪随机数生成器生成的，生成器的种子也是固定的，这意味着方块的下落顺序是固定的。

这次赛题与普通俄罗斯方块不同的还有不同种类方块的生成概率，长条的出现概率被人为调低到 2/29，而最难处理的 S 型和 Z 型出现概率则各被上调到 6/29。赛题在计分规则上相比普通游戏也有所变化，消除时场地格子越多，一次性消除的行数越多，得到的分数越多。想玩游戏的可以点击此处，但不知鹅厂哪个时候会关掉入口。

首先从下落方块数量恒定这点来看，我们要追求的反而不是「不死」了，而是在游戏能够继续的基础上尽可能拿到高分，而绝大多数 Tetris AI 算法都只追求「不死」，所以套用 Tetris AI 算法得到的分数一般都不高。我把我在 Botzone 上天梯第二的程序稍微改了改跑了跑，得到的分数也只有 10w 不到（因为写得太优秀了全程方块高度就没超过 4……）那么我第一个想法就是修改估价函数了。

原本在 Botzone 上的 AI 算法是 MCTS 蒙特卡洛搜索外加估价函数。在魔改了估价函数之后，分数从 10w 到 60w 再到 107w，但距离当时排行榜的第一名 137w 还有点距离。不愿意在调参上浪费太多的我只好决定换个思路。

首先为了追求理论最高分，我不能再用 MCTS 了，如果用 MCTS 找理论最高分的操作我觉得到比赛结束都找不出。所以要搜索，要在包含 $10000\times2^{200}$ 种状态的游戏中搜索出最优解。

「开玩笑呢，这么多状态数怎么搜？」「剪枝啊！」

然后我觉得也许可以用分阶段广搜。简单来说，对于初始局面，我们先搜索出 3~4 步后的局面有哪些，然后使用估价函数对局面做一个删减，丢掉不好的局面，只留下分数高且估价高的局面用于后续的拓展。这其实相当于每搜几步就用估价函数 + 贪心做一次剪枝，整体状态数也可以保持在一个合理的范围内。

然后就遇到了一个问题：估价函数势必要包含「分数」和「格子数」，这两个因素越高越好，但消行带来的影响却是矛盾的，格子数减少了但是分数增加了，这就需要写一个很好的估价函数才能让搜索搜到那个最优解。

「但估价函数很难写啊，还要各种脑洞各种比对测试……」

所以我对算法本体开刀了。实际上，上面提到的分阶段广搜中初步搜索的深度是可以随意调整的，调得越深（例如先搜索 10 步后的局面有哪些）状态数越多，但越能避免最优解在中途因为局面不够优秀而被丢弃。而且，这个搜索深度其实也是可以不固定的。为了解决消行带来的估价问题，我把操作序列中两次消行之间的操作定义为「阶段」，而初步搜索就是负责处理单个「阶段」的搜索。

具体来说，这次的算法分为两层。第一层的搜索树上，游戏局面每一阶段拓展一次；第二层的搜索树上，游戏局面每一轮拓展一次。第一层搜索其实有点像动态规划，我新建了 $10000\times200$ 个桶用来放置游戏局面，定义状态 $\text{bucket}[x][y]$，其中 $x$ 是游戏轮数，$y$ 是场地格子数。每个桶实际上是一个优先队列，只保留前 10 优的游戏局面。第一层搜索每次从桶里拿出一个游戏局面进行第二层搜索，再将搜索结果放回对应的桶内。第二层搜索则是一个简单的广搜，用来搜索可能的「阶段」。第二层搜索对游戏局面进行广度优先搜索，直到出现消行操作才停止拓展，也就是说这棵搜索树的叶子都是经过某次消行操作后的游戏局面。第二层搜索结束后会把搜索树叶子上的游戏局面返回给第一层搜索进行更新。

如何判断游戏局面的优劣呢？对于在同一轮且格子数相等的游戏局面，我通过判断分数和行列变化次数来给各个局面排序，分数高的优先，分数一样的行列变化次数少的优先。

// 返回场面上已被占用格子数
inline int getGrids()
{
    boradGrids = 0;
    for (int y = 1; y <= LIMITHEIGHT; y++)
        boradGrids += bit(gridInfo[nowGame][y]) - 2;
    return boradGrids;
}

// 返回场面上纵行方向上方块从有到无的变化次数，越少场面越平整
inline int getTransitions(bool recount = true)
{
    if (recount) // 重新计算该值
    {
        boardRowTransitions = 0;
        boardColTransitions = 0;
        for (int y = 1; y <= LIMITHEIGHT; y++)
            boardRowTransitions += bit(gridInfo[nowGame][y] ^ (gridInfo[nowGame][y] >> 1)) - 1, // 各行中变换之和
            boardColTransitions += bit(gridInfo[nowGame][y] ^ gridInfo[nowGame][y - 1]);        // 各列中变换之和
    }
    return boardRowTransitions + boardColTransitions;
}

boardRowTransitions 是指对于每一行小方格，从左往右看，从无小方格到有小方格是一种「变换」，从有小方格到无小方格也是一种「变换」，这个属性则是各行中「变换」之和。同理 boardColTransitions 是每一列的变换次数之和，boardTransitions 是行列的变换次数总和。

具体实现方面，本来想全部代码都整合到 C++ 中的，但因为前期写的各个算法模块的耦合度太高了，自己又不想重写，于是只好将两层搜索分开，Python 负责第一层搜索，C++ 负责第二层搜索。反正代码能用就行了嘛……

代码见 GitHub，注释应该都写得很详细了。

还有一个小插曲，其实在 MCTS 卡到 107w 的时候我已经不知道该如何写 MCTS 的估价函数了，然后听说鹅厂要直播一些选手们目前提交的精彩成绩，其中就有 137w 的操作记录，就守着直播守了一晚。虽然直播也只展示了后 1000 块的操作，但也启示了我后面的解题思路。鹅厂你干得好啊！