前言
在盆友圈里收到消息, 鹅厂举办了一场俄罗斯方块的刷分比赛, 私聊一下发图的同学拿到了体验连接, 好像还挺简单的嘛, 遂决定抽空参赛.
由于上班时候在负责别的项目, 整体参赛时间并不多, 上班不摸鱼, 妻子下班比我晚半小时, 下班还要路上买菜, 回家做饭, 洗碗, 拖地, 洗衣服 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 计算, 传入当前的网格状态, 和轮到哪一个方块了
- Windows.ai.calc(this.grids, this.brickCount - 1)
然后在 AI 代码里面做了两个比较简单的函数, 用来加速 AI 的计算和方便自己使用
- // 官方代码的网格用字符串形式, 这里转成 boolean 形式, true 代表有方块占有, false 代表没有
- getBooleanGrid()
- // 下落函数, 官方的下落函数计算目的太多, 修改不方便, 这里自己重写一个, 计算方块下落后, 返回最终的网格状态
- drop()
- // 格子是否有效函数, 判断下落后到哪一行停止
- posValid()
有了上述的几个函数之后, 其实都大概可以推断出我的意图了
AI 流程
有了最终的网格状态之后, 就可以送入评分函数了, 由于评分函数涉及较多理论, 需要的请看源码吧, 评分之后很简单的一个取最大评分数之后, 获取到旋转的方向和应该从哪一列下落, 就可以调用相关函数进行操作游戏了
- let game = Windows.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 的成绩, 把这个参数转到笔记本上重跑一次, 然后输出操作步骤上传成绩, 用这个分数作为最终成绩提交.
后记
感谢大会主办方组织的这次比赛, 作为一个转行从事程序工作的中年程序员, 没有受过专业的软件开发教育, 对于算法也是靠着自己的理解来掌握, 毕竟大学里面不是计算机系, 没有接触过相关的课程. 这次能低门槛地参与到大厂的比赛中, 与一众大佬们切磋技艺, 虽然最后分数不高, 但志在参与, 目标就是为家里爱妻拿一张视频会员卡. 看到别的选手不断晒出缜密的思路, 认识到自己向专业领域要走的路还很长, 还需要加油.
来源: https://www.qcloud.com/developer/article/1865978