并行蒙卡树搜索，性能无损，线性加速，勇闯「消消乐」1000关！

作者 | 快手

责编 | 贾伟

AAAI 2020 已经于 2月 7日 - 12 日在纽约举办，对于 AI 领域的研究者来讲，接下来最近的一个盛会将是4月26日在非洲埃塞俄比亚（亚斯亚贝巴）举办的 ICLR 2020。

ICLR会议是由深度学习三巨头之二的 Yoshua Bengio 和 Yann LeCun 牵头于2013年创办，旨在关注有关深度学习各个方面的前沿研究。尽管ICLR 2020也不过是第九届会议，但这个会议却已经成为业界人士心目中的顶级会议。特别是在前段时间清华发布的新版AI顶会评级中，ICLR更是被评为A级会议。

本届ICLR 会议共有 2594篇投稿，其中 687篇论文被接收（48篇oral论文，107篇spotlight论文和531篇poster论文），接收率为26.5%。本文为 快手 实习生刘安吉完成并发表在ICLR 2020上的 Oral 论文，该论文在OpenReview网站上的评分为 8-6-8。

作者对文章的简介为：我们开发了一种有效的并行UCT算法，该算法在线性加速的同时，性能损失很小。

We developed an effective parallel UCT algorithm that achieves linear speedup and suffers negligible performance loss.

论文链接：https://openreview.net/forum?id=BJlQtJSKDB

蒙特卡洛搜索树（Monte Carlo Tree Search，MCTS）是一种基于模型的强化学习算法（model-based reinforcement learning algorithm）。利用已知或训练出来的环境模型，MCTS将最优优先搜索树和蒙特卡洛方法结合，通过大量在环境模型中进行尝试、规划（planning），找到更优的策略。MCTS在视频游戏、围棋等领域取得了惊人的突破（如大家熟知的AlphaGo）。

与其出众的表现相对应，MCTS对计算资源的需求十分巨大。这主要体现在其需要与环境进行大量的交互。AlphaGo在与人类棋手对弈时就使用了大量计算资源，否则它无法在给定的时间内完成落子。因此，并行MCTS就显得十分必要，尤其在对反馈时间要求较高的任务场景中。

然而，蒙特卡洛搜索树本身是一个串行的算法（每一步迭代需要所有当前已知信息），这导致对其并行将带来不可避免的性能损失。因此，如何最小化并行带来的性能损失就显得十分重要。

如上图(a)所示，MCTS在不断地重复选择（selection）、扩展（expansion）、仿真（simulation）、反向传播（backpropagation）的过程。其中“选择”步骤通过搜索树选择一个节点（对应环境中的一个状态state），“扩展”为搜索树增加一个节点，“仿真”通过环境模型对此节点的回报进行估计，“反向传播”更新得到的回报估计值。

具体而言，在“选择”步骤中，我们通过下式不断选择最优孩子节点：

其中 V_s 是节点 s 的回报平均估值，N_s 是节点 s 的访问次数，C(s) 是 s 的所有孩子节点的集合。

并行 MCTS 的难点可以通过上图中 (b)-(c) 展示。因为有多个 worker 在同时执行上述选择->扩展->仿真->反向传播过程，某一个 worker 在进行「选择」的时候，其他 worker 未结束的仿真结果是无法获取的，这导致大量 worker 只能看到过时且类似的信息，严重影响了搜索树选择节点的好坏，破坏了串行状态下的探索-利用平衡（exploration-exploitation balance）。

为解决这一问题，我们提出了 WU-UCT 算法（Watch the Unobserved in UCT）。这个算法借用了异步并行算法的思想 [2]。WU-UCT 算法的核心在于维护一个额外的统计量用于记录每个节点上有多少个正在对其进行仿真的 worker，并用其对选择算法进行调整：

其中 O_s 是如上所述节点 s 的未返回访问次数统计（unobserved samples）。

此外，根据上面的核心想法，为最大化算法的效率，我们设计了一个并行 MCTS 系统 (a)。我们使用了主-从工作模式的系统。由主进程维护一个完整的搜索树，并进行选择（selection）和反向传播（backpropagation）操作。同时，主进程负责将扩展（expansion）和仿真（simulation）的任务分配给对应的子进程，由子进程完成后将结果返还主进程。这样做的好处在于很好地保证了统计信息对于每次选择都是完整的，同时避免了进程间共享内存和访问冲突等问题。

这一系统在 Atari 游戏和快手「点消快乐城」游戏中进行了测试，发现其加速比能很好地保持线性。

在标准测试环境 Atari 下，WU-UCT 在相同 worker 数和总仿真次数的情况下，在 13/15 个游戏中取得了最好的表现。

此外，随着仿真 worker 数的增大，WU-UCT 基本达到了线性加速比，且其性能损失明显小于对比算法。

最后，WU-UCT 算法已被用于对快手自研的「点消快乐城」游戏进行自动关卡难度测试，并达到了 8.6% 预测误差（Mean Absolute Error，MAE）的表现。

具体而言，我们通过 AI 取代传统人工测试，对大量关卡（超过 1000 关）进行自动难度验证。在 WU-UCT 的帮助下，我们的系统可以准确地预测某一关卡上线后玩家的预期通关率，为关卡设计师提供了很好的指导，达到了不需要人工测试即可得到反馈。此外，我们的测试系统准确率比人工更高，在大幅提高了游戏设计效率的同时，大幅降低了开发成本，也改变游戏制作方式。

感谢

该工作是实习生刘安吉在快手游戏中台和 YTech 的游戏 AI 联合实验室完成。同时感谢腾讯 AI Lab 的陈建树老师对论文的深入参与和建设性的意见。

[1] Anji Liu, Jianshu Chen, Mingze Yu, Yu Zhai, Xuewen Zhou, and Ji Liu,「Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search,」ICLR 2020 (oral 2%) (url: https://openreview.net/forum?id=BJlQtJSKDB)

[2] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu,「Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization,」NIPS 2015 (spotlight 4%)

（url: https://arxiv.org/abs/1506.08272）