原来AI也会通过记小本本来玩游戏

2015年google旗下的DeepMind团队利用深度学习结合强化学习中Q-learning算法，提出了deep Q-learning算法，完成了历史性的壮举，让AI成为了雅达利一款打砖块游戏大师。在这篇文章我们会解释传说中的Q-learning是如何工作的。

假设你在玩一款迷宫游戏，你来操控红色的方块，目标是拿到黄色的原块，然而游戏中有两个黑色的陷阱，一旦碰到则会导致游戏失败而死亡。每次你只能选择移动一个格子距离，黑色方块和黄色圆块都是静止的，我们希望你以最小的移动次数来完成目标。

Q-learning作为一个value-based(基于值)算法，重心在于每次它移动红色小方块之后，它会从系统中接收到一个reward(奖励)，所以我们这样设置每次移动后的打分：

(1)每一步正常移动会得到-1分。这里你可能问，我们虽然没有达到黄色目标，但也没有因为碰到黑色方块而死亡啊，给个0分不是挺好的吗？要知道，我们有一个要求就是以最小的移动次数，所以每一次多余移动都是在浪费时间，所以我们给以-1的奖励。

(2)移动后碰到黑色方块，给予-100奖励，并结束游戏。设置-100是因为它足够小，相对于-1而言，意思就是让程序吃一堑长一智。

(3)移动后碰到黄色方块，给予100分奖励，并结束游戏。

对于AI而言，它是看不见周围的环境，不像我们可以对这十六个方块一览无余，可以轻易避免黑色方块而走到黄色圆块，甚至可以口算出最佳路径。AI所能做的就是制定一套策略(policy)来基于当前位置，选择一个最优的动作。这个就相当于一个攻略，让AI可以一步步走向目标。而这个攻略，就是AI的小本本，术语叫做Q-table。对于这个迷宫而言，这个小本本是一个16*4的表格，16对应于迷宫中的16个方块，而4对应于动作的选择：上下左右。当AI把这个表格都填上了最佳的值，它就完成了完美攻略。而这个完美攻略就是AI最后学会的游戏玩法。

Q-table示意图

由于一开始AI没有玩过这个游戏，所以它的小本本是一片空白。这时候我们让AI的小本本上的每一个值都设置成0。AI开始了它的第一次游戏，由于我们的小本本上的值都是一样的，所以AI会在上下左右动作上随机选择一个，乱走下去，直到碰到黑色方块而死亡，或者意外拿到黄色目标。在这个过程中AI要做的就是记小本本，也就是改变表格中的值。比如它碰到了黑色方块，那么它会把表格对应的值减小，以后尽量避免；相反，如果行动导致了遇到黄色的目标，那么AI会加大表格中的值经过很多次游戏之后，AI的小本本就会成为一个完美攻略：

最后我们从数学角度给出AI是如何更新它的小本本的，

上式是我们最终目标，简单而言就是最大化奖励R。其中S表示状态，也就是你处于哪一个格子；A表示动作，比如上下左右。注意到这是一个求和，把当前的奖励和以后的奖励都假上，我们设置一个衰减因子，让当前时刻后面的奖励随着时间逐步减小。如果这个衰减因子是1，表示我们很注重后面的奖励，如果是0则只关注当前利益。

小本本表格中的每一个值的函数定义如下

于是这个值对应最优的值是

最后的差分更新策略就是