专题 俄罗斯方块的React实现 (三)AI算法及其实现
专题 俄罗斯方块的React实现 (三)AI算法及其实现
田浩hoyt 发表于8个月前
专题 俄罗斯方块的React实现 (三)AI算法及其实现
  • 发表于 8个月前
  • 阅读 86
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

俄罗斯方块游戏本身的实现并不难,实现一个具备一定智能的AI有一定的难度。

整体思路

由于方块的每次可能的着陆状态是有限的,因此枚举所有的着陆可能,并结合当前游戏区域的状态,给每一种可能性予以评分,最后选择得分最高的着陆点,然后生成一条从起落点到终点的路径,就是一个砖块的解。重复这个步骤,就是一个游戏ai。

上述的步骤中,着陆点枚举(包含砖块状态枚举)相对较容易实现,除此之外,有几个难点和关键点:

  • 状态分析,给定一个当前的游戏数据矩阵和活动砖块的着陆点,分析这种结果的好坏
  • 已知活动砖块的起始状态和终止状态,给出一个状态变化序列描述这个过程

状态分析

现有分析指标

如何评判一个俄罗斯方块游戏局给定状态的好坏呢?作为一名年长的俄罗斯方块玩家,我个人有如下一些经验:

  • 游戏区域残留的砖块越少越安全
  • 如果一个砖块下落,可以消除某几行,那么优先考虑这个着陆点
  • 尽量不要让砖块落下后导致出现空洞
  • 砖块最好分布的比较均匀,不要一些地方对了很高、一些地方很低

这些经验可以转化成量化手段,LeeYiyuan在自己的AI实现中提出了是个指标来评价一个着陆状态。原文地址见:http://codemyroad.wordpress.com/2013/04/14/tetris-ai-the-near-perfect-player/ (需要翻墙)。这四个指标分别是:

  • 消除行数,新砖块下落后能消除多少行
  • 空洞数,新砖块下落后,当前局势有多少个空洞
  • 井的数量,新砖块下落后,当前局势井的数量
  • 平整度,新砖块下落后,各列之间的高度差绝对值之和

还有一些更为复杂的评价体系,会将砖块的旋转、水平、垂直方向上的移动都考虑进去。

本文的评价模型

在综合考虑了多种指标体系之后,我采用了一个仿照LeeYiyuan体系的指标,唯一的不同之处是,LeeYiyuan考虑的井这种特殊形状,我放弃了考虑井,取而代之,引入一个新指标:平均高度。因此,本文使用的完整评价指标为:

  • 消除行数,新砖块下落后能消除多少行
  • 平均高度,新砖块下落后,当前局势的平均高度(刨去将被消除的行)
  • 空洞数,新砖块下落后,当前局势有多少个空洞(刨去将被消除的行)
  • 平整度,新砖块下落后,各列之间的高度差绝对值之和(刨去将被消除的行)

虽然只有4个指标,但已经足以量化当前局势的状态。通过平均高度和平整度两个指标,可以激励ai将砖块均匀的分布在游戏区域;通过消除行数,可以激励ai尽可能寻找机会消除砖块;通过平均高度、平整度和空洞度,可以激励ai在压制高度的同时,尽量避免造成空洞。

指标权重

光有这几个指标还不行,这些指标要能组合到一起起作用,还需要有合适的权重系数。指标的选取可以通过阅读文献来获得,但具体的加权系数,就要靠自己去尝试得出了,除非直接使用别人的指标/评价模型和评价方式。

那么如何得知这些指标各自的有效权重呢?通过非常经典的遗传算法,可以帮助我们找出各个指标适合的权重系数。

遗传算法

遗传算法模拟了自然界生物演化的过程,通过不断筛选出适应性更高的个体,并使它们互相结合,甚至引入少量的突变个体,经过几代的演化之后,就能够得出一些近似的最优解。

具体到俄罗斯方块这个项目,遗传算法的应用如下:

  1. 首先生成一批种子权重值,每一项权重的权重值x介于(-val, val)之间,val可以取0.5或者1,初始种子的适应性(fitness)都可以置为Number.NEGATIVE_INFINITY

  2. ai逐一使用这些种子包含的权重系数,去控制游戏,将经历的活动砖块数直接作为适应性的结果

  3. 当所有种子都计算出对应的适应性值时,对种子集按照适应性结果进行排序,按照降序排列,种群前60%的种子保留到下一轮演化,其余的淘汰

  4. 剩下的60%的候选种子进行杂交,并伴随一定概率的突变,得到一个新种群

  5. 重复2~4的步骤,直至候选种群小于某个阈值

在实际的尝试过程中,一般初始种群为1000时,经过2轮演化就会得到一组可以存活超过2000个砖块的种子,运气最好的一次,初始种群里就遇到了一个超过3000个砖块仍然存活的系数种子。

项目中给出了一个专门的遗传算法训练过程页面,可以看到整个遗传算法的实际演化过程。http://open.hoyt-tian.com/Tetris/evolution.html 看着AI一点一点的“聪明”起来,真让人感慨,一个看似复杂的规律,可能背后实际的操控因子就那么简单几个。

路径算法

在已知了活动砖块的起始状态和终止状态时,砖块的路径就比较容易得到了。

首先将砖块旋转到终止状态,然后进行水平方向的移动,最后进行垂直移动,即可到达最终态。而这个操作过程形成的队列,就是需要的结果。

可能有人有疑问,有的时候,还会出现移动到特定位置后的旋转、变形或者水平移动的情况,然后再进行移动。的确,人类在玩俄罗斯方块的时候,时常出现这种情况,来填补由于操作失误或者其他原因导致的部分砖块悬挂,形成的侧边空洞。但为什么这里没有考虑呢?一,是为了简化问题,二是,本身的评价模型中,就考虑了尽量避免这种情况。因为模型的平整性、平均高度两个指标,已经要求ai在考虑时,不要出现某个砖块悬空的情况。实际实践时,也发现ai并不会作出侧边空洞,能够存活很久。

至此,俄罗斯方块的AI实现主要内容全部介绍完毕,详细的实现请参照github代码。

标签: 俄罗斯方块
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 5
码字总数 4943
×
田浩hoyt
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: