蒙特卡洛树搜索入门教程 _蒙特卡洛树

本文是对 Monte Carlo Tree Search – beginners guide 这篇文章的文章大体翻译，以及对其代码的解释。
1 引言蒙特卡洛树搜索在2006年被Rémi Coulom第一次提出，应用于Crazy Stone的围棋游戏。

Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search

蒙特卡洛树搜索大概的思想就是给定一个游戏状态，去选择一个最佳的策略/动作。
1.1 有限双人零和序贯博弈蒙特卡洛树搜索实际上是一个应用非常广泛的博弈框架，这里我们将其应用于有限双人序贯零和博弈问题中。像围棋、象棋、Tic-Tac-Toe都是有限双人序贯零和博弈游戏。
1.2 怎样去表示一个游戏?我们采用博弈树 (Game Tree)来表示一个游戏：每个结点都代表一个状态 (state)，从一个结点 (node)移动一步，将会到达它的子节点 (children node) 。子节点的个数叫作分支因子 (branching factor) 。根节点 (Root node)表示初始状态(initial state) 。终止节点 (terminal nodes)没有子节点了。
在 tic-tac-toe 游戏中表示如下图所示：

文章插图

每次都是从初始状态、树的根结点开始。在 tic-tac-toe 游戏里面初始状态就是一张空的棋盘。
从一个节点转移到另一个节点叫作一个 move 。
分支因子 (branching factor)，tic-tac-toe 中树越深，分支因子也越少，也就是 children node 的数量越少。
游戏结束表示终止节点。
从根节点到终止节点一次表示一个单个游戏 playout。

你不需要关系你是怎么来到这个 node，只需要做好之后的事情就好了。
1.3 最佳策略是什么？minimax和alpha-beta剪枝我们希望找到的就是最佳策略 ( the most promising next move ) 。如果你知道对手的策略那你可以争对这个策略求解，但是大多数情况下是不知道对手的策略的，所以我们需要用 minimax 的方法，假设你的对手是非常机智的，每次他都会采取最佳策略。
假设A与B博弈，A期望最大化自己的收益，因为是零和博弈，所以B期望A的收益最小，Minimax算法可描述为如下形式：

和是玩家和的效益函数。
move 表示从当前状态和采取的动作转移到下一个状态。
eval 评估最终的游戏分数。
是最终的游戏状态。

简单地说，就是给定一个状态期望找到一个动作在对手最小化你的奖励的同时找到一个最大化自己的奖励。
Minimax 算法最大的弱点就是需要扩展整棵树，对于高分支因子的游戏，像围棋、象棋这种，算法就很难处理。
对于上述问题的一种解决方法就是扩展树结构到一定的阈值深度( expand our game tree only up to certain threshold depth d ) 。因此我们需要一个评估函数，评估非终止节点。这对于我们人类来说依据当前棋势判断谁输谁赢是很容易做到的。计算机的解决方法可以参考原文中的：

Chess position evaluation with convolutional neural network in Julia

另一种解决树扩展太大的方法就是 alpha-beta剪枝算法。它会避免一些分支的展开，它最好的结果就是与minimax算法效果相同，因为它减少了搜索空间。
2 蒙特卡洛树搜索(MCTS)基本概念蒙特卡洛通过多次模拟仿真，预测出最佳策略。最核心的东西就是搜索。搜索是对整棵博弈树的组合遍历，单次的遍历是从根结点开始，到一个未完全展开的节点(a node that is not full expanded) 。未完全展开的意思就是它至少有一个孩子节点未被访问，或者称作未被探索过。当遇到未被完全展开过的节点，选择它的一个未被访问的childre node做根结点，进行一次模拟(a single playout/simulation) 。仿真的结果反向传播(propagated back)用于更新当前树的根结点,并更新博弈树节点的统计信息。当整棵博弈树搜索结束后，就相当于拿到了这颗博弈树的策略。
我们再理解一下以下几个关键概念：