方块序列攻略37-【参与心得分享】腾讯内部赛道-鹅罗斯盒子活动笔记
前言
以前写过很多游戏AI，很高兴看到公司有这样的比赛。 遗憾的是，项目组在比赛的两周时间里非常忙碌，但还是希望在有限的时间内做得更好。
挖矿规则
在浏览器中查看js文件，发现有编译前的源码链接，里面的注释特别详细。
我主要关注了core.js和game.js。可以得出结论，在规则方面更关键的信息
区块出现的顺序是完全固定的，最终10000个区块的得分有两个关键因素。 富贵保险中的求和鼓励多线淘汰
也就是说，我们可以设定两个小目标，一个是打完10000个立方体，一个是在打完10000个立方体的基础上获得更多的积分。
算法选择
人们很容易认为俄罗斯方块是一款经典游戏，肯定有很多前人的经验可以借鉴。 所以我很容易在互联网上找到了一个似乎可行的算法，即
El- – 安上的 |
该算法通过比较情境的6个特征构建评价函数，具有较好的永生性，甚至提供了一组调整后的参数。 这样一来，完成第一个小目标，也就是消灭10000个方格，基本上是没有问题的。
语言选择
PD算法看起来更好，我们要做的就是跑遍10000个方格，得到更高的分数。 想要追求完美，计算出更多的分数，肯定需要强大的计算能力。 另外，直接使用JS也是一种方式，因为我们可以直接得到最准确的游戏规则源码。
语言
表现
成本
C++
高的
完整实现游戏规则+AI算法
js
低的
游戏规则微改+AI算法
考虑到时间成本，如果我用C++写，很可能要花很多时间才能体会到游戏规则和官方的一模一样，而我直接用JS加一些优化，当我的东西很少的时候时间，也许从完成游戏案例开始，是更好的选择。
实施过程 1.修改原有游戏规则，使时间禁止
我们首先要做的是将下落速度改为0，这对后面的调试起到关键作用。 修改起来其实很简单，去掉每次掉落的定时器即可。
2.完成基本状态枚举+随机评价功能
我们直接模拟游戏键盘事件即可完成枚举方块序列攻略37，DFS显示所有终止状态。 需要保存的状态包括方块的位置、旋转方向、操作顺序等信息。 注意，由于一个区块掉落的最终决策平均为20左右，条条大路通罗马，我们可以做一个状态记录，使得每个区块在某个坐标状态下只被访问一次。 这样，至此，我们就完成了最基本的AI自动游戏的主要流程，虽然一开始会死掉。
3.完成PD算法
PD算法的实现并不复杂。 DFS每找到一个落点，就将当前方块填充到面板中，根据PD算法的6个特征计算得分。 这 6 个特征包括以下内容：
: 放置棋子的位置 (= the + (the of the piece / 2))Rows : The of rows .Row : The total of row . 空单元格与同一行上的单元格对应的行方块序列攻略37，反之亦然。 : 的总数。 A 当一个空单元格与一个单元格相同时，反之亦然。 孔洞：孔洞是一个空单元格，在同一单元格上方至少有一个单元格。井总和：井是一个空单元格，因此它们的左单元格和右单元格都是。
优化
当我第一次完成PD算法时，结果并没有我想象的那么好。 不能如期完成10000个方格。 游戏中途会出现很多连续的s和z，或者偶尔出现几个连续的is，所以几乎每次1000块左右就死了。 不管怎么调参数，始终卡在3W左右点。 另外我发现盒子越靠后，计算速度越慢，而且越来越明显。 理论上，游戏过程中的计算量不会变化太大，这让我很疑惑。
1.操作顺序回溯策略
游戏从前期到中期越来越慢是个大问题，尤其是在1000速度的时候。 就算我能写出很好的算法，我也永远无法支撑到一万元。 通过谷歌浏览器的性能检测器，我重点关注了DFS状态的保存。 最常用的 DFS 调用是状态保存和回溯。 因为我保存了操作顺序，而且是深拷贝。 而且操作序列是一个很长的字符串，而且会随着游戏的发展越来越长！ 事实上，我们不需要每次都复制整个序列。 可以根据N在序列中出现的位置递增回溯，这样即使在游戏进行到一半的时候，运行速度也可以和开始时差不多。
2.旋转修剪
在dfs过程中，由于立方体可以旋转，所以4个状态为一个循环。 但实际上并不是每个方格都需要旋转3次。 比如正方形根本不需要旋转，而Z、S、I型只有两种旋转状态。 这样可以减少很多中间决策开销和最终决策开销。
3.快速下降
注意dfs过程本来就是模拟键盘操作的，但是我们还是可以稍微改进一下。 如果一个方块在空中，它实际上并不需要在中途做很多花式旋转，它只是在最后绕着底部旋转。 因此，当我们的DFS搜索下层状态时，我们可以直接“跳”下到可触摸位置上方的位置。 这样就省去了中间路径的大量保存和回溯。
4、决策层数增加
事实上，无论你如何调整参数，只有一个方格的情况都不是一个长期的观点。 我们的搜索需要一次搜索更多的方格，也就是增加决策的层数。 在增加层数的过程中，需要更多的状态保存，比如每次多丢一个block时上一步的grid信息。 但是JS的计算性能比较有限。 没有前三个优化，第二层会很慢，不可能等到10000个区块被淘汰。 加上前面的3次优化后，就可以计算出第2层或第3层了。
在两层的情况下，你可以做完10000个方格，效果非常可观，可以得到一件T恤。
5.添加场景块
由于财富和保险的规则，如果场景中的方块越多，分数就会越高。 我发现在可以计算2层楼的情况下，只需要一半的高度就可以稳定整个局面。 因此，如果情况相对安全，可以使用搜索一层的策略来增加高度。 当情况危险时，使用搜索二楼的策略来稳定局势。
这样你就可以玩完10000个方格，同时拥有更多的方格。
总结
这次的最终成绩是35w，排名第48，和百万分的boss还有很大的差距。 但是对于我来说，这次比赛让我学到了很多，在时间有限的情况下，完成一个AI，看着AI自动完成10000个方格，也是很好的体验。最后，我要感谢组织者组织这样的活动~太棒了
以上就是关于：方块序列攻略37-【参与心得分享】腾讯内部赛道-鹅罗斯盒子活动笔记的相关内容，更多精彩请继续关注玩手游。
