使用 Q-Learning 实现 FlappyBird AI

1. Q-Learning算法

算法的详细介绍见文章：深度强化学习 ( DQN ) 初探

2. 实现FlappyBird AI 及效果

2.1 状态空间的表示(Q(s, a))

使用三维数组来表示Q(s, a), double Qmap[H_MAX][V_MAX][ACTION_MAX]

• V 离下个管道竖直方向的距离
• H 离下个管道水平方向的距离
• ACTION 可能的操作：点击屏幕或者不点击

2.2 奖励(reward)

• +1, 移动后小鸟还活着
• +2, 穿过了柱子,小鸟还活着
• -1000， 小鸟死了

2.3 学习

Q表初始化为0

步骤一：观察FlappyBird所处的状态，并执行最大化预期奖励的操作。 执行游戏帧播放循环。现在，FlappyBird处于下一个状态S’

步骤二：观察新状态S’与其相关的奖励，按照2.2中的规则来获取r值

步骤三：根据Q算法更新Q数组

Q[s,a] ← Q[s,a] + α (r + γ*V(s’) - Q[s,a])

训练大约1个小时，小鸟已经足够“智能”，可以一口气穿过1000个管道了。

3. Q-Learning 算法的局限性

对于FlappyBird，Q-Learning算法通过训练可以实现一个效果还不错的AI。主要是因为FlappyBird中的状态表比较小， 决定小鸟”跳”或者“不跳”，仅仅取决于与下一个管道之间的相对距离。在本例代码中，状态表(double QMap[QMAP_D_0][QMAP_D_1][QMAP_D_2])的大小为： 60 30 2 = 3600。 所以训练一个小时，就可以收到不错的效果了。 对于稍微复杂些的游戏， Q-Learning算法就显得力不从心了，如下面的游戏：

我们看看状态来如何表示：决定我方飞机飞行轨迹的因素有：屏幕中全部子弹的相对位置、全部道具的相对位置、以及之前几幅画面中的子弹和道具。 状态表的大小可用如下公式估算：

其中X表示屏幕像素宽度，Y表示屏幕像素高度， n表示决定飞机动作的物品个数，channel表示决定飞机动作的最近几幅画面。 可以看到，此例中，Q状态表太大，并且维度很难降低。

如何用有限的内存空间来表示近乎无穷的Q状态呢？答案是： 用函数拟合。 没错， 这就是 深度神经网络+ Q-Learning. 最有名的实现之一要属DQN了，参见: 深度强化学习 ( DQN ) 初探