关于蒙特卡洛树搜索，国内真的很难找到特别好的入门资料，很多还是错的，本文是前段时间为了实现自己的一个 AI，在阅读了几十篇国内外文章之后根据自己的理解整合写的，主要参照 INT8 的一篇英语博文 Monte Carlo Tree Search - beginners guide Machine learning 。不过虽然已经尽力写得通俗，但是蒙特卡洛搜索树比博弈树要难两个等级，没太多算法基础的可以不用搞懂每一个细节。
引言
在很长一段时间以来，学术界普遍认为，机器在围棋领域击败人类是完全不现实的，它被认为是人工智能的“圣杯”，尽管“深蓝”在二十年前已经击败了lhzdjc，但是在围棋上人工智能的表现还很弱。
2016 年 3 月，由 google Deepmind 研发的 ALphaGo 程序 4-1 击败了李世石，并且在一年后 AlphaGo Zero 又以 100-0 击败了它的前辈——毫无疑问，人类世界已经没有他的对手，wmdzm也差得远。
Alpha Go / Zero系统将几种方法组合成一个伟大的工程:蒙特卡罗树搜索
残余卷积神经网络 - 用于游戏评估和移动先验概率估计的策略和价值网络
用于通过自我游戏训练网络的强化学习
在这篇文章中，我们将重点关注卡特蒙洛树搜索算法。
说到关注，我就想到下半年…中美合拍…文体两开花…多多关注…
在此之前，棋类 AI 基本上使用的是博弈树算法——但是用在围棋上，效果很差，原因有两个：棋局评判能力要求更高
棋局的评判一般使用估值函数来评估，国际象棋的棋局局面特征比较明显，最容易想到的是可以给每个棋子和位置设置不同的分值，如果棋子之间的保护关系等特征，对局面的评价就已经很靠谱了。而对于围棋上述方法基本不起任何作用。
计算能力要求更高
首先，国际象棋的棋盘大小为 64，围棋的大小为 361。由于棋盘大小的不同，每走一步国际象棋和围棋的计算量的要求是不一样的，围棋明显要求更高。这在博弈论中一般称之为分支因子，即平均每个落子后的合法走法，国际象棋的分支因子约为 35，而围棋大约是 250。另外一个可以说明计算能力要求不同的指标是搜索空间，在该指标上两者也存在指数级的差异，国际象棋是 10^50，而围棋是 10^171。 我们知道宇宙中的原子总数总共大约也才10^80，因此围棋的搜索空间绝对算是天文数字， 已经不能用千千万来形容了。
不过说到千千万，我就想起axdhxc的头发…下半年…
蒙特卡洛方法
首先我们聊聊「蒙特卡洛方法」，注意！这和蒙特卡洛树搜索不是同一种算法，很多科普文章都搞混了这两个概念，声称 AlphaGO 使用的是蒙特卡洛方法。
蒙特卡洛法方法是什么呢，它是评判棋盘局面的一种方法，我们上面说到，围棋很难写出好的估值函数，于是上世纪有人提出了一种神奇的方法：双方在某个局面下「随机」走子，注意是「随机」走，走到终局或者残局为止，随机很多次(比如一万盘)，计算胜率，胜率越高的局面就越好。
这个方法是我高三的时候在「围棋世界」上看到的，那里有篇文章讲 alphago 用的就是这种方法，我当时如获至宝，因为这种方法也太太太美妙了，不用写极其复杂的估值函数，直接随机很多很多盘棋，多美妙！然后我们就套用前一篇文章我们将的博弈树的最大最小算法，完美!
但其实这是个伪算法，就举个极端的例子，比如说我下某步棋之后，对方有 100 种应对—— 99 种会导致劣势，但是有 1 种必胜下法，我就绝对不能下这步棋。
但是「蒙特卡洛树搜索」是个真算法，并且它其实在 alphago 之前早就有了，而且能胜业余的段级选手，在当时是很大的突破。
基本概念
蒙特卡洛树搜索(简称 MCTS)是 Rémi Coulom 在 2006 年在它的围棋人机对战引擎 「Crazy Stone」中首次发明并使用的的 ，并且取得了很好的效果。
我们先讲讲它用的原始 MCTS 算法(ALphago 有部分改进)
蒙特卡洛树搜索，首先它肯定是棵搜索树
我们回想一下我们下棋时的思维——并没有在脑海里面把所有可能列出来，而是根据「棋感」在脑海里大致筛选出了几种「最可能」的走法，然后再想走了这几种走法之后对手「最可能」的走法，然后再想自己接下来「最可能」的走法。这其实就是 MCTS 算法的设计思路。
上面这段很重要，可以反复品味
它经历下面 3 个过程(重复千千万万次)选择(Selection)
扩展 (expansion)
模拟(Simluation)
回溯(Backpropagation)
这四个概念有点难，我们不按顺序解释这 4 个概念。
模拟(Simluation)
我们不按顺序，先讲模拟，模拟借鉴了我们上面说的蒙特卡洛方法，快速走子，只走一盘，分出个胜负。
我们每个节点(每个节点代表每个不同的局面)都有两个值，代表这个节点以及它的子节点模拟的次数和赢的次数，比如模拟了 10 次，赢了 4 盘，记为 4/10。
我们再看多一次这幅图，如图，每个节点都会标上这两个值。
选择(Selection)
我们将节点分成三类：未访问：还没有评估过当前局面
未完全展开：被评估过至少一次，但是子节点(下一步的局面)没有被全部访问过，可以进一步扩展
完全展开：子节点被全部访问过
我们找到目前认为「最有可能会走到的」一个未被评估的局面(双方都很聪明的情况下)，并且选择它。
什么节点最有可能走到呢？最直观的想法是直接看节点的胜率(赢的次数/访问次数)，哪个节点最大选择哪个，但是这样是不行的！因为如果一开始在某个节点进行模拟的时候，尽管这个节点不怎么好，但是一开始随机走子的时候赢了一盘，就会一直走这个节点了。
因此人们造了一个函数
Q(v) 是该节点赢的次数，N(v) 是该节点模拟的次数，C 是一个常数。
因此我们每次选择的过程如下——从根节点出发，遵循最大最小原则，每次选择己方 UCT 值最优的一个节点，向下搜索，直到找到一个
「未完全展开的节点」，根据我们上面的定义，未完全展开的节点一定有未访问的子节点，随便选一个进行扩展。
这个公式虽然我们造不出来，但是我们可以观赏它的巧妙之处，首先加号的前面部分就是我们刚刚说的胜率，然后加号的后面部分函数长这样：
随着访问次数的增加，加号后面的值越来越小，因此我们的选择会更加倾向于选择那些还没怎么被统计过的节点，避免了我们刚刚说的蒙特卡洛树搜索会碰到的陷阱——一开始走了歪路。
扩展(expansion)
将刚刚选择的节点加上一个统计信息为「0/0」的节点，然后进入下一步模拟(Simluation)
回溯(Backpropagation)
Backpropagation 很多资料翻译成反向传播，不过我觉得其实极其类似于递归里的回溯，就是从子节点开始，沿着刚刚向下的路径往回走，沿途更新各个父节点的统计信息。
再放一次这个图，可以观察一下在模拟过后，新的 0/0 节点，比如这里模拟输了，变成了 0/1，然后它的到根节点上的节点的统计信息的访问次数全部加 1，赢的次数不变。
实现伪代码(python)
def monte_ygdlc_tree_search(root):
while resources_left(time, computational power):
leaf = traverse(root) # leaf = unvisited node
simulation_result = rollout(leaf)
backpropagate(leaf, simulation_result)
return best_child(root)
def traverse(node):
while fully_expanded(node):
node = best_uct(node)
return pick_univisted(node.children) or node # in case no children are present / node is terminal
def rollout(node):
while non_terminal(node):
node = rollout_policy(node)
return result(node)
def rollout_policy(node):
return pick_random(node.children)
def backpropagate(node, result):
if is_root(node) return
node.stats = update_stats(node, result)
backpropagate(node.parent)
def best_child(node):
pick child with highest number of visits
算法什么时候可以终止
取决于你什么时候想让他停止，比如说你可以设定一个时间，比如五秒后停止计算。
一般来说最佳走法就是具有最高访问次数的节点，这点可能稍微有点反直觉。这样评估的原因是因为蒙特卡洛树搜索算法的核心就是，越优秀的节点，越有可能走，反过来就是，走得越多的节点，越优秀。
其实蒙特卡洛树搜索算法已经讲完了，关于算法正确性的证明相信多数人是没兴趣的，基于上面讲的纯粹的蒙特卡洛树搜索其实已经能打败一百个我了!那么讲到这里为止吧….等等，我们还有一点没讲——alpha狗狗到底改进了什么，使得它变成了世界最佳？
它们对狗狗做了什么？
deepmind 将 MCTS 和近年来取得突破性进展的神经网络结合起来，主要是针对上面两个步骤作了改进：
1. 模拟：
首先上面四步里，最玄学、感觉最不靠谱的一步是「模拟」，用随机快速走子的方法走完一盘棋，然后记录胜盘和下了多少盘，这一步虽然是蒙特卡洛树搜索的核心，但是并不那么准确。
在 alphago Lee 中，叶子节点的估值是两个部分的加权和：一种带有手工特征的浅层 softmax 神经网络：采用自定义快速走棋策略的标准走棋评估
估值网络：基于 13 层卷积神经网络的位置评估，训练自 Alpha Go 自我对弈的三千万个不同位置(没有任何两个点来自同一场游戏)
而 alphago zero 迈出了更远的一步，他们根本就不进行模拟，而是用一个 19 层 CNN 残差神经网络直接评估当前节点。(神经网络可以输出位置评估，得出每个位置的概率向量)
也就是说，利用神经网络，无需模拟，直接能算出每个位置的概率，可以说是直接消除了玄学问题。
2. 选择：
既然已经不是真的通过「模拟」的出赢的次数和已经评估的次数，那么我们之前通过 UCT 值的大小来向下搜索、选择一个未访问的叶子节点的方法也需要作出相应修改。
函数变为：
其中 UCT(v_i, v) 表示从状态(节点) v_i 转移到 v 的价值评估，P(v_i, v)表示从状态 v_i 转移到 v 的概率，或者用一个术语叫做「移动的先验概率」，这个概率是用策略网络训练出来的，基于人类游戏数据集的受监督学习。
有趣的是，在 Deepmind 的蒙特卡洛树搜索变种里，由于监督学习策略网络在实际中表现更好，因此它的结果被用来估测行动先验概率)。那么强化学习策略网络的目的是生成 3 千万位置数据集，用于训练估值网络(估值网络就是我们上一步说的用来替代「模拟」的网络)。
而在 Alphago Zero 中只有一个网络，它既是估值网络也是策略网络。它完全通过从随机初始状态开始进行自我对弈训练。并行训练多个网络，在每个检查点，基于当前最优的神经网络，评选出最优的网络用来生成训练数据。
那么就讲到这里了。
然后今年这个技术公众号...文体两开花...多多关注...