Beat flappy 2048 with Q Learning

介绍

2048这游戏已经被玩坏了，有人把它和Flappy Bird杂交，玩不过不能忍，于是写了个AI玩之。

游戏源码修改

首先需要对游戏进行适当的修改，便于AI获取游戏状态，并输出控制量。

修改application.js，将几个关键的对象放到windows命名空间中便于访问：

window.requestAnimationFrame(function () {
	window.input = KeyboardInputManager;
	window.actuator = HTMLActuator;
  window.score = LocalScoreManager;
  window.game = new GameManager(4, KeyboardInputManager, HTMLActuator, LocalScoreManager);
});

游戏的逻辑主要在game_manager.js中实现：

游戏中的“鸟”的css class是tile-bird，障碍物的css class是tile-block，在本文中分别简称为bird和block。

使用game.jump()跳跃
bird的状态：

变量名	说明
`game.birdpos`	顶端的y坐标，$[0, 1]$之间，0为顶端
`game.birdspd`	y方向速度，向下为正

在任意时刻，只有4个block分别称为a, b, c和d，a与b,c与d成组，有相同的水平坐标，两组block之间一直保持2个tile的距离。每组block只有3种可能状态：全在上、全在下以及一上一下，因此block的状态由两个0~2之间的数字game.ab, game.cd确定。

游戏由一个timer驱动，每一帧计算游戏状态的变化，最后调用window.actuator.actuate()方法计算元素位置，重绘游戏。

在游戏计算出元素位置并重绘后获取状态，并由AI注入控制量是最为便捷的方式。

修改html_actuator.js:

HTMLActuator.prototype.actuate = function (grid, metadata) {
  //.. Other stuff

  // Call AI
  window.AI.play(this);
}

这样对原游戏的改动就完成了，接下来只需要实现AI类，并把类对象赋值到window.AI即可。

Q-Learning

Q-Learning是一种强化学习算法，能用于寻找Markov决策过程(MDP, Markov decision process)的最优解。
MDP问题模型由一个agent，状态$S$以及每个状态对应动作(action)集合$A$构成。Agent通过完成一个动作，从一个状态$S$跳转到另一个状态$S’$，获得一定的奖励。Agent的目标就是使奖励最大化，通过学习在每个状态下最优的动作，达到这个目的。

算法的核心是矩阵$Q$，记录状态-动作对的奖励：

$$Q: S \times A \rightarrow \mathbb{R}$$

算法初始时，$Q$取设计好的值，随后agent每执行一次动作，观察新状态以及获得的奖励，通过如下公式迭代更新：

$$Q_{t+1}(s_t, a_t) = Q_{t}(s_t, a_t) + \alpha_{t}(s_t, a_t) \times [ R_{t+1} + \gamma \max Q_{t}(s_{t+1}, a) - Q_{t}(s_t, a_t) ]$$

其中：

$Q_{t+1}(s_t, a_t)$: 新的$Q$值
$Q_{t}(s_t, a_t)$: 上一时刻$Q$值
$R_{t+1}$: 在$s_t$时执行$a_t$后获得的奖励
$\alpha \in [0, 1]$: learning rate
$\gamma$: 折扣率

算法设计

状态：
- $\Delta y$: bird到能安全通过当前block最高点的垂直距离
- $\Delta x$: bird到下一个block的水平方向距离
动作：
- jump: 跳跃
- idle: 不动作
奖励：
- 死亡：-100
- 存活：1
$Q$的初始化

虽然可以简单的把$Q$全初始化为0，但这样会延长学习时间。并且在很多情况下，会导致bird一直跳跃直到跳出顶端掉不下来，这样不管是jump还是idle都会被惩罚，这样永远无法学习到正确行为。另外在底部也会有同样的问题。

实际实现时，加入了先验知识：

对所有$\Delta y < y_{min}$的$s$，初始化jump的reward为-100。即在上端时禁止跳跃
对所有$\Delta y > n * BirdHeight$的$s$，初始化idle的reward为-5，n接近1。即离最高点的距离小于bird自己高度的时候，倾向于跳跃。注意这里的reward值较小，是因为在某些组合下（如当前block在下，下一个block在上），跳跃会挂掉，值如果过大，$Q$值无法及时对惩罚做出反馈。
不定状态时的随机参数

在jump和action的reward相等时，无法通过$Q$做出决策，这个时候需要随机决定采取何种行为。

实际实现时，同样没有简单的将这个概率设为0.5，而是让不跳跃的概率远大于跳跃。道理很简单，游戏的操作方式是不平衡的，玩家只能干预下落，而不能干预上升，掉得太低跳一下就行了，跳得太高就只有等死。

效果

目前实现的版本在未学习的情况下，可以一次跳跃到700+分，学习一小时后可以到1000分，到后面出错都是遇到比较极端的组合差之毫厘，重现概率不高，所以学习速度会变慢。

玩：Q Learning Flappy 2048

代码：GitHub