【参赛经验分享】腾讯极客挑战赛第四期俄罗斯方块比赛复盘

1.比赛总结

  七月底的时候在网络上看到了这样一个赛事，赛题大概总结起来就是用代码玩一款十分经典的游戏俄罗斯方块，通过游戏得分来排名评比，觉得挺有意思，抱着随便试试的想法就参加了，结果最后获得了全国第49名，最终获得的最高分数是31万多一点，虽然和第一名的一百多万还是有不小的差距，需要改进反省的地方还有很多，但这一成绩还是基本达到了我的预期的，同时我也是成功获得了腾讯招聘的绿色通道，丰富了自己的履历。

最终比赛成绩

2.比赛复盘

  在赛事官网可以找到俄罗斯方块游戏的比赛入口，进入游戏之后可以发现游戏的界面是一下这样的：

腾讯极客挑战赛游戏界面

  光看这个游戏界面，这就是一个普通的俄罗斯方块游戏，但其实玄机藏在浏览器的控制台中，打开浏览器的控制台，很容易就可以找到这个游戏的源码，因为腾讯官方在控制台的代码资源中用注释告诉你了源码的网址。我们将整个游戏项目拉到本地之后，就可以“魔改代码”，大展身手了。

  在本地用IDE打开这个游戏项目，可以看到游戏使用JavaScript写的，而且是基于vue.js框架。虽然我的“主战场”是后端Java Web，但对前端JS还是比较熟悉的，特别是vue框架，“魔改代码”基本上还是绰绰有余的，所以我选择了直接在源码上进行代码添加，实现用算法跑俄罗斯方块。

  经过上网查询俄罗斯方块算法相关资料后，我了解到目前的主流俄罗斯方块AI算法是基于A*算法的启发式搜索。基本思路就是定义一个启发函数对当前局面进行评估，对于每一个当前即将下落的方块，遍历方块下落的所有情况——以各个形状在所有位置下落的情况，对于每一种情况，通过启发函数算出局面评估的评分，在所有情况中，评分最高的就是当前最优的下落情况，然后将当前方块旋转到该最优情况所对应的形状，再移动到对应最佳位置，下落即可。

  我的算法思路基本上就是以上所阐释的启发式搜索，确定了算法方向之后，接下来的关键就是这个启发函数该如何设计，这决定了如何定义方块该以怎样的形状，在哪个位置下落。通过网上资料我了解到，目前存在三种比较普遍的方案。

  第一种是最经典的Pierre Dellacherie算法，其对局面进行评估的启发函数包含以下6项指标：

1.landingHeight(下落高度): 指当前板块放置之后，板块重心距离游戏区域底部的距离

2.erodedPieceCellsMetric(消行评分): 代表的是消除的行数与当前摆放的板块中被消除的小方块的格数的乘积。

3.boardRowTransitions(行变换): 对于每一行小方格，从左往右看，从无小方格到有小方格是一种“变换”，从有小方格到无小方格也是一种“变换”，这个属性是各行中“变换”之和

4.boardColTransitions(列变换): 每一列的变换次数之和

5.boardBuriedHoles(空洞数): 各列中的空洞的小方格数之和

6.boardWells(井数): 各列中“井”的深度的连加和，井是指中间一列为高度低于左右两列的情况，整体呈现为凹字形

最后的启发函数定义为：

value = x1 × landingHeight + x2 × erodedPieceCellsMetric + x3 × boardRowTransitions + x4 × boardColTransitions + x5 × boardBuriedHoles) + x6 × boardWells

x1:-1 x2: 1 x3:-1 x4:-1 x5:-4 x6:-1

value的取值越高，说明当前下落情况越优。

  第二种是在Pierre Dellacherie算法的基础上进行提升的El-Tetris算法，该算法对原Pierre Dellacherie算法的第二项指标erodedPieceCellsMetric有略微调整，同时改进了各个评价指标的系数

1.landingHeight(下落高度): 指当前板块放置之后，板块重心距离游戏区域底部的距离

2.rowsEliminated(消行数): 代表的是消除的行数

3.boardRowTransitions(行变换): 对于每一行小方格，从左往右看，从无小方格到有小方格是一种“变换”，从有小方格到无小方格也是一种“变换”，这个属性是各行中“变换”之和

4.boardColTransitions(列变换): 每一列的变换次数之和

5.boardBuriedHoles(空洞数): 各列中的空洞的小方格数之和

6.boardWells(井数): 各列中“井”的深度的连加和，井是指中间一列为高度低于左右两列的情况，整体呈现为凹字形

启发函数定义为：

value = x1 × landingHeight + x2 × rowsEliminated + x3 × boardRowTransitions + x4 × boardColTransitions + x5 × boardBuriedHoles) + x6 × boardWells

x1: -4.500158825082766 x2: 3.4181268101392694 x3: -3.2178882868487753 x4: -9.348695305445199 x5: -7.899265427351652 x6: -3.3855972247263626

  第三种是我在相关论文——Improvements on Learning Tetris with Cross Entropy 中看到的又一种改进算法，这种算法在Pierre Dellacherie的基础上增加了两个评估指标：holeDepth和rowsWithHoles，同时对评估指标的系数进行了重新定义。

1.landingHeight(下落高度): 指当前板块放置之后，板块重心距离游戏区域底部的距离

2.erodedPieceCellsMetric(消行评分): 代表的是消除的行数与当前摆放的板块中被消除的小方块的格数的乘积。

3.boardRowTransitions(行变换): 对于每一行小方格，从左往右看，从无小方格到有小方格是一种“变换”，从有小方格到无小方格也是一种“变换”，这个属性是各行中“变换”之和

4.boardColTransitions(列变换): 每一列的变换次数之和

5.boardBuriedHoles(空洞数): 各列中的空洞的小方格数之和

6.boardWells(井数): 各列中“井”的深度的连加和，井是指中间一列为高度低于左右两列的情况，整体呈现为凹字形

7.holeDepth（空洞深度）:各列所有的空洞的空洞深度之和

8.rowsWithHoles（存在空洞的行数）：存在空洞的行的行数之和

启发函数定义为：

value = x1 × landingHeight + x2 × erodedPieceCellsMetric + x3 × boardRowTransitions + x4 × boardColTransitions + x5 × boardBuriedHoles) + x6 × boardWells + x7 × holeDepth + x8 × rowsWithHoles

x1: -12.63 x2: 6.60 x3: -9.22 x4: -19.77 x5: -13.08 x6: -10.49 x7: -1.61 x8: -24.04

  以上三种启发函数我都进行了尝试，呈现出的效果是第二种和第三种启发函数明显要比原始的Pierre Dellacherie算法的启发函数更加的优秀，但依旧会有不小的几率中途方块触顶死掉。我分析这其中的原因可能是比赛所有的方块序列都是既定的，而且各个方块的出现次数不一样，s型和z型方块的出现频率明显要高于其他I,L,J,T,O型方块。

  既然AI算法也有可能方块触顶 game over，那么该如何调整呢。我采取的方法是当游戏过程中方块堆叠过高超过设定阈值时，转为手动操作方块下落，AI做不到的事情我来手动完成。当通过我的手动操作，方块堆叠高度又下降到阈值以下后，又转换为AI算法进行操作。在这样做了反复尝试之后，分数最高可以达到23、24万左右的样子。

  随后，为了进一步提高分数，我又在算法中进行了小的调整——在使用AI算法进行自动方块下落的过程中，始终保证局面中最左边的一列中没有空洞，如果当前下落的位置会使最左边的一列出现空洞，即使局面评估分数再高也不选择这个位置进行下落。保证最左边一列没有空洞，这样会使得消去时一次消去多行的可能性有所增加，增加分数倍率，同时也使得局面中的方块堆叠高度维持在一个中等水平，不会太高也不会太低，也可以增加单次消去分数增加量，体现了“富贵险中求”的精神。

（项目源码中官方在注释里给玩家的建议：富贵险中求）

“富贵险中求”

  但这样操作又使得AI算法触顶暴毙的概率进一步增大了，就算切换成手动操作模式我也无力回天，那么又该怎么办呢？我想到的方法是——再设置一个高度阈值，当局面中方块堆叠高度低于这个阈值时，AI算法采用激进模式——保证最左边一列没有空洞，但是当堆叠高度高于这一阈值时，AI算法采用常规模式——不必保证最左边一列没有空洞，这样来回转换AI算法模式，使方块堆叠高度在一个高度区间内反复横跳，分数的增速也比只采用常规模式来的更快。这样进行设置之后，也需要注意一个问题，就是当常规模式切换成激进模式时，需要保证切换的一瞬间局面中最左边一列是没有空洞的，不然就会导致激进模式下最左边一列一直不被填充。

  为了AI算法不死几率进一步提高，我依旧在此基础上设置了手动模式的开启阈值，以及一个激进模式和常规模式的转换触发按键。

  最终我的最高分数来到了31万多一点，排在全国第49名。

3.反思问题

  虽然我最后也是搭上了前50名的末班车。但其实在比赛过程中我还是可以总结出很多问题，首先就是在算法的选择上欠妥，这种启发式搜索算法仅仅只能最大程度的保证游戏的不死性，但对于如何尽量的去获得更高的分数还是无能为力的，即使我为了提高分数在该算法的基础上做出了一点点的改进，但分数提升幅度依然不大，相较于第一名的100多万还是有着很大很大的差距。其次是设计算法时对于如何更有效的提高分数考虑不足，错误的把关注重点放在了如何通过手动模式辅助AI算法去“凑”一个高分，也导致了最终的分数进步幅度一直很小。

  这些方面的问题在比赛后期一直阻挡着我冲刺更高的分数，引以为戒。

4.比赛源码

  比赛源码我放在了我的github中，地址：https://github.com/HelloWorld-Ian/tx_geekGame