蒙特卡洛树搜索 Monte Carlo Tree Search

什么是 MCTS?

全称 Monte Carlo Tree Search,是一种人工智能问题中做出最优决策的方法,一般是在组合博弈中的行动(move)规划形式。它结合了随机模拟的一般性和树搜索的准确性。

MCTS 受到快速关注主要是由计算机围棋程序的成功以及其潜在的在众多难题上的应用所致。超越博弈游戏本身,MCTS 理论上可以被用在以 {状态 state,行动 action} 对定义和用模拟进行预测输出结果的任何领域。


基本算法

基本的 MCTS 算法非常简单:根据模拟的输出结果,按照节点构造搜索树。其过程可以分为下面的若干步:

搜索树的构建过程

  1. 选择 Selection:从根节点 R 开始,递归选择最优的子节点(后面会解释)直到达到叶子节点 L。
  2. 扩展 Expansion:如果 L 不是一个终止节点(也就是,不会导致博弈游戏终止)那么就创建一个或者更多的字子节点,选择其中一个 C。
  3. 模拟 Simulation:从 C 开始运行一个模拟的输出,直到博弈游戏结束。
  4. 反向传播 Backpropagation:用模拟的结果输出更新当前行动序列。

参看Tutorial 了解关于这个过程更多的信息。

每个节点并需包含两个重要的信息:一个是根据模拟结果估计的值和该节点已经被访问的次数。

按照最为简单和最节约内存的实现,MCTS 将在每个迭代过程中增加一个子节点。不过,要注意其实根据不同的应用这里也可以在每个迭代过程中增加超过一个子节点。


节点选择

Bandits 和 UCB

在树向下遍历时的节点选择通过选择最大化某个量来实现,这其实类似于 Multiarmed bandit problem,其中的参与者必须选择一个 slot machine(bandit)来最大化每一轮的估计的收益。我们可以使用 Upper Confidence Bounds(UCB)公式常常被用来计算这个:

其中 v_i 是节点估计的值,n_i 是节点被访问的次数,而 N 则是其父节点已经被访问的总次数。C 是可调整参数。

Exploitation 和 Exploration

UCB 公式对已知收益的 exploitation 和鼓励接触那些相对未曾访问的节点的 exploration 进行平衡。收益估计基于随机模拟,所以节点必须被访问若干次来缺包估计变得更加可信;MCTS 估计会在搜索的开始不大可靠,而最终会在给定充分的时间后收敛到更加可靠的估计上,在无限时间下能够达到最优估计。

MCTS 和 UCT

Kocsis 和 Szepervari 在 2006 年首先构建了一个完备的 MCTS 算法,通过扩展 UCB 到 minimax 树搜索,并将其命名为 Upper Confidence Bounds for Trees(UCT)方法。这其实是用在当前众多 MCTS 实现中的算法版本。

UCT 可以被描述为 MCTS 的一个特例:UCT = MCTS + UCB。


优点

MCTS 提供了比传统树搜索更好的方法。

Aheuristic

MCTS 不要求任何关于给定的领域策略或者具体实践知识来做出合理的决策。这个算法可以在没有任何关于博弈游戏除基本规则外的知识的情况下进行有效工作;这意味着一个简单的 MCTS 实现可以重用在很多的博弈游戏中,只需要进行微小的调整,所以这也使得 MCTS 是对于一般的博弈游戏的很好的方法。

Asymmetric

MCTS 执行一种非对称的树的适应搜索空间拓扑结构的增长。这个算法会更频繁地访问更加有趣的节点,并聚焦其搜索时间在更加相关的树的部分。

非对称的增长

这使得 MCTS 更加适合那些有着更大的分支因子的博弈游戏,比如说 19X19 的围棋。这么大的组合空间会给标准的基于深度或者宽度的搜索方法带来问题,所以 MCTS 的适应性说明它(最终)可以找到那些更加优化的行动,并将搜索的工作聚焦在这些部分。

任何时间

算法可以在任何时间终止,并返回当前最有的估计。当前构造出来的搜索树可以被丢弃或者供后续重用。

缺点

MCTS 有很少的缺点,不过这些缺点也可能是非常关键的影响因素。

行为能力

MCTS 算法,根据其基本形式,在某些甚至不是很大的博弈游戏中在可承受的时间内也不能够找到最好的行动方式。这基本上是由于组合步的空间的全部大小所致,关键节点并不能够访问足够多的次数来给出合理的估计。

速度

MCTS 搜索可能需要足够多的迭代才能收敛到一个很好的解上,这也是更加一般的难以优化的应用上的问题。例如,最佳的围棋程序可能需要百万次的交战和领域最佳和强化才能得到专家级的行动方案,而最有的 GGP 实现对更加复杂的博弈游戏可能也就只要每秒钟数十次(领域无关的)交战。对可承受的行动时间,这样的 GGP 可能很少有时间访问到每个合理的行动,所以这样的情形也不大可能出现表现非常好的搜索。

幸运的是,算法的性能可以通过一些技术显著提升。


提升

很多种 MCTS 强化的技术已经出现了。这些基本上可以归纳为领域知识或者领域独立两大类。

领域知识

特定博弈游戏的领域知识可以用在树上来过滤掉不合理的行动或者在模拟过程中产生重要的对局(更接近人类对手的表现)。这意味着交战结果将会更加的现实而不是随机的模拟,所以节点只需要少量的迭代就能给出一个现实的收益值。

领域知识可以产生巨大的性能提升,但在速度和一般性上也会有一定的损失。

领域独立

领域独立强化能够应用到所有的问题领域中。这些一般用在树种(如 AMAF),还有一些用在模拟(如 在交战时倾向于胜利的行动)。领域独立强化并不和特定的领域绑定,具有一般性,这也是当前研究的重心所在。


背景和历史

1928:John von Neumann 的 minimax 定理给出了关于对手树搜索的方法,这形成了计算机科学和人工智能的从诞生至今的决策制定基础。 1940s:Monte Carlo 方法形成,作为一种通过随机采样解决不太适合树搜索解决的弱良定义问题的方法。 2006:Rémi Coulomb 和其他研究者组合了上面两种想法给出了一个新的围棋程序中行动规划的观点——MCTS。Kocsis 和 Szepesvári 将此观点形式化进 UCT 算法。


研究兴趣

从 MCTS 诞生后几年内,就有超过 150 篇与 MCTS 相关的研究论文发布,平均下来是每两周一篇新的文章。这些文章中包含了大概 50 个推荐的变体、强化和优化,这和传统树搜索自其 1928 年诞生开始的加强的数量也差不太多。

这个新的研究领域当前是 AI 中非常热的研究话题,有很多的开放的研究问题有待发掘和解决。


MCTS: 最新成果

Imperial College London held the first international MCTS workshop in August 2010 on the theme of MCTS: State of the Art. Speakers included: O. Teytaud, "State of the Art: What is MCTS, where is it now, and where is it going?” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:london2010.pdf M. Müller, “Challenges in Monte Carlo Tree Search,” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:london2010-mcts-challenges.pdf R. Hayward, “MoHex: Computer Hex world champion,” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:mohextalk.pdf H. Finnsson and Y. Björnsson, “CadiaPlayer: MCTS in General Game Playing,” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:cadiaplayer_lic_slides_print.pdf A. Rimmel, “Havannah, Monte Carlo Enhancements and Linear Transforms,” 2010 [Online]. Available:http://www.aigamesnetwork.org/_media/main:events:presmctsworkshop_rimmel.pdf

https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/ https://jeffbradberry.com/tag/alphago/ http://lamda.nju.edu.cn/yuy/(S(o2npwm55cfhx2yinvnpmnczl))/course_ai16.ashx http://lamda.nju.edu.cn/yuy/(S(o2npwm55cfhx2yinvnpmnczl))/GetFile.aspx?File=course_ai16/Lecture5.pdf http://www.cameronius.com/cv/mcts-survey-master.pdf

原文发布于微信公众号 - UAI人工智能(UniversityAI)

原文发表时间:2016-09-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏应兆康的专栏

送给刚踏入数模路上的萌新们

送给刚踏入数模路上的萌新们 这里不会引用任何官方术语,均为我个人的理解,所以小伙伴们放心阅读 前面如果觉得很枯燥,可以调到后面,后面会提供干货 顺便打个广告,嘿...

38610
来自专栏数据派THU

哪款安卓手机适合跑AI?移动端芯片性能评测论文出炉

苏黎世联邦理工学院曾经开发了一款 AI Benchmark 应用,用于测试不同安卓设备和芯片的深度学习性能。近期,他们联合谷歌、高通、华为、联发科以及 Arm ...

843
来自专栏新智元

AI当“暖男”:给裸照自动穿上比基尼

【新智元导读】AI可以用来鉴黄,但有时会把含裸女的古典名画过滤掉。巴西的一组研究人员在JICNN上展示了一种新方法,使用生成对抗网络,给女性裸体照“穿上”比基尼...

782
来自专栏人工智能LeadAI

推荐系统 | 威尔逊区间法

我推荐一种之前在惠普做过一种排序方法:威尔逊区间法 我们先做如下设定: (1)每个用户的打分都是独立事件。 (2)用户只有两个选择,要么投喜欢'1',要么投不喜...

4806
来自专栏人工智能快报

人工智能训练使用视网膜扫描发现心脏病风险

谷歌及其子公司Verily的科学家们发现了一种利用机器学习来评估一个人患心脏病风险的新方法。通过分析病人眼睛后部的扫描结果,该公司的软件能够准确地推断出数据,包...

3315
来自专栏AI科技大本营的专栏

资源 | 做一款炫酷的机器人需要哪些学习资源(机器人资源Awesome系列)

翻译 | AI科技大本营 参与 | 赵博 SuiSui 为什么要制作机器人呢?想参加各种机器人大赛?看起来很炫酷?不过从学习角度说,机器人综合了信息技术、电子工...

36410
来自专栏专知

专知主题链路知识推荐#1——马尔科夫链蒙特卡洛采样(附代码)

【导读】主题链路知识是我们专知的核心功能之一,为用户提供AI领域系统性的知识学习服务,一站式学习人工智能的知识,包含人工智能( 机器学习、自然语言处理、计算机视...

3037
来自专栏智能算法

机器视觉(系列二)----图像采集之照明综述

上集我们一起做了个简短入门: 机器视觉算法(系列一)--机器视觉简短入门 在机器视觉中,照明的目的是使被测物的重要特征显现,而抑制不需要的特征。为了达到此目的,...

35212
来自专栏腾讯高校合作

异质信息网络:一种新颖的网络建模与分析方法

异质信息网络被定义为一个有向图,它包含有多种类型的对象或者关系,每个对象属于一个特定的对象类型,每条关系属于一个特定的关系类型。

1.3K7
来自专栏大数据挖掘DT机器学习

PageRank算法(2):PageRank原理剖析

一、PageRank算法的简单举例 Google PageRank算法的思想精华在于:将一个网页级别/重要性的排序问题转化成了一个公共参与、以群体民主投票的方式...

4296

扫码关注云+社区