AAAI 2018最佳论文出炉，中国留学生再下一城

编辑｜Natalie

译者｜马卓奇

消息来源｜AAAI 官网，Twitter

AI 前线导读：人工智能顶级会议 AAAI 2018 于今天（2 月 2 日）在美国路易斯安那州新奥尔良正式开幕。然而，在大会开始前，最佳论文获奖信息就已经在网上传播开了，加拿大阿尔伯塔大学的两名中国留学生斩获这一奖项。1 月 31 日，最佳论文作者 Martin Müller 教授抢先在推特上公开了他们的这篇获奖论文，AI 前线将简要介绍这篇获奖论文的内容。

更多干货内容请关注微信公众号“AI 前线”，（ID：ai-front）

去年的 AAAI 大会上华人学者的名字刷屏了整个接收论文名单，但最佳论文奖和最佳学生论文奖均没有出现华人的名字。这一次，霸屏还在继续，而最佳论文奖也终于再度被华人学者收入囊中。根据 jeffhuang 统计的获奖论文清单（http://jeffhuang.com/best_paper_awards.html）， 这应该是自 1996 年以来华人学者第五次获得 AAAI 最佳论文奖。

AAAI 最佳论文奖获奖论文体现了技术贡献和阐述的最高标准。这个奖通常是奖励给在计算机科学领域兼具广度和独特性的研究者，这些研究通常构建了不同科系和学科之间的桥梁。

Martin Müller 教授 Twitter 消息

AAAI 官方程序手册节选

本届获得 AAAI“最佳论文奖”的是加拿大阿尔伯塔大学的 Martin Müller 教授与他的两位学生 Chenjun Xiao、Jincheng Mei 的论文：“Memory-Augmented Monte Carlo Tree Search”（记忆增强的蒙特卡洛树搜索）。

AI 前线趣闻：

该论文的导师，阿尔伯塔大学教授 Martin Müller 是计算机围棋顶级专家，主要研究领域包括：博弈树搜索和规划的蒙特卡洛方法、大规模并行搜索和组合博弈论。实际上，2016 年揭开人工智能火热大戏序幕的 AlphaGo 的设计研发主导人物 David Silver 和黄士杰（Aja Huang）（他们分别是发表于 Nature 的 AlphaGo 论文的一作和二作）都曾师从于他。甚至有知乎网友将 Martin Müller 教授称为“王背后的男人——AlphaGo 背后的祖师爷”。

Chenjun Xiao 于 2014 年加入 Martin Müller 教授的研究小组，攻读硕士学位，2016 年开始攻读博士学位。

Jincheng Mei 本科毕业于华南理工大学，硕士毕业于上海交通大学，于 2015 年进入加拿大阿尔伯塔大学攻读博士学位，师从 Dale Schuurmans 教授。

以下是 AI 前线对论文内容的简要编译：

摘要

这篇论文提出了记忆增强的蒙特卡洛树搜索算法（Memory-Augmented Monte Carlo Tree Search，M-MCTS），为在线实时搜索提供了一个新的利用泛化性的方法。M-MTCS 的核心思想是为 MCTS 增加了一个记忆结构，该结构的每一个入口都含有一个特殊状态信息。记忆结构结合相似状态的估计产生一个近似的值估计。作者发现，基于记忆的值估计结果比温和条件下高概率的普通蒙特卡洛算法估计结果更好。作者在围棋游戏中评测了 M-MCTS 的性能。实验结果表明，在相同模拟次数下，M-MCTS 优于原来的 MCTS。

论文介绍

MCTS 的核心思想是根据快速蒙特卡洛模拟对状态的估计值构建搜索树。给定当前棋面状态，通过随机的自我博弈模拟上千场棋局，直到游戏结束。随后，根据模拟结果的平均值估测状态值。同时，搜索树通过 bandit 算法对于探索（exploration）和利用（exploitation）进行权衡，导引模拟的方向。然而，对于巨大的状态空间，值估计的准确率不能得到有效保证，因为在有限的搜索时间内，平均值估计容易呈现较高方差。这种不准确的估计会误导搜索树的构建方向，从而严重影响算法的性能。

近期提出了几个新的机器学习算法，旨在解决 MCTS 的这一缺点。例如，使用深度神经网络来学习域知识，并近似状态值函数。它们与 MCTS 的结合为实践中提高搜索样本效率带来了启发式算法。

机器学习方法的成功绝大部分可以归结于其强大的泛化能力，例如相似状态共享信息。广义的域知识通常由函数近似来表示，例如深度神经网络，通过专门的数据集或自我生成的模拟进行离线训练。

目前已有大量的研究从离线学习中发现泛化能力，相比之下很少有人关注在线实时搜索时如何利用算法泛化带来的好处。这篇论文提出了记忆增强的 MCTS 算法，为利用在线泛化提供了一个不一样的方法。作者设计了一个记忆结构（memory），每一个入口包含某一个特定状态的信息，作为构建在线值近似的基础。论文从理论和实践（围棋游戏实验）上证实了该基于记忆的框架对 MCTS 性能的提升。

图 1：M-MCTS 算法解释。

当叶子状态 s 被搜索到时，特征表示ϕ(s) 随之产生，随后用于搜索基于记忆的值近似。值近似用于更新 s 和所有的父节点，这一过程由图中红色箭头表示。

实验

作者在中国围棋游戏中对 M-MCTS 算法进行了测试。

基准实验

算法实现基于开源围棋项目 Fuego，但是增加了深度卷积神经网络（DCNN）来提升性能。DCNN 在状态节点刚被添加入搜索树时调用，来初始化模拟数据。算法以一种同步方式在 MCTS 中加入 DCNN，即当 DCNN 返回估测结果时，搜索会继续进行。基准实验在 Fuego 中取得了 97% 的胜利率，每一步进行 10000 次模拟。

实验结果

算法主要有 3 个参数，记忆结构中的近邻数量 M：、温度参数τ：，及每步模拟运行次数：。作者在实验中测试了这 3 个参数对 M-MCTS 算法性能的影响。

图 2（a）-（c）显示了不同 M 值的实验结果。

当 M 和τ分别取时，算法得到了最好结果：每步运行模拟次数为 10000，与基准实验进行围棋游戏中取得了 70% 的胜利率，每一次结果的标准差大约在 2.5%。

在同等参数情况下，作者对记忆结构的大小进行了实验。记忆结构的大小取值为。一般情况下，记忆结构越大，算法性能越好，因为搜索中能包括更多的候选状态。图 2（d）显示，记忆结构大小为 10000 时算法取得最佳性能。

作者也对比了在每走一步所需计算时间相同的情况下（每步 5 秒），M-MCTS 在与基准实验进行围棋游戏中取得了 61% 的胜利率。

未来工作

作者计划未来探索以下两个方向：

1）是否可以通过将离线学习的近似值与所提出的在线基于记忆的框架结合，得到更好的泛化效果。

2）M-MCTS 中利用了为预测行为而设计的神经网络进行特征表示，未来将探索如何将特征表示学习与 M-MCTS 整合，成为端到端的算法。