跳一跳还是退步了，看当年FLAPPY BIRD搞出多少算法

这篇文章的起因是看到了这样一条朋友圈，一个朋友说根本不用什么18岁的照片，文工团的电影，只要看了一些破解“跳一跳”的视频，就能感慨年华易逝，5年前Flappy bird也是一夜爆火，我们为了让鸟活更长，研究了多少算法。

其实跳一跳和Flappy Bird相比，原理要简单很多，虽然同样是解决触发时间和距离的问题，但不像5年前那只小鸟一样需要一直调整逐渐下落的位置，如今的小人只需要解答一个摁压时间和距离的关系即可，甚至只一个y=ax²+bx+c的抛物线方程。

而想想当初为了教会Flappy Bird中的小鸟飞行，我们搞出了多少算法。

先看一段简单的视频

这个视频简单形象的给大家演示了运用神经网络和遗传算法，小鸟从菜瓜到无敌的过程。总得来说呢就是，玩家开始先随机创建了鸟小白，上来就是瞎飞能飞到哪是哪，死了就死了，留下来的继续飞，直到都死掉，但不管结局怎样，每只鸟在飞行的时候都有自己最棒的运动轨迹，都有一个自己学习的经验，当游戏再开始的时候，新一代的鸟就继承了上一代死去的鸟的优质经验，在此经验上再做学习、淘汰和继承，最终就产生了一只无敌小鸟，不管游戏速度加到多少倍，只要计算反应的过来，它就能一直找到最优解一直飞。

那什么是神经网络搭建，又怎么运用在小鸟的学习中呢？视频中也有解释：

鸟小白从刚开始的瞎飞上来就死，到慢慢积累学习的经验，走过一个、两个甚至更多的障碍物，其实就是在用机器为它搭建的神经网络去决定每一刻飞还是不飞。

每一只小鸟的神经网络都有3个神经层：

第1层，有2个神经元，就是小鸟所在x、y的坐标位置。

第2层，有6个神经元，是1个黑匣子的决策层，也就是6种决策方式，这6种方式也是在不断调试的，比如说此时输入了一个x、y值，有1个决策说等1秒飞，结果撞到障碍物死了，那这个决策就要被反过来被修正了，经过了上万次上百万次实验得知，哦，1.362秒时飞正好，那这个决策的神经元就被从1被修正测会给你1.362了。

第3层，有1个神经元，就是最终决定飞还是不飞。

上图中只单独拿出一只随机生成的小鸟神经网络建设的过程进行分析，但视频中是随机生成了10种小鸟，他们都在经历从小白到大师过程，他们的经验是交叉验证和激励成长的。最终所有好的经验都继承在了一只鸟上，于是它就可以刷着各种你想要的分。

如果这样的叙述不难理解，也让你觉得很有意思，那我们就可以进阶的了解通过“强化学习（reinforcement learning）”让小鸟从小白到无敌的学习过程了

问题分析

让小鸟学习怎么飞是一个强化学习（reinforcement learning）的过程，强化学习中有状态(state)、动作(action)、奖赏(reward)这三个要素。智能体（Agent，在这里就是指我们聪明的小鸟）需要根据当前状态来采取动作，获得相应的奖赏之后，再去改进这些动作，使得下次再到相同状态时，小鸟就能做出更优的动作了。

状态(state)：这里选用的是小鸟到下一根下侧管子的水平距离和垂直距离差。

小鸟当前状态状态为（dx，dy），dx为水平距离，dy为垂直距离。

小鸟动作的选择有两种：一是向上飞一下，二是什么都不做。

奖赏：小鸟活着时，每一帧给予1的奖赏；若死亡，则给予-1000的奖赏；若成功经过一个水管，则给予50的奖赏。

关于Q

提到Q-learning，我们需要先了解Q的含义。Q为动作效用函数（action-utility function），用于评价在特定状态下采取某个动作的优劣，我们可以理解为智能体小鸟的大脑。我们可以把Q当做是一张表。表中的每一行是一个状态（dx，dy），都有两种选择——是飞还是不飞。

这张表一共有 m*n行，表示m*n个状态，每个状态所对应的动作都有一个效用值。训练之后的小鸟在某个位置处飞与不飞的决策就是通过这张表确定的。小鸟会先去根据当前所在位置查找到对应的行，然后再比较两列的值——飞与不飞的大小，选择值较大的动作作为当前帧的动作。

训练：小鸟的大脑，也就是这个Q是怎么训练得来的呢，贴一段伪代码。

Initialize Q arbitrarily //随机初始化Q值Repeat (for each episode): //每一次游戏，从小鸟出生到死亡是一个episode Initialize S //小鸟刚开始飞，S为初始位置的状态 Repeat (for each step of episode): 根据当前Q和位置S，使用一种策略，得到动作A //这个策略可以是ε-greedy等 做了动作A，小鸟到达新的位置S'，并获得奖励R //奖励可以是1，50或者-1000 Q(S,A) (1-α)*Q(S,A) + α*[R + γ*maxQ(S',a)] //在Q中更新S S S' until S is terminal //即到小鸟死亡为止

其中有两个值得注意的地方：

1.“根据当前Q和位置S，使用一种策略，得到动作A，这个策略可以是ε-greedy等。”

如何在探索与经验之间平衡？假如我们的小鸟在训练过程中，每次都采取当前状态效用值最大的动作，那会不会有更好的选择一直没有被探索到？小鸟一直会被桎梏在以往的经验之中。而假若小鸟在这里每次随机选取一个动作，会不会因为探索了太多无用的状态而导致收敛缓慢？

于是就有人提出了ε-greedy方法，即每个状态有ε的概率进行探索（即随机选取飞或不飞），而剩下的1-ε的概率则进行开发，也就是选取当前状态下效用值较大的那个动作。ε一般取值较小，0.01即可。当然除了ε-greedy方法还有一些效果更好的方法，不过可能复杂很多。以此也可以看出，Q-learning并非每次迭代都沿当前Q值最高的路径前进。

2.Q（S,A）（1-α）*Q（S,A）+α*[R+γ*MAXaQ（S',a）]这个Q-learning的训练公式。

其中α为学习速率（learning rate），γ为折扣因子（discount factor）。根据公式可以看出，学习速率α越大，保留之前训练的效果就越少。折扣因子γ越大，MAXaQ（S',a）所起到的作用就越大。

MAXaQ（S',a）指的是：小鸟在对状态进行更新时，会考虑到眼前利益（R），和记忆中的利益MAXaQ（S',a）。

MAXaQ（S',a）指的便是记忆中的利益。它是指小鸟记忆里下一个状态S'的动作中效用值的最大值。如果小鸟之前在下一个状态S'的某个动作上吃过甜头（选择了某个动作之后获得了50的奖赏），那么它就更希望提早地得知这个消息，以便下回在状态S可以通过选择正确的动作继续进入这个吃甜头的状态S'。

可以看出，γ越大，小鸟就会越重视以往经验，越小，小鸟只重视眼前利益（R）。

根据上面的伪代码，就可以写出Q-learning的代码了。

成果：训练后的小鸟一直挂在那里可以飞到几千分~

说了这么多学习、决策、算法，我不禁好奇我们的科学决策工程师因为知道了这些原理，会不会在玩“跳一跳”这种游戏时会觉得没意思，他们的回答是：他们都把分遮住玩，会比较有意思

参考资料：

1、YouTube：https://www.youtube.com/watch?v=aeWmdojEf0

2、知乎作者牛阿关于“如何用简单例子讲解Q-learning的具体问题”的回答。

链接：https://www.zhihu.com/question/26408259/answer/123230350