文档章节

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

 田浩hoyt
发布于 2017/08/31 23:39
字数 1797
阅读 121
收藏 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
全国人大常委会:对人工智能涉及的法律问题进行研究

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

新华网
11/24
0
0
基于 React Native 框架实现的俄罗斯方块 - react-tetris

react-tetris —— 用 React、Redux、Immutable 实现的俄罗斯方块游戏,支持自适应、数据持久化等。 在线体验:https://chvin.github.io/react-tetris/ 效果预览 正常速度的录制,体验流畅 ...

匿名
11/28
0
0
人工智能学习路线

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

飞行员塔塔
2017/12/16
0
1
技术争鸣!七大主题报告,四大技术专题,AI开发者大会首日议程全回顾

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/83899345 技术争鸣,座无虚席! 11 月 8 日,北京诺金酒店,2018 AI开发者...

AI科技大本营
11/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
11分钟前
1
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
27分钟前
1
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
28分钟前
6
0
MYSQL索引

索引的作用 索引类似书籍目录,查找数据,先查找目录,定位页码 性能影响 索引能大大减少查询数据时需要扫描的数据量,提高查询速度, 避免排序和使用临时表 将随机I/O变顺序I/O 降低写速度,占用磁...

关元
46分钟前
7
0
撬动世界的支点——《引爆点》读书笔记2900字优秀范文

撬动世界的支点——《引爆点》读书笔记2900字优秀范文: 作者:挽弓如月。因为加入火种协会的读书活动,最近我连续阅读了两本论述流行的大作,格拉德威尔的《引爆点》和乔纳伯杰的《疯传》。...

原创小博客
58分钟前
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部