【参赛经验分享】含可以手玩的网页版（带AI）

最终提交分数433550

游戏初步分析

简单看了一下游戏源代码，可以发现：（1）游戏里面共有10000块；（2）游戏里面每一块都是确定的，和操作无关。

然后再试试游戏的提交分数函数，又发现：（3）在后端的评分程序（下同），每一块移动时不能穿越其他块（横向和纵向都不能穿越）；（4）可以中途悬停（即使前几天游戏界面没有悬停按钮）。

第一次尝试

知道这些之后，就用C++把游戏复刻出来。见https://pastebin.com/4mbSk8US（用里面的old_main函数替换main函数可以从标准输入读入操作序列并计算得分）。接着写了很简单的代码尝试自动搜索方块位置，但是这样的代码只能拿到7000余分，远远不够。考虑到C++不容易对游戏进行操作（“手玩”），因此放弃了。

第二次尝试

我想起了以前了解的一个俄罗斯方块AI。这个AI的介绍可以见这里。

AI的原理

每个方块最多有4个方向（部分方块旋转180度后和原来相同，因此只有两个），先将旋转后的方块左右移动，最多有10种位置（通常会只有7-9种），然后往下移动到触底为止。考虑连续2个方块，最多有1600种不同放法。对每个放法，考虑以下4个指标：

1. Aggregate Height：每一列最上面的格子（含）到底部的方块数称为每列的高度，这个指标是所有列高度的和。
2. Complete Lines：就是可以消去的行数。
3. Holes：上面有方格的空位（“洞”）的个数。
4. Bumpiness：通常情况下相邻两列高度不应相差过大，考虑相邻两列高度差的绝对值，共有9个“相邻两列”，这个指标是9个绝对值的和。

然后对这4个指标加权求和，选择其中加权和最大的方块。原博客使用遗传算法优化4个权重。

遗传算法

设p为某个权重向量（模归一化为1），取100个随机的方块序列（每次计算的方块序列重新生成），每个序列有500个方块，f(p)定义为该权重下AI能消去的总行数（在遗传算法中，称为“适应度")。遗传算法包括以下步骤：

1. 初始化：生成1000个随机向量，并计算它们的适应度。
2. 交叉：在1000个随机向量中随机取100个，然后取100个向量中最好的2个进行杂交（即按适应度加权平均，适应度高的权重大，然后将模归一化为1），如此生成300个新向量。
3. 变异：每个新向量有5%的概率变异，变异会将随机一个分量的值加上-0.2至0.2间的随机数。变异后模再次归一化为1。
4. 选择：所有1300个向量中，最差的300个被丢弃，其余回到第2步重新开始。

2-4三步可反复执行，直到效果足够好为止。最终原作者得到的四个权重分别为-0.510066、0.760666、-0.35663和-0.184483。如果7种方块等概率出现，该算法可消去至少200万行。

算法的应用

为了应用于本比赛，需要修改里面的计分函数和生成方块的函数，这样直接运行仍然只有8000多分。进一步对AI进行修改：

1. 每一步不能在没有消除任何行的情况下占用顶行（按源代码中给出的规则）
2. 增加消去行数的权重

这样分数就增加到了20000分，但是这仍然不够。

接着我对代码进行了修改，增加了存档的功能，每次消去一行都会存档，并且可以调出较早的存档。然后Game Over时自动往前退到倒数第10个存档，在那个存档任意操作一步（有时需要再往前退），然后启动AI，这个时候可能能取得更高的分数。把10000块都用完有280000分。

注意每次Game Over的时候都要人工操作，次数较多很麻烦，因此可以在最大高度大于15时搜索第三层（搜索3层最多有64000种放法，比搜索2层慢得多，因此高度小的时候没有必要），此时分数大约有300000分，但是Game Over需要手动干预的情况减少了。

接着修改评分函数，计算每一种放法组合可以得到的分数，用此替代上文4个指标中“可以消去的行数”。经过对权重的一些调整，可以拿到460000分（提交的是433550分的结果）。

修改后的游戏

见https://tetrisai.gitlab.io/。和原版相比，除了算法外有以下不同：

1. AI不使用的时候没有重力，这样方便操作。
2. 使用AI的时候没有动画效果，也即每个方块都会直接出现在其最终位置。
3. 增加了以下快捷键：,（逗号）和.（句号）键用于前后切换存档；/（斜杠）键用于显示可以用于提交的操作序列；Z键用于保存存档。这些键只有AI不活跃的时候才有效。另外Game Over的时候会自动显示操作序列（会丢弃10000个方块后的操作）。

一个坑是由于旋转的实现不同，这些操作序列不一定有效（例如旋转时碰上其他方块），因此提交的时候如果发现在中间某一步Game Over那么需要回退到Game Over前的状态手动操作几步（主要是把不合法操作涉及的方块重新放置），然后继续。

由于手动操作的存在，最终分数为400000至500000均为正常。

做到这里，总共用时不超过12小时，其中从第二次尝试开始共用了不超过6小时。由于自己的实习此后周一到周五都只关注排行榜变化，这个分数（433550分）从第5名掉到了第38名（因为后来一些选手不再计入排名，目前是第33名）。周末（8月7日至8日）我再尝试多次修改AI，可以达到预期分数540000分（使用1513块达到82324分），但是达到这个分数需要大量手动操作，而且即使600000分也进不了前20名，因此没有继续进行了。

总结

本次参加比赛仍然有很多不足。

就目前的AI来说，这些参数大部分仍然沿用原版俄罗斯方块AI，没有特意去调优（即重新跑一遍遗传算法）。目前用AI从0跑到100000分大约需要1分钟，用这个AI对1000种可能的参数测试是不现实的。事实上，代码中用JavaScript实现的grid和piece都不是最优的实现（C++代码给出了较优的），要进一步训练AI必须用C++（或至少WebAssembly）重写整个AI。

这个AI的算法也只考虑了先左右移动再往下移动这种操作方法，因此不完全封闭的“洞”无法填补。同时，有时悬停可以消去更多的行。但是，考虑更多情况会增加搜索状态数。我曾经把代码改成Beam Search（广度优先搜索然后丢弃掉每层分数较小的点，其他的报告称为集束搜索，但是在我的印象中称为柱型搜索），但是没有明显帮助。

文中的算法是Pierre Dellacherie算法的一个变种。但是对本问题来说这类算法的问题在于没有用到方块序列的确定性。因此我参赛时就知道这种方法不是正解（也即能达到1000000分的解法）。即使分段每段单独调参，也没有用到序列的确定性。但是我但是还以为正解是强化学习等机器学习算法。

第一天时有人能拿到1000000分，注意任何步骤结束时（方块消去后）第一行必须是空的，且每行不能填满，因此最多有170个格子（显然格子数量为偶数），然后放了一个格子，有174个格子。另一方面，10000块共40000个格子，即使全部消去也只会消去4000行。每次消去一行，理论可得到的最大分数为696000；每次消去四行，理论可得到的最大分数为1740000。

以上全文按CC-BY 4.0协议释出。