(图片来自百度百科)

作者|叶卡捷琳娜·尼科诺娃，雅各布·吉罗特，

译者|天宇

出品| AI技术大本营(ID:rgznai100)

现在说到《愤怒的小鸟》，我们不得不把人们的记忆拉回到差不多十年前。

这是当时流行的游戏。玩家可以用弹弓弹射出几只鸟。目标是摧毁所有的绿色猪，并获得尽可能高的分数。许多猪经常藏在复杂的结构中。因为顺序决策，不确定的游戏环境，复杂的状态和动作，不同功能特征的小鸟，最佳弹射时间，愤怒的小鸟很难有一个好的AI智能体。

最近，来自捷克查尔斯大学的研究人员发表了一篇论文“愤怒的小鸟的深度Q-网络”，称他们使用DDDQN(双决斗深度Q-网络)算法实现了一个深度强化学习应用，可以用来玩愤怒的小鸟。他们的目的之一是创造一个游戏代理，它可以根据玩家在前21关的以往游戏记录来突破游戏。

为了实现这一目标，他们收集了游戏记录的数据集，并为DQN游戏代理商提供了各种方案。游戏中需要做出很多关于顺序的决定，两次弹射会相互影响，每次弹射的准确性也很重要。例如，一个糟糕的决定可能会导致一头猪被几个物体卡住。因此，为了更好地完成游戏中的任务，游戏代理应该具备基于决策预测和模拟结果的能力。

以下是论文《愤怒的小鸟深度Q-网络》的概述:

相关著作

2012年，愤怒的小鸟AI大赛首次举办，众多游戏代理亮相。这里有两个优秀的代理。第一个是Datalab Birds 2014，由捷克技术大学的一个团队开发。游戏代理至今保持第三名。正如他们在论文中描述的那样，他们的主要想法是根据当前的环境、可能的弹射轨迹和鸟的类型来制定最佳策略。第二个是Eagles Wings，这是滑铁卢大学和Zazzle在2017年愤怒的小鸟AI比赛中联合开发的智能播放器。他们的经纪人目前排名第16。据说游戏代理在人工调试的结构分析基础上开发了简单的多策略能力，即在多种策略中做出选择。他们使用机器学习算法xgboost来学习决策能力。

背景介绍

为了解决《愤怒的小鸟》中的顺序决策问题，我们考虑了基于每个时间步的游戏环境ε。在每个时间步T，代理将获得观察值St，然后从可能的动作集中选择一个动作。

然后你会得到奖励。

。接下来，代理的目标是根据以下公式最大化奖励:

上式中，s是当前状态，a是选择的动作，是奖励项。

决定奖励项目对未来结果重要性的是权重系数。现在，我们将最佳q值定义如下:

通过选择每个状态下最大值对应的动作，可以得到最佳策略。

DQN算法的理论基础

为了模拟最佳动作值函数，我们使用深度神经网络作为非线性函数逼近器，并且我们定义了逼近函数:

其中，

Q-网络第I次迭代的权重。

如文中所述，强化学习算法与非线性函数逼近器如神经网络的结合，会出现不稳定甚至偏移，原因如下:a)序列中观测值之间的相关性；B) Q值和目标值

它们之间的相关性；c)这种方法对q值的变化极其敏感。

深度Q-learning试图用技术解决第一个问题，即体验回放。通过随机化收集的数据，这种技术消除了序列中观察值之间的相关性。我们对体验的定义如下:

其中，

是t时刻的状态，

对时间t采取的动作，

为了t+1时刻的奖励，

是执行后的状态。我们将我们的经验保存在经验集中:

接下来，我们从经验集M中采样一些经验，并更新Q网络中的Q值。

为了解决第二个问题，我们需要使用下面的损失函数:

其中I是迭代次数，

是权重系数，

是实时网络的权重，

是目标网络的权重。

接下来，我们的DQN目标如下:

A.双深Q-网络

原DQN算法在动作选择和动作表现评估中都使用最大值，容易导致高估。基于这一缺陷，双Q学习算法应运而生。与传统的DQN算法只使用一个神经网络不同，现在我们使用一个网络来选择行动，然后使用另一个网络来评估所做的决定。因此，我们可以将原来的Q-learning目标改写为:

其中，

对于实时重量，

就是第二个权重集，也就是实时权重用来选择动作，第二个权重用来评价动作。幸运的是，同样的方法也可以应用于DQN算法，我们可以替换更新函数如下:

哪里是DQN的实时重量，

是目标DQN的重量。

B.决斗深度Q-网络

在某些场景下，不同动作得到的数值非常接近，没必要对每个动作进行评价。在《愤怒的小鸟》中，有时候玩家会陷入无解的境地，比如小猪被一些物体卡住。在这种情况下，无论采取什么行动，结果都是一样的，所以任何行动的得分都差不多，我们只关心状态本身的得分。考虑到这些场景的优化，决斗结构应运而生。为了实现决斗Q学习结构，我们需要使用两个完全连接的层。在将卷积层的输出分成两部分后，我们需要将它们合并以获得Q函数。首先，定义价值函数:

优势函数是:

换句话说，价值函数可以告诉我们特定状态的质量，而优势函数则告诉我们每个动作的重要性。这样我们就可以构建我们的第一个全连接层，并获得输出。

和第二完全连接层，可以获得输出。

这里α和β是全连接层的权重，θ是卷积层的权重。为了组合这两个值并得到Q值，我们将网络的最后一个模块定义如下:

这样就得到价值估计函数和优势估计函数，结合之前定义的深度Q-网络和双Q-学习，就可以用在游戏《愤怒的小鸟》中。

将DQN应用于鸟类

为了将DQN应用于愤怒的小鸟，我们首先需要定义:a)状态，b)动作，c)Q-网络结构，d)奖励函数。AIBirds大赛主办方提供了可以截图比赛的软件，可以得到840x480像素的图片。图1显示了逐步处理图片的过程。

图1:游戏截图的处理流程，从左至右:原始截图、裁剪、调整大小、标准化。

我们规定该行动是

，其中每个数字代表喷射角度。接下来，我们根据软件找到每个给定角度的最终发布点。为了计算投放点，弹道模块首先寻找弹弓的参考点，然后计算投放点。

我们的DQN结构基于Google DeepMind DQN，图2显示了我们的DQN结构。该模型包括四个卷积层，核分别为8×8、4×4、3×3和7×7，步距分别为4×4、2×2、2×2和1×1。在最后一个卷积层后面连接两个展平层，最后将它们组合生成q值。

图2:

双决斗DQN结构

奖励函数使用的技术通常称为奖励削波。该方法将大的或小的分数修剪为1或-1的分数，以表示好的动作或坏的动作。《愤怒的小鸟》的主要目标不仅仅是过关，更是活出尽可能高的分数。考虑到这一点，我们需要如下改变奖励函数:

上式中，score是在S状态下采用动作A后的分数，当前级别的最高分是当前级别的历史最高分。基于这个公式，我们期望游戏代理通过学习动作的奖励机制来学习分数的重要性并刷新当前级别的分数。

A.训练集

我们的训练集包括经典系列《愤怒的小鸟》中的21个关卡。在训练阶段，游戏代理基于11.5万张图片进行网络训练。代理需要等待5秒后才能进行游戏的截屏。这种小的调整是必要的，以便平息由发射的鸟引起的振动。

B.验证集

我们的验证集包括经典的愤怒的小鸟系列的10个级别。由于代理人的训练重点只有红鸟、蓝鸟、黄鸟，我们只好选择没有新鸟的等级作为验证集。从第二页和第三页选择的水平比第一页更难。玩家在玩这些关卡的时候，一定要找到一些不太明显的结构弱点，提前仔细规划好策略。

结果

我们比较了几个比赛的结果，如图3所示。对比不同的代理结果，可以帮助我们了解哪种AI技术更适合《愤怒的小鸟》。然而，我们仍然想不通的是，与人类相比，这些游戏代理的表现如何。

图3:几种不同DKN试剂的比较

在本文中，我们还将AI与人类进行了对比。人类参赛者可以尝试无数次，直到他们觉得自己得到了最好的成绩。我们从不同层次的人中挑选参与者。玩家1和玩家3有4年玩愤怒的小鸟的经验。玩家2很久以前玩过几次这个游戏，没有太多经验。4号玩家以前玩这个游戏，最近不怎么玩了。

如图4所示，我们的游戏代理在总分上超过了一个人类玩家，输给了其他玩家。造成这个结果的主要原因是代理过不了18级。在其他关卡中，代理可以在某些关卡超越某些玩家。总的来说，我们的DQN代理在前21关得了1007189分，它输给了四个人类玩家中的三个。所以我们机构空还是有很大提升的。

图4:4:DQN特工和人类玩家的游戏分数对比。

图5验证集上5位代理的性能。不出我们所料，代理商之前没见过的关卡，大部分都过不了。

图5:验证集上DQN代理的结果

愤怒的小鸟人工智能大赛结果

除了将我们的代理人与人类玩家进行对比，我们还在IJCAI-2018大会上展示了他们，并参加了愤怒的小鸟AI大赛。比赛本身由三轮组成:四分之一决赛、半决赛和决赛。每一轮，参赛的游戏代理都要面对8个从未见过的关卡。

表1显示了四分之一决赛中所有游戏代理的总得分。在所有基于神经网络的代理中，我们的DQ鸟表现最好，通过了八个级别中的三个。MYTBirds也用了神经网络，但是只过了一关。其他代理使用除神经网络之外的方法。

表1

结论

对于AI特工来说，愤怒的小鸟永远是一项艰巨的任务。我们提出了一个基于双决斗DQN的博弈主体来解决博弈中的顺序决策问题。在目前的研究工作中，我们还没有实现的是在这个游戏中超越人类玩家。但好处是我们的代理只需要一次通关机会。有意思的是，大多数情况下，只需要一次精准的弹射就能击中要害，过关。

总之，虽然我们的代理商已经超越了之前的一些选手和AIBirds比赛的一些选手，但是还是有很大的进步空。比如我们可以尝试在奖励函数中加入超级参数。我们也可以尝试今天已经公开的所有深度强化学习优化技术。接下来，我们计划根据更多的游戏关卡来培养游戏代理。

(*本文为AI技术大本营整理文章，转载请联系微信1092722531)

◆

◆