蒙特卡洛树搜索(英语:Monte Carlo tree search;简称:MCTS)是一种用于某些决策过程的启发式搜索算法,最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序[1],它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。
历史
基于随机抽样的蒙特卡洛方法可以追溯到20世纪40年代[2]。布鲁斯·艾布拉姆森(Bruce Abramson)在他1987年的博士论文中探索了这一想法,称它“展示出了准确、精密、易估、有效可计算以及域独立的特性。”[3]他深入试验了井字棋,然后试验了黑白棋和国际象棋的机器生成的评估函数。1992年,B·布鲁格曼(B. Brügmann)首次将其应用于对弈程序[4],但他的想法未获得重视。2006年堪称围棋领域蒙特卡洛革命的一年[5],雷米·库洛姆(Remi Coulom)描述了蒙特卡洛方法在游戏树搜索的应用并命名为蒙特卡洛树搜索[6]。列文特·科奇什(Levente Kocsis)和乔鲍·塞派什瓦里(Csaba Szepesvári)开发了UCT算法[7],西尔万·热利(Sylvain Gelly)等人在他们的程序MoGo中实现了UCT[8]。2008年,MoGo在九路围棋中达到段位水平[9],Fuego程序开始在九路围棋中战胜实力强劲的业余棋手[10]。2012年1月,Zen程序在19路围棋上以3:1击败二段棋手约翰·特朗普(John Tromp)[11]。
![Thumb](http://upload.wikimedia.org/wikipedia/commons/8/84/Computer-go-ratings-Chinese.png)
蒙特卡洛树搜索也被用于其他棋盘游戏程序,如六贯棋[13]、三宝棋[14]、亚马逊棋[15]和印度斗兽棋[16];即时电子游戏,如《吃豆小姐》[17][18]、《神鬼寓言:传奇》[19]、《罗马II:全面战争》[20];不确定性游戏,如斯卡特[21]、扑克[22]、万智牌[23]、卡坦岛[24]。
原理
蒙特卡洛树搜索的每个循环包括四个步骤:[25]
- 选择(Selection):从根节点R开始,连续向下选择子节点至叶子节点L。下文将给出一种选择子节点的方法,让游戏树向最优的方向扩展,这是蒙特卡洛树搜索的精要所在。
- 扩展(Expansion):除非任意一方的输赢使得游戏在L结束,否则创建一个或多个子节点并选取其中一个节点C。
- 仿真(Simulation):再从节点C开始,用随机策略进行游戏,又称为playout或者rollout。
- 反向传播(Backpropagation):使用随机游戏的结果,更新从C到R的路径上的节点资讯。
每一个节点的内容代表胜利次数/游戏次数
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b3/MCTS_%28English%29.svg/640px-MCTS_%28English%29.svg.png)
探索与利用
选择子结点的主要困难是:在较高平均胜率的移动后,在对深层次变型的利用和对少数模拟移动的探索,这二者中保持某种平衡。第一个在游戏中平衡利用与探索的公式被称为UCT(Upper Confidence Bounds to Trees,上限置信区间算法 ),由匈牙利国家科学院电脑与自动化研究所高级研究员列文特·科奇什与阿尔伯塔大学全职教授乔鲍·塞派什瓦里提出[7]。UCT基于奥尔(Auer)、西萨-比安奇(Cesa-Bianchi)和费舍尔(Fischer)提出的UCB1公式[26],并首次由马库斯等人应用于多级决策模型(具体为马尔可夫决策过程)[27]。科奇什和塞派什瓦里建议选择游戏树中的每个结点移动,从而使表达式 具有最大值。在该式中:
- 代表第次移动后取胜的次数;
- 代表第次移动后仿真的次数;
- 为探索参数—理论上等于;在实际中通常可凭经验选择;
- 代表仿真总次数,等于所有的和。
目前蒙特卡洛树搜索的实现大多是基于UCT的一些变形。
参见
参考来源
延伸阅读
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.