机器之心编辑部发布

获顶会最佳论文,天津大学等用强化学习寻找游戏bug

软件工程领域顶级会议 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)。

论文链接: https://yanzzzzz.github.io/files/PID6139619.pdf

背景介绍

长久以来,游戏测试一直被认为是一项极具挑战性的任务。在工业界,游戏测试一般使用脚本测试以及手动测试相结合的形式。时至今日,自动化游戏测试的研究仍然处于初级阶段,一个主要原因是玩游戏本身是一个持续决策的过程,而游戏缺陷(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 个相关算法的代码覆盖率基本一致,而通过上述实验结论,我们认为使用状态空间覆盖数量作为衡量游戏软件的测试完备性指标,具有较高的有效性;且从强化学习的角度来看,该指标也具有较强的逻辑性与解释性。

本文是深度强化学习研究在游戏测试领域的初步探索,且该领域还存在诸多难题以及值得研究的方向。本课题组会沿着该方向,致力于推动深度强化学习技术在智能游戏测试产业的落地与发展。

更多内容请查看:https://sites.google.com/view/gametesting/home

理论游戏bug强化学习天津大学
1
相关数据
网易机构

网易成立于1997年6月24日,是中国领先的互联网技术公司,为用户提供免费邮箱、游戏、搜索引擎服务,开设新闻、娱乐、体育等30多个内容频道,及博客、视频、论坛等互动交流,网聚人的力量。

https://www.163.com/
排序算法技术

排序算法是将一串数据依照特定排序方式进行排列的算法,最常用到的排序方式是数值顺序以及字典顺序。基本上,排序算法的输出必须遵守下列两个原则:输出结果为递增序列(递增是针对所需的排序顺序而言);输出结果是原输入的一种排列、或是重组。

深度强化学习技术

强化学习(Reinforcement Learning)是主体(agent)通过与周围环境的交互来进行学习。强化学习主体(RL agent)每采取一次动作(action)就会得到一个相应的数值奖励(numerical reward),这个奖励表示此次动作的好坏。通过与环境的交互,综合考虑过去的经验(exploitation)和未知的探索(exploration),强化学习主体通过试错的方式(trial and error)学会如何采取下一步的动作,而无需人类显性地告诉它该采取哪个动作。强化学习主体的目标是学习通过执行一系列的动作来最大化累积的奖励(accumulated reward)。 一般来说,真实世界中的强化学习问题包括巨大的状态空间(state spaces)和动作空间(action spaces),传统的强化学习方法会受限于维数灾难(curse of dimensionality)。借助于深度学习中的神经网络,强化学习主体可以直接从原始输入数据(如游戏图像)中提取和学习特征知识,然后根据提取出的特征信息再利用传统的强化学习算法(如TD Learning,SARSA,Q-Learnin)学习控制策略(如游戏策略),而无需人工提取或启发式学习特征。这种结合了深度学习的强化学习方法称为深度强化学习。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

多目标优化技术

多目标优化是多准则决策的一个领域,它是涉及多个目标函数同时优化的数学问题。多目标优化已经应用于许多科学领域,包括工程、经济和物流,其中需要在两个或多个相互冲突的目标之间进行权衡的情况下作出最优决策。分别涉及两个和三个目标的多目标优化问题的例子有:在购买汽车时降低成本,同时使舒适性最大化;在使车辆的燃料消耗和污染物排放最小化的同时将性能最大化。

暂无评论
暂无评论~