【参赛经验分享】腾讯内部赛道-鹅罗斯方块赛事笔记

前言

我在过去,写过不少游戏AI,所以当看到公司有这样一个比赛很是高兴。不巧比赛的两周刚好项目组特别忙,但我仍希望能在有限的时间来做得更好。

挖掘规则

在chrome浏览器中查看js文件,发现里面有完整编译前的源码的链接,而且里面的注释写得特别的详细。

我主要关注了其中的core.js和game.js。
从中可以得出在规则上比较关键的信息

  1. 方块出现的序列出现的顺序完全固定,且为10000块
  2. 最终得分有两个关键的因素,富贵险中求和鼓励多行消除

也就是说,我们可以定两个小目标,一是打完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个方块,也算是一次不错的体验了。最后,感谢主办方能够举办这样一个活动~很棒

本站文章资源均来源自网络,除非特别声明,否则均不代表站方观点,并仅供查阅,不作为任何参考依据!
如有侵权请及时跟我们联系,本站将及时删除!
如遇版权问题,请查看 本站版权声明
THE END
分享
二维码
海报
【参赛经验分享】腾讯内部赛道-鹅罗斯方块赛事笔记
我在过去,写过不少游戏AI,所以当看到公司有这样一个比赛很是高兴。不巧比赛的两周刚好项目组特别忙,但我仍希望能在有限的时间来做得更好。
<<上一篇
下一篇>>