马里奥 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 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

使用LSTM预测比特币价格

本文以“时间序列预测的LSTM神经网络”这篇文章为基础。如果没有阅读,我强烈建议你读一读。 考虑到近期对比特币货币的泡沫的讨论,我写了这篇文章,主要是为了预测比...

3317
来自专栏机器学习之旅

提升有监督学习效果的实战解析

之前写过销售预估算法,但是被诸多大佬吐槽有监督学习部分毫无深度,其实我是想写给一些刚入门的朋友看的,这边我boss最近也想让我总结一些相对"上档次"的一点的东西...

893
来自专栏AI科技评论

直播 | 如何让对抗网络GAN生成更高质量的文本?LeakGAN现身说法:“对抗中,你可能需要一个间谍!”(今晚8点直播)

AI科技评论按:自生成式对抗性网络 GANs 出现以来,它和它的变体已经无数次在图像生成任务中证明了自己的有效性,也不断地吸引着越来越多的研究人员加入到提高GA...

3309
来自专栏AI研习社

通过高效信息传播来提升深度神经网络的学习效率

目前,前馈神经网络 (FFN) 已经得到了广泛的应用,尤其是在图像和语音识别上功能突出。尽管取得了这些经验上的成功,但对底层设计理论的理解仍然有限。在 FFN ...

783
来自专栏机器之心

教程 | 利用AllenNLP,百行Python代码训练情感分类器

情感分析是一种流行的文本分析技术,用来对文本中的主观信息进行自动识别和分类。它被广泛用于量化观点、情感等通常以非结构化方式记录的信息,而这些信息也因此很难用其他...

791
来自专栏机器学习算法与Python学习

干货|谷歌大规模机器学习:模型训练、特征工程和算法选择

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 谷歌机器学习:实际应用技巧 ? ? ...

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

一个强化学习 Q-learning 算法的简明教程

本文是对 http://mnemstudio.org/path-finding-q-learning-tutorial.htm 的翻译,共分两部分,第一部分为...

4658
来自专栏机器之心

16岁高中生夺冠Kaggle地标检索挑战赛!而且竟然是个Kaggle老兵

1743
来自专栏人工智能头条

cuDNN 5对RNN模型的性能优化

2625
来自专栏机器之心

深度 | 使用高斯过程的因果推理:GP CaKe 的基本思路

我们最近开发出了一种用于时间序列数据中因果推理的全新方法 [Ambrogioni et al., 2017]。我们称之为「GP CaKe」,即具有因果核的高斯过...

271

扫码关注云+社区