Introduction to Monte Carlo Tree Search （蒙特卡罗搜索树简介）

　部分翻译自“Monte Carlo Tree Search and Its Applications”。

　　论文链接：http://digitalcommons.morris.umn.edu/cgi/viewcontent.cgi?article=1028&context=horizons

　　MCTS 结合了传统 MC 随机采样的方法和树搜索的方法。MC 方法利用重复的随机采样来得到结果。在 MCTS 中，随机采样的过程是在随机模拟的形式中，用来拓展游戏树。该游戏树紧接着别用来决定下一个 move。MCTS 随着游戏树迭代的生长。每一次迭代，game tree 就 traversed 和 expanded。一段时间之后，game tree 就会收敛。这意味着在每次迭代中都 traversed 同一个路径。这表明 MCTS 已经找到了一个 move 可以得到从当前游戏状态下的模拟赢的最多次数。因为这个过程是随机的，所以 MCTS 是一种概率的方法。MCTS 并不能永远都找到最优的 move，但是拥有合理的推理过程，能够使得选择的 move 有很大的机会赢！这就比较牛逼了！

　　1. The Tree Structure

　　MCTS 编码了游戏的状态和其潜在的moves 到这个树当中。树种每一个节点都表示一个潜在的游戏状态，根节点表示当前状态。每一个边表示合法move，使得游戏状态从一个转移到另一个。换句话说，它代表了从父节点到子节点的转移。任何一个节点都有许多孩子节点作为其合法的 move。

　　例如，游戏 TicTacToe 开始的时候，根节点有9个子节点，每一个表示一个可能的移动。后面的子节点也有比上一个少一个选择的子节点，由于上一次的选择已经无法作为当前的选项了。

　　图1 表示一个树的顶端， AI 做出首次移动，所以根节点是第一个游戏板，每一个子节点代表从当前游戏状态所可以选择的潜在的移动。该图是一个简化的版本，此处应该有 9个子节点，而这里只是画出了 3 个。一旦 MCTS 决定选择哪个动作，选中的子节点就变成了新的根节点。扔掉其兄弟姐妹节点。

　　随着游戏状态，每一个节点有一个联系的值，执行那个子树的模拟。每一个节点只执行一次模拟。所以，三个子树就从3次模拟中得到其值。通过选择带有最大预测值的节点， MCTS 算法选择最优可能赢的路径，这意味着 MCTS 算法最大化其能够选择的赢的move 个数。这就是 MCTS 能够有效的主要原因。

　　2. The Four Steps of MCTS

　　蒙特卡罗搜索树可以分为 4 个步骤：selection expansion simulation backpropagation.

　　迭代的执行这4个步骤，直到 AI 做出决定。下图给出了一个示例：

　　第一个数字：代表在这个子树上赢的次数；

　　第二个数字：代表在这个子树上执行模拟的次数。

　　这个比值就提供给我们这个节点的预测值（estimated value）。

　　Selection：

　　在这个过程中， MCTS 算法利用树的策略遍历整个树。一个树策略利用一个 evaluation function 用预测的最大值来优化节点。一旦遍历到一个叶子节点，则需要转成 expansion step。

　　Expansion：

　　添加一个 “？”的叶子节点。这是每次迭代中唯一添加的节点。

　　Simulation：又称 playout 或者 rollout

　　选择操作，直到达到结束状态，或者满足设定的阈值，就停止该操作。然后基于模拟的结果，建立新添加节点的值。

　　Backpropagation：

　　既然已经决定了新添加节点的值，那么剩下的树就要进行更新。从新的节点开始，算法反向遍历回到根节点。在遍历的过程中，存在每一个节点上的模拟的次数都会增加，如果新节点的模拟导致了赢的局面，那么赢的次数也要增加。图2中仅仅值为 0/1 的节点不给更新，由于他们不是新添加节点的祖先。这些操作步骤确保每个节点的值准确的反应了在子树中执行的模拟情况。

　　3. Upper Confidence Bound

　　应用在树上的 upper confidence bound 被用在 MCTS 上（UCT），在遍历树的过程中的选择步骤作为树策略。 UCT 平衡了 exploration 和 exploitation 的思想。

　　exploration approach 促使去探索尚未发现的树的其他领域。这会将倾向于探索树的广度，而不是深度。

　　exploitation approach 倾向于选择拥有最大预测值的路径。这种是属于贪心算法，趋于探索树的深度。

　　UCT 通过给定相对未探索的节点一个 exploration bonus，来平衡 exploration 和 exploitation：　　

　　当遍历树的时候，孩子节点从这个等式返回的最大值将被选中。N 代表在那个节点和其子孙节点上进行模拟的总次数。W 代表多少次这样的模拟才会得到赢的局面。C 代表一个经验得到的 exploration constant。UCT 的第一部分考虑到该节点的估计值占所有模拟的比例。这是 exploitation 部分。第二个部分是 exploration bonus，这个和在父节点和子孙节点执行模拟次数的总数相比。这意味着，该节点模拟次数越小，等式中这部分占得比例越大。

　　另外，可以参考如下博客：

　　1. https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/

　　2. 论文链接：http://digitalcommons.morris.umn.edu/cgi/viewcontent.cgi?article=1028&context=horizons