月初看到TEG公众号推送的极客挑战赛, 主题居然是完成俄罗斯方块的游戏, 顿时来了精神. 想起当初编写各种QQ游戏大厅外挂的快乐时光, 已经快十年了吧.
解题这几天实在是太开心了, 实在值得写一篇帖子记录一下.
本文不涉及具体的代码, 主要是记录和分享一下自己的思路和心得.
也是抛砖引玉, 期待能看到其他选手的宝贵思路.
游戏是网页呈现, 页面代码的注释里十分贴心地提供了调试和提交接口, 以及编译前的js源文件链接.
简单分析可以得知以下信息:
所以:
A. 试图欺骗服务器基本上行不通(不加验证才怪...
B. 方块数目存在上限, 通过不死策略刷分行不通.
C. 结合得分规则, 高分需要尽可能垒高盘面, 确实"富贵险中求".
方块出现次序固定, 于是题目变成了一个寻找最优解的问题. 大概率需要使用些启发式算法 (Hedonistic Algorithms).
悬停功能很有意思, 使得方块在盘面上部分摆脱了"重力", 近而可以考虑类似棋类游戏的布局方式.
俄罗斯方块问世已接近40年, 对相关策略算法的研究必然已经存在很多. 虽然本题目由于方块次序固定, 方块形状并非等概率出现, 方块次数存在上限等特性, 现有算法未必适用, 但终归还是要了解尝试下的.
搜索"俄罗斯方块+策略算法"这样的关键字, 被提到最多的大概就是Pierre Dellacherie算法了. 算法复杂度低, 清晰有效.
算法的策略结构为:
算法核心是针对盘面优劣的评估函数, Pierre Dellacherie算法中使用了6组特征, 包括:
这6组特征值乘以各自评估系数并求和, 即为最终的盘面优劣程度分数. 其中评估系数由算法提供.
不过针对本次比赛的题目, Pierre Dellacherie算法表现一般. 实现并微调过部分系数后, 此策略大概在3万多分后方块触顶结束游戏.
上面提到, Pierre Dellacherie算法提供了一组评估系数用于评估盘面优劣. 那这个评估系数从何而来呢? 如果想设计新的策略引入更多的盘面特征做评估, 原本的系数还有效吗? 新的系数又如何设置呢?
类似的问题, 遗传算法(Genetic Algorithm)可以给出答案. 遗传算法是由进化学说和遗传机制的启发发展出的一种优化算法. 广泛应用于参数优化的问题中. 前面描述的这组评估系数的选择, 就可以看作是参数优化问题.
遗传算法解决问题的过程如下:
不严谨地说, 这是一个瞎猫碰上死耗子的故事: 初代瞎猫们表现很差, 但架不住种群够大, 总会有有点视力能捡到死耗子的. 他们的后代眼神越来越好, 终将选育出了优秀的猎手.
回到俄罗斯方块的例子, 假设我们使用同Pierre Dellacherie算法相同的6组特征, 而希望通过遗传算法找到一组更合适的权重. 会怎样呢?
个人认为遗传算法的方案是比较适合本次题目的.
从题目设置上看, 因为方块序列是固定的, 某种程度是希望能达到一个"过拟合"的效果. 通过遗传算法可以轻易训练出一组或者多组模型以供选择. 从工程角度上看, 遗传算法很方便并行化实现.
自DeepMind两篇奠基性论文, DQN (Deep Q-Network)和AlphaGo发布, 几年来深度增强学习迅速发展, 诞生了很多重量级的应用.
本次题目也十分符合强化学习(Reinforcement Learning)的适用场景. 即:
而对应到俄罗斯方块的游戏设定:
网络上可以找到很多基于DQN实现俄罗斯方块AI的项目实践. 相信经过精心设计的强化学习策略是可以胜任这道题目的. 不过自己在这个方向上涉猎很浅, 所以这一次并没有深入探索. 或许有其他选手比赛中使用了基于RL的设计, 对于相关的经验分享十分期待.
这部分重点参照借用了 GABot 这篇帖子的内容, 原作者通过遗传算法设计了一个可以打破GameBoy上的俄罗斯方块游戏记录的AI算法.
遗传算法的原理已经在#2.2章节介绍过, 本章着重介绍一些实现细节, 更多信息可参考原帖.
第四章, 第五章将着重介绍针对本次比赛的特异性调整.
类似Pierre Dellacherie算法, 这里选择了9组特征用来评估盘面. 分别是:
评估函数即为9组特征与其权重的线性组合, 即
Fitness即为一个模型好坏的评价指标, 指标可以体现出模型选择的倾向性, 进而迭代出完全不同的策略模型. 比如这里使用每次游戏的最终得分作为评价每组参数好坏的标准.
通过这种方式实现的算法模型, 可以得到3万分左右的分数. 游戏大概持续几百块就会GameOver.
主要的原因是比赛规则的特殊性并没有被完全考虑和利用. 即所有方块的出现顺序是固定的.
于是, 问题就化解为两个新的目标, 即:
输入块的固定顺序带来了无限可能.
正是因为这种确定性, 某种程度上需要追求一种"过拟合"的效果获得更匹配,可以得到更高分数的模型.
上一章节中, 通过仅9个参数的单一的线性模型来完美覆盖10000个方块和局面是不现实的.
但"确定性"使得我们可以对这10000种局面进行分段处理, 对每个分段选择最适合的模型来保证不死/高分策略.
确定了这种方式后, 原本的问题就变成了两个子问题:
均匀分配最简单直接: 比如均匀分割成200个段, 每个模型处理50个方块的掉落摆放.
但是这个分段大小的参数其实并不容易选择, 因为针对某个特定的模型, 其可以有效处理的方块个数是不确定的.
因此我并没有限定分段的大小, 而是让每个模型玩到游戏结束后, 选择从其结束前的最合适衔接的一个盘面, 切换到下一个模型接管游戏.
无论如何分段, 分段之间的衔接都是需要考虑的重要问题.
每个分段结束后, 都会有一个"残局"留给下一个模型作为初始盘面. 残局的特点决定了能否顺利衔接.
最明显的特性就是, "残局"留下的空间是否足够下一组模型发挥.
由此, 可以通过限制"残局"中列的最高高度, 来保证不同分段之间的顺利交接.
综上, 对上一章节的遗传算法进行简单的包装改造, 就可以利用分段的方式使用多个模型顺利消化掉10000个方块.
具体来说, 在遗传算法每一代模型选择中, 不再使用模型完成游戏后总分数作为Fitness指标. 而是使用模型在游戏过程中, 使用局面不超过指定高度时刻获得的最高分数作为Fitness指标选择模型. 这样就可以选择出分数不错并且可以换个模型继续玩下去的模型, 舍弃掉分数很低或者分数很高但是很快会挂掉的模型. 这个用作fitness选择的中间盘面, 即为"残局", 用以作为下一段训练的初始盘面状态.
图3给出一个这样的例子, 指定模型之间交接的高度为10行, 某组参数在给定的初始状态下, 经历状态-1, 状态-2, 状态-3, 最后结束游戏得到12345的分数. 其中, 状态-2即为不超过10行最后盘面, 当时的得分8000分即为模型本轮的fitness值, 以及如果模型被选中, 状态-2的盘面状态将作为残局交由下一组模型.
程序运行中游戏的中间状态都会完整记录, 使得程序的调试和调优非常方便.
Again, 模型衔接的限制高度设置越低, 衔接越安全, 但是得分越低(因为积分的规则), 进展越慢(不是所有模型都可以将盘面消除到较低的情况);
相反地, 限制高度设置越高, 得分效率越高, 进展迅速, 但可能出现后续模型无法接手的情况.
我在测试中发现, 10~16的高度设置都是不错的选择. 完成这一步, 基本就可以做到30万以上的总分数了.
下一步, 是如何利用得分规则进一步提升得分效率.
游戏中每次消除得分计算公式为:
分数 = 盘面方块数 * 消除系数 (1,3,6,10对应一次消除1,2,3,4行).
这其中消除系数既定, 比较可控的是盘面块数, 可以通过设置较高的衔接高度(见上一章节)得到.
同时, 我们可以对Fitness指标进行进一步改造, 不再使用 局面不超过指定高度时刻获得的最高分数 , 而选择是局面不超过指定高度时刻,局内单位块数得分作为新的Fitness指标.
有些拗口, 还是以图3的游戏局面举个例子:
通过这种方式可以进一步筛选出得分效率高的模型. 但同时也降低了训练进展, 提高了分段衔接难度.
针对无法分段无法衔接的情况, 我使用了四种策略来缓解.
完成到这一步, 理论上可以达到70万以上的分数了.
而实际的情况是: 比赛的最后一天程序还没有跑完, 只好更改策略提交了一个59万的分数. 没能进入前20名, 非常遗憾.
总结起来, 还有很多地方可以改进的.
比如Fitness的选择可以更加精妙; 比如可以通过更完善的回退机制来提升整体训练过程的稳定性.
就游戏本身来说, 方块悬停或许在某种情况下可以比降落到底消除更多的行数. 以及方块下落过程中可能出现左右移动"蹭"进缺口的情况. 但基于我的模型设计下应该不会产生质的变化了.
参加这次比赛是个很宝贵的经历了, 很开心, 有收获.
第一次如此具体的实现和应用遗传算法解决问题. 以往自己对这类算法总有点直觉上的偏见, 这次却深深感受到这种"大力出奇迹"式的算法震撼到. 只依靠一组随机的起始参数, 配合几轮选择和随机的突变, 就可以实现如此精巧的控制策略. 十分神奇!
写到这会儿, 已经看到了Nano的题解和代码了, 官方也公开了前50名选手的提交记录.
看到大家对初始的题目设定会有类似的分析, 而根据各自的领域和能力选择出的策略又会如此不同.
方块掉落, 局面变得精彩起来, 有的优雅讲究, 力求最优; 有的粗犷豪放, 大刀阔斧. 背后隐隐约约透出智慧的光, 太奇妙了.
本来只想做个简单的记录, 结果越写越多, 啰哩啰嗦, 写下了这么长的一篇. 十分感谢你能耐心看到这里.
也十分感谢鹅厂的这次比赛. 来日方长, 后会有期, 我们下次比赛再见啦!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。