马里奥 AI 实现方式探索 :神经网络+增强学习(下)

《马里奥 AI 实现方式探索 :神经网络+增强学习(上)》

马尔可夫决策过程(MDP)

一提到马尔科夫,大家通常会立刻想起马尔可夫链(Markov Chain)以及机器学习中更加常用的隐式马尔可夫模型(Hidden Markov Model, HMM)。它们都具有共同的特性便是马尔可夫性:当一个随机过程在给定现在状态及所有过去状态情况下,其未来状态的条件概率分布仅依赖于当前状态;换句话说,在给定现在状态时,它与过去状态(即该过程的历史路径)是条件独立的,那么此随机过程即具有马尔可夫性质。具有马尔可夫性质的过程通常称之为马尔可夫过程。7

之后我们便来说说马尔可夫决策过程(Markov Decision Process),其也具有马尔可夫性,与上面不同的是MDP考虑了动作,即系统下个状态不仅和当前的状态有关,也和当前采取的动作有关。

用表格描述马尔可夫各个模型的关系(摘自8)

基本定义

一个马尔可夫决策过程由五元组组成
  • S:表示状态集(states)
  • A:表示一系列动作(actions)
  • 表示状态转移概率。表示的是在当前s ∈ S状态下,经过a ∈ A作用后,会转移到的其他状态的概率分布情况。比如,在状态s下执行动作a,转移到s’的概率可以表示为p(s’|s,a)。

(dicount factor):表示阻尼系数[0,1)

  • R:
    ,表示回报函数(reward function) MDP 的动态过程如下:某个智能体(agent)的初始状态为s0,然后从 A 中挑选一个动作a0执行,执行后,agent 按概率随机转移到了下一个s1状态,s1∈
    。然后再执行一个动作a1,就转移到了s2,接下来再执行a2…,我们可以用下面的图表示状态转移的过程。
    如果回报r是根据状态s和动作a得到的,则MDP还可以表示成下图:
    值函数上面我们给出了MDP的定义,作为一个智能体(agent),当它在决定下一步应该走什么时,最简单的方式就是看下Reward函数的值是多少,即比较走不同动作的回报,从而做出决定。但是就像下棋的时候,我们每走一步都会向后考虑,所谓“走一步看三步”,所以这里我们只看一步即一次Reward函数是不够的,这就引出了值函数(Value Function)也叫折算累积回报(discounted cumulative reward)。状态值函数(state value function)当我们遵循某个策略
    ,我们将值函数定义如下:
    我们将上面的式子写作递推的样子如下:
    另外当策略
    ,在状态s时,我们可以确定唯一的动作a,但是s经过动作a会进入哪个状态是不唯一的,比如同样是掷骰子操作,可能得到的状态有6种,那么利用Bellman等式我们便可以得到下面的公式:
    再根据我们最初增强学习的目的,我们便可以得出,求V的目的就是想找到一个当前状态s下,最优的行动策略,表示如下:
    动作值函数(action value function)上面我们的值函数的只与状态s有关,如果与状态s和动作a都有关,便称为动作值函数,即所谓的Q函数,如下:
    从上式我们可以看出,我们不仅仅依赖状态s和策略,并且还依赖于动作a。综上我们可以将MDP的最优策略定义如下:
    关于MDP的求解主要分为值迭代和策略迭代,分别站在不同的角度对MDP进行求解,这里我们不在赘述,网上有很多相关资料。下面我们简单阐述下动作值函数的值迭代求解方式,即所谓的Q-learningQ学习Q学习的基本迭代公式如下:
    从公式中我们也可以看出它是一种值迭代方式,因为我们每次更新的是Q函数的值,而非策略。简单起见,整理一个简单的例子加以说明。假设我们有这样一个房间:
    我们的目的是训练一个机器人,使得它在图中的任意一个房间都能够到达房间外。OK,我们对房间进行建模:
    并得到reward矩阵:
    通过一下过程的迭代我们最终得出了我们的结果Q矩阵
    可以看出,我们的机器人现在无论在哪个房间,都可以利用我们的Q矩阵顺利的走到屋外。噗噗噗,终于写到这里了,综上我们将马里奥只能AI需要用到的算法简单整理了下(如有任何谬误请指出^v^)。下面我们结合两种成熟的算法,归纳整理马里奥AI的两种实现方式。基于NEAT算法的马里奥AI实现所谓NEAT算法即通过增强拓扑的进化神经网络(Evolving Neural Networks through Augmenting Topologies),算法不同于我们之前讨论的传统神经网络,它不仅会训练和修改网络的权值,同时会修改网络的拓扑结构,包括新增节点和删除节点等操作。 NEAT算法几个核心的概念是:
  • 基因:网络中的连接
  • 基因组:基因的集合
  • 物种:一批具有相似性基因组的集合
  • Fitness:有点类似于增强学习中的reward函数
  • generation:进行一组训练的基因组集合,每一代训练结束后,会根据fitness淘汰基因组,并且通过无性繁殖和有性繁殖来新增新的基因组
  • 基因变异:发生在新生成基因组的过程中,可能会出现改变网络的权重,增加突出连接或者神经元,也有可能禁用突触或者启用突触

下图我们展示了算法从最一开始简单的神经网络,一直训练到后期的网络

利用NEAT算法实现马里奥的只能通关的基本思想便是,利用上面NEAT算法的基本观点,从游戏内存中获取实时的游戏数据,判断马里奥是否死忙、计算Fitness值、判断马里奥是否通关等,从而将这些作为神经网络的输入,最后输出对马里奥的操作,包括上下左右跳跃等操作,如下图:

大多数该算法实现马里奥的智能通关都依赖于模拟器,运用lua语言编写相应脚本,获取游戏数据并操作马里奥。NeuroEvolution with MarI/O。实现效果图如下:

基于Deep Reinforcement Learning的马里奥AI实现

NEAT算法是相对提出较早的算法,在2013年大名鼎鼎的DeepMind提出了一种深度增强学习的算法,该算法主要结合了我们上面讨论的CNN和Q-Learning两种算法,DeepMind的研究人员将该算法应用在Atari游戏机中的多种小游戏中进行AI通关。

其基本算法核心便是我们之前介绍的CNN和增强学习的Q-Learning,游戏智能通关的基本流程如下图:

利用CNN来识别游戏总马里奥的状态,并利用增强学习算法做出动作选择,然后根据新的返回状态和历史状态来计算reward函数从而反馈给Q函数进行迭代,不断的训练直到游戏能够通关。研究人员在训练了一个游戏后,将相同的参数用在别的游戏中发现也是适用的,说明该算法具有一定的普遍性。下图反映了一个学习的过程

而同样的方法,将DRL应用在马里奥上,github上有一个开源的实现方式:aleju/mario-ai

其最终的实现效果图如下:

我们发现在CNN识别过程中,每4帧图像,才会进行一次CNN识别,这是识别速率的问题,图中曲线反映了直接回报函数和简介回报函数。

总结

综上便是从最基本的神经网络算法+增强学习,到将这些算法用在智能AI上的一些基本整理,长舒一口气,整理了好久。。。关于智能AI的应用有很多,也跟好多小伙伴讨论过,包括智能测试、新式游戏、游戏平衡性调整以及AI机器人的加入。这个领域除了枯燥的理论知识还能玩游戏,想想有点小激动。总结完毕,如有任何纰漏还请指出,我会尽快修改,谢谢^v^。

最后感谢smurfyu(于洋)、apache(何庆玮)的指导以及小伙伴lufyzhang(张宇飞)、youngywang(王洋)、supercwang(王超)、bingyanshi(施冰燕)

参考文献:

漫谈ANN(1):M-P模型

漫谈ANN(2):BP神经网络

卷积神经网络

卷积神经网络全面解析

重磅!神经网络浅讲:从神经元到深度学习

R.Sutton et al. Reinforcement learning: An introduction , 1998

马尔可夫性质

增强学习(二)——- 马尔可夫决策过程MDP

增强学习(三)——- MDP的动态规划解法

增强学习(Reinforcement Learning and Control)

wiki-Q-learning

Q-Learning example

Stanley K O, Miikkulainen R. Evolving neural networks through augmenting topologiesJ. Evolutionary computation, 2002, 10(2): 99-127.

Wang Y, Schreiber B. Creating a Traffic Merging Behavior Using NeuroEvolution of Augmenting TopologiesJ. 2015.

Cussat-Blanc S, Harrington K, Pollack J. Gene regulatory network evolution through augmenting topologiesJ. IEEE Transactions on Evolutionary Computation, 2015, 19(6): 823-837.

Mnih V, Kavukcuoglu K, Silver D, et al. Playing atari with deep reinforcement learningJ. arXiv preprint arXiv:1312.5602, 2013.

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

1 条评论
登录 后参与评论

相关文章

来自专栏机器之心

读懂概率图模型:你需要从基本概念和参数估计开始

选自statsbot 作者:Prasoon Goyal 机器之心编译 参与:Panda 概率图模型是人工智能领域内一大主要研究方向。近日,Statsbot 团...

34111
来自专栏大数据文摘

斯坦福CS231N深度学习与计算机视觉第八弹:神经网络训练与注意点

983
来自专栏人工智能LeadAI

最终章 | TensorFlow战Kaggle“手写识别达成99%准确率

这是一个TensorFlow的系列文章,本文是第三篇,在这个系列中,你讲了解到机器学习的一些基本概念、TensorFlow的使用,并能实际完成手写数字识别、图像...

3109
来自专栏AI科技大本营的专栏

经典重读 | 深度学习方法:卷积神经网络结构变化——Spatial Transformer Networks

作者 | 大饼博士X 本文具体介绍Google DeepMind在15年提出的Spatial Transformer Networks,相当于在传统的一层Co...

34511

自然语言处理指南(第3部分)

在阅读之前,请一定要查看第 1 部分和第 2 部分!

2616
来自专栏人工智能

深入浅出了解OCR识别票据原理

光学字符识别技术(OCR)目前被广泛利用在手写识别、打印识别及文本图像识别等相关领域。小到文档识别、银行卡身份证识别,大到广告、海报。因为OCR技术的发明,极大...

2.7K3
来自专栏AI科技评论

想了解递归神经网络?这里有一份入门教程

本文来自deeplearning4j,AI科技评论编辑。 递归神经网络是一类人工神经网络,用于识别诸如文本、基因组、手写字迹、语音等序列数据的模式,或用于识别传...

2933
来自专栏AI研习社

CS231n 课后作业第二讲 : Assignment 2(含代码实现)| 分享总结

CS231n 是斯坦福大学开设的计算机视觉与深度学习的入门课程,授课内容在国内外颇受好评。其配套的课后作业质量也颇高,因此雷锋网 AI 研习社在近期的线上公开...

38210
来自专栏人工智能头条

漫谈词向量之基于Softmax与Sampling的方法

2704
来自专栏大数据挖掘DT机器学习

数据挖掘案例:基于 ReliefF和K-means算法的应用

.NET数据挖掘与机器学习 原文:http://www.cnblogs.com/asxinyu/archive/2013/08/29/3289682.html ...

2788

扫码关注云+社区