现在最热的话题莫过于李世石和 AlphaGo 的围棋大战。虽然我也想蹭下这个热点，但我不懂深度学习，不懂强化学习，更不懂围棋的。因此我只能认真看 AlphaGo 的 论文 和田渊栋大牛的 知乎文章 ，写一些简明笔记分享给大家。希望没有什么基础的童鞋也能看懂。

对于这个大热点，新闻媒体自然有自己的解读和分析，比如人工智能多么牛逼，人工智能会/不会威胁人类和深度学习多么牛逼之类的。不过我们更关心技术层面的东西。如果你了解机器学习，知道些 CNN 和搜索，你可能会关心 AlphaGo 是如何把 CNN 接到搜索上的。

alphago

()

AlphaGo 的工作原理

介绍 AlphaGo，就必须说下 AlphaGo 的四个系统组成：

1. 策略网络 CNN模型。输入当前局面，输出19*19个概率值(棋盘是19*19的方格)，对应下一步落子位置的概率。 2. 快速走子 线性模型。目标和策略网络一致。相比策略网络，速度快1000倍但精度低。 3. 价值网络 CNN模型。输入当前局面，输出获胜的概率。 4. 蒙特卡罗树搜索（Monte Carlo Tree Search, MCTS） 把以上三个部分连起来，形成一个完整的系统。

如何把策略网络，估值网络和快速走子三者接到 MCTS 上？博客标题有点标题党了，搜索上接到的可不止是 CNN。首先我们介绍下 MCTS 的递归树状结构，如下所示。

monte carlo tree mcts a tree

树中每一个节点 s 代表了一个围棋盘面，并带有两个数字。一个是访问次数N(s)，另一个质量度Q(s)。访问次数 N(s)表示在搜索中节点被访问的次数。面对一个盘面，MCTS 会进行重复搜索，所以一个节点可能会被反复访问，这个下面细说。质量度Q(s)表示这个节点下 AlphaGo 的优势程度，其计算公式如下所示。

这个公式的意思是：1）对于非叶子节点，质量度等于该节点所有树中已有子节点的质量度均值。2）对于叶子节点，质量度跟价值网络估计的获胜概率(v_{\theta}(s_L))有关，还跟快速走子模拟后续比赛得到的胜负结果(z_L)有关。叶子节点的质量度等于这两者的加权混合，其中混合参数(\lambda)介于0和1之间。

有了 MCTS 的结构，我们就可以继续介绍 MCTS 怎么做搜索的。当李世石落了一子，AlphaGo 迅速读入当前盘面，将之当作搜索的根节点，展开搜索。MCTS 搜索的流程如下图所示，一共分为四个步骤：

monte carlo tree search MCTS

1. 选择 从根节点 R 开始，递归选择某个子节点直到达到叶子节点 L。当在一个节点s，我们怎么选择子节点

s^{*}

呢？我们选择子节点不应该乱选，而是应该选择那些优质的子节点。AlphaGo 中的选择子节点的方式如下所示。 (1)

\begin{eqnarray*} s^{*} &=& argmax_{s_i}(Q(s_i) + u(s_i)) \nonumber \\ u(s_i) &\propto& \frac{P(s_i|s)}{1+N(s_i)} \nonumber \end{eqnarray*}

其中

P(s_i|s)

是策略网络的输出。一个有意思的点在于一个节点被访问次数越多，选择它作为子节点的可能性越小，这是为了搜索多样性考虑。 2. 扩展 如果 L 节点上围棋对弈没有结束，那么可能创建一个节点 C。