接《马里奥 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.