被Flappy Bird虐过么？反击的号角吹响了
作为一个曾经风靡一时的游戏，《Flappy Bird》曾经虐过很多的人类玩家。
而过去一段时间以来，好多人类借助AI技术把这款游戏“玩坏了”。量子位粗略的数了一下，比较流行的有六大“门派”，特收录如下，供有兴趣的同学仿照操练。
姑且称之：《AI玩转Flappy Bird全书》
⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄
目录：
- DQN大法(TensorFlow)
- DQN大法(Keras)
- 强化学习
- 强化学习(改进版)
- A3C大法
- 神经进化大法
DQN大法(TensorFlow)
简介
作者：yenchenlin（http://yclin.me/）
这个项目使用了DeepMind团队在《Playing Atari with Deep Reinforcement Learning》论文中描述的Deep Q Learning算法，表明这个算法可以进一步推广应用到《Flappy Bird》。
论文地址：https://arxiv.org/abs/1312.5602#
这里所谓DQN(Deep Q-Network)，是一个卷积神经网络，用Q-Learning的变量训练，其输入是原始像素，其输出是估计未来奖励的价值函数。
安装环境
- Python 2.7或3
- TensorFlow 0.7
- pygame
- OpenCV-Python
如何运行？
git clone https://github.com/yenchenlin1994/DeepLearningFlappyBird.git
cd DeepLearningFlappyBird
python deep_q_network.pyDQN算法
下面就是Deep Q Learning的伪代码
Initialize replay memory D to size N
Initialize action-value function Q with random weights
for episode = 1, M do
Initialize state s_1
for t = 1, T do
With probability ϵ select random action a_t
otherwise select a_t=max_a Q(s_t,a; θ_i)
Execute action a_t in emulator and observe r_t and s_(t+1)
Store transition (s_t,a_t,r_t,s_(t+1)) in D
Sample a minibatch of transitions (s_j,a_j,r_j,s_(j+1)) from D
Set y_j:=
r_j for terminal s_(j+1)
r_j+γ*max_(a^' ) Q(s_(j+1),a'; θ_i) for non-terminal s_(j+1)
Perform a gradient step on (y_j-Q(s_j,a_j; θ_i))^2 with respect to θ
end for
end for实验
环境
由于DQN基于游戏屏幕上原始像素进行训练，所以移除游戏背景可以更快的收敛。
网络架构
首先对游戏画面进行如下几步的处理：
1、将图像转换为灰度
2、调整大小为80×80
3、堆叠最后4帧，可以产生80×80×4的输入阵列
下图就是网络的架构。第一层对输入的图像，用步长为4、尺寸为8×8×4×32的卷积核进行卷积。输出接着通过一个2×2的Max Pooling层……全部过程如下图所示，最后的隐藏层由256个全连接的ReLU节点构成。
最终的输出层的维度，和游戏中的有效动作相同，其中第0个索引总是代表什么也不做。输出层的数值，代表每个有效动作输入状态的Q函数。每个时间步长里，网络使用ϵ greedy策略来执行对应最高Q值的动作。
训练
最开始，我使用标准偏差为0.01的正态分布随机初始化所有权重矩阵，然后把replay memory的最大值设定为5万次。随后作者开始调整网络，最后ϵ固定在0.001。
这还有一段7分钟的视频
全部细节和代码，请访问如下网址：
https://github.com/yenchenlin/DeepLearningFlappyBird
DQN大法(Keras)
简介
作者：Ben Lau
这个项目演示了如何使用Deep-Q Learning算法与Keras，一起玩转《Flappy Bird》。总共200行Python代码就搞定了。
安装环境
- Python 2.7
- Keras 1.0
- pygame
- scikit-image
如何运行？
只用CPU/TensorFlow
git clone https://github.com/yanpanlau/Keras-FlappyBird.git
cd Keras-FlappyBird
python qlearn.py -m "Run"GPU版本(Theano)
git clone https://github.com/yanpanlau/Keras-FlappyBird.git
cd Keras-FlappyBird
THEANO_FLAGS=device=gpu,floatX=float32,lib.cnmem=0.2 python qlearn.py -m "Run"lib.cnmem=0.2意思是分配20%的GPU内存给程序
代码解读
作者对代码有非常详细的解读，包括图像输入和预处理，卷积神经网络的构建，网络权重和参数的调整，DQN算法的解读等等非常详细。
特别提示：最好有一个GPU加速计算。作者使用TITAN X，训练了100万次才有了收效。
全部细节和代码，请访问如下网址：
https://yanpanlau.github.io/2016/07/10/FlappyBird-Keras.html
强化学习
简介
作者：SarvagyaVaish
玩过几次《Flappy Bird》之后，我意识到可以用这个游戏来搞机器学习。基本的思路是强化学习+Q Learning。下图就是Q Learning的算法。
状态空间
我用如下参数来描述空间，如图所示：
- 从下方管子开始算起的垂直距离
- 从下一对管子算起的水平距离
- 鸟命：死或生
动作
每一个状态，有两个可能的动作
- 点击一下
- 啥也不干
奖励
奖励的机制完全基于鸟命这个参数
- +1，如果小鸟还活着
- -1000，如果小鸟死了
循环学习
第一步：观察Flappy Bird处于什么状态，并执行最大化预期奖励的行动。然后继续运行游戏，接着获得下一个状态s’。
第二步：观察新的状态s’和与之相关的奖励：+1或者-1000。
第三步：根据Q Learning规则更新Q阵列
Q[s,a] ← Q[s,a] + α (r + γ*V(s') - Q[s,a])
这里alpha设定为0.7，因为我们有一个确定性的状态。
第四步：设定当前状态为s’，然后重新来过。
后续
大约花了6-7个小时，《Flappy Bird》才算训练的比较好，得分能过150。如果开始的时候实例化不止一只小鸟，效率会有所提升。
全部细节和代码，请访问如下网址：
http://sarvagyavaish.github.io/FlappyBirdRL/
强化学习(改进版)
简介
作者：chncyhn
每次玩游戏的时候，Python携程的机器人会观察小鸟所处的状态，以及所采取的行动。基于行动的结果，会得到奖励或者惩罚的反馈。如是反复，终获高分。
这个项目深受上面sarvagyavaish成果的影响，但在状态空间和算法上有所改进。
状态空间
我定义了状态空间和动作集，根据小鸟在游戏中的表现，对状态-动作的对应关系进行奖励。
我定义的状态和sarvagyavaish有点不同。如上所述，他用于下一个管道的水平和垂直距离定义了状态，但我发现这样的话，收敛需要很长的时间。所以，我把距离离散成10×10的网格，这极大的减少了状态空间。此外，我还在状态空间中增加了小鸟的垂直速度。
算法也做了一点改变，不再每次观察后更新Q值，而是每次游戏结束时进行后向。所以Q值会从最后一个动作反向加到第一个。我认为这有助于更快的传播“坏状态”。另外，如果小鸟触到管道的顶部而挂掉的话，这个状态会被额外的惩罚。
可以看到，大约在1500次游戏迭代之后，机器已经玩得很好，平均大约150分，并且偶尔可以得到很高的分数。
更新
使用5×5网格取代10×10之后，收敛花费了更长的时间，但总分可以到675左右，明显比之前的150分高，而且好几次到了3000多分。
全部细节和代码，请访问如下网址：
https://github.com/chncyhn/flappybird-qlearning-bot
A3C大法
简介
作者：babaktr
这是一个尝试使用异步评价器算法(Asynchronous Advantage Actor-Critic，A3C)，来训练人工智能代理玩《Flappy Bird》的案例。
设置
作者详细介绍了部分参数的设置情况。例如：
代理设置
mode / [train, display, visualize] - 模式设定
use_gpu / [True, False] - 是否启用GPU加速训练
parallel_agent_size - 训练中并行的代理数量
训练和优化设置
max_time_step - 40 000 000 - 最大训练步长
gamma - 0.99 - 奖励的折扣系数
entropy_beta - 0.01 - 熵正则化常数
开始
以默认参数启动训练，运行：
$ python a3c.py如果想检查进度，以及实时比较不同的实验，可以进入async-deep-flappybird文件夹，并且运行tensorboard：
$ tensorboard --logdir summaries/全部细节和代码，请访问如下网址：
https://github.com/babaktr/async-deep-flappybird
神经进化大法
简介
作者：xviniette
为了理解这个方法，让我们先谈谈达尔文的进化理论。核心是三个要素：
1、变化
2、选择
3、遗传
这个方法完全基于这个理论。首先，随机生成50只小鸟，小鸟被赋予跳跃的能力，但它们不知道什么时候该跳，也不知道应该跳多高。
小鸟试图随机跳跃求生，但是很少能够做到，尤其在最初几代。每一代后，新的小鸟被创建，但这一次不是随机生成，而是通过算法“选择”那些飞的更久的小鸟作为“父母”。新的小鸟遗传了上一代的信息，然后重新生成50只小鸟。
在这个过程中，每一代小鸟都不断进化以适应生存。
Demo
干说不如直接看Demo，可以通过按钮选择模拟的速度。Demo地址：
https://xviniette.github.io/FlappyLearning/
神经进化的代码
// Initialize
var ne = new Neuroevolution({options});
//Default options valuesvar options = { network:[1, [1], 1], // Perceptron structure population:50, // Population by generation elitism:0.2, // Best networks kepts unchanged for the next generation (rate) randomBehaviour:0.2, // New random networks for the next generation (rate) mutationRate:0.1, // Mutation rate on the weights of synapses mutationRange:0.5, // Interval of the mutation changes on the synapse weight historic:0, // Latest generations saved lowHistoric:false, // Only save score (not the network) scoreSort:-1, // Sort order (-1 = desc, 1 = asc) nbChild:1 // number of child by breeding}
//Update options at any time
ne.set({options});
// Generate first or next generation
var generation = ne.nextGeneration();
//When an network is over -> save this score
ne.networkScore(generation[x], <score = 0>);
评价
这个案例在Hacker News上引发广泛的讨论。有人说这就是所谓的“用这么一点代码就搞定了?!”，并且推这个方式推崇备至。不过也有用户在复制这个方法后，没有得到稳定的结果。
全部细节和代码，请访问如下网址：
https://github.com/xviniette/FlappyLearning
另外：
同样的方法，金融领域也用，见我们此前的报道：
