蒙特卡罗树搜索（MCTS）

蒙特卡罗树搜索（MCTS）

一种基于树结构的，在搜索空间巨大时仍有效的方法（区别于极大极小搜索和Alpha-Beta搜索）

1.思想：

• 将搜索树集中在更值得搜索的分枝上，如果某个着法不错，蒙特卡罗树会将其拓展的很深，反之就不去拓展。

2.优点

• 蒙特卡罗树搜索结合了广度优先搜索和深度优先搜索，故该方法在搜索空间很大时，仍能找到最优解。
• 蒙特卡罗树搜索利用其快速走多子模拟可以进行一个近似的局面评估。

3.原理

• 蒙特卡罗树搜索通过蒙特卡洛抽样方法逐步建立和拓展博弈树，在树内一般采用贪心算法，书外采用随机策略。
• 由于结合了随机模拟的一般性和博弈树搜索的准确性，使得更有可能成为最优着法的分枝获得更多的搜索机会，在有限的时间内使用有限的资源提高搜索的准确率。

4.构建

• 蒙特卡罗树搜索将当前待评估局面作为根节点开始不断构建搜索树。中间节点包含被访问频次和当前局面的估值信息两部分。

5.步骤

1. 选择：从根节点开始根据树内搜索策略递归到叶子结点，选择不是游戏结果且存在未走过的后续着法的叶子；
2. 扩展：将一个没试过的着法0/0加入博弈树中；
3. 模拟：通过蒙特卡罗方法随机生成博弈双方的合理动作，并得到一个确定的结果；
4. 回溯：将模拟估值得到的结果从叶子开始层层回溯到父节点，并调整父节点估值；
5. 在规定的时间或搜索次数内重复1-4步。随着输的不断生长和回溯，可以在足够长的时间后收敛到最优解。

6.改进

1. 改进方法：引入UCB替换选择阶段的树内搜索，形成UCT（基于博弈树的上限置信区间算法）
2. 改进优势：区别于非好即坏，改进后的每个节点既考虑利用（深搜）又考虑探索（广搜）
3. UCT原理：在选择一个父节点n的子节点时，计算出各个子节点ni的评估值ri，如果父节点在max层，则树内选择策略会选择评估值最大的子节点；如果父节点在min层，则树内选择策略会选择评估值最小的子节点。Ti：子节点ni的访问次数，Vi：ni的估值，c：手工设定的常数（c越大越偏向于广搜，越小越偏向于深搜）

注明：图中样例代入公式的结果为小编自己算的结果，同书中的0.62c答案不一致，故仅供参考。欢迎感兴趣的朋友为小编指点小编的运算漏洞

写在最后

本文是小编对于博弈强化学习这一部分知识体系在学习的过程中结合书中内容和自己的理解写的学习笔记，如内容有误，请大家谅解并指出，感谢您的阅读！