游戏人工智能 读书笔记（八）游戏与强化学习

作者：杨敬文 腾讯IEG研究员

本文内容包含（但不限于）以下章节： Chapter 2 AI Methods Chapter 2.6 Reinforcement Learning 本书英文版： Artificial Intelligence and Games - A Springer Textbook4

强化学习这个名词说起来大家可能不是很熟悉（也有很多地方翻译为增强学习）。但是说起AlphaGo，大家就很熟悉了，其实AlphaGo就是强化学习应用极其成功的一个例子（当然它的成功还得益于蒙特卡洛树搜索和深度神经网络的技术）。实际上，相比传统的监督学习，强化学习与游戏有着更深的渊源。这篇文章我们就简单介绍一下强化学习与游戏的前世今生。

什么是强化学习？

强化学习讲究在一系列的情景之下，通过多步的决策来达到一个目标，是一种序列多步决策的问题。我们拿大家熟悉的植物大战僵尸这个游戏来举例子。

在与僵尸对抗的过程中，需要选择播种的植物，选择播种的位置，收集阳光，选择植物成长......等等这么多操作之后才能击败僵尸。但是往往要到最后所有僵尸过来了，我们才知道我们播种的植物品种好不好，位置好不好。也就是说，我们在播种植物的过程中，仅能得到一个当前的反馈，比如收集的阳光多了，可以播种的植物更多了，每一条路径上都有植物守护了这些与胜负有关，但又不决定最后胜负的一些信息（我们通常它们称为即时奖赏）。如何才能玩好这个游戏呢？如果没人教的话，我们就需要不断的去玩，通过不断的尝试播种策略才能总结出一个好的玩游戏的策略。

通过这个过程我们可以看到强化学习有别于监督学习，它不能实时获得最终胜负的标记，但是能够得到与之相关的奖赏，因此可以说强化学习是一种标记延迟的监督学习，是监督学习的一种特例。另外一方面，强化学习实际上和我们人类与环境的交互方式类似。是一套非常通用的框架，可以用来解决各种各样的人工智能的问题。

总结来说，强化学习的目标就是要寻找一个能使得我们获得最大累积奖赏的策略。为啥是累积奖赏？因为我们往往不是说打败僵尸就可以，还需要评分高，比如收集到很多的阳光之类的

数学上，累积奖赏表示为J_t=r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+...其中 \gamma(0\leqslant\gamma\leqslant1) 为折扣系数， t 表示第几步。引入折扣系数这个东西，主要是出于奖赏对于不同的阶段带来的收益应当是有差别的。比如大家做买卖都喜欢现钱，因为如果通货膨胀钱贬值了，那就相当于少赚了。策略一般是用 \pi(s)=a 来表示，也就是在状态 s 下，根据 \pi 策略，我们采取 a动作。有了策略的定义，我们还得知道一个策略到底好不好？最直接的就是用一个值函数来评估，值越高越好呗。比如可以定义一个值函数 Q^\pi(s,a) ，它表示在策略 \pi 下，从状态 s 出发，执行动作 a 所带来的累积奖赏。

强化学习的基本算法

这两个基本的概念实际上给我们指了两条可以求解强化学习的明路。一种就是直接去寻找一个好的策略。另外一种就是能求解一个最优的值函数，这个最优的值函数能够告诉我们在这个状态下，选取哪个动作能得到的期望值最高，不管在什么状态，我们总是能从值函数表那里查表获得应该选取哪个动作。这个表实际上也就可以作为策略了。

我们首先来看看怎么直接寻找策略。前面也提到了策略实际上就是一个从状态到动作的一个映射，那么就可以用个参数 \theta 的模型去近似它（表示为 a=\pi_{\theta}(s) ）。既然目标就是要让累积的奖赏最大，我们只要以这个目标求梯度 \nabla_{\theta}J ，按照梯度不断更新 \theta 值，就可以最终得到期望的策略。

然后再来看看基于值函数的方法。几乎所有的强化学习的模型都是定义在Markov决策过程上的。这个是什么呢？其实就是包含了上面我们说的那些状态，动作，奖赏，以及影响状态转移的概率，在这个模型下，未来的状态只与当前状态有关，与以前的没有关系（即Markov性质）。一个Markov决策过程可以表示为s_0,a_0,r_1,s_1,a_1,...

基于这个假设，很容易得到值函数是满足一个递归式子的。

最优值函数也是一样

这个式子指导我们通过不断迭代就能够得到最优的值函数。如图所示，一个实心点就是值函数Q，白圈表示状态。上述的Bellman Equation实际上可以按照Markov决策过程展开成一个树状的结构，我们不断向前看，探索后面的情况，然后将这些得到的奖赏综合起来。然后就能得到一步一步往状态动作值函数里填。

目前最常用的求解算法是Q-learning，算法流程很简单，如下图所示

其中的Q的更新方式为

这个更新策略简单来说就是用新的Q值和之前估计的状态转换得到的Q值的一个加权平均，不断迭代下去，Q值函数就能收敛。

那么上面的 \epsilon - greedy 准则又是啥呢？其实就是 \epsilon 的概率从所有动作中均匀随机选取一个，以 1-\epsilon 的概率选取当前策略给出的最优动作。这样做的目的是为了不让机器做井底之蛙，有时候如果只选当前最优的策略，可能只是在当前认知范围内最好的，这样极容易造成“自我满足”，从而停滞不前。世界太大，我们需要出去看看！当然这只是一个简单的处理方法，这里涉及到exploitation & exploration dilemma的问题，在多臂赌博机（Multi-armed Bandit Problem）中有相当多的研究。

强化学习与游戏

由于强化学习当前算法的仍有很大的局限性，对于目前市面上复杂的电子游戏而言，还难以直接处理，因此目前还没有看到在商用游戏中的广泛应用。但是相信这一天很快就到来了！因为目前在学术研究中已经有很多令人欣喜的成就！

除了AlphaGo之外，其实早在1992年，IBM就利用强化学习在一个古老的桌面游戏Backgammon上取得了巨大的成功，成为了当时这个游戏最强的玩家。

而在其他棋类游戏上，并没有取得如此巨大的成功，比如在象棋上，也有像NeuroChess这样的工作，但是并没有取得令人瞩目的成绩，大获成功的深蓝计算机也并不是因为强化学习而取胜。这一方面是由于棋盘的特征表示是比较困难的（虽然围棋的难度更大，但是棋盘和棋子相比象棋却更为简单）；另一方面也有研究表明象棋类游戏状态空间的采样有很大的难度，如果自我对弈设置不合理，就很容易陷入一个局部最优解。

除了这些棋类游戏，在视频类游戏上，DeepMind在广为人知的AlphaGo之前就已经利用强化学习来玩Atari游戏了。这也是深度学习与强化学习（所谓深度强化学习）一个非常经典的研究。

这个工作主要是利用上了当前深度学习在抽取特征上的优势，并且利用诸如Replay Memory（存储原来的样本，一同参与采样）这样的技术提高了强化学习的学习效率。以一个端到端的模型，在很多小游戏上达到甚至超过了人类的水平。

在射击游戏上也是有很多研究工作，以VizDoom为平台的比赛每年都会吸引大量顶尖团队参加。

在AlphaGo在围棋上取得巨大成功之后，更多的研究者开始把目光放到了更为复杂的即时战略游戏中，DeepMind联合暴雪公布了基于星际争霸2的开发环境sc2le

并且在最近公布了一个新的成果，能够利用逻辑推断进行关系型强化学习，在6个小任务中都取得了当前最佳的表现，并且在其中4个超过了人类高手的水平。

Facebook也在跟进这方面的研究，也开源了自己的游戏智能研究平台ELF，也偷偷参加了AIIDE（The Artificial 'Intelligence and Interactive Digital Entertainment）的星际争霸比赛，可惜名次并不佳。

星际争霸中包含了诸多的关于人工智能的重要问题，详细可以参见我之前写的文章 为什么要研究星际争霸的AI？，如果星际争霸上取得了突破性的进展，相信强化学习在游戏中的应用会变得更为广泛（当然这个技术突破的影响就不在仅仅局限于游戏范畴了）

总结

强化学习有别于传统的监督学习，它不需要大量的标记样本，就可以自动的完成复杂任务的学习。对于游戏这样，天生具有出色的模拟环境的场合，强化学习的技术可以非常容易的得到施展，帮助游戏开发者创造水平极高的游戏智能。

但是他的局限目前也很多，他需要使用者去精心设计反馈函数，因为很多复杂游戏中（比如王者荣耀，吃鸡等）很难说用一个像Atari那样简单的实时评分就可以作为反馈奖赏的，而另外一方面，复杂游戏的状态和动作空间也都往往非常大（比如王者荣耀中，每个英雄的技能都大不相同，当前携带的铭文，释放的方式，角度，时机，对位的英雄是谁都会对动作的选择有非常大的影响），这些对于强化学习的学习效率也提出了非常高的要求。如何能够在商业级游戏中应用强化学习，还需要我们应对很多挑战！

参考资料

• - 这个领域最经典的教材就是Richard Sutton教授的Reinforcement Learning: An Introduction
• - 还有他的学生David Silver（也是现在DeepMind的核心成员）在UCL 开的公开课程Reinforcement Learning，搭配食用更佳 : )