蒙特卡洛树搜索

✍ dations ◷ 2025-07-10 15:37:31 #组合博弈论,蒙地卡罗方法,人工智能,搜寻算法

蒙特卡洛树搜索(英语:Monte Carlo tree search;简称:MCTS)是一种用于某些决策过程的启发式搜索算法,最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序,它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

基于随机抽样的蒙特卡洛方法可以追溯到20世纪40年代。布鲁斯·艾布拉姆森(Bruce Abramson)在他1987年的博士论文中探索了这一想法,称它“展示出了准确、精密、易估、有效可计算以及域独立的特性“。他深入试验了井字棋,然后试验了黑白棋和国际象棋的机器生成的评估函数。1992年,B·布鲁格曼(B. Brügmann)首次将其应用于对弈程序,但他的想法未获得重视。2006年堪称围棋领域蒙特卡洛革命的一年,雷米·库洛姆(Remi Coulom)描述了蒙特卡洛方法在游戏树搜索的应用并命名为蒙特卡洛树搜索。列文特·科奇什(Levente Kocsis)和乔鲍·塞派什瓦里(Csaba Szepesvári)开发了UCT算法,西尔万·热利(Sylvain Gelly)等人在他们的程序MoGo中实现了UCT。2008年,MoGo在九路围棋中达到段位水平,Fuego程序开始在九路围棋中战胜实力强劲的业余棋手。2012年1月,Zen程序在19路围棋上以3:1击败二段棋手约翰·特朗普(John Tromp)。

蒙特卡洛树搜索也被用于其他棋盘游戏程序,如六贯棋、三宝棋、亚马逊棋和印度斗兽棋;即时电子游戏,如《吃豆小姐(英语:Ms. Pac-Man)》、《神鬼寓言:传奇(英语:Fable Legends)》、《罗马II:全面战争》;不确定性游戏,如斯卡特、扑克、万智牌、卡坦岛。

蒙特卡洛树搜索的每个循环包括四个步骤:

每一个节点的内容代表

选择子结点的主要困难是:在较高平均胜率的移动后,在对深层次变型的利用和对少数模拟移动的探索,这二者中保持某种平衡。第一个在游戏中平衡利用与探索的公式被称为UCT(Upper Confidence Bounds to Trees,上限置信区间算法 ),由匈牙利国家科学院计算机与自动化研究所高级研究员列文特·科奇什与阿尔伯塔大学全职教授乔鲍·塞派什瓦里提出。UCT基于奥尔(Auer)、西萨-比安奇(Cesa-Bianchi)和费舍尔(Fischer)提出的UCB1公式,并首次由马库斯等人应用于多级决策模型(具体为马尔可夫决策过程)。科奇什和塞派什瓦里建议选择游戏树中的每个结点移动,从而使表达式 w i n i + c ln t n i {\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln t}{n_{i}}}}} 具有最大值。在该式中:

大多数当代蒙特卡洛树搜索的实现都是基于UCT的一些变形。

相关

  • 微米微米(Micrometer、㎛)是长度单位,符号µm。1微米相当于1米的一百万分之一(10-6,此即为“微”的字义)。此外,在ISO 2955的国际标准中,“u”已经被接纳为一个代替“μ”来代表10-6的国
  • 鸦片类药物过量鸦片类药物过量是指因为鸦片类药物使用过量造成的中毒现象。鸦片类药物包括吗啡、海洛因、芬太尼、曲马多和美沙酮。症状包括呼吸量不足(英语:respiratory depression)、瞳孔缩
  • 核磁核磁共振(NMR,Nuclear Magnetic Resonance)是基于原子尺度的量子磁物理性质。具有奇数质子或中子的核子,具有内在的性质:核自旋,自旋角动量。核自旋产生磁矩。NMR观测原子的方法,是
  • 布拉格瓦茨拉夫·哈维尔国际机场布拉格瓦茨拉夫·哈维尔机场(捷克语:Letiště Václava Havla Praha;IATA代码:PRG;ICAO代码:LKPR),旧称布拉格鲁济涅国际机场(Mezinárodní letiště Praha-Ruzyně),是捷克首都布拉
  • 第四马其顿军团第四马其顿军团(英语:Legio IV Macedonica)古罗马军队建制名称。由尤利乌斯·凯撒于公元前48年建立,该军团曾参加罗马内战并发挥作用。公元70年被罗马帝国君主韦斯伯芗解散,重组
  • 伊戈尔·德米特里耶维奇·谢尔盖耶夫伊戈尔·德米特里耶维奇·谢尔盖耶夫(俄语:Игорь Дмитриевич Сергеев,1938年4月20日-2006年11月10日),苏联和俄罗斯军事将领,俄罗斯联邦元帅,曾任俄罗斯国防
  • 陈焜培陈焜培(1896年-1985年),澳门著名建筑师,原籍新会,出生于澳门。年青时就读于三巴仔圣若瑟书院,毕业后从师于澳门著名的葡国设计师施利华。1919年考入澳门工务厅成为当时最年轻的画则
  • 中国科学院生态环境研究中心中国科学院生态环境研究中心,为中国科学院下属研究机构。成立于1975年,位于北京市海淀区,是以生态环境科学研究为主的国家科研机构。1975年,国务院在原中国科学院化学研究所二部
  • 超级飞侠《超级飞侠》(英语:,港澳译《超级飞侠》,台湾译《Super Wings》,韩语:《출동! 슈퍼윙스》)是韩国、中华人民共和国、美国播出的电视动画影集。《超级飞侠》是奥飞动漫历经三年制作
  • 克拉克默斯县克拉克默斯县(英语:Clackamas County)是位于美国俄勒冈州西北部的一个县。面积4,867平方公里。根据美国2000年人口普查,共有人口338,391。县治俄勒冈市 (Oregon City)。1843年7