软件工程领域顶级会议 34th IEEE/ACM International Conference on Automated Software Engineering (ASE 2019) 将于 2019 年 11 月 10 日至 15 日在美国圣地亚哥举办，本次会议共收到 445 篇提交论文，最终接收 86 篇，接收率为 19.3%。本文介绍天津大学强化学习实验室同网易伏羲人工智能实验室、NTU 合作的 ASE 2019 论文《Wuji: Automatic Online Combat Game Testing Using Evolutionary Deep Reinforcement Learning》。
该论文主要融合了进化算法与深度强化学习算法，从多目标优化的角度，旨在解决大规模商业游戏的自动化智能测试问题，并荣获 ASE 2019 的最佳论文奖 (Distinguished Paper Award)。
背景介绍
长久以来，游戏测试一直被认为是一项极具挑战性的任务。在工业界，游戏测试一般使用脚本测试以及手动测试相结合的形式。时至今日，自动化游戏测试的研究仍然处于初级阶段，一个主要原因是玩游戏本身是一个持续决策的过程，而游戏缺陷（bug）往往隐藏的较深，只有当某些困难的中间任务完成后，才有可能被触发，这就要求游戏测试算法拥有类人的智能。近年来，深度强化学习算法（DRL）取得的非凡的成功，特别在游戏控制领域，甚至表现出了超越人类的智能，这为推进自动化游戏测试提供了启示。然而，既有的 DRL 算法主要关注如何赢得游戏，而不是游戏测试，导致其可能无法广泛地覆盖需要测试的分支场景。
为此，首选我们针对四款网易游戏产品中的 1349 个真实 bug 进行深入分析，并针对性的提出了四个用于 bug 检测的 oracle。其次，我们提出了实时游戏测试框架 Wuji，通过融合了进化算法，DRL 算法和多目标优化机制，实现了智能的自动化游戏测试。Wuji 在赢得游戏和探索游戏空间之间取得了较好的平衡。其中，赢得游戏可以使得智能体在游戏中取得进展；而空间探索则可以增加发现错误的可能性。
最后，我们使用一个仿真游戏和两个大型商业游戏对 Wuji 算法的效果进行了大规模评估，结果证明了 Wuji 在探索游戏状态空间方面以及检测 bug 方面的有效性。此外，Wuji 算法还检测到了游戏中先前从未被发现过的漏洞，进一步论证了算法的有效性。
Wuji - 基于多目标优化的进化强化学习框架
从强化学习算法的角度看，不同的策略π都能够探测到游戏中不同的状态空间。从进化算法的角度看，通过维护一个策略种群，可以实现游戏空间的高效探索。直观上，可以将二者结合，实现有效的游戏测试。Wuji 正是构建在这样的进化强化学习架构之上（上图）。
然而，进化算法需要选择优质的后代，而如前文所述，使用胜率作为策略的单一衡量指标，会使得种群内的策略都趋同于取胜，无法探测到更广泛的游戏空间，降低游戏测试效果。为此，Wuji 使用多目标优化机制，对每个策略分别从胜率以及空间探索能力两个维度衡量策略性能，并以此进行优质后代的选择。
具体来说，每个策略用于后代选择的 Fitness-Value (FV) 计算方式如下：
比如，给定游戏G，使用策略π执行一个回合后，〖RS〗_G^π表示策略在当前回合的胜率，而〖ES〗_G^π表示策略π在当前回合中探索的状态空间的数量。至此，策略的 FV 从标量拓展到了向量。因此，后代选择的方式也从选择较大的标量，转变成了向量之间的比较。因此，本文提出使用非支配排序（non-dominate sorting, NDS）来选择非支配集（non- dominate set），进而选择更优质的后代。具体过程如上图（右）所示，图中每一个点代表一个策略，两个维度衡量了策略在获胜能力与探索能力两个维度的表现。其中，整个种群中存在一个集合 F_1，该集合中的策略相互不支配 (例如π_1 的胜利比π_2 高，但是探索能力却比较低；因此无法说明两个策略谁更优秀)，该策略集又被称为帕累托前沿 (Pareto Frontier)。
基于此，进行后代选择的时候，优先选择集合中的帕累托前沿（如 F_1）；接着从种群中剔除 F_1 后再进行非支配集的筛选，找到 F_2 在加入到后代中，循环往复直至种群数量达到上限。值得注意的是，当将 F_3 加入到后代种群时，如果遇到种群规模超出上限阈值的情况，需要针对 F_3 内的策略进行筛选。
为此，本项目提出使用聚集距离（crowding distance）对策略的密集程度进行度量，并基于聚集距离实现策略的聚集距离排序算法（crowding distance sorting, CDS）实现策略的末位淘汰。如上图右所示，针对策略π_1，其聚集距离定义如下公式：
其中 d_1 与 d_4 衡量了在探索能力的维度，距离π_1 最近的邻居策略的距离。同理，d_2 与 d_3 衡量了胜率维度的距离。根据聚集距离对策略进行CDS，保留聚集距离较大的策略，淘汰聚集距离较小的策略，以此实现策略的多样性。CDS 尽可能选择两端的策略，以及均匀分布在两个极端之间的策略，以实现后代策略的多样性。
综上所述，Wuji 借助进化强化学习算法框架，结合多目标优化机制，使得种群内的策略朝着胜率以及探索能力两个方向不断优化，同时还保证部分策略均匀的分布在两个优化目标之间。二者的融合使 Wuji 能够完成更多任务并探索游戏的更多状态，提升发现 bug 的几率。
实验结果
我们在仿真迷宫环境 (Block Maze) 和网易游戏《倩女幽魂》（L10）与《逆水寒》(NSH) 上分别进行了实验，实验结果证明了Wuji在探索游戏状态空间方面以及检测 bug 方面的有效性，还发现了先未知的漏洞。
在仿真迷宫环境中，我们注入了随机分布的 bugL10 以及 NSH 分别注入了游戏开发过程中真实发现的 bug。在此基础上，我们分别使用了猴子测试算法（Random）、基于单目标优化的进化算法（EA_S）、基于多目标优化的进化算法（EA_M）、深度强化学习算法（DRL, aka. A3C）、进化强化学习算法（EA_S+DRL）以及 Wuji 算法对三个游戏环境进行了测试，并记录下测试过程发现的 bug，结果如上图 5 所示（平均发现的 bug 数量）。
总体来说，Wuji 相比其他算法发现了更多的漏洞；同时，上图6展示了不同算法最终发现 bug 的数量的箱形统计图，进一步论证了 Wuji 算法发现更多 bug 这一结论的统计意义。
另一方面，上表统计了不同算法在游戏测试过程中的状态空间的覆盖情况（去重后的状态数量）。可以发现，Wuji 相比其他算法在同样的设备与测试时间下，探索到了更多的状态空间，这也进一步解释了Wuji能够发现更多bug的原因。
最后值得一提的发现是，在传统系统测试中，代码覆盖率是衡量系统测试完备性的一个重要指标；但在整个测试过程中，6 个相关算法的代码覆盖率基本一致，而通过上述实验结论，我们认为使用状态空间覆盖数量作为衡量游戏软件的测试完备性指标，具有较高的有效性；且从强化学习的角度来看，该指标也具有较强的逻辑性与解释性。
本文是深度强化学习研究在游戏测试领域的初步探索，且该领域还存在诸多难题以及值得研究的方向。本课题组会沿着该方向，致力于推动深度强化学习技术在智能游戏测试产业的落地与发展。
