蒙特卡罗树搜索之初学者指南

摘要：介绍蒙特卡罗树搜索由于年作为的一个组成部分引入，令人印象深刻的是其出色的引擎的能力，同时也是的核心组件。蒙特卡罗树搜索主要目的是给出一个状态来选择最佳的下一步。之前蒙特卡罗树搜索产生的一些统计数据可能仍然存在于你正在考虑的新分支中。

摘要： 一直以来，学术界普遍认为在围棋游戏中机器是远不能和人类相比的，它被认为是未来十年内人工智能需要实现的目标之一。令人惊讶的是，在2016年3月由谷歌发明的Alpha Go以4-1击败了韩国的世界冠军。

蒙特卡罗树搜索由RémiCoulom于2006年作为Crazy Stone的一个组成部分引入，令人印象深刻的是其出色的引擎的能力，同时也是Alpha Go / Zero的核心组件。蒙特卡罗树搜索主要目的是：给出一个状态来选择最佳的下一步。我们回顾AlphaGo / Zero，试图解释在Alpha Go中使用了哪些蒙特卡罗树搜索变体。

两人有限零和顺序游戏

在该环境下，蒙特卡罗树搜索内运行的是一个游戏，其本身是一个很抽象、很广义的术语，因此在这里我们专注于单一游戏类型：二人有限零和顺序博弈。把它分解成以下几个部分：

游戏意味着需要处理互动的情况，一些参与者（一个或多个）。

“有限”一词表明，在任何时间点，参与者之间存在有限的交互方式。

两人博弈意味着两个参与者参与了我们的游戏。

连续的，因为参与者交替地移动他们的动作。

最后，零和游戏意味着双方都有相反的目标，换句话说：在游戏的任何终端状态，所有玩家的收益总和等于零。
围棋、象棋或井字棋都是两人有限零和顺序游戏。事实上，有两个人参与，总是有限的动作，并且两个参与者的目标是完全相反的（所有游戏的结果总和为零）。

形式上，游戏由一些基本的数学实体表示。在博弈理论书中，你可以找到以下定义：

定义1.一个广泛的表单游戏由一个元组定义：

从计算机程序员的角度来看，一个正式的定义可能有点混乱。幸运的是，我们可以使用一个众所周知的数据结构来简化表示为：一个游戏树。
游戏树是一个树，其中每一个节点代表游戏的某些状态。从节点到其子节点（如果存在）的转换是一个移动。节点的子节点的数目称为分支因子，树的根节点代表游戏的初始状态。如果游戏树的终端节点没有子节点，游戏就不能继续了。让我们试着描述（部分）看到的井字游戏树：
1.在顶部，你可以看到树的根部，代表井字游戏的初始状态，空白纸板（标记为绿色）。
2.从一个节点到另一个节点的任何转换都表示一个移动。
3.井字游戏的分支因素各不相同- 它取决于树的深度。
4.游戏结束于终端节点（标记为红色）。
游戏树是一个递归数据结构，所以在选择最佳移动后，最终会在子节点中实现，而子节点实际上是其子树的根节点。因此，你可以把一个游戏看作是一个“最佳的下一步”序列的代表，每次都有一个游戏树（不同的根节点）。通常在实践中，你不必记住通往当前状态的路径，因为它不是当前游戏状态中的关注点。

我们的最终目标是在给定游戏状态和游戏树暗示的情况下找到最佳的下一步行动。我们假设在国际象棋中，你知道你的对手是一个业余爱好者，你可以选择简单的策略来欺骗他并迅速获胜。但是，针对强大对手的时候采用相同策略会对你产生不利影响。如果你根本不了解你的对手，那么有一个非常激进的策略叫做minimax，假设你的对手很厉害，那么这个策略可以得到最大化效果。在A和B之间的两人有限零和序贯博弈时，minimax
算法可以用下面的递归公式来描述：

简单地说，假设你的对手试图最大限度地限制你，而你利用minimax算法将会产生最大的回报，这也是minimax算法的由来
。我们需要的只是扩展整个游戏树，并根据递归公式给出的规则来反向传播。

minimax算法的最大弱点是扩展整个游戏树的必要性，对于具有高度分支因素的游戏（如围棋或象棋），它会产生巨大的游戏树并导致失败。

接下来我介绍两种方法，一种方法是将我们的游戏树扩展到一定的阈值深度D。但是，我们不能保证阈值树级别D中的任何节点都是终端。因此，我们需要一个函数来评估一个非终端游戏状态。这对人类来说是很自然的：通过看国际象棋或围棋，即使游戏仍在继续，你也能预测赢家。例如：

克服游戏树大小问题的另一种方法是通过alpha-beta修剪算法修剪游戏树。Alpha-beta修剪算法以minimax方式遍历游戏树，避免某些树枝的扩展。结果最多与minimax相同，但alpha-beta修剪算法通过减少搜索空间来保证改进。

蒙特卡罗树搜索的主要概念是搜索。搜索是一组沿着游戏树的遍历，单次遍历是从根节点（当前游戏状态）到未完全展开的节点的路径。未完全展开的节点意味着至少有一个子节点未被访问，而没有被探索。遇到未完全展开的节点时，其子节点不会选择成为一个根节点。然后将模拟结果反向传播到当前游戏树节点以统计数据。一旦搜索（受时间或计算能力限制）终止，则根据收集的统计信息选择移动。
让我们试着接着上面简单描述的关键问题，以便慢慢理解所有的部分：
1.什么是扩展或不完全扩展的游戏树节点？
2.在搜索过程中，下一个（子）节点如何选择？
3.什么是模拟？
4.什么是反向传播？
5.在扩展的游戏树节点中传播和更新哪些统计数据？
6.最后的移动如何选择？

模拟

我们首先关注模拟，因为它不会严重依赖其他术语的定义。模拟是一种单一的游戏行为，是一系列从当前节点开始，并终止于可计算游戏结果的终端节点的动作序列。模拟是通过在该节点处开始以某种方式随机游戏来计算的游戏树节点评估近似值。在模拟过程中如何选择动作？在模拟过程中，选择一个称为“转出策略”的函数：

它消耗一个游戏状态并产生下一个移动/动作。在实践中，它被设计成能够快速地模拟，默认的转出策略函数是一个统一的随机函数。

最简单形式的模拟只是随机的一系列动作，从给定的游戏状态开始并终止。模拟对于我们所谈论的游戏来说总是会产生一个评估，胜利、失败或平局，通常任何结果都是模拟的合法结果。

给定一个根节点加上游戏规则，我们可以遍历它，而不需要将整个树存储在内存中。在最初的形式中，它根本没有扩展并且处于游戏树的根部，其余节点未被访问。一旦我们考虑到一个动作，就会想象这个动作会产生什么样的结果。
蒙特卡罗树搜索游戏树也有同样的区别。节点被视为访问或未访问，对于要访问的节点意味着如果一个节点的所有子节点都被访问，则节点被认为是完全扩展的，否则它没有完全扩展，但是可能会进一步扩展。

在实践中，一旦搜索开始，所有的根节点都未被访问。如果其中一个被选中，第一个模拟立即开始。请注意，在模拟过程中，由转出策略函数选择的节点不被考虑访问。它们是未经许可的，只有模拟开始的节点被标记为已访问过。

一旦完成了一个叶节点的模拟，其结果已准备好传播回当前的游戏树根节点，然后模拟开始的节点被标记为已访问。

反向传播是从叶节点（模拟开始）到根节点的遍历。模拟结果被传送到根节点，并且对于反向传播路径上的每个节点更新某些统计信息。反向传播保证每个节点的统计数据反映在其所有后代中开始的模拟结果（因为模拟结果被传送到游戏树根节点）。

在搜索的一开始，由于我们还没有开始任何模拟，所以首先选择未访问的节点。单个模拟从根节点开始遍历到叶节点，结果又反向传播到根节点，然后根节点被认为完全展开。

当前的节点标记为蓝色，并且已完全展开，它必须存储其节点统计信息：总体模拟结果和总访问次数。这同样适用于其子节点。

我们现在知道成功实施蒙特卡罗树搜索所需的所有条件，但我们什么时候才能真正结束蒙特卡罗树搜索程序？答案是：它取决于上下文。如果你构建了一个游戏引擎，那么你的“思考时间”可能是有限的，再加上计算机的计算能力也有限制。一旦蒙特卡罗树搜索程序完成，最好的移动通常是访问次数N最多的移动，因为它的估计价值最高（经常被探索）。

在使用蒙特卡罗树搜索选择你的移动后，你所选择的节点将成为你的对手移动的游戏状态。一旦他选择了他的移动，你将再次开始蒙特卡罗树搜索程序。之前蒙特卡罗树搜索产生的一些统计数据可能仍然存在于你正在考虑的新分支中。这带来了重新使用统计数据而不是从头开始构建新树的想法，事实上这也是Alpha Go / Alpha Zero的创建者所做的。

文章标题《Monte Carlo Tree Search – beginners guide》

详细内容请查看原文。