文档章节

程序员带你一步步分析AI如何玩Flappy Bird

Yao--靠自己
 Yao--靠自己
发布于 2017/07/12 10:18
字数 4424
阅读 18
收藏 0

       以下内容来源于一次部门内部的分享,主要针对AI初学者,介绍包括CNN、Deep Q Network以及TensorFlow平台等内容。由于笔者并非深度学习算法研究者,因此以下更多从应用的角度对整个系统进行介绍,而不会进行详细的公式推导。

 

       关于Flappy Bird Flappy Bird(非官方译名:笨鸟先飞)是一款2013年鸟飞类游戏,由越南河内独立游戏开发者阮哈东(Dong Nguyen)开发,另一个独立游戏开发商GEARS Studios发布。—— 以上内来自《维基百科》 Flappy Bird操作简单,通过点击手机屏幕使Bird上升,穿过柱状障碍物之后得分,碰到则游戏结束。由于障碍物高低不等,控制Bird上升和下降需要反应快并且灵活,要得到较高的分数并不容易,笔者目前最多得过10分。

       本文主要介绍如何通过AI(人工智能)的方式玩Flappy Bird游戏,分为以下四个部分内容: Flappy Bird 游戏展示 模型:卷积神经网络 算法:Deep Q Network 代码:TensorFlow实现 一、Flappy Bird 游戏展示 在介绍模型、算法前先来直接看下效果,上图是刚开始训练的时候,画面中的小鸟就像无头苍蝇一样乱飞,下图展示的是在本机(后面会给出配置)训练超过10小时后(训练步数超过2000000)的情况,其最好成绩已经超过200分,人类玩家已基本不可能超越。


训练数小于10000步(刚开始训练)

 

训练步数大于2000000步(10小时后)

 

        由于本机配置了CUDA以及cuDNN,采用了NVIDIA的显卡进行并行计算,所以这里提前贴一下运行时的日志输出。

        关于CUDA以及cuDNN的配置,其中有一些坑包括:安装CUDA之后循环登录,屏幕分辨率无法正常调节等等,都是由于NVIDIA驱动安装的问题,这不是本文要讨论的主要内容,读者可自行Google。

 

  • 加载CUDA运算库
  • 加载CUDA运算库

  • TensorFlow运行设备 /gpu:0
  • TensorFlow运行设备/gpu:0

  • /gpu:0 这是TensorFlow平台默认的配置方法,表示使用系统中的第一块显卡。 本机软硬件配置: 系统:Ubuntu 16.04 显卡:NVIDIA GeForce GTX 745 4G 版本:TensorFlow 1.0 软件包:OpenCV 3.2.0、Pygame、Numpy、… 细心的朋友可能发现,笔者的显卡配置并不高,GeForce GTX 745,显存3.94G,可用3.77G(桌面占用了一部分),属于入门中的入门。对于专业做深度学习算法的朋友,这个显卡必然是不够的。知乎上有帖子教大家怎么配置更专业的显卡,有兴趣的可以移步。

 

二、模型:卷积神经网络

神经网络算法是由众多的神经元可调的连接权值连接而成,具有大规模并行处理、分布式信息存储、良好的自组织自学习能力等特点。人工神经元与生物神经元结构类似,其结构对比如下图所示。

生物神经元

 

人工神经元

       人工神经元的输入(x1,x2...xm)类似于生物神经元的树突,输入经过不同的权值(wk1, wk2, ....wkn),加上偏置,经过激活函数得到输出,最后将输出传输到下一层神经元进行处理。 单神经元输出函数 激活函数为整个网络引入了非线性特性,这也是神经网络相比于回归等算法拟合能力更强的原因。常用的激活函数包括sigmoid、tanh等,它们的函数表达式如下:

sigmoid函数

tanh双曲正切函数

这里可以看出,sigmoid函数的值域是(0,1),tanh函数的值域是(-1,1)。

卷积神经网络起源于动物的视觉系统,主要包含的技术是:

  1. 局部感知域(稀疏连接);
  2. 参数共享;
  3. 多卷积核;
  4. 池化。

1. 局部感知域(稀疏连接) 全连接网络的问题在于:

  1. 需要训练的参数过多,容器导致结果不收敛(梯度消失),且训练难度极大;
  2. 实际上对于某个局部的神经元来讲,它更加敏感的是小范围内的输入,换句话说,对于较远的输入,其相关性很低,权值也就非常小。 人类的视觉系统决定了人在观察外界的时候,总是从局部到全局。

       比如,我们看到一个美女,可能最先观察到的是美女身上的某些部位(自己体会)。

       因此,卷积神经网络与人类的视觉类似,采用局部感知,低层的神经元只负责感知局部的信息,在向后传输的过程中,高层的神经元将局部信息综合起来得到全局信息。

全连接与局部连接的对比(图片来自互联网)

       从上图中可以看出,采用局部连接之后,可以大大的降低训练参数的量级。

   2. 参数共享

       虽然通过局部感知降低了训练参数的量级,但整个网络需要训练的参数依然很多。

        参数共享就是将多个具有相同统计特征的参数设置为相同,其依据是图像中一部分的统计特征与其它部分是一样的。其实现是通过对图像进行卷积(卷积神经网络命名的来源)。

       可以理解为,比如从一张图像中的某个局部(卷积核大小)提取了某种特征,然后以这种特征为探测器,应用到整个图像中,对整个图像顺序进行卷积,得到不同的特征。
 

卷积过程(图片来自互联网)

       每个卷积都是一种特征提取方式,就像一个筛子,将图像中符合条件(激活值越大越符合条件)的部分筛选出来,通过这种卷积就进一步降低训练参数的量级。

  • 3. 多卷积核

       如上,每个卷积都是一种特征提取方式,那么对于整幅图像来讲,单个卷积核提取的特征肯定是不够的,那么对同一幅图像使用多种卷积核进行特征提取,就能得到多幅特征图(feature map)

不同的卷积核提取不同的特征(图片来自互联网)

多幅特征图可以看成是同一张图像的不同通道,这个概念在后面代码实现的时候用得上。

  • 4. 池化

         得到特征图之后,可以使用提取到的特征去训练分类器,但依然会面临特征维度过多,难以计算,并且可能过拟合的问题。从图像识别的角度来讲,图像可能存在偏移、旋转等,但图像的主体却相同的情况。也就是不同的特征向量可能对应着相同的结果,那么池化就是解决这个问题的。

        池化就是将池化核范围内(比如2*2范围)的训练参数采用平均值(平均值池化)或最大值(最大值池化)来进行替代。

        终于到了展示模型的时候,下面这幅图是笔者手画的(用电脑画太费时,将就看吧),这幅图展示了本文中用于训练游戏所用的卷积神经网络模型。

卷积神经网络模型

图像的处理过程

  1. 初始输入四幅图像80×80×4(4代表输入通道,初始时四幅图像是完全一致的),经过卷积核8×8×4×32(输入通道4,输出通道32),步距为4(每步卷积走4个像素点),得到32幅特征图(feature map),大小为20×20;
  2. 将20×20的图像进行池化,池化核为2×2,得到图像大小为10×10;
  3. 再次卷积,卷积核为4×4×32×64,步距为2,得到图像5×5×64;
  4. 再次卷积,卷积核为3×3×64*64,步距为2,得到图像5×5×64,虽然与上一步得到的图像规模一致,但再次卷积之后的图像信息更为抽象,也更接近全局信息;
  5. Reshape,即将多维特征图转换为特征向量,得到1600维的特征向量;
  6. 经过全连接1600×512,得到512维特征向量;
  7. 再次全连接512×2,得到最终的2维向量[0,1]和[1,0],分别代表游戏屏幕上的是否点击事件。

 

        可以看出,该模型实现了端到端的学习,输入的是游戏屏幕的截图信息(代码中经过opencv处理),输出的是游戏的动作,即是否点击屏幕。深度学习的强大在于其数据拟合能力,不需要传统机器学习中复杂的特征提取过程,而是依靠模型发现数据内部的关系。

        不过这也带来另一方面的问题,那就是深度学习高度依赖大量的标签数据,而这些数据获取成本极高。

三、算法:Deep Q Network

 

        有了卷积神经网络模型,那么怎样训练模型?使得模型收敛,从而能够指导游戏动作呢?机器学习分为监督学习、非监督学习和强化学习,这里要介绍的Q Network属于强化学习(Reinforcement Learning)的范畴。在正式介绍Q Network之前,先简单说下它的光荣历史。

        2014年Google 4亿美金收购DeepMind的桥段,大家可能听说过。那么,DeepMind是如何被Google给盯上的呢?最终原因可以归咎为这篇论文:

Playing Atari with Deep Reinforcement Learning

 

        DeepMind团队通过强化学习,完成了20多种游戏,实现了端到端的学习。其用到的算法就是Q Network。2015年,DeepMind团队在《Nature》上发表了一篇升级版:

Human-level control through deep reinforcement learning

 

        自此,在这类游戏领域,人已经无法超过机器了。后来又有了AlphaGo,以及Master,当然,这都是后话了。其实本文也属于上述论文的范畴,只不过基于TensorFlow平台进行了实现,加入了一些笔者自己的理解而已。

        回到正题,Q Network属于强化学习,那么先介绍下强化学习。

强化学习模型    

这张图是从UCL的课程中拷出来的,课程链接地址(YouTube):
https://www.youtube.com/watch?v=2pWv7GOvuf0

        强化学习过程有两个组成部分:

  • 智能代理(学习系统)
  • 环境

        如图所示,在每步迭代过程中,首先智能代理(学习系统)接收环境的状态st,然后产生动作at作用于环境,环境接收动作at,并且对其进行评价,反馈给智能代理rt。不断的循环这个过程,就会产生一个状态/动作/反馈的序列:(s1, a1, r1, s2, a2, r2.....,sn, an, rn),而这个序列让我们很自然的想起了:

  • 马尔科夫决策过程

MDP:马尔科夫决策过程

    马尔科夫决策过程与著名的HMM(隐马尔科夫模型)相同的是,它们都具有马尔科夫特性。那么什么是马尔科夫特性呢?简单来说,就是未来的状态只取决于当前的状态,与过去的状态无关。

HMM(马尔科夫模型)在语音识别,行为识别等机器学习领域有较为广泛的应用。条件随机场模型(Conditional Random Field)则用于自然语言处理。两大模型是语音识别、自然语言处理领域的基石。

 

        上图可以用一个很形象的例子来说明。比如你毕业进入了一个公司,你的初始职级是T1(对应图中的 s1),你在工作上刻苦努力,追求上进(对应图中的a1),然后领导觉得你不错,准备给你升职(对应图中的r1),于是,你升到了T2;你继续刻苦努力,追求上进......不断的努力,不断的升职,最后升到了sn。当然,你也有可能不努力上进,这也是一种动作,换句话说,该动作a也属于动作集合A,然后得到的反馈r就是没有升职加薪的机会。

        这里注意下,我们当然希望获取最多的升职,那么问题转换为:如何根据当前状态s(s属于状态集S),从A中选取动作a执行于环境,从而获取最多的r,即r1 + r2 ……+rn的和最大 ?这里必须要引入一个数学公式:状态值函数。
 

状态值函数模型

 

        公式中有个折合因子γ,其取值范围为[0,1],当其为0时,表示只考虑当前动作对当前的影响,不考虑对后续步骤的影响,当其为1时,表示当前动作对后续每步都有均等的影响。当然,实际情况通常是当前动作对后续得分有一定的影响,但随着步数增加,其影响减小。

         从公式中可以看出,状态值函数可以通过迭代的方式来求解。增强学习的目的就是求解马尔可夫决策过程(MDP)的最优策略。

        策略就是如何根据环境选取动作来执行的依据。策略分为稳定的策略和不稳定的策略,稳定的策略在相同的环境下,总是会给出相同的动作,不稳定的策略则反之,这里我们主要讨论稳定的策略。

        求解上述状态函数需要采用动态规划的方法,而具体到公式,不得不提:

  • 贝尔曼方程

贝尔曼方程

 

        其中,π代表上述提到的策略,Q π (s, a)相比于V π (s),引入了动作,被称作动作值函数。对贝尔曼方程求最优解,就得到了贝尔曼最优性方程

状态值函数最优解

动作值函数最优解

        求解该方程有两种方法:策略迭代值迭代

  • 策略迭代

策略迭代分为两个步骤:策略评估策略改进,即首先评估策略,得到状态值函数,其次,改进策略,如果新的策略比之前好,就替代老的策略。

策略迭代

  • 值迭代

从上面我们可以看到,策略迭代算法包含了一个策略估计的过程,而策略估计则需要扫描(sweep)所有的状态若干次,其中巨大的计算量直接影响了策略迭代算法的效率。而值迭代每次只扫描一次,更新过程如下:

值迭代

即在值迭代的第k+1次迭代时,直接将能获得的最大的Vπ(s)值赋给Vk+1。

  • Q-Learning

Q-Learning是根据值迭代的思路来进行学习的。该算法中,Q值更新的方法如下:

Q值更新方法

        虽然根据值迭代计算出目标Q值,但是这里并没有直接将这个Q值(是估计值)直接赋予新的Q,而是采用渐进的方式类似梯度下降,朝目标迈近一小步,取决于α,这就能够减少估计误差造成的影响。类似随机梯度下降,最后可以收敛到最优的Q值。具体算法如下:

Q-Learning算法

如果没有接触过动态规划的童鞋看上述公式可能有点头大,下面通过表格来演示下Q值更新的过程,大家就明白了。

 

状态 a1 a2 a3 a4
S1 Q(1, 1) Q(1, 2) Q(1, 3) Q(1, 4)
S2 Q(2, 1) Q(2, 2) Q(2, 3) Q(2, 4)
S3 Q(3, 1) Q(3, 2) Q(3, 3) Q(3, 4)
S4 Q(4, 1) Q(4, 2) Q(4, 3) Q(4, 4)

        Q-Learning算法的过程就是存储Q值的过程。上表中,横列为状态s,纵列为Action a,s和a决定了表中的Q值。

  • 第一步:初始化,将表中的Q值全部置0;
  • 第二步:根据策略及状态s,选择a执行。假定当前状态为s1,由于初始值都为0,所以任意选取a执行,假定这里选取了a2执行,得到了reward为1,并且进入了状态s3。根据Q值更新公式:

Q值更新公式

        来更新Q值,这里我们假设α是1,λ也等于1,也就是每一次都把目标Q值赋给Q。那么这里公式变成:

Q值更新公式

所以在这里,就是

本次Q值更新

那么对应的s3状态,最大值是0,所以

Q值

Q表格就变成:

状态 a1 a2 a3 a4
S1 0 1 0 0
S2 0 0 0 0
S3 0 0 0 0
S4 0 0 0 0

 

然后置位当前状态s为s3。

  • 第三步:继续循环操作,进入下一次动作,当前状态是s3,假设选择动作a3,然后得到reward为2,状态变成s1,那么我们同样进行更新:

Q值更新

所以Q的表格就变成:

状态 a1 a2 a3 a4
S1 0 1 0 0
S2 0 0 0 0
S3 0 0 3 0
S4 0 0 0 0
  • 第四步: 继续循环,Q值在试验的同时反复更新,直到收敛。

本文转载自:http://www.jianshu.com/p/0a04426ee3ad

共有 人打赏支持
Yao--靠自己
粉丝 2
博文 44
码字总数 20071
作品 0
哈尔滨
程序员
强化学习和AI适用场景的思考

随着AlphaGo和围棋第一人柯洁的对战,强化学习又将迎来一波热潮。 强化学习到底是怎么让机器能够玩游戏的,这个问题很久之前就困扰着我。 (如果需要从数理上了解强化学习,请阅读参考资料,...

中和软件技术推进
2017/04/14
0
0
Chrome暗藏的恐龙跳一跳,已经被AI轻松掌握了

夏乙 郭一璞 发自 凹非寺 量子位 出品 | 公众号 QbitAI 什么!未连接到互联网!! 明明是联网状态,为什么我想访问的页面 无!法!打!开! 淡定。 作为一个Google Chrome浏览器的用户,当你...

yh0vlde8vg8ep9vge
05/08
0
0
Android 5.0 开发者预览版隐藏Flappy Bird克隆

在发布Android 5.0 Lollipop之后, Google发布了开发者预览版更新,加入了一些用户以后将会在正式版本中使用到的新功能,它还隐藏了一个至今最大的Android彩蛋——一个可玩的Flappy Bird克隆...

oschina
2014/10/21
4.8K
9
如何用Python脚本玩微信《跳一跳》游戏

  【IT168 资讯】近日,微信6.6.1 版本中加入了小游戏功能,并提供了官方 DEMO【跳一跳】。   大家在玩游戏的过程中,有没有觉得这款游戏似曾相识呢?该游戏通过按压屏幕事件的长短来控制...

it168网站
01/02
0
0
如何在 AI 领域找到高薪工作

文末彩蛋,错过哭一年。。。   随着AI产业快速突破,机器学习在各行各业开始崭露头角。各大公司在AI领域的人才动向也在引起极大关注,对技术熟练、知识渊博的研究人员和开发人员的需求将变得...

iodjsvf8u1j7kyc
01/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java异常处理最佳实践

总结一些Java异常的处理原则 Java异常处理最佳实践 不要忘记关闭资源 在finally里关闭资源 public void readFile() { FileInputStream fileInputStream = null; File file = new Fil...

yysue
38分钟前
0
0
00.编译OpenJDK-8u40的整个过程

前言 历经2天的折腾总算把OpenJDK给编译成功了,要说为啥搞这个,还得从面试说起,最近出去面试经常被问到JVM的相关东西,总感觉自己以前学的太浅薄,所以回来就打算深入学习,目标把《深入理...

凌晨一点
今天
4
0
python: 一些关于元组的碎碎念

初始化元组的时候,尤其是元组里面只有一个元素的时候,会出现一些很蛋疼的情况: def checkContentAndType(obj): print(obj) print(type(obj))if __name__=="__main__": tu...

Oh_really
昨天
6
2
jvm crash分析工具

介绍一款非常好用的jvm crash分析工具,当jvm挂掉时,会产生hs_err_pid.log。里面记录了jvm当时的运行状态以及错误信息,但是内容量比较庞大,不好分析。所以我们要借助工具来帮我们。 Cras...

xpbob
昨天
124
0
Qt编写自定义控件属性设计器

以前做.NET开发中,.NET直接就集成了属性设计器,VS不愧是宇宙第一IDE,你能够想到的都给你封装好了,用起来不要太爽!因为项目需要自从全面转Qt开发已经6年有余,在工业控制领域,有一些应用...

飞扬青云
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部