文档章节

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

 田浩hoyt
发布于 2017/08/31 23:39
字数 1797
阅读 95
收藏 0
点赞 0
评论 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学院
昨天
0
0
一篇文章讲清楚人工智能、机器学习和深度学习的区别和联系

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

深蓝学院
04/24
0
0
『七月直播』人工智能第一场——人工智能学习与发展路线规划【唐宇迪老师】

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

51CTO学院
昨天
0
0
人工智能学习路线

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

飞行员塔塔
2017/12/16
0
1
人工智能、大数据、复杂系统学习

黑科技,人工智能前进之路势不可挡! “做大做强新兴产业集群,实施大数据发展行动,加强新一代人工智能研发应用。发展智能产业,拓展智能生活。” 人工智能已作为国家乃至全球新的经济增长动...

自学号
05/10
0
0
顶级AI医学影像课程,第五期:福州大学生物医学与健康工程首席科学家、研究院长余轮教授主讲

主题:人工智能和医疗影像:基于眼底影像和人工智能的健康医学服务系统 时间:1月11日(周四),晚上8点 嘉宾:余轮教授,福州大学生物医学与健康工程首席科学家、研究院长,德国汉堡大学医学...

李雨晨
01/10
0
0
大数据、人工智能、机器学习、深度学习,这些到底在说什么?

1,大数据、人工智能、机器学习、深度学习的关系。 大数据,或者说大数据分析平台,更具体一点就是大数据分析PaaS平台,其实是一种针对需要处理海量数据统计分析的PaaS云平台。 大数据学习可...

卢家大少
06/06
0
0
基于 React 的高质量坦克大战复刻版

坦克大战当年红遍大江南北,很多和我一样的九零后应该都有着对这个游戏的记忆。现在显示器分辨率越来越高,使用矢量图来实现像素风格游戏,可以获得非常高的展现质量。该复刻版 是我花了很长...

cacao111
07/11
0
0
浙大的游戏设计教程

第一部分 游戏程序设计概览 计算机游戏简介:什么是游戏、游戏的分类等 游戏的基本开发流程? 游戏开发的基本理念及方法 游戏软件的体系结构:包括三维游戏引擎的架构分析 游戏的调试与测试 ...

Matrix4X4
2012/08/19
361
2
前沿情报丨当人工智能遇上量子计算机 AlphaGo将爆发出洪荒之力

这一周, 人工智能成为新闻热词, AlphaGo对战世界围棋第一人柯洁, 掀起了人工智能与人类的一场智力巅峰对决。 但几乎不出人意料, AlphaGo连胜两局。 聂卫平开玩笑道: “柯洁想赢估计只能...

雪花又一年
05/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

流利阅读笔记29-20180718待学习

高等教育未来成谜,前景到底在哪里? Ray 2018-07-18 1.今日导读 在这个信息爆炸的年代,获取知识是一件越来越容易的事情。人们曾经认为,如此的时代进步会给高等教育带来众多便利。但事实的...

aibinxiao
20分钟前
7
0
第15章FTP服务搭建与配置

15.1FTP介绍 FTP多用于Windows传文件到linux rz sz在文件超过4G,就无法使用了——>安装包yum install -y install lrzsz rz把 window 上的文件传输到 linux 上 sz 把 linux 上的文件传输到 ...

Linux学习笔记
27分钟前
0
0
OSChina 周三乱弹 —— 你被我从 osc 老婆们名单中踢出了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小鱼丁:分享五月天的单曲《后来的我们 (电影《后来的我们》片名曲)》: 《后来的我们 (电影《后来的我们》片名曲)》- 五月天 手机党少年们想...

小小编辑
32分钟前
7
1
Spring Boot Admin 2.0开箱体验

概述 在我之前的 《Spring Boot应用监控实战》 一文中,讲述了如何利用 Spring Boot Admin 1.5.X 版本来可视化地监控 Spring Boot 应用。说时迟,那时快,现在 Spring Boot Admin 都更新到 ...

CodeSheep
51分钟前
0
0
Python + Selenium + Chrome 使用代理 auth 的用户名密码授权

米扑代理,全球领导的代理品牌,专注代理行业近十年,提供开放、私密、独享代理,并可免费试用 米扑代理官网:https://proxy.mimvp.com 本文示例,是结合米扑代理的私密、独享、开放代理,专...

sunboy2050
今天
0
0
实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
今天
1
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

六库科技
今天
0
0
牛客网刷题

1. 二维数组中的查找(难度:易) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...

大不了敲一辈子代码
今天
0
0
linux系统的任务计划、服务管理

linux任务计划cron 在linux下,有时候要在我们不在的时候执行一项命令,或启动一个脚本,可以使用任务计划cron功能。 任务计划要用crontab命令完成 选项: -u 指定某个用户,不加-u表示当前用...

黄昏残影
昨天
0
0
设计模式:单例模式

单例模式的定义是确保某个类在任何情况下都只有一个实例,并且需要提供一个全局的访问点供调用者访问该实例的一种模式。 实现以上模式基于以下必须遵守的两点: 1.构造方法私有化 2.提供一个...

人觉非常君
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部