2016年3月，Alpha Go Master击败最强的人类围棋选手之一李世石。击败李的版本，在训练过程中使用了大量人类棋手的棋谱。2017年10月19日，DeepMind公司在《自然》杂志发布了一篇新的论文，AlphaGo Zero——它完全不依赖人类棋手的经验，经过3天的训练，Alpha Go Zero击败了Master版本。AlphaGo Zero最重要的价值在于，它不仅仅可以解决围棋问题，它可以在不需要知识预设的情况下，解决一切棋类问题，经过几个小时的训练，已击败最强国际象棋冠军程序Stockfish。其应用场景非常广泛。
AlphaGo Zero 采用了蒙特卡洛树搜索＋深度学习算法，本文将尽可能用简单易懂的语言解释其工作原理。
树搜索
treesearch
从一个棋盘的初始状态，开始思考下一步如何走。我们可以回顾一下我们思考的过程，我们会思考自己可以有哪几种走法，如果我走了这里，对手可能会走哪里，那么我还可以在哪里走。我和对手都会选择最有利的走法，最终价值最大的那一手，就是我要选择的下法。很明显这个思维过程是一颗树，为了寻找最佳的行棋点的过程，就是树搜索。
围棋第一手有361种下法，第二手有360种，第三手有359，依次类推，即一共有 361! 种下法，考虑到存在大量不合规则的棋子分布，合理的棋局约占这个数字的1.2%(Counting Legal Positions in Go). 约为2.081681994 * 10^170。这个一个天文数字，比目前可观测宇宙的所有原子数还要多。要进行完全树搜索，是不可能的。因此我们必须进行剪枝，并限制思考的深度。所谓剪枝，就是指没必要考虑每种下法，我们只需考虑最有价值的几手下法。所谓限制思考的深度，就是我们最多只思考5步，10步，20步。常见的算法是Alpha-beta剪枝算法。但是，剪枝算法也有它的缺陷，它很有可能过早的剪掉了后期价值很大走法。
蒙特卡洛方法
简而言之，蒙特卡洛方法(Monte Carlo method)，是一种“统计模拟方法”。20世纪40年代，为建造核武器，冯.诺伊曼 等人发明了该算法。因赌城蒙特卡洛而得名，暗示其以概率作为算法的基础。
假设我们要计算一个不规则形状的面积，我们只需在包含这个不规则形状的矩形内，随机的掷出一个点，每掷出一个点，则N+1，如果这个点在不规则图形内则W+1。落入不规则图形的概率即为 W/N。当掷出足够多的点之后，我们可以认为：不规则图形面积＝矩形面积＊W/N。
要应用蒙特卡洛算法的问题，首先要将问题转化为概率问题，然后通过统计方法将其问题的解估计出来。
蒙特卡洛树搜索（MCTS）
1987年Bruce Abramson在他的博士论文中提出了基于蒙特卡洛方法的树搜索这一想法。这种算法简而言之是用蒙特卡洛方法估算每一种走法的胜率。如果描述的再具体一些，通过不断的模拟每一种走法，直至终局，该走法的模拟总次数N，与胜局次数W，即可推算出该走法的胜率为 W/N。
该算法的每个循环包含4个步骤：选择、扩展、仿真、反向传播。一图胜千言。
MCTS
图中N表示总模拟次数，W表示胜局次数。每次都选择胜率最大的节点进行模拟。但是这样会导致新节点无法被探索到。为了在最大胜率和新节点探索上保持平衡，UCT（Upper Confidence Bound，上限置信区间算法）被引入。所谓置信区间，就是概率计算结果的可信度。打个比方，如果掷了3次硬币，都是正面朝上，我们就认为掷硬币正面朝上概率是100%，那肯定是错误的，因为我们的样本太少了。所以UCT就是用来修正这个样本太少的问题。具体公式如下：
UCT公式
其中wi 是i节点的胜利次数，ni是i节点的模拟次数，Ni是所有模拟次数，c是探索常数，理论值为 √2，可根据经验调整。公式的后半部分，探索次数越少，值会越大，所以，那些被探索比较少的点，会获得更多的探索机会。
蒙特卡洛树搜索算法因为是直接模拟到游戏终局，所以这种算法更加的准确，而且并不需要一个明确的“估值函数”，你只需要实现游戏机制就足够了。而且，蒙特卡洛算法，可以随时终止，根据其训练的时间给予近似的最优结果。
但是对于围棋这种游戏而言，它的选择点依然太多，这棵树会非常的大。可能有一个分支早已被丢弃，那么它将不会被统计，这可能是李世石能够在第四局击败AlphaGo的主要原因。对于这类情况，我们依然需要依赖一个好的估值函数来辅助。
深度学习
近年来，深度卷积神经网络在视觉领域取得很大的成功，如图片分类，人脸识别等。深度学习的网络结构在此不赘述，简而言之，深度学习是一个最优化算法。
我们可以将深度神经网络理解为一个黑盒，这个黑盒接收一批输入，得到一个输出，并根据输出计算出损失（误差），这个误差会反馈给黑盒，当给了足够多的数据之后，这个黑盒将具备一个特性，就是使误差最小化。
如果这么说还是难以理解的话，可以打个比方：深度神经网络是一种生物，它喜欢吃糖，有学习的能力，你给它看一张图片，它告诉你是猫还是狗，如果它猜对了，你就给它一颗糖，猜错了，就不给糖，久而久之，它就有了分辨猫狗的能力。作为创造者，你甚至不知道它是如何分辨猫狗的，但是它做到了，看得越多，识别的就越准。
这里至关重要的是——输入是什么？输出是什么？什么时候给糖的动作，也就是损失函数如何设计？在实际的操作过程中，网络结构的设计也很重要，这里不再细述。
对于围棋来说，深度网络可以用来评估下一步的主要选点（降低树的宽度），以及评估当前局面的值。
AlphaGo Zero
在AlphaGo Lee版本，有两个神经网络，一个是策略网络，是一个有监督学习，它利用了大量的人类高手的对弈棋局来评估下一步的可能性，另一个是价值网络，用来评价当前局面的评分。而在AlphaGo Zero版本，除了围棋规则外，没有任何背景知识，并且只使用一个神经网络。
这个神经网络以19x19棋盘为输入，以下一步各下法的概率以及胜率为输出，这个网络有多个batch normalization卷积层以及全连接层。
AlphaGo Zero的核心思想是：MCTS算法生成的对弈可以作为神经网络的训练数据。 还记得我们前面说过的深度学习最重要的部分吗？输入、输出、损失！随着MCTS的不断执行，下法概率及胜率会趋于稳定，而深度神经网络的输出也是下法概率和胜率，而两者之差即为损失。随着训练的不断进行，网络对于胜率的下法概率的估算将越来越准确。这意味着什么呢？这意味着，即便某个下法AGZ没有模拟过，但是通过神经网络依然可以达到蒙特卡洛的模拟效果！也就是说，我虽然没下过这手棋，但凭借我在神经网络中训练出的“棋感”，我可以估算出这么走的胜率是多少！
AlphaGo Zero的对弈过程只需应用深度网络计算出的下法概率、胜率、MCTS的置信区间等数据即可进行选点。
AlphaGo Zero 论文节选
AlphaGo Zero增强学习过程
a:自我对弈过程s1，...，sT。 在每个状态st, 使用最近一次的网络fθ，执行一次MCTS αθ （见图2）。 下法根据MCTS计算的搜索概率而选择，at ~ πt. 评价终止状态sT，根据游戏规则来计算胜利者z。
b: AlphaGo Zero的神经网络训练。网络使用原始的棋盘状态st作为输入，通过数个卷积层，使用参数θ，输出有向量 pt, 表示下法的分布概率，以及一个标量vt，表示当前玩家在st的胜率。网络参数θ将自动更新，以最大化策略向量pt和搜索概率πt的相似性，并最小化预测赢家vt与实际赢家z的误差。新参数将应用于下一次自我对弈a的迭代。
AlphaGo Zero 蒙特卡洛树搜索过程
a: 每次模拟选择的分支，有最大Q+U, 其中Q是动作价值，U是上限置信，U依赖于一个存储在分支上的优先概率P和该分支的访问次数N（每访问一次N+1）。
b: 扩展叶节点，神经网络（P(s, .), V(s)) = fθ(s)评估s; 将向量P的值被存储在s的扩展边上。
c: 根据V更新动作价值（action-value)Q，反映所有该动作的子树的平均值。
d: 一旦搜索结束，搜索概率π被返回，与 Ν^(1/τ) 成正比，N是每个分支的访问次数，而τ是一个参数控制着温度（temperature）。
AlphaGo Zero的应用
AGZ算法本质上是一个最优化搜索算法，对于所有开放信息的离散的最优化问题，只要我们可以写出完美的模拟器，就可以应用AGZ算法。所谓开放信息，就像围棋象棋，斗地主不是开放信息，德扑虽然不是开放信息，但本身主要是概率问题，也可以应用。所谓离散问题，下法是一步一步的，变量是一格一格，可以有限枚举的，比如围棋361个点是可以枚举的，而股票、无人驾驶、星际争霸，则不是这类问题。Deepmind要攻克的下一个目标是星际争霸，因为它是不完全信息，连续性操作，没有完美模拟器（随机性），目前在这方面AI还是被人类完虐
所以看到AG打败人类，AGZ打败AG，就认为人工智能要打败人类了，这种观点在未来可能成立，但目前还有点危言耸听。距离真正打败人类，AGZ还差得很远。
作者简介
桂糊涂，多年从事服务端架构工作，2015年开始机器学习相关研究，现任某互联网公司CTO。长期招聘高可用架构、机器学习、Go、node.js、移动端开发等优秀工程师
网友评论