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