AlphaGo 是如何把 CNN 接到搜索的？

原文链接：AlgorithmDog

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

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

AlphaGo 的工作原理

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

1. 策略网络
CNN模型。输入当前局面，输出19*19个概率值(棋盘是19*19的方格)，对应下一步落子位置的概率。

2. 快速走子
线性模型。目标和策略网络一致。相比策略网络，速度快1000倍但精度低。

3. 价值网络
CNN模型。输入当前局面，输出获胜的概率。

4. 蒙特卡罗树搜索（Monte Carlo Tree Search, MCTS）
把以上三个部分连起来，形成一个完整的系统。

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

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

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

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

1. 选择
从根节点 R 开始，递归选择某个子节点直到达到叶子节点 L。当在一个节点s，我们怎么选择子节点  s∗  呢？我们选择子节点不应该乱选，而是应该选择那些优质的子节点。AlphaGo 中的选择子节点的方式如下所示。

s∗u(si)=∝argmaxsi(Q(si)+u(si))P(si|s)1+N(si)

其中 P(si|s) 是策略网络的输出。一个有意思的点在于一个节点被访问次数越多，选择它作为子节点的可能性越小，这是为了搜索多样性考虑。

2. 扩展
如果 L 节点上围棋对弈没有结束，那么可能创建一个节点 C。

3. 模拟
用价值网络和快速走子计算节点 C 的质量度。

4. 反向传播
根据 C 的质量度，更新它爸爸爷爷祖先的质量度。

      上述搜索步骤反复进行，直到达到某个终止条件。搜索结束后，MCTS 选择根节点的质量度最高的子节点作为 AlphaGo 的着法。从上面描述来看，策略网络、快速走子和价值网络主要用于减少搜索宽度和减少搜索深度两个方面。策略网络用于使得搜索朝着几个恰当的候选集中，从而减少了搜索宽度。价值网络和快速走子用在评估叶子节点质量度上，使得搜索就不用继续往下搜索，从而减少了搜索的深度。

策略网络，快速走子和估值网络的训练

      AlphaGo 将策略网络，估值网络和快速走子三者在蒙特卡罗搜索树框架下构成的一个系统。这三者的效果和效率就很关键。那么 DeepMind 是怎么训练这三者呢?

      1.策略网络的训练

      策略网络就是一个深层的 CNN 模型。策略网络输入是棋局，输出是19*19个概率值(棋盘是19*19的方格)，对应下一步落子位置的概率。其实 AlphaGo 一共训练了两个策略网络：有监督学习策略网络 (Supervised Learning network, SL network) 和强化学习策略网络 (Reinforcement Learning network, RL network)。SL network 用的人类棋谱做训练数据。田渊栋的知乎文章评论有 SL network，“这种做法一点也没有做搜索，但是大局观非常强，不会陷入局部战斗中，说它建模了‘棋感’一点也没有错”，“当然，只用走棋网络问题也很多，就我们在DarkForest上看到的来说，会不顾大小无谓争劫，会无谓脱先，不顾局部死活，对杀出错，等等。有点像高手不经认真思考的随手棋”。

      训练好 SL network 之后，然后使用强化学习进行自我对局进一步更新参数，从而得到 RL network 。RL network 是 SL network 的加强，能力得到了很大提高。据论文报告的结果，RL network 对 SL network 的胜率达到了 80%。不过 AlphaGo 搜索使用的是 SL network, 理由是 SL network 着法比较多样。

      2.快速走子的训练

      论文里说局部特征匹配（local pattern matching）加逻辑回归（logistic
regression）的方法。局部特征匹配就是一些匹配局部形势的特征，比如周围有多少个敌方棋子，有多少个我方棋子。训练数据是人类棋谱。但论文没有太看重这一块。

      3.价值网络的训练

      价值网络也是一个深层的 CNN 模型，输入棋局，输出获胜的概率。价值网络的训练有意思的是训练数据的选择。从人类棋谱里，我们能整理出棋局-胜负对应关系。但如果用人类棋谱，数据量好像不是很够，训练直接过拟合了。论文中报告的结果，如果用人类棋谱，价值网络的训练误差为0.19而测试误差达到了0.37。因此作者们用的是 RL network 自我对弈的3000万棋局作为训练数据，价值网络的训练误差为0.226而测试误差达到了0.234。

      AlphaGo 各个模块的训练流程可以用论文中的一张图表示。

再说点啥

      田渊栋的文章总结说到：“总的来说，这整篇文章是一个系统性的工作，而不是一两个小点有了突破就能达到的胜利。在成功背后，是作者们，特别是两位第一作者 David Silver 和 Aja Huang，在博士阶段及毕业以后五年以上的积累，非一朝一夕所能完成的。他们能做出 AlphaGo 并享有现在的荣誉，是实至名归的”。向大牛们致敬！

      另外，祈祷崔永元不要谈人工智能。