独家 | 专访AAAI 2018最佳论文作者，记忆增强蒙特卡洛树搜索细节解读

2018 年 2 月 6 日 机器之心 Synced

机器之心原创

作者：李泽南

AAAI 2018 大会已于 2 月 2 日在美国新奥尔良开幕。在此之前，大会获奖论文的结果已经放出，阿尔伯塔大学提交的论文《Memory-Augmented Monte Carlo Tree Search》获得了 AAAI 2018 大会的杰出论文奖。该论文作者分别为博士生 Chenjun Xiao、梅劲骋与教授 Martin Müller。

Chenjun Xiao 硕士与博士阶段均就读于阿尔伯塔大学，师从 Martin Müller 教授。

梅劲骋本科毕业于华南理工大学，研究生赴上海交通大学，师从计算机系吕宝粮教授。2015 年起，他来到阿尔伯塔大学攻读博士，导师为 Dale Schuurmans 教授。

该论文的导师，阿尔伯塔大学教授 Martin Müller 则因计算机围棋而闻名于世。Müller 教授所带领的团队在博弈树搜索和规划的蒙特卡洛方法、大规模并行搜索和组合博弈论方面颇有建树。围棋程序 AlphaGo 的设计研发主导人物 David Silver 和黄士杰（Aja Huang）（他们分别是 AlphaGo Nature 论文的第一作者和第二作者，也名列于最近的 AlphaGo Zero 论文中）都来自于 Müller 门下。

这篇论文提出了记忆增强的蒙特卡洛树搜索（M-MCTS）方法，M-MCTS 的核心思想是将 MCTS 结合一种记忆结构，其中每一项记录包含一个特定状态的信息。通过结合相似状态的估计，这些记忆被用于生成一个近似值估计。研究人员在围棋中评估了 M-MCTS，实验结果表明 M-MCTS 的性能优于原始蒙特卡洛方法。

在得知获奖信息后，机器之心第一时间联系到了 Martin Müller 教授，并对论文的三位作者共同对论文中的内容、未来研究方向以及一些感兴趣的问题进行了交流。

对于论文的两名中国作者而言，得知获奖后的第一反应是惊讶和幸运。不过，在国际人工智能重要会议的最佳论文奖项上，中国人名字的出现早已成为常态，华人正在 AI 领域扮演着越来越重要的角色。阿尔伯塔大学里，Martin Müller 教授带领的博士生中有很多来自国内。「在阿尔伯塔大学，我们幸运地拥有很多世界级的学生前来攻读学位。」Müller 介绍道，「经我指导已经毕业的中国博士包括 Fan Xie（现为谷歌软件工程师），正在带的博士生有 Gaojian Fan、Chao Gao 和 Chenjun Xiao。他们都是在中国接受本科或研究生教育之后来到阿尔伯塔的，他们在理论背景上训练有素，同时也具备相关领域工作的实践经验。」

作为阿尔伯塔大学的博士生，Chenjun Xiao 等人可以说和 David Silver 和黄士杰师出同门。他们也对 DeepMind 最新的 AlphaGo Zero 发表了一番看法。

「这是我们目前已知的最佳启发式方法了。」Chenjun Xiao 说道。

Martin Müller 教授则认为 AlphaGo Zero 还未到达算法的极限：「但它仍然是一个启发式方法，非常强大，但并不完美……」

梅劲骋也指出了 AlphaGo 目前存在的限制：「当状态、模型和转换是完美已知的时候，这种方法才能展现能力。」

随着人工智能技术逐渐走向实用化，越来越多的科技巨头开始参与其中，业界的学术影响力也在日益提升。在 ICLR 2018 的论文中，来自谷歌的被接收论文数量高达四十余篇，是第二名 UC Berkeley 的四倍之多。目前大学中的人工智能研究或许正因为计算资源的不足而逐渐落后于科技巨头。但 Martin Müller 认为，在大学环境中，学者们仍然可以进行有意义的研究。最佳论文也对这种观点给出了有力的证明。

在围棋之外，阿尔伯塔大学的研究者们也把蒙特卡洛方法应用在了六贯棋上（Hex，一种在六边形格棋盘上进行的桌游），Martin Müller 博士生 Chao Gao 和 Ryan Hayward 教授正在共同研究这一方向。此外，研究人员们已经在把眼光投向了更为复杂的强化学习任务，如即时战略游戏上。

深度学习作为近期人工智能发展的标志性技术，引出了无数的新方法和新应用，却也因为使用场景受限而遭到越来越多人的诟病。近日，Gary Marcus、Yann LeCun 等人对深度学习的局限性展开了很多探讨。Martin Müller 也对此表达了自己的态度：「深度学习对于学习非常复杂的函数而言非常有用，但搜索会始终在这一过程中扮演重要的角色。搜索永远不会被「纯粹的知识」取代。AlphaGo Zero 就是最好的例子，神经网络加上搜索的 Elo 得分超过了单独的神经网络高达 2000 分！这是一个非常大的差距，随着机器获取的知识越来越多，这个差距只会越来越大。」

AlphaGo Zero 的论文中指出，未使用蒙特卡洛树搜索的网络（Raw Network）其 Elo 评分低于完整的 AlphaGo Zero 达 2000 分之多。

因当时最佳论文还未公开，在文章《学界 | AAAI 2018 获奖论文提前揭晓：两大奖项花落阿尔伯塔、牛津》中我们无法介绍更多技术细节。如今，该论文已经放出，机器之心编译介绍如下：

蒙特卡洛树搜索（MCTS）的核心思想是构建一个搜索树，且搜索树的状态由快速蒙特卡洛模拟（Coulom 2006）评估。若从给定博弈状态开始，并通过随机 Self-play 在观察到最终结果前模拟成千上万次博弈，然后我们就可以将模拟的平均输出作为状态值的估计。同时，MCTS 在模拟中会维护一个搜索树，因而借助它指导模拟的方向，其中我们可以使用老虎机算法（bandit algorithm）来权衡利用（exploitation）和探索（exploration）（Kocsis and Szepesvari 2006）。然而，MCTS 不能有效保证「大型状态空间」的价值估计准确度，因为在相对有限的搜索时间内，状态的平均值作为估计会有较高的方差。因此，不准确的估计会误导搜索树的构建，并严重降低程序的性能。

最近，已经有学者提出几种机器学习方法来克服 MCTS 的这种缺点。例如深度神经网络可以用来学习领域知识和逼近状态值的函数。这些方法和与 MCTS 相结合可以提供启发式的方法以提高搜索样本的效率（Silver et al. 2016; Tian and Zhu 2015）。

机器学习方法的成功可以很大程度上归因于模型的泛化性能，即类似的状态共享相似的信息。泛化空间的领域知识一般由函数近似表征，例如深度网络通过一般数据集或自生成的模拟数据集来离线训练（Silver et al. 2016）。

与从离线学习过程中探索泛化的研究相比，在线实时搜索并没有过多关注利用泛化的优势。本论文提出和评估了一种增强记忆的 MCTS 算法，它提供了一种利用在线泛化优势的替代型方法。我们设计了一种记忆，其中每个元素（entry）都包含特定状态的信息，并可作为构建在线值近似的基础。我们利用围棋的实验证明这种基于记忆的框架对于提升 MCTS 的性能十分有效，不论是在理论还是实践中。

论文：Memory-Augmented Monte Carlo Tree Search

论文链接：https://webdocs.cs.ualberta.ca/~mmueller/ps/2018/Chenjun-Xiao-M-MCTS-aaai18-final.pdf

摘要：我们在本文中提出记忆增强的蒙特卡洛树搜索（Memory-Augmented Monte Carlo Tree Search，M-MCTS）并对其进行了评估，提供了利用在线实时搜索的泛化能力的新方法。M-MCTS 的核心思想是将 MCTS 结合一种记忆结构，其中每一项记录包含一个特定状态的信息。通过结合相似状态的估计，这些记忆被用于生成一个近似值估计。我们在本文中表明基于记忆的值逼近在温和条件下高概率地优于原始的蒙特卡洛评估方法。我们在围棋中评估了 M-MCTS。实验结果表明 M-MCTS 在相同的模拟次数下优于原始的 MCTS。

蒙特卡洛树搜索

MCTS 构建树以评估状态并进行快速模拟（Coulom 2006）。树中的每个节点对应一个具体的状态 s∈S，并包含模拟统计 V (s) hat 和 N(s)。在算法的每一次迭代中，一个模拟从一个初始状态 s_0 状态开始，之后进入两个阶段： in-tree 和 rollout。在当前的搜索树表征了状态 s_t 时，会应用树策略选择一个动作，以达到下一个状态。树策略的最常用选择是使用老虎机算法，例如 UCB1（Kocsis and Szepesvari 2006）。对于树之外的策略，树将应用 roll-out 策略模拟一场博弈直到结束，其中被访问的状态的轨迹为 T = {s_0, s_1, . . . , s_T }，并在最后获得返回值 R。树中的 s∈T 的统计根据下式进行更新：

此外，树也同时在生长。在最简单的方案中，第一个被访问的尚未在树中的节点会被添加到树上。

MCTS 结合记忆

我们现在介绍记忆增强 MCTS（M-MCTS）算法。图（1）提供了简要的图示。M-MCTS 和常规的 MCTS 的主要区别在于，M-MCTS 搜索树的每一个节点都会存储统计的一个扩展集合：

这里，N_M 是近似记忆值 V_M(s) hat 的估计次数。在 MCTS 的 in-tree 树搜索期间，我们使用取代 V(s) hat 作为状态 s 的值，用于 in-tree 选择，例如在 UCB 公式中。λ_s 是一个延迟参数，确保不存在非对称的偏差。

图 1：M-MCTS 的简要图示。当搜索到一个叶状态时，会生成一个特征表征φ（s），然后其被用于询问（query）基于记忆的值近似 V_M(s) hat。V_M(s) hat 被用于根据下式更新 s 和 s 的所有过去状态，如图中的红色箭头所示。

我们在围棋游戏中评估了 M-MCTS，我们的基线结果是基于开源的围棋程序 Fuego（Enzenberger and Muller 2008 2017），但是添加了 DCNN 以提升性能。下图展示了实验结果：

图 2：(a)-(c) 展示了测试 M 的不同值的结果。(d) 展示了测试不同记忆规模的结果。在所有的图中，x 轴是每次落子（s 到达下一个状态）的模拟数量，y 轴是与基线方法博弈的胜率。

我们每次落子从 {1000, 5000, 10000} 使用不同的模拟次数，实验结果展示在上图 2(a)-(c) 中。在我们使用设定 {M = 50, τ = 0.1} 时获得了最好的结果，它以每次落子进行 10000 次模拟对抗基线算法并实现了 71% 的胜率。此外，我们也探索了不同记忆大小 {1000, 5000, 10000} 的影响。M 和 τ 分别设置为 50 和 0.1，实验结果在上图的 2(d) 中展示。直观上，我们会认为较大的记忆会有更好的性能，因为 query 会包含更多的候选状态，以上的实验结果也证明了这一点。

结论和未来工作

在本论文中，我们提出了一个有效的方法来利用实时搜索的在线泛化。我们的方法，记忆增强的蒙特卡洛树搜索（M-MCTS），将原始的 MCTS 算法与存储框架相结合，来提供基于存储的在线数值近似。未来，我们计划探索以下两个方向。首先，我们想探索是否可以通过结合离线学习的数值近似来让我们的在线存储框架获得更好的泛化性能；其次，让 M-MCTS 的特征表示重用一个神经网络来预测下一步。