【参赛经验分享】鹅罗斯方块解题报告: 遗传算法+分段策略

2021-08-16 10:14:18 浏览数 (1)

月初看到TEG公众号推送的极客挑战赛, 主题居然是完成俄罗斯方块的游戏, 顿时来了精神. 想起当初编写各种QQ游戏大厅外挂的快乐时光, 已经快十年了吧.

解题这几天实在是太开心了, 实在值得写一篇帖子记录一下.

本文不涉及具体的代码, 主要是记录和分享一下自己的思路和心得.

也是抛砖引玉, 期待能看到其他选手的宝贵思路.

1. 游戏信息收集

游戏是网页呈现, 页面代码的注释里十分贴心地提供了调试和提交接口, 以及编译前的js源文件链接.

简单分析可以得知以下信息:

  1. 提交内容包括指令序列和最后得分, 后台会对提交的分数和序列做有效性验证, 每天提交上限500次.
  2. 游戏区域为20行10列, 方块上限为10000块, 方块出现顺序和初始位置固定.
  3. 每次消行得分由消灭行数的对应系数与消行前盘面上已有格子数相乘得出.
  4. 游戏增加了"悬停"功能, 可以终止方块下落使其停在空中.
  5. 各形状方块出现概率不同, S, Z形最多, I形最少.

所以:

A. 试图欺骗服务器基本上行不通(不加验证才怪...

B. 方块数目存在上限, 通过不死策略刷分行不通.

C. 结合得分规则, 高分需要尽可能垒高盘面, 确实"富贵险中求".

方块出现次序固定, 于是题目变成了一个寻找最优解的问题. 大概率需要使用些启发式算法 (Hedonistic Algorithms).

悬停功能很有意思, 使得方块在盘面上部分摆脱了"重力", 近而可以考虑类似棋类游戏的布局方式.

2. 相关算法搜集

俄罗斯方块问世已接近40年, 对相关策略算法的研究必然已经存在很多. 虽然本题目由于方块次序固定, 方块形状并非等概率出现, 方块次数存在上限等特性, 现有算法未必适用, 但终归还是要了解尝试下的.

2.1 Pierre Dellacherie 算法

搜索"俄罗斯方块 策略算法"这样的关键字, 被提到最多的大概就是Pierre Dellacherie算法了. 算法复杂度低, 清晰有效.

算法的策略结构为:

  • 针对当前下落的方块, 存在旋转和调整落点两种操作 (其实并未覆盖所有操作情况, 详见后记讨论).
  • 方块最多有4种旋转可能, 落点数目取决于盘面列数(一般为10列). 因此可以穷举出最多40种可能情况.
  • 针对每一种情况, 算法通过一个评估函数计算其下落后盘面的优劣得分(用于评估盘面优劣程度, 非游戏得分). 进而可以选择出最优操作.

算法核心是针对盘面优劣的评估函数, Pierre Dellacherie算法中使用了6组特征, 包括:

  1. 下落高度(Landing Height)
  2. 消灭行数(Rows Eliminated)
  3. 行变换数(Row Transitions)
  4. 列变换数(Column Transitions)
  5. 空洞数目(Number of Holes)
  6. 井数(Well Sum)

这6组特征值乘以各自评估系数并求和, 即为最终的盘面优劣程度分数. 其中评估系数由算法提供.

不过针对本次比赛的题目, Pierre Dellacherie算法表现一般. 实现并微调过部分系数后, 此策略大概在3万多分后方块触顶结束游戏.

2.2 遗传算法 (Genetic Algorithm)

上面提到, Pierre Dellacherie算法提供了一组评估系数用于评估盘面优劣. 那这个评估系数从何而来呢? 如果想设计新的策略引入更多的盘面特征做评估, 原本的系数还有效吗? 新的系数又如何设置呢?

类似的问题, 遗传算法(Genetic Algorithm)可以给出答案. 遗传算法是由进化学说和遗传机制的启发发展出的一种优化算法. 广泛应用于参数优化的问题中. 前面描述的这组评估系数的选择, 就可以看作是参数优化问题.

遗传算法解决问题的过程如下:

  • 首先算法生成一定数量的个体集合(Population), 每个个体都包含一组决定其特性的遗传信息(Chromosome).
  • 然后算法通过适应值(Fitness)来评估个体的好坏程度.
  • 选择出适应良好的优秀个体, 将其遗传信息通过选择(Selection), 交叉(Crossover), 变异(Mutation)传递给下一代个体.
  • 周而复始直到得到满意的评估效果.
图1. 遗传算法基本流程图1. 遗传算法基本流程

不严谨地说, 这是一个瞎猫碰上死耗子的故事: 初代瞎猫们表现很差, 但架不住种群够大, 总会有有点视力能捡到死耗子的. 他们的后代眼神越来越好, 终将选育出了优秀的猎手.

回到俄罗斯方块的例子, 假设我们使用同Pierre Dellacherie算法相同的6组特征, 而希望通过遗传算法找到一组更合适的权重. 会怎样呢?

  • 首先, 初始化一个集合(比如包括了100个个体), 每个个体就是一组随机初始化的6个权重参数(遗传信息). 这样我们相当于得到了100个Pierre Dellacherie的变种算法.
  • 然后, 分别用他们进行俄罗斯方块的游戏直到游戏结束, 这时可以根据游戏的最后得分(适应度)来判断每个变种算法的好坏.
  • 选择一些表现比较好的个体, 将他们的权重信息进行交叉组合, 再添加一点点扰动, 构成了下一代变种算法集合.
  • 循环往复即可得到想要的权重组合.

个人认为遗传算法的方案是比较适合本次题目的.

从题目设置上看, 因为方块序列是固定的, 某种程度是希望能达到一个"过拟合"的效果. 通过遗传算法可以轻易训练出一组或者多组模型以供选择. 从工程角度上看, 遗传算法很方便并行化实现.

2.3 强化学习 (Reinforcement Learning)

自DeepMind两篇奠基性论文, DQN (Deep Q-Network)和AlphaGo发布, 几年来深度增强学习迅速发展, 诞生了很多重量级的应用.

本次题目也十分符合强化学习(Reinforcement Learning)的适用场景. 即:

  • 给定一个环境状态(State), 程序根据某种策略(Policy)选择一个对应的动作行为(Action);
  • 环境状态在执行动作后转变为新的状态, 同时程序获得了一个反馈值(Reward);
  • 程序根据反馈值对策略进行调整, 使得其在一系列动作中获得尽可能多的激励.

而对应到俄罗斯方块的游戏设定:

  • 游戏局面和当前下落的方块构成了环境状态(也可选择某种反映盘面特性的观测值作为状态);
  • 旋转和落点选择为需要考虑的动作行为;
  • 获得的分数(或其他量度指标)可以作为即时反馈值.

网络上可以找到很多基于DQN实现俄罗斯方块AI的项目实践. 相信经过精心设计的强化学习策略是可以胜任这道题目的. 不过自己在这个方向上涉猎很浅, 所以这一次并没有深入探索. 或许有其他选手比赛中使用了基于RL的设计, 对于相关的经验分享十分期待.

3. 遗传算法方案

这部分重点参照借用了 GABot 这篇帖子的内容, 原作者通过遗传算法设计了一个可以打破GameBoy上的俄罗斯方块游戏记录的AI算法.

遗传算法的原理已经在#2.2章节介绍过, 本章着重介绍一些实现细节, 更多信息可参考原帖.

第四章, 第五章将着重介绍针对本次比赛的特异性调整.

3.1 特征选择

类似Pierre Dellacherie算法, 这里选择了9组特征用来评估盘面. 分别是:

  1. 高度累加(Aggregate Height): 每一列的高度之和;
  2. "洞"数 (Number of holes): 所有"洞"的数目, "洞"即四周被方块或墙壁包围(直接或间接)的单位空格;
  3. 至少单洞的列数(Number of columns with at least one hole): 字面含义;
  4. 凹凸程度(Bumpiness): 相邻列高度差异绝对值之和;
  5. 列变换 (Row transitions): 空格与方块或墙壁相邻转换为一次变换;
  6. 行变换 (Column transitions): 同上;
  7. "坑"数 (Number of pits): "坑"指没有任何方块的列;
  8. 最大"井"深(Deepest well): "井"为两侧都有方块(或墙壁)填充的空列;
  9. 消除行数 (Lines cleared): 当前方块下落后可以消除的行数;

评估函数即为9组特征与其权重的线性组合, 即

score = w_1 * agg_height w_2 * n_holes w_3*n_cols_with_holes \ w_4 * bumpiness w_5 * row_trans w_6 * col_trans \ w_7 * n_pits w_8 * deepest_well w_9 * line_cleared

3.2 精英选择(Elitism), 选择(Selection), 交叉(Crossover) 和 变异(Mutation)

  • 精英选择 每一代模型评估后, 根据每个模型的Fitness指标, 选择分数前20%的个体可以直接进入到下一代模型评估.
  • 选择与交叉 同时, 以Fitness指标作为概率权重选择出两个模型, 交叉其权重参数生成下一代模型. 即新一代模型的每一项权重值都等概率继承自父亲或者母亲.
  • 变异 最后, 在新一代模型中随机选择出20%的个体, 在其参数上添加50%的高斯噪声, 以引入新的随机性.

图2. 种群进化的过程图2. 种群进化的过程

3.3 Fitness的选择

Fitness即为一个模型好坏的评价指标, 指标可以体现出模型选择的倾向性, 进而迭代出完全不同的策略模型. 比如这里使用每次游戏的最终得分作为评价每组参数好坏的标准.

通过这种方式实现的算法模型, 可以得到3万分左右的分数. 游戏大概持续几百块就会GameOver.

主要的原因是比赛规则的特殊性并没有被完全考虑和利用. 即所有方块的出现顺序是固定的.

于是, 问题就化解为两个新的目标, 即:

  1. 完全利用掉给定的10000个方块;
  2. 在1)基础上, 获得更高的得分效率.

4. 消灭10000块

输入块的固定顺序带来了无限可能.

正是因为这种确定性, 某种程度上需要追求一种"过拟合"的效果获得更匹配,可以得到更高分数的模型.

上一章节中, 通过仅9个参数的单一的线性模型来完美覆盖10000个方块和局面是不现实的.

但"确定性"使得我们可以对这10000种局面进行分段处理, 对每个分段选择最适合的模型来保证不死/高分策略.

确定了这种方式后, 原本的问题就变成了两个子问题:

  1. 如何分段?
  2. 如何保证分段之间, 模型之间的顺利衔接?

4.1 如何分段

均匀分配最简单直接: 比如均匀分割成200个段, 每个模型处理50个方块的掉落摆放.

但是这个分段大小的参数其实并不容易选择, 因为针对某个特定的模型, 其可以有效处理的方块个数是不确定的.

因此我并没有限定分段的大小, 而是让每个模型玩到游戏结束后, 选择从其结束前的最合适衔接的一个盘面, 切换到下一个模型接管游戏.

4.2 如何衔接

无论如何分段, 分段之间的衔接都是需要考虑的重要问题.

每个分段结束后, 都会有一个"残局"留给下一个模型作为初始盘面. 残局的特点决定了能否顺利衔接.

最明显的特性就是, "残局"留下的空间是否足够下一组模型发挥.

  • 如果残局行高太高, 即留下的空间太小, 那么下一个分段就很容易触顶;
  • 如果残局行高太矮, 留下大片空间, 那么会限制当下的得分效率. 毕竟得分与当下局面的方块数正相关.

由此, 可以通过限制"残局"中列的最高高度, 来保证不同分段之间的顺利交接.

综上, 对上一章节的遗传算法进行简单的包装改造, 就可以利用分段的方式使用多个模型顺利消化掉10000个方块.

具体来说, 在遗传算法每一代模型选择中, 不再使用模型完成游戏后总分数作为Fitness指标. 而是使用模型在游戏过程中, 使用局面不超过指定高度时刻获得的最高分数作为Fitness指标选择模型. 这样就可以选择出分数不错并且可以换个模型继续玩下去的模型, 舍弃掉分数很低或者分数很高但是很快会挂掉的模型. 这个用作fitness选择的中间盘面, 即为"残局", 用以作为下一段训练的初始盘面状态.

图3给出一个这样的例子, 指定模型之间交接的高度为10行, 某组参数在给定的初始状态下, 经历状态-1, 状态-2, 状态-3, 最后结束游戏得到12345的分数. 其中, 状态-2即为不超过10行最后盘面, 当时的得分8000分即为模型本轮的fitness值, 以及如果模型被选中, 状态-2的盘面状态将作为残局交由下一组模型.

图3. 不超过高度限制(10)获得的最高分数为8000分.图3. 不超过高度限制(10)获得的最高分数为8000分.

程序运行中游戏的中间状态都会完整记录, 使得程序的调试和调优非常方便.

Again, 模型衔接的限制高度设置越低, 衔接越安全, 但是得分越低(因为积分的规则), 进展越慢(不是所有模型都可以将盘面消除到较低的情况);

相反地, 限制高度设置越高, 得分效率越高, 进展迅速, 但可能出现后续模型无法接手的情况.

我在测试中发现, 10~16的高度设置都是不错的选择. 完成这一步, 基本就可以做到30万以上的总分数了.

5. 获取更高分数

下一步, 是如何利用得分规则进一步提升得分效率.

游戏中每次消除得分计算公式为:

分数 = 盘面方块数 * 消除系数 (1,3,6,10对应一次消除1,2,3,4行).

这其中消除系数既定, 比较可控的是盘面块数, 可以通过设置较高的衔接高度(见上一章节)得到.

同时, 我们可以对Fitness指标进行进一步改造, 不再使用 局面不超过指定高度时刻获得的最高分数 , 而选择是局面不超过指定高度时刻,局内单位块数得分作为新的Fitness指标.

有些拗口, 还是以图3的游戏局面举个例子:

  • 模型接手游戏时, 游戏是50块5000分的初始状态;
  • 模型玩到110块 / 12345分的时候GameOver了;
  • 但是GameOver之前出现过局面高度小于10的情况(衔接高度设置为10), 当时的情况是85块,8000分;
  • 则此模型的局内单位块数得分为 (8000-5000)/(85-50) = 120分/块;

通过这种方式可以进一步筛选出得分效率高的模型. 但同时也降低了训练进展, 提高了分段衔接难度.

针对无法分段无法衔接的情况, 我使用了四种策略来缓解.

  1. 回退: 回退到上一段或者更久之前的状态, 重新训练, 依靠遗传算法的随机性绕过不利局面.
  2. 回退 限制修改: 回退到上一段或者更久之前的状态, 修改衔接高度重新训练, 促使局面改变.
  3. 回退 模型切换: 回退到上一段或者更久之前的状态, 换用不同的Fitness指标将局面清理出更多的空间供后续模型发挥.
  4. 双线并进: 主程序进行的同时, 使用不同的进程/机器从中间状态独立训练用以作为替补状态.

完成到这一步, 理论上可以达到70万以上的分数了.

而实际的情况是: 比赛的最后一天程序还没有跑完, 只好更改策略提交了一个59万的分数. 没能进入前20名, 非常遗憾.

6. 后记

总结起来, 还有很多地方可以改进的.

比如Fitness的选择可以更加精妙; 比如可以通过更完善的回退机制来提升整体训练过程的稳定性.

就游戏本身来说, 方块悬停或许在某种情况下可以比降落到底消除更多的行数. 以及方块下落过程中可能出现左右移动"蹭"进缺口的情况. 但基于我的模型设计下应该不会产生质的变化了.

参加这次比赛是个很宝贵的经历了, 很开心, 有收获.

第一次如此具体的实现和应用遗传算法解决问题. 以往自己对这类算法总有点直觉上的偏见, 这次却深深感受到这种"大力出奇迹"式的算法震撼到. 只依靠一组随机的起始参数, 配合几轮选择和随机的突变, 就可以实现如此精巧的控制策略. 十分神奇!

图4. 由遗传算法生成的摆放策略图4. 由遗传算法生成的摆放策略

写到这会儿, 已经看到了Nano的题解和代码了, 官方也公开了前50名选手的提交记录.

看到大家对初始的题目设定会有类似的分析, 而根据各自的领域和能力选择出的策略又会如此不同.

方块掉落, 局面变得精彩起来, 有的优雅讲究, 力求最优; 有的粗犷豪放, 大刀阔斧. 背后隐隐约约透出智慧的光, 太奇妙了.

本来只想做个简单的记录, 结果越写越多, 啰哩啰嗦, 写下了这么长的一篇. 十分感谢你能耐心看到这里.

也十分感谢鹅厂的这次比赛. 来日方长, 后会有期, 我们下次比赛再见啦!

引用

  1. el-tetris, https://imake.ninja/el-tetris-an-improvement-on-pierre-dellacheries-algorithm/
  2. DQN https://medium.com/mlearning-ai/reinforcement-learning-on-tetris-707f75716c37
  3. DQN_BOThttps://github.com/michiel-cox/Tetris-DQN
  4. GA https://en.wikipedia.org/wiki/Genetic_algorithm
  5. GABot https://towardsdatascience.com/beating-the-world-record-in-tetris-gb-with-genetics-algorithm-6c0b2f5ace9b
腾讯极客挑战赛

0 人点赞