MCTS和UCT学习

MCTS定义：（Monte Carlo tree search）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

UCT定义：（Upper Confidence Bound Apply to Tree），即上限置信区间算法，是一种博弈树搜索算法，该算法将蒙特卡洛树搜索(Monte—Carlo Tree Search，MCTS)方法与UCB公式结合，在超大规模博弈树的搜索过程中相对于传统的搜索算法有着时间和空间方面的优势。

定义相同差异对比：UCT 可以被描述为 MCTS 的一个特例：UCT = MCTS + UCB。

历史来历：基于随机抽样的蒙特卡洛方法可以追溯到20世纪40年代（由S.M.乌拉姆和J.冯·诺伊曼在20世纪40年代为研制核武器而首先提出，在这之前，蒙特卡罗方法就已经存在，1777年法国Buffon提出用投针实验的方法求圆周率π，这被认为是蒙特卡罗方法的起源）。布鲁斯·艾布拉姆森（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）。

原理说明：蒙特卡洛树搜索的每个循环包括四个步骤：

• 选择（Selection）：从根结点R开始，选择连续的子结点向下至叶子结点L。后面给出了一种选择子结点的方法，让游戏树向最优的方向扩展，这是蒙特卡洛树搜索的精要所在。

• 扩展（Expansion）：除非任意一方的输赢使得游戏在L结束，否则创建一个或多个子结点并选取其中一个结点C。

• 仿真（Simulation）：在从结点C开始，用随机策略进行游戏，又称为playout或者rollout。

• 反向传播（Backpropagation）：使用随机游戏的结果，更新从C到R的路径上的结点信息。

每一个节点的内容代表胜利次数/游戏次数。

摘自维基百科

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

wi：子节点获胜的次数

ni：子节点参与模拟的次数

Ni：当前节点参与模拟的次数

C：加权系数（为探索参数—理论上等于1.44，在实际中通常可凭经验选择）

蒙特卡洛树搜索通过迭代来一步步地扩展博弈树的规模，UCT 树是不对称生长的，其生长顺序也是不能预知的。它是根据子节点的性能指标导引扩展的方向，这一性能指标便是 UCB 值。它表示在搜索过程中既要充分利用已有的知识，给胜率高的节点更多的机会，又要考虑探索那些暂时胜率不高的兄弟节点，这种对于“利用”（Exploitation）和“探索”（Exploration）进行权衡的关系便体现在 UCT 着法选择函数的定义上， UCB 公式由两部分组成，其中前一部分就是对已有知识的利用，而后一部分则是对未充分模拟节点的探索。C小偏重利用；而 C大则重视探索。需要通过实验设定参数来控制访问节点的次数和扩展节点的阈值。

蒙特卡洛树搜索（MCTS）仅展开根据 UCB 公式所计算过的节点，并且会采用一种自动的方式对性能指标好的节点进行更多的搜索。具体步骤概括如下：

1.由当前局面建立根节点，生成根节点的全部子节点，分别进行模拟对局；

2.从根节点开始，进行最佳优先搜索；

3.利用 UCB 公式计算每个子节点的 UCB 值，选择最大值的子节点；

4.若此节点不是叶节点，则以此节点作为根节点，重复 2；

5.直到遇到叶节点，如果叶节点未曾经被模拟对局过，对这个叶节点模拟对局；否则为这个叶节点随机生成子节点，并进行模拟对局；

6.将模拟对局的收益（一般胜为 1 负为 0）按对应颜色更新该节点及各级祖先节点，同时增加该节点以上所有节点的访问次数；

7.回到 2，除非此轮搜索时间结束或者达到预设循环次数；

8.从当前局面的子节点中挑选平均收益最高的给出最佳着法。

由此可见 UCT 算法就是在设定的时间内不断完成从根节点按照 UCB 的指引最终走到某一个叶节点的过程。而算法的基本流程包括了选择好的分支（Selection）、在叶子节点上扩展一层（Expansion）、模拟对局（Simulation）和结果回馈（Backpropagation）这样四个部分。

UCT 树搜索还有一个显著优点就是可以随时结束搜索并返回结果，在每一时刻，对 UCT 树来说都有一个相对最优的结果。