前言
我在过去，写过不少游戏AI，所以当看到公司有这样一个比赛很是高兴。不巧比赛的两周刚好项目组特别忙，但我仍希望能在有限的时间来做得更好。
挖掘规则
在chrome浏览器中查看js文件，发现里面有完整编译前的源码的链接，而且里面的注释写得特别的详细。
我主要关注了其中的core.js和game.js。 从中可以得出在规则上比较关键的信息
- 方块出现的序列出现的顺序完全固定，且为10000块
- 最终得分有两个关键的因素，富贵险中求和鼓励多行消除
也就是说，我们可以定两个小目标，一是打完10000块方块，二是打完10000块的基础上拿更多的分。
算法选择
很容易想到，俄罗斯方块是一个经典的游戏，它一定有很多前人经验可以借鉴。因此我在网上很容易就找到了一个看起来可行的算法，即Pierre Dellacherie’s Algorithm
El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm | imake
这个算法通过对局面6个特征来构造评估函数，有比较好的不死性，它甚至给出一组已经调整好的参数。这样要完成第一个小目标，即消除10000个方块，基本上是没问题了。
语言选择
PD算法看起来比较美好，而我们要做的，是跑完10000方块的同时分数更高。如果要追求完美，计算更多的得分，必然需要强的计算力。另外直接使用JS也是一种方式，因为我们可以直接得到游戏规则上的最准确的源码。
语言 | 性能 | 成本 |
|---|---|---|
C | 高 | 完整实现游戏规则 AI算法 |
JS | 低 | 少量修改游戏规则 AI算法 |
考虑到时间成本，如果我用C 来编写，很可能实现游戏规则和官方完全一样就要花上不少时间，而我在时间很少的情况下，直接使用JS加入一些优化，或许从完成比赛的情况下，是一个更好的选择。
实现过程
1. 修改原有游戏规则，让时间禁止
我们首先要做的就是把下落速度变成0，这对后面的调试会起到很关键的作用。 要修改它其实也很简单，只需要把每次下落的定时器去掉即可。
2. 完成基本的状态枚举 随机评估函数
我们通过直接模拟游戏键盘事件，DFS出所有终止状态的情形即可完成枚举。 需要保存的状态包括，方块的位置，旋转的方向，操作的序列等信息。 注意到，由于一次方块下落的最终决策平均大约20种，而条条道路通罗马，我们可以做个状态记录，让每一个方块在某一个坐标的状态仅访问1次。 这样，至此，我们就完成了最基本的AI自动游戏主流程，虽然它会在开局就很快死掉。
3. 完成PD算法
PD算法实现并不复杂，每次在DFS找到一个落点时，把当前的方块填充到面板中，按照PD算法的6个特征计算得分即可。这6个特征包括一下内容：
Landing Height: The height where the piece is put (= the height of the column (the height of the piece / 2)) Rows eliminated: The number of rows eliminated. Row Transitions: The total number of row transitions. A row transition occurs when an empty cell is adjacent to a filled cell on the same row and vice versa. Column Transitions: The total number of column transitions. A column transition occurs when an empty cell is adjacent to a filled cell on the same column and vice versa. Number of Holes: A hole is an empty cell that has at least one filled cell above it in the same column. Well Sums: A well is a succession of empty cells such that their left cells and right cells are both filled.
优化
在刚完成PD算法的时候，结果并没有我预期的好。它并不能如期打完10000个方块，游戏中途会出现大量连续s和z，或者偶尔连续来几个I，所以几乎每次在1000块左右就死掉了，不论怎么调参数，总是卡在3W分左右。另外我发现，方块越到后面，计算速度就越慢，而且慢得越来越明显。理论上游戏过程中的计算量大小不会又太大的变化，让我很费解。
1. 操作序列回溯策略
游戏前期发展到中期越来越慢是个大问题，在第1000个速度顿卡的尤为突出，即使我能写出好的算法，也绝无法撑到10000块。 通过谷歌浏览器的性能探测器，我聚焦到了DFS的状态的保存上。DFS调用最多的就是状态的保存和回溯。由于我保存了操作序列，并且是深拷贝。而操作序列是一个很长的字符串，它会随着游戏的发展越来越长！ 实际上我们并不用每次都全量拷贝整个序列。可以根据序列中N出现的位置来增量回溯，这样即使到了游戏中期，运行速度也能和开局时相差无几了。
2. 旋转剪枝
在dfs过程中，由于方块可以旋转，4个状态为一个循环。但实际上不是每个方块都需要旋转3次，例如正方形它是完全不用旋转的，而Z和S和I型只有两种旋转状态。这样可以减少大量的中间决策开销和最终决策开销。
3. 快速下落
注意到dfs过程原本是对键盘操作的模拟，但我们仍可以有一点点改进。如果一个方块在空中，事实上它不需要在中途做出大量花式旋转，只需要在最后快到底时再旋转。因此我们DFS向下方状态搜索时，可以直接向下“跳”到可以触碰到的位置上面一格。这样可以节省中间路径的大量的保存和回溯过程。
4. 决策层数增加
事实上不管怎么调参，只有一格方块的局面，看的都不是长远的。我们的搜索需要一次搜索更多的方块，也就是增加决策的层数。层数增加的过程中，状态的保存也需要更多，比如每次多下落一个方块时，上一步的网格信息。但是JS的计算性能比较有限，如果没有前面3个优化，2层都会非常慢，完全无法等到10000块消除完。加入了前面3个优化后，才能计算到2层或者3层。
在两层的情况下，就能打完10000个方块了，效果很可观，可以拿到T-shirt了。
5. 增加场面方块
由于富贵险中求的规则，如果场面方块更多，得分更高。我发现，在能计算2层的情况下，只需要一半的高度就能稳住整个局面。 因此如果局面比较安全，可以用搜1层的策略增加高度，局面危险的时候，用搜2层的策略来稳住局面。
这样，就可以在打完10000个方块的同时方块更多。
总结
本次最终得分35w，排名48，和百万得分的大佬还有许多差距。不过我对我来说，这次比赛学到了很多东西，并且在时间有限的情况下，完成一个AI，看着AI自动刷刷的打完10000个方块，也算是一次不错的体验了。最后，感谢主办方能够举办这样一个活动~很棒
