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

机器心脏原件

2月2日，AAAI 2018大会在美国新奥尔良开幕。在此之前，获奖论文的结果已经公布，阿尔伯塔大学提交的论文《记忆-增强蒙特卡罗树搜索》获得了AAAI 2018会议优秀论文奖。本文作者为博士生肖晨军、梅金成和马丁·米勒教授。

肖晨军在阿尔伯塔大学攻读硕士和博士学位，师从马丁·穆勒教授。

梅锦程本科毕业于华南理工大学，研究生毕业于上海交通大学，师从计算机系鲁保良教授。自2015年起，他来到阿尔伯塔大学攻读博士学位，导师是Dale Schuurmans教授。

本论文的导师、阿尔伯塔大学教授马丁·穆勒(Martin Müller)以计算机围棋而闻名。穆勒教授领导的团队在博弈树搜索与规划的蒙特卡罗方法、大规模并行搜索、组合博弈论等方面取得了巨大的成就。Go程序AlphaGo的设计开发领军人物大卫·西尔弗(David Silver)和阿佳·黄(Aja Huang)(他们是AlphaGo Nature论文的第一作者和第二作者，也在最近的AlphaGo Zero论文中列出)都来自穆勒。

提出了一种记忆增强的蒙特卡罗树搜索方法(M-MCTS)。M-MCTS的核心思想是将MCTS与一种记忆结构相结合，在这种记忆结构中，每条记录都包含特定状态的信息。通过组合相似状态的估计，这些存储器被用来产生近似估计。研究者对围棋中的M-MCTS进行了评估，实验结果表明，M-MCTS的性能优于原有的蒙特卡罗方法。

得知获奖信息后，机器心第一时间联系了马丁·穆勒教授，与论文三位作者分享了论文内容、未来研究方向和一些有趣的问题。

对于论文的两位中国作者来说，得知获奖后的第一反应是惊讶和幸运。而中文名字的出现早已成为国际人工智能大会最佳论文奖的常态，中文在AI领域的作用越来越大。在阿尔伯塔大学，马丁·米勒教授带领的许多博士生来自中国。“在阿尔伯塔大学，我们很幸运有许多世界级的学生来攻读学位。米勒介绍说:“在我指导下毕业的中国博士有(现谷歌软件工程师)，即将带来的博士生有范、、肖晨军。他们都是在国内接受本科或研究生教育后来到艾伯塔省的。他们受过良好的理论背景培训，在相关领域有实践经验。」

作为阿尔伯塔大学的博士生，肖晨军等人可以说是和大卫·西尔弗、一样。他们还对DeepMind最新的AlphaGo Zero发表了看法。

"这是迄今为止我们知道的最好的启发式方法. "陈军晓说。

马丁·穆勒教授认为AlphaGo Zero还没有达到算法的极限:“但它仍然是一种启发式方法，非常强大，但并不完美……”

梅锦程也指出了AlphaGo目前的局限性:“当状态、模型、跃迁都完美已知时，这种方法才能显示出它的能力。」

随着人工智能技术逐渐实用化，越来越多的技术巨头开始参与其中，行业的学术影响力也在不断增加。在ICLR 2018论文中，从谷歌获得的论文数量高达40多篇，是加州大学伯克利分校的四倍，位居第二。目前，由于计算资源的缺乏，大学对人工智能的研究可能会逐渐落后于技术巨头。但马丁·穆勒认为，在大学环境下，学者仍然可以做有意义的研究。最好的论文也有力地证明了这一观点。

除了围棋，阿尔伯塔大学的研究人员还将蒙特卡罗方法应用于十六进制(一种在六边形棋盘上玩的棋盘游戏)，马丁·穆勒的高朝博士和瑞安·海沃德教授正在共同研究这个方向。此外，研究人员将注意力转向更复杂的强化学习任务，如实时策略游戏。

深度学习作为人工智能近期发展的标志性技术，带来了无数新的方法和应用，但也因其使用场景有限而受到越来越多人的批评。最近加里马库斯，Yann LeCun等人讨论了深度学习的局限性。马丁·穆勒也表达了自己的态度:“深度学习对于学习非常复杂的函数非常有用，但搜索在这个过程中始终会发挥重要作用。搜索永远不会被“纯知识”所取代。AlphaGo Zero就是最好的例子。神经网络加搜索的Elo评分超过单个神经网络2000分！这是一个非常大的差距。随着机器获取的知识越来越多，这种差距只会越来越大。」

根据AlphaGo Zero的论文，没有蒙特卡洛树搜索的Raw Network的Elo评分比完全AlphaGo Zero低了多达2000分。

因为当时没有发表最好的论文，所以无法在文章《学术圈| AAAI 2018获奖论文提前公布:两个奖项在阿尔伯塔和牛津度过》中介绍更多的技术细节。现在论文已经发布，机心的编写介绍如下:

蒙特卡罗树搜索(MCTS)的核心思想是建立一个搜索树，并通过快速蒙特卡罗模拟(库仑2006)来评估搜索树的状态。如果我们从一个给定的游戏状态出发，模拟成千上万个游戏，然后随机自玩观察最终结果，那么我们可以把模拟的平均输出作为状态值的估计。同时，MCTS在模拟中维护了一个搜索树，因此它可以引导模拟的方向，在其中我们可以使用土匪算法来平衡开发和勘探(Kochis和Szeepsvari 2006)。然而，MCTS不能有效保证“大状态空”之间的值估计的准确性，因为在相对有限的搜索时间内，状态的平均值作为估计会有较高的方差。因此，不准确的估计会误导搜索树的构建，严重降低程序的性能。

最近，一些学者提出了几种机器学习方法来克服MCTS的这个缺点。例如，深度神经网络可以用于学习领域知识和接近状态值的功能。这些方法结合MCTS可以提供启发式方法来提高搜索样本的效率(Silver等2016；田，朱(2015).

机器学习方法的成功可以归因于模型的泛化性能，即相似的状态共享相似的信息。泛化空之间的领域知识一般以函数逼近为特征。例如，深度网络通过通用数据集或自生成模拟数据集离线训练(Silver等人，2016年)。

与从离线学习探索泛化的研究相比，在线实时搜索并不太重视泛化的优势。本文提出并评估了一种记忆增强MCTS算法，该算法提供了一种利用在线泛化能力的替代方法。我们设计了一种内存，其中每个条目包含特定状态的信息，可以作为构建在线值逼近的基础。我们在围棋上的实验表明，无论在理论上还是在实践中，这种基于记忆的框架对于提高MCTS的性能都是非常有效的。

论文:记忆增强蒙特卡罗树搜索

论文链接:MMU eller/PS/2018/chenjun-肖-m-mcts-aaai18-final.pdf

本文提出并评价了记忆增强蒙特卡罗树搜索(M-MCTS)，并提供了一种利用在线实时搜索泛化能力的新方法。M-MCTS的核心思想是将MCTS与一种记忆结构相结合，在这种记忆结构中，每条记录都包含特定状态的信息。通过组合相似状态的估计，这些存储器被用来产生近似估计。在本文中，我们证明了在温和的条件下，基于记忆的数值逼近方法比原有的蒙特卡罗评估方法具有更高的概率。我们评估了《围棋》中的MCTS。实验结果表明，在相同的模拟次数下，M-MCTS优于原MCTS。

蒙特卡罗树搜索

MCTS建立了一棵树来评估状态并进行快速模拟(库仑2006)。树中的每个节点对应一个特定的状态s∈S，包含模拟统计量V (s) hat和N(s)。在算法的每次迭代中，模拟从初始状态s_0开始，然后进入两个阶段:树内和卷展栏。当当前搜索树表示状态s_t时，它将应用树策略来选择一个动作以到达下一个状态。树策略最常见的选择是使用老虎机算法，比如UCB1(Kocsis和Szepesvari 2006)。对于树外的策略，树将应用展开策略来模拟一个游戏直到结束，其中被访问状态的轨迹是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的树内搜索中，我们使用

例如，在UCB公式中，将V(s) hat替换为树内选择的状态s的值。λ_s是一个延迟参数，用于确保没有不对称偏差。

图1:m-MCT的简图。当搜索一个叶状态时，生成一个特征表示φ(s)，然后用它来查询基于内存的近似值V_M(s) hat。V_M(s) hat用于根据以下公式更新s和s的所有过去状态，如图中红色箭头所示。

我们在围棋游戏中评价了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)。直觉上我们认为内存越大性能越好，因为查询会包含更多的候选状态，上面的实验结果也证明了这一点。

结论和今后的工作

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

这篇文章是为机器的心脏而写的。请联系本微信官方账号进行授权。