前言

在盆友圈里收到消息，鹅厂举办了一场俄罗斯方块的刷分比赛，私聊一下发图的同学拿到了体验连接，好像还挺简单的嘛，遂决定抽空参赛。

由于上班时候在负责别的项目，整体参赛时间并不多，上班不摸鱼，妻子下班比我晚半小时，下班还要路上买菜、回家做饭、洗碗、拖地、洗衣服blabla，周末还要和父母相聚喝一下早茶聊几句日常，实在躲不掉，这么算起来其实最后的参赛时间也就10小时左右。

本来打算用C语言重写AI逻辑然后计算，无奈时间上并不足够，我也知道JS的运行效率相对较低，但是这也是我时间限制之内能够做到的最大操作了，望各位看官大佬们见笑。

代码分析

show me the code！！！

好吧，github地址在这，master上面几条提交记录，都是针对不同分数的调参结果

https://github.com/jiabuda/tetris-ai

用1小时准备开发环境

前面说了，参赛时间并不多，当我着手准备参赛的时候已经是周三夜晚，幸好主办方并没有在代码上刁难选手，直接在js里面提供了压缩前的代码，由于平时也经常采用vue框架开发项目，所以类似动态渲染、闭包这种写法并不在话下。用谷歌浏览器打开页面，F12然后点击source先把首页源码抠下来，然后把所有min.js都替换成未压缩前的js代码，试运行了一次，能跑通，下落几次然后输出方块操作步骤无误，第一步结束。

用2小时研究算法

周四上一天班下来，上班午休也有搜索了一下相关的资料，还在github上下载了C#和JS版的两份俄罗斯方块的AI程序，到了晚上，抽时间研究一下相关算法，相信很多参赛的朋友首先搜索到的算法应该都是这个PD算法，作者名字还超级难念，暂且念作皮埃尔·得拉契吧，本人熟练粤语、国语、英语，和别人说起这个名字，都想含在嘴里吐不出来的感觉，相关资料如下

El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm

从算法上看，并不是太复杂，针对一个方块，旋转4次90度，针对每一列的下落到底情况，对最后的整体叠加状态进行评分，一共有6个评分值，还有通过群论推断出来的6个相应的权重

评分 =  下落位置的高度 *-4.500158825082766 + 消行数 *3.4181268101392694+
        行变换*-3.2178882868487753 + 列变换 *-9.348695305445199+
        空洞数 *-7.899265427351652 + 井统计 *-3.3855972247263626

具体的参数介绍可以查看相关的文章，其中行变换、列变换、井统计都是有一定理论的，这也是影响AI外挂摆放形态的关键，另外，使用这种算法是针对随机方块，对当前局面进行的一种评分，网络上很多继承这种方法的代码，都号称能做到玩不死，跑了一晚手工停止。但是这也是限制这种算法在这个比赛的一个很大的因素。

用2小时分析【鹅罗斯方块】代码并加入外挂

周五上班下来，晚上开始动手搞鹅厂的代码了，现在这个地方引入一个自定义的AI文件，这种做法也是很多网页型外挂的常用做法，包括某电商大厂经常推出积分活动，论坛里就经常有大佬写出JS的外挂，只要执行一句代码，引入他写的js文件，网页上就可以自动浏览，自动积分等等……

<!-- 俄罗斯方块核心计算文件，包含：获取方块、移动方块、旋转方块、边界检测等功能 -->
<script type="text/javascript" src="js/tetris.core.js"></script>

<!--引入自定义AI-->
<script type="text/javascript" src="js/tetris.ai.js"></script>

<!-- 俄罗斯方块游戏主文件，包含：游戏的启动暂停、游戏时钟单步 runner 的逻辑控制（playStep 和 replayStep）、游戏回放（playRecord）、画布渲染 -->
<script type="text/javascript" src="js/tetris.game.js"></script>

然后找到俄罗斯方块核心代码里面，生成新方块的位置，把AI代码植入

this.trackOp('new');

if (isValid) {
    this.nextBrickRawInfo = nextBrickRawInfo;
}

//在这里可以触发AI计算，传入当前的网格状态，和轮到哪一个方块了
window.ai.calc(this.grids, this.brickCount - 1)

然后在AI代码里面做了两个比较简单的函数，用来加速AI的计算和方便自己使用

//官方代码的网格用字符串形式，这里转成boolean形式，true代表有方块占有，false代表没有
getBooleanGrid()

//下落函数，官方的下落函数计算目的太多，修改不方便，这里自己重写一个，计算方块下落后，返回最终的网格状态
drop()

//格子是否有效函数，判断下落后到哪一行停止
posValid()

有了上述的几个函数之后，其实都大概可以推断出我的意图了

有了最终的网格状态之后，就可以送入评分函数了，由于评分函数涉及较多理论，需要的请看源码吧，评分之后很简单的一个取最大评分数之后，获取到旋转的方向和应该从哪一列下落，就可以调用相关函数进行操作游戏了

let game = window.game
//1毫秒后自动操作
setTimeout(() => {
    for (let i = 0; i < bestS; i++) {
        //旋转方块
        game.tetris.rotate()
    }
    if (bestC > 4) {
        //右移
        game.playStep('right', bestC - 4, true)
    }
    if (bestC < 4) {
        //左移
        game.playStep('left', 4 - bestC, true)
    }
    //下落到底
    game.tetris.drop();
}, 1)

这里一个简单的外挂就已经完成了，整个游戏已经可以自己玩下去了，使用PD算法可以获得15w分左右的分数

用2小时改进，使用DFS进行多层搜索

其实参赛的初期，看到有的选手已经拿到了100w+的分数，我就知道这个游戏肯定不会那么简单，有网友称PD算法是针对无状态局面，意思就是AI压根就不知道下一个方块是什么，只是针对当前给到的方块给出最佳的位置。而鹅厂的代码是使用线性同余随机数产生的方块排列，理论上可以遍历所有的方块获取最佳排序，然后给出设定的条件拿到最好的路径。

因为工作原因，平时公司的工作都是针对棋类进行算法编写，所以我知道这个计算量根本就不是普通计算机可以承受的，一层搜索就40种可能（当然没把o型特殊性考虑，这里只是纯理论说说），二层搜索就1600种可能，三层搜索就64000种可能……

“只有一种可能性”是奇异博士通过“时间宝石”窥视未来，得到了14000506次结局当中唯一一次胜利的机会。

所以不用想了，搜索个10层，比找到打败灭霸的方法还要难。而且针对鹅罗斯方块的计分方式，因为是采用【富贵险中求】的方式进行计分，可能第一层搜索到的低分数局面，大概率会在第二层中获得高分数（例如二层消4），所以盲目地对第一层进行剪枝是不可取的。

所以，我这里简单地使用了二层搜索，取二层的最高分，然后把第一层的结果输出给画面进行摆放，这时候可以获得了20W分的成绩。但是，缺点也带进来了，DFS需要时间进行计算以获得高分数，不使用深度搜索，3分钟就可以打完10000个方块，使用DFS两层搜索，需要20分钟才能结束，而且还可能因为过度追求高分数，而把自己“绊死”的局面，导致AI完全找不到一种可以放方块的可能性，然后结束了游戏。

最后一天冲刺，人肉调参算出高分数

改用DFS的时候已经是周六，当天还被家里人拉出去喝早茶，然后参观别人家的鱼池，泡茶磕龙眼聊聊家常，足足闲了一天。本来打算能有20W分就算了吧，但看了下形势，可能掉出名次拿不到任何奖励，那也心有不甘。这时候我最容易想到的方式就是调参，因为PD的参数没有针对【富贵险中求】这个玩法进行优化，查看了几次“绊死”的局面，AI对于“井统计”这个参数并不重视导致最后一个深深的井把自己送进了死路。所以调整了几个参数，进行了跑分。

这里有一个比较有趣的插曲，本人上班的电脑是九代i5+16G台式机，平日在家会用家里的老笔记本处理一下服务器故障，需要的时候远程一下办公室电脑进行编程操作。偏偏那天网络抽了风的慢，鼠标一卡一卡的，遂放弃远程连接。把家里所有能跑JS的设备都堆到一起，同时对不同的参数组合进行刷分。

刷分的时候已经是周日的早上10点多了，做完家务开始处理最后的冲刺

出场的设备有四代的i5，某果11，某为P30Pro，还有一台平时刷b站用的2代赛扬chromebook，居然刷了几次分数，发现某果的处理器对于h5优化真的是出奇的好，用一骑绝尘来形容真不是夸张，用这个DFS无剪枝的算法跑到300个方块仅需要40多秒，而四代的i5还需要50秒，当然9代i5只需要28秒就可以了。

最后调节了几个参数，跑了一下午的分，也没有想过上三层搜索，三层搜索估计到比赛结束都不知道能不能跑完一轮，一个方块要差不多1.5s的运算时间。修正了几次参数之后，用某果11跑出了47w的成绩，把这个参数转到笔记本上重跑一次，然后输出操作步骤上传成绩，用这个分数作为最终成绩提交。

后记

感谢大会主办方组织的这次比赛，作为一个转行从事程序工作的中年程序员，没有受过专业的软件开发教育，对于算法也是靠着自己的理解来掌握，毕竟大学里面不是计算机系，没有接触过相关的课程。这次能低门槛地参与到大厂的比赛中，与一众大佬们切磋技艺，虽然最后分数不高，但志在参与，目标就是为家里爱妻拿一张视频会员卡。看到别的选手不断晒出缜密的思路，认识到自己向专业领域要走的路还很长，还需要加油。