【参赛经验分享】腾讯内部赛道139万分解题报告

我参加的是腾讯内部赛道，最后得分 1395326，在内部赛道排名第一。将内网的解题报告搬运一份到云+社区：

TL;DR

没有用机器学习，主要算法是集束搜索（beam search），剪枝时优先保留 “每次消除平均得分” 高的结点，以及砖块数量多、排列紧凑的结点。算法用到的参数先人肉调，调不动了以后，用遗传算法调。

题目分析

题目以一个网页游戏的形式呈现，熟悉一下环境和规则以后，先按 F12 看看。题目并不打算在 JS 上给我们制造太多麻烦，不仅提供了未混淆未压缩的 JS，怎么重放、怎么提交成绩也都写在了注释里：

<!-- 浏览器控制台快速调试方法（可直接复制到控制台中运行） -->
<!-- 1、回放操作序列：game.pause();game.playRecord('N,D19,N,D17,N,D16,N,D14,N,D11,N,D9,N,D6,N,D4,N,D3,N,D1'.split(',')); -->
<!-- 2、提交上传成绩（会消耗提交次数）：axios.post(`api/upload`, { record: 'N,D19,N,D17,N,D16,N,D14,N,D11,N,D9,N,D6,N,D4,N,D3,N,D1', score: 0 }).then(({ data }) => { console.log('提交结果', data); if(data.info) {console.log(data.info)} }); -->

随后发现，方块序列是固定的，通过 JS 里一个固定种子的线性同余伪随机算法生成。那么，就可以直接在本地写程序构造一个最佳玩法，再用 JS 接口提交上去。

与常规的俄罗斯方块最大的不同点是：它有一个“富贵险中求”的计分规则，即得分会乘以屏幕上已有的砖块数。玩过俄罗斯方块都知道，屏幕上已有砖块越多，越容易不小心挂掉。

常规的俄罗斯方块算法

常规的俄罗斯方块，比较常见的一个算法是：定义局面函数 Quality，对当前的局面进行评分，每一步都选择使 Quality 最大的玩法。（在群里了解到，这叫 Pierre Dellacherie 算法。）将 Quality 定义好，通常就可以取得比较好的成绩，至少持续玩很长时间不死的问题不大。Quality 函数可以考虑的因子例如：

• 消除的行数或得分
• 屏幕中砖块总数越少越好
• 每一列的高度差异不要太大（但如果这个限制过于严格，又会减少一次性消4行的机会，可以只对差距超过4行的情况进行惩罚），有的版本实现为计算砖块的重心，越低越好
• 行变换/列变换（row/column transition）：即同行/同列中相邻两格不同的数量，越小越好，可以反应堆叠的“紧凑度”
• “空洞”和“井”的数量

把这些因子加权得到 Quality。权重可以人工拍+做实验，也可以用遗传算法来计算。

定义好 Quality 后，每一步的决策就成了求最大值：

image.png

多数俄罗斯方块游戏允许预知下一个方块，可以多搜索一步：

image.png

一般来说，搜一两步已经够用了。如果确实有必要，也可以搜更多步，例如搜索三步：

image.png

注意“下下一步方块”属于不确定性，要取 min。

如果算力允许，还可以继续：

image.png

每一步都是对自己可以控制的部分取 max，对不确定的部分取 min，这就是 minimax 算法。

鹅罗斯方块算法

因为方块序列确定，不必像常规的俄罗斯方块那样逐方块决策，直接视为一个整体，目标是逼近这个最值：

image.png

或者表达为一棵搜索树：

image.png

第 n 层代表掉落了 n 个方块，每一层结点的数量相比上一层会膨胀几百倍，所以必需要剪枝。

这里我采用了集束搜索（beam search），它是广度优先搜索的一个变种。每轮计算出一层的结点，然后进行剪枝，将进入下一轮搜索的结点数控制在不超过 9041 个。这样 10000 个方块下来，总的计算量在 9041 万个结点，在个人电脑上还能跑得动。（先不要问为什么是 9041 这个魔数……）

一开始考虑的是最佳优先搜索（best-first search），但它会要求对不同层的结点进行排序，更难设计出好的排序公式，而集束搜索只要求对同层结点排序。

接下来的问题是剪枝，最直观的想法：按得分剪？不行，我们的规则是“富贵险中求”，仅按得分剪一定陷入局部最优，会优先消除而不是优先让屏幕上砖块数量增加。反复调整了多次，最后是组合了这些因素用来剪枝：

• 每次消除平均得分：定义为得分/累计消除次数。实验显示使用这个因子比直接使用得分好，它能在一定程度上对抗局部最优：如果过早消除，虽然得分提高，每次消除的平均得分反会变低。
• Quality 函数：主要描述格子排列的紧凑度，从常规俄罗斯方块算法修改而来：
  • 每一个砖块加 600 分（从而砖块越多 Quality 越高）
  • 每一个行变换（row transition）扣 458 分（一行中相邻两个格子不同为一个行变换）
  • 每一个上方有砖块的空格子扣 1080 分
• 结点多样性：避免每一层的结点过于“同质化”，具体考虑了两点：
  • 砖块高度的多样性：通常来说，砖块高是好的，每次消除平均得分和 Quality 高的结点，砖块高度一般也比较高。但是，砖块高的局面容易死。所以通过砖块高度多样性，确保不同高度都能有一部分进入下一轮，如果高的在后面死得多，矮的可以起到替补作用。
  • 祖先结点的多样性：意思是避免同一结点的子孙过快垄断搜索列表。直观考量是：有可能 A 局面实际上比 B 局面更有利于很多步以后得分，但 Quality(A) < Quality(B)。大概率，A 的子结点的 Quality 也会比 B 的子结点的 Quality 低，这样可能一两步以后，就被 B 的子孙垄断了，因此引入祖先结点多样性，强制在后续几层中保留一部分 A 的子孙结点，给它一个在几步以后翻盘的机会。

此外还加了几个硬规则：

• 砖块高度低于 16 或砖块数少于 126 时，禁止消除一行/两行；砖块高度低于 17 或砖块数低于 135 时，禁止消除三行/四行
• 得分低于同一层结点最高分 2200 分以上的结点全部剪掉
• 方块形状像“一根树枝伸向空中”的直接剪掉，具体实现为：最高的非空 5 行每行砖块数都少于 3

这些因子和规则是在调试过程中慢慢堆上去的，未必每个都真的有效。

上面算法描述中的魔数，一开始是人工拍的，筛选出一部分表现比较好的，最后用遗传算法优化一轮（搜索空间就是那些参数的不同取值），所以那些数字变得有零有整。

代码实现

动手之前， tetris.config.js, tetris.core.js 这两个文件完整读一遍，保证细节实现得一致，方块序列、触顶的判断、旋转逻辑等都可以从 JS 里面找到。

因为预料到搜索空间会很大，选择了用 C++ 实现，在工程效率上做一些优化，能比较明显地减少搜索时间。

• 用 jemalloc，程序运行时间直接减少了一半
• O 方块只有一种方向，S、Z、I 方块只有两种方向，不要都按照四种来实现
• 用位图表达格子，每行一个 uint16_t，这样描述整个屏幕只要 40 字节，拷贝更快，同时有一些计算也可以利用位运算高效完成
• 多线程搜索
• 确保代码的确定性，每次运行的分数严格一致，不要因为随机数或者多线程等原因产生偶然波动，对 debug 和调参有很大便利

遗传算法用 Python 写的，写得比较糙，好在性能瓶颈不在这里。因为每计算一条染色体的时间都很长（至少 15 分钟以上），所以加了一个特殊逻辑，如果在计算过程中预判当前染色体相比已知的最好 20 个染色体都要差，直接放弃，不用搜索完 10000 步。

得分过程

• 按常规俄罗斯方块算法实现，消耗完 10000 个方块，11 万分；
• 增加了一个高度阈值，砖块高度小于 10 行时不消除，43 万分；
• 进一步提高阈值，如果死掉，后退一定步数并降低阈值，最高优化到 87 万分；
• 改为集束搜索，提高到 103 万分；
• 调整剪枝策略 + 细节优化 + 人肉调参，137.5 万；
• 遗传算法调参，最终得分 139.5 万。

后记

感谢龙哥发起极客技术挑战赛，感谢码客、安平组织比赛。从第一期到现在，每一期都参加了，题目既有趣又有挑战性，解题过程中的思维碰撞也受益颇多。这一次比赛，在群里看到有用机器学习做的，有游戏大神手动打完 10000 个方块的（TAS），还看到了很多有趣的链接，从 tetris 大佬那里听到了很多新名词（t-spin、SRS、TSD、踢墙……），大开眼界。

最后几天一直想赶超外部赛道的第一名。外部赛道有大神在第一天晚上就做到了 137.2 万分，自己在 8 月 4 号优化了 136.6 万后，眼看着就要赶上了，却卡住好长一段时间。就在已经准备放弃时，龙哥发来一条消息：“加油，离外部赛道第一就差一点点了”，在龙哥鼓励下又坚持几个小时，终于调到 137.5 万，超过了当时的外部赛道第一名。后来又提高到了 139.5 万，但外部赛道也提高到了 141.3 万，最终还是没赶上，比较遗憾。也很期待看到外部赛道的分享。

附录

代码： https://github.com/chys87/mk-tetris-challenge

1395326 分的序列： https://github.com/chys87/mk-tetris-challenge/blob/main/out/1395326.replay.js