文档章节

专题 俄罗斯方块的React实现 (三)AI算法及其实现

 田浩hoyt
发布于 2017/08/31 23:39
字数 1797
阅读 99
收藏 0

俄罗斯方块游戏本身的实现并不难,实现一个具备一定智能的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
作品 0
杭州
『七月直播』人工智能专场——用Python和C++,如何跻身科技前沿?

第一场——主题:人工智能学习与发展路线规划 7月19日(周四) 20:00 >主讲老师:唐宇迪 同济大学计算机博士,专注于机器学习与计算机视觉领域,深度学习领域一线实战专家,善于实现包括人脸...

51CTO学院
07/17
0
0
人工智能学习路线

学习路径: 1、看书,coursera视频教程,了解大数据和机器学习算法。 2、学习Python,爬虫以及基于Python的机器学习实战。 3、TensorFlow+Python学习,TensorFlowLite+Android学习。 以小项目...

飞行员塔塔
2017/12/16
0
1
『七月直播』人工智能第一场——人工智能学习与发展路线规划【唐宇迪老师】

第一场——主题:人工智能学习与发展路线规划 7月19日(周四) 20:00~21:00 >主讲老师:唐宇迪 同济大学计算机博士,专注于机器学习与计算机视觉领域,深度学习领域一线实战专家,善于实现...

51CTO学院
07/17
0
0
一篇文章讲清楚人工智能、机器学习和深度学习的区别和联系

人工智能的浪潮正在席卷全球,诸多词汇时刻萦绕在我们耳边:人工智能(Artificial Intelligence)、机器学习(Machine Learning)、深度学习(Deep Learning)。不少人对这些高频词汇的含义及...

深蓝学院
04/24
0
0
人工智能时代,开发者是逆袭还是走向末日?

去年,由美国人工智能协会(American Association for Artificial Intelligence)组织的AAAI大会上,在2571篇投稿论文中,中国的投稿数量占到31%。虽然在被接收论文数量上仍有不足,但数量已...

AI科技大本营
09/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部