文档章节

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

 田浩hoyt
发布于 2017/08/31 23:39
字数 1797
阅读 146
收藏 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
杭州
私信 提问
如何让AI教机器自己玩俄罗斯方块?

作者 | Ahab 转载自公众号Ahab杂货铺(ID:PythonLearningCamp) 人工智能大火的今天,如果还是自己玩俄罗斯方块未免显得太 LOW,为什么不对游戏升级,让机器自己去玩俄罗斯方块呢?有了这个想...

AI科技大本营
02/18
0
0
让 AI 教机器自己玩俄罗斯方块

作者 | Ahab 责编 | 仲培艺 人工智能大火的今天,如果还是自己玩俄罗斯方块未免显得太 LOW,为什么不对游戏升级,让机器自己去玩俄罗斯方块呢?有了这个想法之后,我用了两天时间去搜集了大量...

CSDN资讯
02/18
0
0
『七月直播』人工智能专场——用Python和C++,如何跻身科技前沿?

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

51CTO学院
2018/07/17
0
0
我在这个开源项目里找到了童年!

提到《俄罗斯方块》(Tetris),那真是几乎无人不知无人不晓,除此之外,相信许多程序员第一个编程实践项目就是编写一个俄罗斯方块或者是坦克大战 这类的游戏各种编程语言的实现版本都有,今...

编程资源库
05/22
0
0
全国人大常委会:对人工智能涉及的法律问题进行研究

(原标题:全国人大常委会委员长会议组成人员进行专题学习 栗战书主持并讲话) 全国人大常委会委员长会议组成人员24日进行专题学习,学习习近平总书记在中央政治局第九次集体学习时的重要讲话...

新华网
2018/11/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

EasyExcel

<!-- alibaba EasyExcel escel导入导出 --> <dependency> <groupId>com.alibaba</groupId> <artifactId>easyexcel</artifactId> <version>1.0.0-RELEASE</version> </dependency>......

少年已不再年少
13分钟前
0
0
解决:warning: deprecated conversion from string constant to 'char*' [-Wwrite-strings]

代码 static int CheckOneReg(uint8_t busNo, char *title, int32_t addr, uint32_t *val, BOOL isPrintfNL, ErrMsg_t const *pMsg)res |= CheckOneReg(busNo,"fwVer:", HALREG_FW_VER, ......

SamXIAO
13分钟前
0
0
jenkins搭建全流程

安装环境   操作系统:linux   软件:jdk 8   软件:tomcat(apache-tomcat-7.0.90) 软件:jenkins 软件:maven 软件:git 1.1安装步骤 1.1.1安装jdk 由于Jenkins是基于Java开发的,安...

shzwork
19分钟前
0
0
Java的战争

本文来自微信公众号: 金捷幡(ID:jin-jiefan) ,作者:金捷幡,封面:拉里·埃里森(东方IC) 2019年5月,彻底撕破脸的特朗普掀起对华为的战争,谷歌被迫吊销了华为的Android授权。开源软...

Java领航员
今天
8
0
超详细的LM3414MRX/NOPB规格参数介绍就在这里

超详细的LM3414MRX/NOPB规格参数介绍就在这里 描述 LM3414和LM3414MRX/NOPB是具有1-A 60 W(1)共阳极功能的恒流降压LED驱动器。它们适用于驱动单串3-W HBLED,效率高达96%。它们可接受4.5...

不能吃肉的仙女
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部