本文内容来源：知乎日报

试论DeepMind 研发的围棋 AI AlphaGo 系统是如何下棋的——

19 年前计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，现在计算机又要来攻克围棋了吗！？

虚竹在天龙八部里自填一子，无意中以“自杀”破解“珍笼”棋局，逍遥子方才亲传掌门之位。难道以后“阿尔法狗”要出任逍遥派掌门了？

1933 年，东渡日本 19 岁的吴清源迎战当时的日本棋坛霸主、已经 60 岁的本因坊秀哉，开局三招即是日本人从未见过的三三、星、天元布阵，快速进击逼得对方连连暂停“打卦”和弟子商量应对之策。随后以“新布局”开创棋坛新纪元。难道阿尔法狗会再造一个“新新布局”？

作为一个关心人工智能和人类命运的理科生，近些天刷了好些报道，记者们说“阿尔法狗是个‘价值神经网络’和‘策略神经网’络综合蒙特卡洛搜索树的程序”，但我觉得光知道这些概念是不够的。我想看看“阿尔法狗”的庐山真面目。

准备好棋盘和脑容量，一起来探索吧？

围棋棋盘是 19x19 路，所以一共是 361 个交叉点，每个交叉点有三种状态，可以用 1 表示黑子，-1 表示白字，0 表示无子，考虑到每个位置还可能有落子的时间、这个位置的气等其他信息，我们可以用一个 361 * n 维的向量来表示一个棋盘的状态。我们把一个棋盘状态向量记为 s。

当状态 s 下，我们暂时不考虑无法落子的地方，可供下一步落子的空间也是 361 个。我们把下一步的落子的行动也用 361 维的向量来表示，记为 a。

这样，设计一个围棋人工智能的程序，就转换成为了，任意给定一个 s 状态，寻找最好的应对策略 a，让你的程序按照这个策略走，最后获得棋盘上最大的地盘。

如果你想要设计一个特别牛逼惊世骇俗的围棋程序，你会从哪里开始呢？对于在谷歌 DeepMind 工作的黄士杰和他的小伙伴而言，第一招是：

“深度卷积神经网络”

深度卷积神经网络早在 98 年就攻克了手写数字识别，近些年在人脸识别、图像分类、天气预报等领域无往而不利，接连达到或超过人类的水平，是深度学习火遍大江南北的急先锋。我们现在看到的 Picasa 照片自动分类，Facebook 照片识别好友，以及彩云天气高精度天气预报（软广出现，不要打我）都是此技术的应用。这等天赐宝物，如果可以用来下围棋，岂不是狂拽酷炫吊炸天？

所以 2015 年黄士杰发表在 ICLR 的论文[3]一上来就使出了“深度神经网络”的杀招，从网上的围棋对战平台 KGS（外国的 qq 游戏大厅）可以获得人类选手的围棋对弈的棋局。观察这些棋局，每一个状态 s，都会有一个人类做出的落子 a，这不是天然的训练样本<s,a>吗？如此可以得到 3000 万个样本。我们再把 s 看做一个 19x19 的二维图像（具体是 19x19 x n，n 是表示一些其他 feature），输入一个卷积神经网络进行分类，分类的目标就是落子向量 a’，不断训练网络，尽可能让计算机得到的 a’接近人类高手的落子结果 a，不就得到了一个模拟人类棋手下围棋的神经网络了吗？

于是我们得到了一个可以模拟人类棋手的策略函数 P_human，给定某个棋局状态 s，它可以计算出人类选手可能在棋盘上落子的概率分布 a = P_human(s)，如下图：

红圈就是 P_human 觉得最好的落子方案。每一步都选择概率最高的落子，对方对子后再重新计算一遍，如此往复就可以得到一个棋风类似人类的围棋程序。

这个基于“狂拽酷炫”深度学习的方案棋力如何呢？

不咋地。黄士杰说 P_human 已经可以和业余 6 段左右的人类选手过招，互有胜负，但还未能超过当时最强的电脑程序 CrazyStone[1,5]，距离人类顶尖玩家就差得更远了。

所以，为求更进一步，黄士杰打算把 P_human 和 CrazyStone 的算法结合一下，师夷长技以制夷，先击败所有的其他围棋 AI 再说。

等等，CrazyStone 的算法是什么？

哦，那个算法是黄士杰的老师 Remi Coulum 在 2006 年对围棋 AI 做出的另一个重大突破：

“MCTS，蒙特卡洛搜索树”

蒙特卡洛搜索树（Monte-Carlo Tree Search）是一种“大智若愚”的方法。面对一个空白棋盘 S0，黄士杰的老师 Coulum 最初对围棋一无所知，便假设所有落子方法分值都相等，设为 1。然后扔了一个骰子，从 361 种落子方法中随机选择一个走法 a0。Coulum 想象自己落子之后，棋盘状态变成 S1，然后继续假设对手也和自己一样二逼，对方也扔了一个筛子，随便瞎走了一步，这时棋盘状态变成 S2，于是这两个二逼青年一直扔骰子下棋，一路走到 Sn，最后肯定也能分出一个胜负 r，赢了就 r 记为 1，输了则为 0，假设这第一次 r=1。这样 Coulum 便算是在心中模拟了完整的一盘围棋。

Coulum 心想，这样随机扔骰子也能赢？运气不错啊，那把刚才那个落子方法（S0,a0）记下来，分值提高一些：

新分数= 初始分 + r
我刚才从（S0, a0）开始模拟赢了一次，r=1，那么新分数=2，除了第一步，后面几步运气也不错，那我把这些随机出的局面所对应落子方法(Si,ai)的分数都设为 2 吧。然后 Coulum 开始做第二次模拟，这次扔骰子的时候 Coulum 对围棋已经不是一无所知了，但也知道的不是太多，所以这次除（S0, a0）的分值是 2 之外，其他落子方法的分数还是 1。再次选择 a0 的概率要比其他方法高一点点。

那位假想中的二逼对手也用同样的方法更新了自己的新分数，他会选择一个 a1 作为应对。如法炮制，Coulum 又和想象中的对手又下了一盘稍微不那么二逼的棋，结果他又赢了，Coulum 于是继续调整他的模拟路径上相应的分数，把它们都 +1。随着想象中的棋局下得越来越多，那些看起来不错的落子方案的分数就会越来越高，而这些落子方案越是有前途，就会被更多的选中进行推演，于是最有“前途”的落子方法就会“涌现”出来。

最后，Coulum 在想象中下完 10 万盘棋之后，选择他推演过次数最多的那个方案落子，而这时，Coulum 才真正下了第一步棋。

蒙特卡洛搜索树华丽转身为相当深刻的方法，可以看到它有两个很有意思的特点：

1）没有任何人工的 feature，完全依靠规则本身，通过不断想象自对弈来提高能力。这和深蓝战胜卡斯帕罗夫完全不同，深蓝包含了很多人工设计的规则。MCTS 靠的是一种类似遗传算法的自我进化，让靠谱的方法自我涌现出来。让我想起了卡尔文在《大脑如何思维》中说的思维的达尔文主义[6]。

2）MCTS 可以连续运行，在对手思考对策的同时自己也可以思考对策。Coulum 下完第一步之后，完全不必要停下，可以继续进行想象中的对弈，直到对手落子。Coulum 随后从对手落子之后的状态开始计算，但是之前的想象中的对弈完全可以保留，因为对手的落子完全可能出现在之前想象中的对弈中，所以之前的计算是有用的。这就像人在进行对弈的时候，可以不断思考，不会因为等待对手行动而中断。这一点 Coulum 的程序非常像人，酷毙了。

但黄士杰很快意识到他老师的程序仍然有局限：初始策略太简单。我们需要更高效地扔骰子。

如何更高效的扔骰子呢？

用 P_human()来扔。

黄士杰改进了 MCTS，一上来不再是二逼青年随机掷骰子，而是先根据 P_human 的计算结果来得到 a 可能的概率分布，以这个概率来挑选下一步的动作。一次棋局下完之后，新分数按照如下方式更新：

新分数= 调整后的初始分 + 通过模拟得到的赢棋概率
如果某一步被随机到很多次，就应该主要依据模拟得到的概率而非 P_human。

所以 P_human 的初始分会被打个折扣：

调整后的初始分= P_human/（被随机到的次数 + 1）
这样就既可以用 P_human 快速定位比较好的落子方案，又给了其他位置一定的概率。看起来很美，然后实际操作中却发现：“然并卵”。因为，P_human()计算太慢了。

一次 P_human()计算需要 3ms，相对于原来随机扔骰子不到 1us，慢了 3000 倍。如果不能快速模拟对局，就找不到妙招，棋力就不能提高。所以，黄士杰训练了一个简化版的 P_human_fast()，把神经网络层数、输入特征都减少，耗时下降到了 2us，基本满足了要求。先以 P_human()来开局，走前面大概 20 多步，后面再使用 P_human_fast()快速走到最后。兼顾了准确度和效率。

这样便综合了深度神经网络和 MCTS 两种方案，此时黄士杰的围棋程序已经可以战胜所有其他电脑，虽然距离人类职业选手仍有不小的差距，但他在 2015 年那篇论文的最后部分信心满满的表示：“我们围棋软件所使用的神经网络和蒙特卡洛方法都可以随着训练集的增长和计算力的加强（比如增加 CPU 数）而同步增强，我们正前进在正确的道路上。”

看样子，下一步的突破很快就将到来。同年 2 月，黄士杰在 Deepmind 的同事在顶级学术期刊 nature 上发表了“用神经网络打游戏”的文章[2]。这篇神作，为进一步提高 MCTS 的棋力，指明了前进的新方向：

“左右互搏，自我进化”

红白机很多人小时候都玩过，你能都打通吗？黄士杰的同事通过“强化学习”方法训练的程序在类似红白机的游戏机上打通了 200 多个游戏，大多数得分都比人类还好。

“强化学习”是一类机器学习方法，Agent 通过和环境 s 的交互，选择下一步的动作 a，这个动作会影响环境 s，给 Agent 一个 reward，Agent 然后继续和环境交互。游戏结束的时候，Agent 得到一个最后总分 r。这时我们把之前的环境状态 s、动作 a 匹配起来就得到了一系列<s,a>，设定目标为最后的总得分 r，我们可以训练一个神经网络去拟合在状态 s 下，做动作 a 的总得分。下一次玩游戏的时候，我们就可以根据当前状态 s，去选择最后总得分最大的动作 a。通过不断玩游戏，我们对<s,a>下总得分的估计就会越来越准确，游戏也玩儿得越来越好。

打砖块游戏有一个秘诀：把球打到墙的后面去，球就会自己反弹得分。强化学习的程序在玩了 600 盘以后，学到这个秘诀：球快要把墙打穿的时候评价函数 v 的分值就会急剧上升。

黄士杰考虑给围棋也设计一个评价函数 v(s)，在 P_human()想象自己开局走了 20 多步之后，不需要搜索到底，如果有一个 v(s)可以直接判断是否能赢，得到最后的结果 r，这样肯定能进一步增加 MCTS 的威力。

黄士杰已经有了国外的 qq 游戏大厅 KGS 上的对局，但是很遗憾这些对局数量不够，不足以得到局面评价函数 v。但是没关系，我们还可以左右互搏自对弈创造新的对局。

机器学习的开山鼻祖 Samuel 早在 1967 年就用自对弈的方法来学习国际跳棋[7]，而之前的蒙特卡洛搜索树也是一个自对弈的过程。但是现在黄士杰不仅有一个从人类对弈中学习出的 P_human 这样一个高起点，而且有一个神经网络可以从对弈样本中学习，有理由相信这次会有更好的结果。

先用 P_human 和 P_human 对弈，比如 1 万局，就得到了一万个新棋谱，加入到训练集当中，训练出 P_human_1。然后再让 P_human_1 和 P_human_1 对局，得到另外一万个新棋谱，这样可以训练出 P_human_2，如此往复，可以得到 P_human_n。P_human_n 得到了最多的训练，棋力理应比原来更强。我们给最后这个策略起一个新名字：P_human_plus。这时，再让 P_human_plus 和 P_human 对局，在不用任何搜索的情况下胜率可达 80%，不加任何搜索策略的 P_human_plus 和开源的 MCTS 相比也有 85% 的胜率。自对弈方法奏效了。

既然 P_human_plus 这么强，我们先代入到 MCTS 中试试，用 P_human_plus 来开局，剩下的用 P_human_fast。可惜，这样的方法棋力反而不如用 P_human。黄士杰认为是因为 P_human_plus 走棋的路数太集中，而 MCTS 需要发散出更多的选择才好。看来，P_human_plus 练功还是太死板，还没有进入无招胜有招的境界。

没关系，黄士杰还有局面评价函数 v(s)这一招，有了 v(s)，如果我可以一眼就看到“黑棋大势已去”，我就不用 MCTS 在想象中自我对弈了。但考虑到 P_human_plus 的招法太过集中，黄士杰在训练 v( )的时候，开局还是先用 P_human 走 L 步，这样有利于生成更多局面。黄士杰觉得局面还不够多样化，为了进一步扩大搜索空间，在 L+1 步的时候，干脆完全随机掷一次骰子，记下这个状态 SL+1，然后后面再用 P_human_plus 来对弈，直到结束获得结果 r。如此不断对弈，由于 L 也是一个随机数，我们就得到了开局、中盘、官子不同阶段的很多局面 s，和这些局面对应的结果 r。有了这些训练样本<s,r>，还是使用神经网络，把最后一层的目标改成回归而非分类，黄士杰就可以得到一个 v( )函数，输出赢棋的概率。

v( )可以给出下一步落子在棋盘上任意位置之后，如果双方都使用 P_human_plus 来走棋，我方赢棋的概率。如果训练 v()的时候全部都使用 P_human 不用 P_human_plus 呢？实验表明基于 P_human_plus 训练的 v，比基于 P_human 训练的 v’，棋力更强。强化学习确实有效。

万事俱备，只欠东风。准备好 P_human()，MCTS，以及评价函数 v()，黄士杰和小伙伴们继续进击，向着可以和人类专业选手过招的围棋 AI 前进：

“阿尔法狗”


黄士杰准备在 MCTS 框架之上融合局面评估函数 v()。这次还是用 P_human 作为初始分开局，每局选择分数最高的方案落子，下到第 L 步之后，改用 P_human_fast 把剩下的棋局走完，同时调用 v(SL)，评估局面的获胜概率。然后按照如下规则更新整个树的分数：

新分数= 调整后的初始分 + 0.5 * 通过模拟得到的赢棋概率 + 0.5 * 局面评估分
前两项和原来一样，如果待更新的节点就是叶子节点，那局面评估分就是 v(SL)。如果是待更新的节点是上级节点，局面评估分是该节点所有叶子节点 v()的平均值。

如果 v()表示大局观，“P_human_fast 模拟对局”表示快速验算，那么上面的方法就是大局观和快速模拟验算并重。如果你不服，非要做一个 0.5: 0.5 之外的权重，黄士杰团队已经实验了目前的程序对阵其他权重有 95% 的胜率。

以上，便是阿尔法狗的庐山真面目。

上图演示了阿尔法狗和樊麾对弈时的计算过程，阿尔法狗执黑，红圈是阿尔法狗实际落子的地方。1、2、3 和后面的数字表示他想象中的之后双方下一步落子的地方。白色方框是樊麾的实际落子。在复盘时，樊麾觉得位置 1 的走法更好。

深度学习、蒙特卡洛搜索树，自我进化三招齐出，所有其他围棋 ai 都毫无还手之力。99% 的胜率不说，“阿尔法狗”还可以在让四子的情况下以 77% 的胜率击败 crazystone。“阿尔法狗”利用超过 170 个 GPU，粗略估算超过 800 万核并行计算，不仅有前期训练过程中模仿人类，自我对弈不断进化，还有实战时的模拟对局可以实时进化，已经把现有方法发挥到了极限，是目前人工智能领域绝对的巅峰之作。

后记

围棋是 NP-hard 问题，如果用一个原子来存储围棋可能的状态，把全宇宙的原子加起来都不够储存所有的状态。于是我们把这样的问题转换为寻找一个函数 P，当状态为 S 时，计算最优的落子方案 a = P(s)。我们看到，无论是“狂拽酷炫”的深度学习，还是“大智若愚”的 MCTS，都是对 P(s)的越来越精确的估计，但即使引入了“左右互搏”来强化学习，黄士杰和团队仍然做了大量的细节工作。所以只有一步一个脚印，面对挑战不断拆解，用耐心与细心，还有辛勤的汗水，才能取得一点又一点的进步，而这些进步积累在一起，终于让计算机达到并超过了人类职业选手的水平。

因为一盘棋走一步需要 3ms（P_human_plus 遍历整个棋盘的时间），谷歌用大规模集群进行并行化计算，自我对弈 3000 万盘棋生成训练集只需要一天左右的时间[4]，所以如果对弈更多棋局可以提高棋力的话，黄士杰他们早就做了。目前的方案可能已经达到了 CNN 网络能力的极限。完整的阿尔法狗不仅需要生成训练集，还要用训练集来生成局面评估函数 v()，而这还使用了两周时间，一局比赛需要花掉 4 个小时，自我对局速度不够快，这也许是阿尔法狗并没有能够完全使用强化学习，而仅仅是在整个过程的一小部分使用左右互搏的原因。左右互博用的还不够多，这是一个遗憾。

如果存在一个“围棋之神”，一个已经穷尽了所有的围棋步法的“上帝”，那他每一步都是最优应对。一些顶尖棋手在接受采访时表示[8]，“围棋之神”对战人类选手可能还有让 4 子的空间，也就是说，就算下赢了人类，计算机也还有很大进步的空间。

面对一个如此高难度的问题，计算机和人类都无法在有限时间内找到完全的规律（柯洁和李世乭比赛是一人有 3 小时时间思考，阿尔法狗今年 3 月和李世乭进行的比赛则是每人 2 小时）。计算机和人都是在对问题做抽象，然后搜索最佳策略。要下好围棋所需要的能力已经接近人类智力的极限：要有大局观、要懂得取舍、还要会精打细算，治理一个国家也不过如此。计算机可以学会围棋，就能学会很多一样难度的技能。在未来，也许围棋、自动驾驶、同声传译都会被一一攻克。甚至在数论、量子场论等领域，深度学习和搜索相结合，可能也会带给我们更多惊喜，比如攻克“哥德巴赫猜想”。

那么，人工智能是否真的会很快登顶呢？

虽然在智力方面 AI 有希望登峰造极，但高智商只是人类众多能力的一个方面。吴清源先生在方寸之间纵横无敌，但仍然漂泊一生，被命运推着前进。早年他做段祺瑞的门客，棋盘上把段祺瑞打的落花流水，弄得下人都没有早饭吃；后来东渡日本，三易国籍，留下许多遗憾。如果把“强人工智能”比作一个天才少年，虽然智商爆表，但其他方面还需要我们悉心加以引导。创造出“德才兼备，匡扶济世”的人工智能，才是我辈真正应该努力实现的目标。

一起加油吧，科学少年们！

To the infinity and beyond !

参考文献：

1, EfficientSelectivity and Backup Operators in Monte-Carlo Tree Search

2, Human-level control through deep reinforcementlearning

3, Move Evaluation In GO Using Deep Convolutional Neural Networks

4. Masteringthe Game of Go with Deep Neural Networks and Tree Search

5. A Survey ofMonte Carlo Tree Search Methods

6. 大脑如何思维—智力演化的今昔

7. Some Studies in Machine LearningUsing the Game of Checkers.II-Recent Progress

8.围棋之神存在的话，可以让你几子？

本文内容来源：知乎日报

试论DeepMind 研发的围棋 AI AlphaGo 系统是如何下棋的——

19 年前计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，现在计算机又要来攻克围棋了吗！？

虚竹在天龙八部里自填一子，无意中以“自杀”破解“珍笼”棋局，逍遥子方才亲传掌门之位。难道以后“阿尔法狗”要出任逍遥派掌门了？

1933 年，东渡日本 19 岁的吴清源迎战当时的日本棋坛霸主、已经 60 岁的本因坊秀哉，开局三招即是日本人从未见过的三三、星、天元布阵，快速进击逼得对方连连暂停“打卦”和弟子商量应对之策。随后以“新布局”开创棋坛新纪元。难道阿尔法狗会再造一个“新新布局”？

作为一个关心人工智能和人类命运的理科生，近些天刷了好些报道，记者们说“阿尔法狗是个‘价值神经网络’和‘策略神经网’络综合蒙特卡洛搜索树的程序”，但我觉得光知道这些概念是不够的。我想看看“阿尔法狗”的庐山真面目。

准备好棋盘和脑容量，一起来探索吧？

围棋棋盘是 19x19 路，所以一共是 361 个交叉点，每个交叉点有三种状态，可以用 1 表示黑子，-1 表示白字，0 表示无子，考虑到每个位置还可能有落子的时间、这个位置的气等其他信息，我们可以用一个 361 * n 维的向量来表示一个棋盘的状态。我们把一个棋盘状态向量记为 s。

当状态 s 下，我们暂时不考虑无法落子的地方，可供下一步落子的空间也是 361 个。我们把下一步的落子的行动也用 361 维的向量来表示，记为 a。

这样，设计一个围棋人工智能的程序，就转换成为了，任意给定一个 s 状态，寻找最好的应对策略 a，让你的程序按照这个策略走，最后获得棋盘上最大的地盘。

如果你想要设计一个特别牛逼惊世骇俗的围棋程序，你会从哪里开始呢？对于在谷歌 DeepMind 工作的黄士杰和他的小伙伴而言，第一招是：

“深度卷积神经网络”

深度卷积神经网络早在 98 年就攻克了手写数字识别，近些年在人脸识别、图像分类、天气预报等领域无往而不利，接连达到或超过人类的水平，是深度学习火遍大江南北的急先锋。我们现在看到的 Picasa 照片自动分类，Facebook 照片识别好友，以及彩云天气高精度天气预报（软广出现，不要打我）都是此技术的应用。这等天赐宝物，如果可以用来下围棋，岂不是狂拽酷炫吊炸天？

所以 2015 年黄士杰发表在 ICLR 的论文[3]一上来就使出了“深度神经网络”的杀招，从网上的围棋对战平台 KGS（外国的 qq 游戏大厅）可以获得人类选手的围棋对弈的棋局。观察这些棋局，每一个状态 s，都会有一个人类做出的落子 a，这不是天然的训练样本<s,a>吗？如此可以得到 3000 万个样本。我们再把 s 看做一个 19x19 的二维图像（具体是 19x19 x n，n 是表示一些其他 feature），输入一个卷积神经网络进行分类，分类的目标就是落子向量 a’，不断训练网络，尽可能让计算机得到的 a’接近人类高手的落子结果 a，不就得到了一个模拟人类棋手下围棋的神经网络了吗？

于是我们得到了一个可以模拟人类棋手的策略函数 P_human，给定某个棋局状态 s，它可以计算出人类选手可能在棋盘上落子的概率分布 a = P_human(s)，如下图：

红圈就是 P_human 觉得最好的落子方案。每一步都选择概率最高的落子，对方对子后再重新计算一遍，如此往复就可以得到一个棋风类似人类的围棋程序。

这个基于“狂拽酷炫”深度学习的方案棋力如何呢？

不咋地。黄士杰说 P_human 已经可以和业余 6 段左右的人类选手过招，互有胜负，但还未能超过当时最强的电脑程序 CrazyStone[1,5]，距离人类顶尖玩家就差得更远了。

所以，为求更进一步，黄士杰打算把 P_human 和 CrazyStone 的算法结合一下，师夷长技以制夷，先击败所有的其他围棋 AI 再说。

等等，CrazyStone 的算法是什么？

哦，那个算法是黄士杰的老师 Remi Coulum 在 2006 年对围棋 AI 做出的另一个重大突破：

“MCTS，蒙特卡洛搜索树”

蒙特卡洛搜索树（Monte-Carlo Tree Search）是一种“大智若愚”的方法。面对一个空白棋盘 S0，黄士杰的老师 Coulum 最初对围棋一无所知，便假设所有落子方法分值都相等，设为 1。然后扔了一个骰子，从 361 种落子方法中随机选择一个走法 a0。Coulum 想象自己落子之后，棋盘状态变成 S1，然后继续假设对手也和自己一样二逼，对方也扔了一个筛子，随便瞎走了一步，这时棋盘状态变成 S2，于是这两个二逼青年一直扔骰子下棋，一路走到 Sn，最后肯定也能分出一个胜负 r，赢了就 r 记为 1，输了则为 0，假设这第一次 r=1。这样 Coulum 便算是在心中模拟了完整的一盘围棋。

Coulum 心想，这样随机扔骰子也能赢？运气不错啊，那把刚才那个落子方法（S0,a0）记下来，分值提高一些：

新分数= 初始分 + r
我刚才从（S0, a0）开始模拟赢了一次，r=1，那么新分数=2，除了第一步，后面几步运气也不错，那我把这些随机出的局面所对应落子方法(Si,ai)的分数都设为 2 吧。然后 Coulum 开始做第二次模拟，这次扔骰子的时候 Coulum 对围棋已经不是一无所知了，但也知道的不是太多，所以这次除（S0, a0）的分值是 2 之外，其他落子方法的分数还是 1。再次选择 a0 的概率要比其他方法高一点点。

那位假想中的二逼对手也用同样的方法更新了自己的新分数，他会选择一个 a1 作为应对。如法炮制，Coulum 又和想象中的对手又下了一盘稍微不那么二逼的棋，结果他又赢了，Coulum 于是继续调整他的模拟路径上相应的分数，把它们都 +1。随着想象中的棋局下得越来越多，那些看起来不错的落子方案的分数就会越来越高，而这些落子方案越是有前途，就会被更多的选中进行推演，于是最有“前途”的落子方法就会“涌现”出来。

最后，Coulum 在想象中下完 10 万盘棋之后，选择他推演过次数最多的那个方案落子，而这时，Coulum 才真正下了第一步棋。

蒙特卡洛搜索树华丽转身为相当深刻的方法，可以看到它有两个很有意思的特点：

1）没有任何人工的 feature，完全依靠规则本身，通过不断想象自对弈来提高能力。这和深蓝战胜卡斯帕罗夫完全不同，深蓝包含了很多人工设计的规则。MCTS 靠的是一种类似遗传算法的自我进化，让靠谱的方法自我涌现出来。让我想起了卡尔文在《大脑如何思维》中说的思维的达尔文主义[6]。

2）MCTS 可以连续运行，在对手思考对策的同时自己也可以思考对策。Coulum 下完第一步之后，完全不必要停下，可以继续进行想象中的对弈，直到对手落子。Coulum 随后从对手落子之后的状态开始计算，但是之前的想象中的对弈完全可以保留，因为对手的落子完全可能出现在之前想象中的对弈中，所以之前的计算是有用的。这就像人在进行对弈的时候，可以不断思考，不会因为等待对手行动而中断。这一点 Coulum 的程序非常像人，酷毙了。

但黄士杰很快意识到他老师的程序仍然有局限：初始策略太简单。我们需要更高效地扔骰子。

如何更高效的扔骰子呢？

用 P_human()来扔。

黄士杰改进了 MCTS，一上来不再是二逼青年随机掷骰子，而是先根据 P_human 的计算结果来得到 a 可能的概率分布，以这个概率来挑选下一步的动作。一次棋局下完之后，新分数按照如下方式更新：

新分数= 调整后的初始分 + 通过模拟得到的赢棋概率
如果某一步被随机到很多次，就应该主要依据模拟得到的概率而非 P_human。

所以 P_human 的初始分会被打个折扣：

调整后的初始分= P_human/（被随机到的次数 + 1）
这样就既可以用 P_human 快速定位比较好的落子方案，又给了其他位置一定的概率。看起来很美，然后实际操作中却发现：“然并卵”。因为，P_human()计算太慢了。

一次 P_human()计算需要 3ms，相对于原来随机扔骰子不到 1us，慢了 3000 倍。如果不能快速模拟对局，就找不到妙招，棋力就不能提高。所以，黄士杰训练了一个简化版的 P_human_fast()，把神经网络层数、输入特征都减少，耗时下降到了 2us，基本满足了要求。先以 P_human()来开局，走前面大概 20 多步，后面再使用 P_human_fast()快速走到最后。兼顾了准确度和效率。

这样便综合了深度神经网络和 MCTS 两种方案，此时黄士杰的围棋程序已经可以战胜所有其他电脑，虽然距离人类职业选手仍有不小的差距，但他在 2015 年那篇论文的最后部分信心满满的表示：“我们围棋软件所使用的神经网络和蒙特卡洛方法都可以随着训练集的增长和计算力的加强（比如增加 CPU 数）而同步增强，我们正前进在正确的道路上。”

看样子，下一步的突破很快就将到来。同年 2 月，黄士杰在 Deepmind 的同事在顶级学术期刊 nature 上发表了“用神经网络打游戏”的文章[2]。这篇神作，为进一步提高 MCTS 的棋力，指明了前进的新方向：

“左右互搏，自我进化”

红白机很多人小时候都玩过，你能都打通吗？黄士杰的同事通过“强化学习”方法训练的程序在类似红白机的游戏机上打通了 200 多个游戏，大多数得分都比人类还好。

“强化学习”是一类机器学习方法，Agent 通过和环境 s 的交互，选择下一步的动作 a，这个动作会影响环境 s，给 Agent 一个 reward，Agent 然后继续和环境交互。游戏结束的时候，Agent 得到一个最后总分 r。这时我们把之前的环境状态 s、动作 a 匹配起来就得到了一系列<s,a>，设定目标为最后的总得分 r，我们可以训练一个神经网络去拟合在状态 s 下，做动作 a 的总得分。下一次玩游戏的时候，我们就可以根据当前状态 s，去选择最后总得分最大的动作 a。通过不断玩游戏，我们对<s,a>下总得分的估计就会越来越准确，游戏也玩儿得越来越好。

打砖块游戏有一个秘诀：把球打到墙的后面去，球就会自己反弹得分。强化学习的程序在玩了 600 盘以后，学到这个秘诀：球快要把墙打穿的时候评价函数 v 的分值就会急剧上升。

黄士杰考虑给围棋也设计一个评价函数 v(s)，在 P_human()想象自己开局走了 20 多步之后，不需要搜索到底，如果有一个 v(s)可以直接判断是否能赢，得到最后的结果 r，这样肯定能进一步增加 MCTS 的威力。

黄士杰已经有了国外的 qq 游戏大厅 KGS 上的对局，但是很遗憾这些对局数量不够，不足以得到局面评价函数 v。但是没关系，我们还可以左右互搏自对弈创造新的对局。

机器学习的开山鼻祖 Samuel 早在 1967 年就用自对弈的方法来学习国际跳棋[7]，而之前的蒙特卡洛搜索树也是一个自对弈的过程。但是现在黄士杰不仅有一个从人类对弈中学习出的 P_human 这样一个高起点，而且有一个神经网络可以从对弈样本中学习，有理由相信这次会有更好的结果。

先用 P_human 和 P_human 对弈，比如 1 万局，就得到了一万个新棋谱，加入到训练集当中，训练出 P_human_1。然后再让 P_human_1 和 P_human_1 对局，得到另外一万个新棋谱，这样可以训练出 P_human_2，如此往复，可以得到 P_human_n。P_human_n 得到了最多的训练，棋力理应比原来更强。我们给最后这个策略起一个新名字：P_human_plus。这时，再让 P_human_plus 和 P_human 对局，在不用任何搜索的情况下胜率可达 80%，不加任何搜索策略的 P_human_plus 和开源的 MCTS 相比也有 85% 的胜率。自对弈方法奏效了。

既然 P_human_plus 这么强，我们先代入到 MCTS 中试试，用 P_human_plus 来开局，剩下的用 P_human_fast。可惜，这样的方法棋力反而不如用 P_human。黄士杰认为是因为 P_human_plus 走棋的路数太集中，而 MCTS 需要发散出更多的选择才好。看来，P_human_plus 练功还是太死板，还没有进入无招胜有招的境界。

没关系，黄士杰还有局面评价函数 v(s)这一招，有了 v(s)，如果我可以一眼就看到“黑棋大势已去”，我就不用 MCTS 在想象中自我对弈了。但考虑到 P_human_plus 的招法太过集中，黄士杰在训练 v( )的时候，开局还是先用 P_human 走 L 步，这样有利于生成更多局面。黄士杰觉得局面还不够多样化，为了进一步扩大搜索空间，在 L+1 步的时候，干脆完全随机掷一次骰子，记下这个状态 SL+1，然后后面再用 P_human_plus 来对弈，直到结束获得结果 r。如此不断对弈，由于 L 也是一个随机数，我们就得到了开局、中盘、官子不同阶段的很多局面 s，和这些局面对应的结果 r。有了这些训练样本<s,r>，还是使用神经网络，把最后一层的目标改成回归而非分类，黄士杰就可以得到一个 v( )函数，输出赢棋的概率。

v( )可以给出下一步落子在棋盘上任意位置之后，如果双方都使用 P_human_plus 来走棋，我方赢棋的概率。如果训练 v()的时候全部都使用 P_human 不用 P_human_plus 呢？实验表明基于 P_human_plus 训练的 v，比基于 P_human 训练的 v’，棋力更强。强化学习确实有效。

万事俱备，只欠东风。准备好 P_human()，MCTS，以及评价函数 v()，黄士杰和小伙伴们继续进击，向着可以和人类专业选手过招的围棋 AI 前进：

“阿尔法狗”


黄士杰准备在 MCTS 框架之上融合局面评估函数 v()。这次还是用 P_human 作为初始分开局，每局选择分数最高的方案落子，下到第 L 步之后，改用 P_human_fast 把剩下的棋局走完，同时调用 v(SL)，评估局面的获胜概率。然后按照如下规则更新整个树的分数：

新分数= 调整后的初始分 + 0.5 * 通过模拟得到的赢棋概率 + 0.5 * 局面评估分
前两项和原来一样，如果待更新的节点就是叶子节点，那局面评估分就是 v(SL)。如果是待更新的节点是上级节点，局面评估分是该节点所有叶子节点 v()的平均值。

如果 v()表示大局观，“P_human_fast 模拟对局”表示快速验算，那么上面的方法就是大局观和快速模拟验算并重。如果你不服，非要做一个 0.5: 0.5 之外的权重，黄士杰团队已经实验了目前的程序对阵其他权重有 95% 的胜率。

以上，便是阿尔法狗的庐山真面目。

上图演示了阿尔法狗和樊麾对弈时的计算过程，阿尔法狗执黑，红圈是阿尔法狗实际落子的地方。1、2、3 和后面的数字表示他想象中的之后双方下一步落子的地方。白色方框是樊麾的实际落子。在复盘时，樊麾觉得位置 1 的走法更好。

深度学习、蒙特卡洛搜索树，自我进化三招齐出，所有其他围棋 ai 都毫无还手之力。99% 的胜率不说，“阿尔法狗”还可以在让四子的情况下以 77% 的胜率击败 crazystone。“阿尔法狗”利用超过 170 个 GPU，粗略估算超过 800 万核并行计算，不仅有前期训练过程中模仿人类，自我对弈不断进化，还有实战时的模拟对局可以实时进化，已经把现有方法发挥到了极限，是目前人工智能领域绝对的巅峰之作。

后记

围棋是 NP-hard 问题，如果用一个原子来存储围棋可能的状态，把全宇宙的原子加起来都不够储存所有的状态。于是我们把这样的问题转换为寻找一个函数 P，当状态为 S 时，计算最优的落子方案 a = P(s)。我们看到，无论是“狂拽酷炫”的深度学习，还是“大智若愚”的 MCTS，都是对 P(s)的越来越精确的估计，但即使引入了“左右互搏”来强化学习，黄士杰和团队仍然做了大量的细节工作。所以只有一步一个脚印，面对挑战不断拆解，用耐心与细心，还有辛勤的汗水，才能取得一点又一点的进步，而这些进步积累在一起，终于让计算机达到并超过了人类职业选手的水平。

因为一盘棋走一步需要 3ms（P_human_plus 遍历整个棋盘的时间），谷歌用大规模集群进行并行化计算，自我对弈 3000 万盘棋生成训练集只需要一天左右的时间[4]，所以如果对弈更多棋局可以提高棋力的话，黄士杰他们早就做了。目前的方案可能已经达到了 CNN 网络能力的极限。完整的阿尔法狗不仅需要生成训练集，还要用训练集来生成局面评估函数 v()，而这还使用了两周时间，一局比赛需要花掉 4 个小时，自我对局速度不够快，这也许是阿尔法狗并没有能够完全使用强化学习，而仅仅是在整个过程的一小部分使用左右互搏的原因。左右互博用的还不够多，这是一个遗憾。

如果存在一个“围棋之神”，一个已经穷尽了所有的围棋步法的“上帝”，那他每一步都是最优应对。一些顶尖棋手在接受采访时表示[8]，“围棋之神”对战人类选手可能还有让 4 子的空间，也就是说，就算下赢了人类，计算机也还有很大进步的空间。

面对一个如此高难度的问题，计算机和人类都无法在有限时间内找到完全的规律（柯洁和李世乭比赛是一人有 3 小时时间思考，阿尔法狗今年 3 月和李世乭进行的比赛则是每人 2 小时）。计算机和人都是在对问题做抽象，然后搜索最佳策略。要下好围棋所需要的能力已经接近人类智力的极限：要有大局观、要懂得取舍、还要会精打细算，治理一个国家也不过如此。计算机可以学会围棋，就能学会很多一样难度的技能。在未来，也许围棋、自动驾驶、同声传译都会被一一攻克。甚至在数论、量子场论等领域，深度学习和搜索相结合，可能也会带给我们更多惊喜，比如攻克“哥德巴赫猜想”。

那么，人工智能是否真的会很快登顶呢？

虽然在智力方面 AI 有希望登峰造极，但高智商只是人类众多能力的一个方面。吴清源先生在方寸之间纵横无敌，但仍然漂泊一生，被命运推着前进。早年他做段祺瑞的门客，棋盘上把段祺瑞打的落花流水，弄得下人都没有早饭吃；后来东渡日本，三易国籍，留下许多遗憾。如果把“强人工智能”比作一个天才少年，虽然智商爆表，但其他方面还需要我们悉心加以引导。创造出“德才兼备，匡扶济世”的人工智能，才是我辈真正应该努力实现的目标。

一起加油吧，科学少年们！

To the infinity and beyond !

参考文献：

1, EfficientSelectivity and Backup Operators in Monte-Carlo Tree Search

2, Human-level control through deep reinforcementlearning

3, Move Evaluation In GO Using Deep Convolutional Neural Networks

4. Masteringthe Game of Go with Deep Neural Networks and Tree Search

5. A Survey ofMonte Carlo Tree Search Methods

6. 大脑如何思维—智力演化的今昔

7. Some Studies in Machine LearningUsing the Game of Checkers.II-Recent Progress

8.围棋之神存在的话，可以让你几子？

精彩评论

今天看到这篇文章，有一种豁然开朗的感觉。这篇文章alpah狗的原理深入浅出的分成几个阶段
1、利用蒙特卡洛搜索树，通过自己模拟剪枝，进行计算，这种算法的缺点在于围棋下一步的可能性太多太深，所以就这样算，机器难以在有限时间内得出最优解（NP-hard）
2、深度卷积算法
利用人类以往的对局来判断在某些场景下，每个选点的可能性，这样可以大大减少蒙特卡洛搜索树的复杂度（因为可能性很低的就不算了，狗狗对李世石的第四盘就是这情况，狗狗认为李世石下那个地方的可能性只有万分之一，所以先剪掉了......）
3、但由于2的运算时间很长，所以狗狗团队优化了深度卷积算法（计算机的同学应该知道，这里有大量工作），使得性能和以前随机运算没有太大差别
4、不停修正评分策略
5、自己和自己下，自我进化（为什么会进化，其实和人类推算复盘是一样的，遍历的分支越多，评分就越准确，就越能通过“直觉”得到局部最优解）
简而言之，狗狗就是一个在人类围棋大师基础上，快速验证纠错进步的智能软件

上周master在网上联系击败人类高手60次，高晓松先生惊叹“围棋的道路已经走完”，然后新科应氏杯冠军唐韦星先生激烈地反驳，认为棋道并没有完，高晓松先生是在危言耸听。作为一个臭棋篓子，本不好说什么棋道，但是纵观近代围棋发展的历史，那些伟大的名字，
过百龄，范西屏，道策，秀策，秀荣，吴清源，木谷实，武宫正树等等，都在围棋上不停突破原来的定式和思想，寻找所谓的“神之一手”（给定局面下面的最佳应对），真正的求道家，往往勇于挑战自己的极限（例如新布局运动）。所以围棋根本就没有完，因为按照目前的原理，距离真正的神之一手肯定还有很长距离
a、人类的模型本身就不是最强，所以初始值还有优化空间
b、机器的运算速度，剪枝效率还可以优化
但是就分先对弈来说，人类的顶尖棋手不敌ai这个其实是很正常（现在有那个高人敢说自己一年下来的天气预报都比超级计算机准吗），但是如果想更逼近神之一手的话，棋界完全可以抛下胜负，共同研究，有深刻棋理积累的棋士，更有助计算机进行初始化和剪支进化，也就更容易逼近围棋手的最高目标，寻找“神之一手”
所以，围棋并没有完，棋道（我这里只是粗浅地理解成寻找神之一手的工作）也可以继续，只是在前行的道路上，有机器相助