Q-learning

用Q-learning算法做一个Flappy Bird的AI这个想法是来自zhihu的一个回答，觉得很有趣，就自己尝试着实现了。

Q-learning是强化学习的一种算法，他将我们需要强化的对象抽象成State和Action，我们的智能体Agent，将根据State，决定所采取的Action，从而得到新的State’，根据新的State’，我们将更新旧的State的策略，我们称之为Reward。

举Flappy Bird的例子来说，我们可以定义State为小鸟和下一个管道的坐标之差(dx, dy)

当然，也可以将垂直速度也加入进来(dx, dy, speed)一起构成State

而对于每个状态，小鸟能采取的Action都只有两个，跳or不跳。

而我们用一张表来记录我们采取的策略，这张表其实就是我们Agent的大脑，记为Q（实际上在术语里被称为动作效应函数）:

对于特定的State，我们可以选择表中值较大的那栏作为Action（当然还有不同的选择方法，比如为了充分探索的$𝜖-𝑔𝑟𝑒𝑒𝑑𝑦$策略）

根据Action之后状态的不同，我们将给予Agent不同的Reward，即根据State’来更新表中对应State和Action的值。

具体公式如下:

这里的s代表State,a代表Action，Q(s,a)即State下选择的Action对应的Q表里的值，$𝛼$是学习速率，取(0,1)之间，越大则学习的越快，也越容易丢失之前学习的效果。r是我们选择给予的Reward，以我自己的例子来说，是死亡的时候给予-1000，活着给1，得分给42.75，${max}_{{𝑎}^{\prime }}𝑄\left({𝑠}^{\prime },{𝑎}^{\prime }\right)$则是我们在新的State’下能够得到的最大的利益（准确的说是我们记忆中能得到的最大利益），$𝛾$是一个常数，越大则代表我们越重视潜在利益或者说以往的经验。

游戏里的每一帧，我们都重复迭代进行这个过程，直到我们得到一个满意的模型。

可以用以下伪代码来表示:

initialize Q
repeat
    initialize S
    repeat until dead
        choose Action A depend on S and Q
        Get S' depend on S and A
        Get r depend on S'
        Q(S,A) <- Q(S,A)+α(r+γmaxQ(S',A')-Q(S,A))
        S <- S'

由于中了OOP的毒，我已经没办法驾驭自己写的代码了，所以这个项目就暂时到此为止吧，至少自己的主要目的还是达到了。（逃