AlphaGo对战李世石谁能赢？两万字长文深挖围棋AI技术（一）

李理，出门问问NLP工程师

编者按：李世石与Google Deepmind AlphaGo对战在即，围棋界和人工智能界对结果各有预测，但对于程序员来说，了解AlphaGo的技术路线可能更有意思。本文来自出门问问NLP工程师李理，详细解读了AlphaGo背后的MCTS的工作原理及其对围棋AI的贡献，深度学习包括DCNN在围棋AI领域的发展（包括Facebook darkfmcts），以及二者在AlphaGo系统中的具体协作。文章还结合作者本人的经历对围棋算法与中国象棋算法的差异进行了比较。

本文原标题：AlphaGo的棋局，与人工智能有关，与人生无关

前言：人生如棋

回顾一下我的人生，似乎和棋是有一些关联的。

1997年中考后的暑假在姑父公司的机房第一次接触电脑，当时应该是80386的微机。学习电脑就是学习DOS命令和打字，完全不懂干什么用的，打字尤其是五笔字型，更是学得头疼——王旁青头戋五一，土士二干十寸雨……唯一的乐趣就是趁姑父不在的时候键入CCH，和电脑下一盘象棋（本文象棋特指中国象棋，如果是国际象棋不会简称象棋）。这个软件的棋力挺强的，至少对于我这样业余水平来说是这样的。总共下来估计有一二十盘，我赢的次数也只有一两盘，其余的都是输了。我第一步一般走中炮，电脑第一步总是走马，而当第二步我上马的时候，电脑不是走常见的屏风马，而是起横车，另外一侧的马都不动。从棋理的角度说，这种布局是有问题的，中路很空虚。但是我却找不到什么破绽，原因可能是中局计算能力相差太远。

当时就觉得挺神奇的，电脑竟然会下棋，而且还这么厉害，心想我以后能不能做一个比它还厉害的软件。

同年，IBM的深蓝击败了国际象棋世界冠军卡斯帕罗夫，不过我知道这个消息应该是在读大学之后了。

2000年，由于高三最后半年沉迷于电脑游戏，高考考得不好，而且还想离家远一点去闯荡，就去了北京科技大学。阴差阳错地选择了电子信息工程专业。这个专业在我之前只有两届学生，课程设计挺混乱的，有一部分电子系的课程，如数电模电等，也有部分通信的课程，如信号与系统。但是我对这些课程都不感兴趣，自学了很多计算机的课程。

大概是在2003年的时候在书店看到了王小春写的《PC游戏编程–人机博弈》，如获至宝，学着写过一个黑白棋的软件。也改过光盘里附带源码的象棋程序，不过发现要写一个超过自己水平的象棋并不容易。

2006年考研，填报的是计算机系的人工智能实验室，不过分数不够高，后来调剂到了智能系的听觉实验室，做自然语言处理方向。

同年，MCTS第一次被提出并在围棋上却得极大的突破；而Hinton通过DBN让深度神经网络重新进入人们的视野。不过当时NLP还不流行Deep Learning，当时更多的还是structured SVM、CRFs和Graphical Model。当时还打印过《Learning CRFs with Hierarchical Features: An Application to Go》这篇论文。

2016年，Google DeepMind的文章被Nature发表，AlphaGo击败欧洲冠军樊麾并且将要在3月份挑战李世石。

围棋和深度学习再次大规模高热度地出现在世人眼前。

象棋与围棋的比较

俗与雅

如果你在公园或家门口看到一群人围成一团，围观的比下棋的还多，并且出谋划策指手画脚，那一定是象棋。同样在路边摊上摆“祖传”残局的也一定是象棋。围棋则“高雅”的多，所以琴棋书画里的棋必然是围棋。象棋下得好，也只能在民间摆摆路边摊。而围棋专门有个官职叫“棋待诏”，陪皇帝下棋的。当然伴君如伴虎，陪皇帝下棋可没有与路边的大爷下棋轻松，赢了皇帝肯定不行，但老是输或者输得太假了也不行。要像贾玄那样让皇帝每次都觉得自己棋差一着，可不是简单的事情。喜欢下围棋的皇帝很多，比如传说中“一子定乾坤”的李世民，《西游记》里魏征梦斩泾河龙王时也是在和李世民下棋。即使围棋下不到国手的水平能陪皇帝下棋，还是有很多达官贵人也附庸风雅的。比如《红楼梦》里的贾政老爷，那么无趣的人，也是要下下围棋的，因此很多詹光这样的门客。贾府四位大小姐的丫鬟是琴棋书画，迎春的丫鬟是司棋，按说迎春下棋应该很厉害，不过在书中并没有写迎春下棋，倒是写惜春和妙玉下棋，惜春在角上被倒脱靴。另外探春和宝琴下棋，“探春因一块棋受了敌，算来算去，总得了两个眼，便折了官着儿，两眼只瞅着棋盘，一只手伸在盒内，只管抓棋子作想”，因此林之孝家的来请示也未听到。

孰难孰易

围棋似乎更“平等”一些，每个棋子除了颜色没有什么不同，它的重要性取决于它的位置以及整个棋盘其它棋子（包括自己和对手）的整体分布。而象棋似乎不同，车一般都要比马有价值，将帅的价值无穷大，虽然它没有什么大作用。偶尔在某些特殊情况下，虎落平阳被犬欺，车的价值可能比不上一个马，但大部分情况下车都超过两个马的价值，真是“王侯将相确有种乎”！

从理想主义的角度，我更喜欢围棋，每个棋子都是同样的可塑性，它的重要性取决于它的位置。但是每个棋子的位置又是它自己能决定的吗？也许在开始一盘对局之前它的位置就大致确定了！放在棋罐里最上面的棋子当然最可能被选择，另外位置好坏更由下棋的棋手决定，棋子本身没有什么决定权。

而且从现实的角度来说个体的差异确实是存在的，打篮球的话姚明就生来比其他人有优势。

从入门的角度说，象棋的估值函数相对简单，因此入门应该更容易一些。

MiniMax搜索/Alpha-Beta剪枝和象棋

这个算法最早是冯诺依曼提出来的。其实每一个下棋的人可能都在不自觉的使用这个算法，只不过没有形式化的语言描述出来而已。

第一次下棋的时候，我们很可能尝试当前局面下所有的可能走法，然后选择最“好”的一个局面。拿象棋来说，“好”可以比较简单的用双方棋子的分值来表示，一个车的价值大致相当于两个炮，马和炮差不多，相当于两个士或者相，兵的价值最低。那么很可能我们第一次走棋时就是看哪步走法能“吃”到对方的棋子，然后就走这一步。可惜下棋是两个人的博弈，你用车吃对方一个兵，对方可能用马把你的车吃了，这样算下来，用一个车换一个兵，明显是亏了。通过这样的例子，你学到对手是在和你“作对”，你有很多走法，如果你只考虑一步，选择最好的局面，那么对手会在这个局面走对他有利的局面，有可能这个局面对你非常不利。所以你觉得应该要考虑两步也就是一个回合，首先你尝试所有的可能（当然也可能做一些裁剪，滤掉明显不好的走法，比如没事走动自己的老将），比如用车吃对手的卒，然后站在对手的角度选择对手最好的走法（用马吃你的车），然后评估一下这个局面，发现局势对你并不有利。接着再尝试用兵吃对手的马，接着对手选择用车吃你的兵，这个结果明显对你有利。

当然随着你计算能力的增强，你可能把搜索的深度从2扩展到4或者更多。

(from https://en.wikipedia.org/wiki/Minimax)

上面的“算法”用上图来说明。圆形的节点表示“你”面对的局面，而方块的节点表示对手面对的局面。这里是4层两个回合的搜索树。

我们从最下层第4层开始，这一层是叶子节点，不再展开，你需要评估局面的“好坏”，比如前面描述的“简单”算棋子分数的算法（其实也不那么简单，想想第一次下棋的人怎么知道？这是几千年来前人总结出来的经验！）计算出得分。

接着第3层对手从这些局面中选择他最好的局面（也就是你最坏的局面），也就是得分最少的局面（因为计算得分是从你的角度计算的）。

接着你在第2层选择得分最多的局面。

接着对手在第1层选择得分最少的局面。

最后你在第0层选择得分最多的局面。

这里忽略或者说假设了一个非常重要的东西——估值函数。也就是之前说的怎么评估一个局面的好坏。

对于一个游戏来说，局面可以分为两类：结束局面和非结束局面。比如对于象棋来说，结束局面就是一方的将/帅被吃了（实际的规则是一方的将/帅没有“合法”的走法了。但是我们总是可以假设将帅是可以走不能走的位置，然后被“吃”掉，或者将帅碰面也可以看成被吃，我小时候学下象棋的时候就是这么认为的），其它的所有合法局面都是非结束局面（现代象棋还有一些规则为了避免重复局面或者“无赖”的长将长打长捉指定了一些规则约束，高手过招时甚至会“合理”地利用这样的规则，另外在某些特殊的残棋里这些规则也会决定胜负）。

对于很多游戏来说，结束局面的好坏一般是游戏规则规定的。比如象棋的结束一般是某方的将帅被吃了，那么被吃的一方就输了，可以认为这个局面的得分是负无穷大，而相对的另一方得分是无穷大。当然实际比赛中也有和棋，也就是双方都没有办法吃掉对方的将帅或者超过自然限着的回合数。

从理论上来说，如果我们的计算能力足够，我们可以搜索到游戏的结束局面，那么我们就可以说完全“解决”了这个游戏。但是从上面的搜索过程我们可以发现，搜索的节点数是随着层次的增加指数级增加的（后面我们讨论的alph-beta剪枝能减少部分不必要的搜索，但是并不影响总的复杂度）。一般认为中国象棋的分支因子在40-50之间（也就是平均每步有这么多种合法的走法），那么搜索20步就需要40的20次方需要多久呢？我们假设计算机每秒可以搜索1G个节点(1GHz，时间一个CPU时钟周期肯定不能搜索一个节点)，那么也需要3486528500050735年！

因此，我们只能搜索有限的深度，这就带来一个问题，非结束局面的得分的计算问题。也就是给定一个局面，怎么计算“好坏”？

首先，我们需要定义这个“好坏”。定义其实非常简单，这个得分就是把这个局面搜索到结束局面的得分，基本上三种可能：胜/负/和。当然这个理论得分是不知道的，那么我们怎么近似它呢？一种最简单而且实际上我们人类一直在使用的方法就是统计的方法：我们看以往对弈的结果，如果这个局面下了100局，我方胜了60局，输了40局，那么我可能认为这个局面还不错，反之如果我方胜了30局输了70局，那么就不太好。

当然，我们统计的是“高手”的对局，如果是随机的对局，可能没有统计意义。这里其实有个鸡生蛋蛋生鸡的过程。类似于EM算法。我们首先有一个还“不错”的估值函数（人类高手），然后不停的模拟对局（下棋），然后统计新的局面得分，然后用这些局面得分更新我们的估值函数。

这样一代一代的积累下来，人类的下棋水平越来越高。这其实和下面我们要讨论的强化学习和MCTS有类似的思想！我们下面会再讨论这个问题。

比如我们有了一个基本的估值函数：计算棋子的静态得分，将10000分，车10分，马和炮5分，相士2分，兵卒1分。然后我们不断下棋，发现有些局面从棋子看双方都一样，但是棋子的不同位置会导致最终胜负的差距很大。因此我们会更新我们的估值函数：比如兵卒过河要变成两分。棋子的行动力越大分越高，越靠近中间分越高，不同的棋子如果有保护或者攻击关系，我们会增加一些分数，另外一些特殊的局面，比如空头炮，三子归边会有很高的胜率，我们也会增加分数，从而出现棋子攻杀。

因此一个棋手的棋力除了计算能力（这个更多是天赋，当然也能通过训练提高），另外一个很重要的能力就是评估局面的能力，这个就更多的靠后天的训练。而一个游戏是否“有趣”/“好玩”，其实也跟评估函数有关。如果一个游戏很容易评估，那么基本不需要搜索，看一个回合就知道最终的结果了，就没有什么意思。最有“意思”的局面是“看”起来很差但“其实”很好的棋，或者看起来某个局面很平稳，但其实某方优势很明显，所谓的“妙手”是也。什么叫“看”起来很差？就是搜索很浅的层次评估或者不搜索直接评估得分很差(比如走窝心马或者被架空头炮)，但是搜索很深之后发现这是当前局面下最好的走法，甚至是反败为胜的唯一招法。高手和低手的差别也在于此，对于那种很明显的好坏，大家都能看得出来；而有些局面，对于低手来说可能觉得局面双方还差不多，但是在高手看来胜负早已了然于胸了。

Alpha-Beta剪枝

(from https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning)

假设minimax是4层的深度优先搜索，并且是如图的从左到右的顺序。那么有些子树是不用搜索，可以被剪枝掉的。

比如下面这棵子树：

第0层是MAX操作，第一个孩子返回了5，现在我们正准备搜索第二个孩子（4的那个，当然现在还不知道）。我们知道它的只至少是5了，>=5。

它是一个MIN操作，首先搜索到7，所以它的取值<=7，接着搜索到4，所以它的取值<=4，这个时候就可以停止了，为什么？

因为第0层的节点的值已经>=5了，而第1层的右边那个节点已经<=4了，所以不管它的第三个孩子得分多少，第0层都不会选择了，所以可以把它剪枝掉了。max(5, (<=4))=5。

搜索完两个孩子之后，第0层的值已经>=6了，然后搜索第1层(5)的那个节点，它的第一个孩子已经返回5了，所以它的值必然<=5了，所以它的第二个孩子(8)也没有必要搜索了。因为max(6, (<=5))=6。

类似的，对手在MIN的时候也可以剪枝，min(3, (>=4))=3。

当然上面是非常形式化的描述，其实在实际的下棋过程中我们可能自觉不自觉的使用了alpha-beta剪枝。

比如，我们有这样的推理：我可以走车吃对手一个兵而且对手吃不了我任何子(得分+1)；也可以走马吃对手的卒，走马后对手有很多走法，其中一个走法是吃掉我的马而且我还吃不了他任何棋子(得分-4)，那么这个时候我就不会走马了，因为不管其余的走法怎么样(也许对手还有更好的走法，比如吃我一个车得10分；当然也有更差的走法不吃我的子让我得+1分，但他不会这么走)，这个走法下我“至少”损失一个马了，那么我现在有一个得分+1的走法，我就不要考虑对手其它的走法了，直接剪枝掉了。用形式化的语言描述 max(1, (<=-5))=1。

alpha-beta能否剪枝非常依赖于搜索的顺序，如果把最优的走法先搜索，那么能得到最大程度的剪枝。所以这个树的展开顺序非常重要。一般会使用很多启发式规则来排序。比如吃对方的棋子很可能是比较好的走法，而没事走动老将不是什么好的走法。

要下好象棋，计算能力和评估局面的能力缺一不可。因为人的计算能力有限(计算机也是一样)，所以搜索到一定层次之后需要停下来评估局面。当然人的搜索不是固定的，而是和评估函数一起工作的，对于“简单”的局面（比如明显很差或者很好的），就不要搜索很深，而对于“复杂”的局面，则会尽可能深的搜索下去。所以好的评估局面的能力对于下象棋很重要，这个容易理解。

那么计算能力（搜索深度）的重要性呢？这个似乎更加显而易见，棋经云：“多算胜，少算不胜，况乎无算。”

不过仔细思考一下，有似乎没有那么明显。为什么搜索深比搜索浅好呢？除非你能搜索到游戏结束，否则都得提前结束使用估值函数。搜索深比搜索浅好的一个隐含假设就是越深的局面越容易评估。对于象棋来说这是很明显的，因为象棋的特定是越下棋子越少，局面也就更容易评估。而围棋就不一样，棋子越到后来越多，局面的评估难度并没有明显的下降（甚至可能上升，我个人围棋水平也就是会简单规则的程度，所以很可能不是这样）。当然围棋的评估局面比象棋也复杂很多（至少我是这么觉得的）。

当然一个人的计算能力是有限的，所以“离线”的计算对于职业棋手也很重要。很多棋手对于某些布局有非常细致的研究，他们“离线”研究了各种可能的变化，因此你如果走到了他熟悉的布局，你基本上很难战胜他。因此残局库和开局库的研究和记忆是一个职业棋手努力的方向。

要设计一个好的象棋程序也是一样，首先是计算（搜索）能力，这个对于相对于人类来说是它的强项。因此更关键的就是评估局面的函数。由于象棋的局面特征还是比较明显的，静态的棋子分值估计能解决80%的局面，再加上一下位置特征（比如棋子在不同的位置有不同的加减分），棋子的行动力，棋子之间的保护关系等等，就能解决大部分的局面。那些非常复杂的局面可以通过更深的搜索层次来解决。另外像开局库，残局库这些对于计算机都不是问题，它的记忆能力远超人类。

有了这些重要的特征，可以人工设计估值函数，也可以用机器学习的方法学习更加准确的估值函数。所以解决象棋应该是“比较”容易的（相对于围棋）。所以现在国际象棋人类的水平和计算机差距越来越大，人类几乎没有获胜的可能了。

围棋为什么不能用类似的方法

国际象棋解决之后，大家把注意力放到了围棋上。用类似的方法效果很差，比如GnuGo的棋力大概在13级(kyu)。

13级什么概念呢？从下图中可以看到是非常差的水平。

(from https://en.wikipedia.org/wiki/Go_ranks_and_ratings#Kyu_and_dan_ranks)

为什么对于象棋非常有效的方法用在围棋上就不行呢？我们需要分析两种棋的差别。不过由于我本人下棋水平一般，围棋更是刚入门的水平，所以更多的是从程序员的角度来分析两种棋的差异。

分支因子和深度

国际象棋的分支因子是35，而围棋是250（https://en.wikipedia.org/wiki/Branching_factor）。这个数值只是估计，但可以看出大致的差别。从这个角度来说围棋要比国际象棋复杂。但如果只是这一个因素的差别不可能导致最好的国际象棋程序超过人类而围棋只有13k的水平。

估值函数

前面我们分析的是中国象棋，国际象棋和中国象棋类似，所以它的估值函数是相对容易和准确的。而围棋就比较困难，数棋子的个数明显是没有任何用处的。

“围棋难的地方在于它的估值函数非常不平滑，差一个子盘面就可能天翻地覆，同时状态空间大，也没有全局的结构。这两点加起来，迫使目前计算机只能用穷举法并且因此进展缓慢。但人能下得好，能在几百个选择中知道哪几个位置值得考虑，说明它的估值函数是有规律的。这些规律远远不是几条简单公式所能概括，但所需的信息量还是要比状态空间本身的数目要少得多（得多）。”

（http://www.almosthuman.cn/2016/01/12/ebfzg/）

后面我讨论用深度学习(CNN)来评估局面时会分析这两个因素哪个更重要，至少从个人感觉来看，第二个更加重要一些。

围棋和象棋的差别还是挺大的，比如MCTS搜索，在围棋中效果不错，但是用到象棋里就没有什么效果。

MCTS

多臂老虎机(Multi-Arm Bandits)和UCB(Upper Confidence Bounds)

这是强化学习里最简单的一个问题，在很多地方都有应用，比如互联网广告(https://support.google.com/analytics/answer/2844870?hl=en)，游戏厅有一个K臂的老虎机，你可以选择其中的一个投币，每个手臂都是一个产生一个随机的奖励，它们的均值是固定的（也有Nonstationary的多臂老虎机，我这里只考虑Stationary的）。你有N次投币的机会，需要想办法获得最大的回报(reward)。

当然如果我们知道这个K个手臂的均值，那么我们每次都选择均值最大的那个投币，那么获得的期望回报应该是最大的。

可惜我们并不知道。那么我们可能上来每个都试一下，然后接下来一直选择最大的那个。不过这样可能也有问题，因为奖励是随机的，所以一次回报高不代表真实的均值回报高。当然你可以每个都试两次，估计一下奖励的均值。如果还不放心，你可以每个都试三次，或者更多。根据大数定律，试的次数越多，估计的就越准。最极端的一种做法就是每个手臂都投一样多的次数；另外一种极端就是碰运气，把所有的机会都放到一个手臂上。后一种如果运气好是最优的，但是很可能你抽到的是回报一般的甚至很差的手臂，期望的回报其实就是K个手臂的平均值。前一种呢？回报也是K个手臂的平均值！我们实际的做法可能是先每个手臂都试探几次，然后估计出比较好的手臂（甚至几个手臂），然后后面重点尝试这个(些)手臂，当然偶尔也要试试不那么好的手臂，太差的可能就不怎么去试了。但这个“度”怎么控制就是一个很复杂的问题了。这就是exploit-explore的困境(dilemma)。利用之前的经验，优先“好”的手臂，这就是exploit；尝试目前看不那么“好”的手臂，挖掘“潜力股”，这就是explore。

一种策略(Policy)的Regret(损失)为：

(from A Survey of Monte Carlo Tree Search Methods)

我觉得mu_j应该放到求和符号里面的。

不要被数学公式吓到了，用自然语言描述就是：最理想的情况是n次都试均值最大的那个手臂(mu star)，不过我们并不知道，E[Tj(n)]是这个策略下选择第j个手臂的期望。那么R就是期望的损失，如果我们的策略非常理想，这个策略只尝试最好的手臂，其它不试，那么R就是0。

但是这样的理想情况存在吗？很明显不太可能存在（存在的一种情况是k个手臂的均值一样）。那么我们的策略应该尽量减少这个损失。

Lai and Robbins证明了这个损失的下界是logn，也就是说不存在更好的策略，它的损失比logn小（这类似于算法的大O表示法）。

所以我们的目标是寻找一种算法，它的损失是logn的。

UCB就是其中的一种算法：

每次决策之前，它都用上面的公式计算每个手臂的UCB值，然后选中最大的那个手臂。公式右边的第一项是exploit项，是第j个手臂的平均回报的估计。这个值越大我们就越有可能再次选中它。第二项是explore项，n_j是第j个手臂的尝试次数，n_j越小这个值就越大，也就是说尝试次数越少的我们就越应该多尝试。当n_j=0时，第二项为无穷大，所以这个算法会首先尝试完所有的手臂（explore），然后才会选择回报最大的那个(exploit)，试了之后这个手臂的平均值可能变化，而且n_j增加，explore值变小，接着可能还是试最大的那个，也可能是第二大的，这要看具体情况。

我们来分析一些极端的情况，一种情况是最好的（假设下标是k)比第二好的要好很多，那么第一项占主导，那么稳定了之后大部分尝试都是最好的这个，当然随着n_k的增加explore项在减少(其它手表不变)，所以偶尔也试试其它手臂，但其它手臂的回报很少，所以很快又会回到第k个手臂。但是不管怎么样，即使n趋于无穷大，偶尔也会尝试一下其它的手臂的。不过因为大部分时间都在第k个手臂上，所以直觉上这个策略还是可以的。

另一种极端就是k个手臂都差不多（比如都是一样的回报），那么exploit项大家都差不多，起决定作用的就是explore项，那么就是平均的尝试这些手臂，由于k各手臂回报差不多，所以这个策略也还不错。

出于中间的情况就是有一些好的和一些差的，那么根据分析，大部分尝试都是在好的手臂上，偶尔也会试一试差的，所以策略的结果也不会太差。

当然这个只是简单的直觉的分析，事实上可以证明这个算法的regret是logn的，具体证明细节请参看论文《Finite-time Analysis of the Multiarmed Bandit Problem》。

MCTS（Monte Carlo Tree Search）和UCT（Upper Confidence Bound for Trees）

(from A Survey of Monte Carlo Tree Search Methods)

MCTS算法就是从根节点(当前待评估局面)开始不断构建搜索树的过程。具体可以分成4个步骤，如上图所示。

1. Selection

使用一种Policy从根节点开始，选择一个最“紧急”(urgent)的需要展开(expand)的可以展开(expandable)的节点。

说起来有点绕口，可以展开的节点是非叶子节点（非游戏结束局面），而且至少还有一个孩子没有搜索过。比如上图展示的选择过程，最终选择到的节点不一定是叶子节点（只有它还有没有搜索过的孩子就行）。具体的选择策略我们下面会讨论。

2. Expansion

选中节点的一个或者多个孩子被展开并加入搜索树，上图的Expansion部分展示了展开一个孩子并加入搜索树的过程。

3. Simulation

从这个展开的孩子开始模拟对局到结束，模拟使用的策略叫Default Policy。

4. Backpropagation

游戏结束有个得分(胜负)，这个得分从展开的孩子往上回溯到根节点，更新这些节点的统计量，这些统计量会影响下一次迭代算法的Selection和Expansion。

经过足够多次数的迭代之后（或者时间用完），我们根据某种策略选择根节点最好的一个孩子（比如访问次数最多，得分最高等等）。

上面的算法有两个policy：tree policy 和 default policy。tree policy决定怎么选择节点以及展开；而default policy用于simulation（也有文献叫playout，就是玩下去直到游戏结束)

在讨论MCTS和UCT之前，我们来分析一下人在下棋时的搜索过程。

首先人的搜索肯定不是之前的固定层次的搜索的，很多“明显”不“好”的局面可能就只搜索很浅的层次，而不那么“明显”的局面可能需要搜索更深的层次（之前我们讨论过这里隐含了一个假设：深的局面比浅的局面容易评估，对于象棋这是比较明显的），“好”的局面也需要多搜索几层确保不会“看走眼”。

MCTS其实有类似的思想：我们着重搜索更urgent的孩子，所谓urgent，就是更promising的孩子。当然偶尔也要看看那些不那么promising的孩子，说不定是潜力股。这其实就有之前讨论的exploit和explore的平衡的问题。

另外MCTS直接Simulation到对局的结束，“回避”了局面评估的难题（不过这个问题最终还是绕不过去的，我们下面会再讨论）。

既然是exploit和explore的问题，那么之前我们讨论的UCB就可以直接用上了，把UCB用到MCTS就是UCT算法（注意：MCTS其实是一族算法的统称，不同的Tree Policy和Default Policy就是不同的MCTS算法）.

UCT算法

Selection和Expansion的公式如上，和UCB很类似，只是多了一个常量Cp，用来平衡exploit和explore。

每个节点v都有两个值，N(v)和Q(v)，代表v访问过的次数（每次迭代都是从root到结束状态的一条Path，这条Path上的每个点都被visit一次）和v的回报，如果这次simulation己方获胜，则Q(v)+1，否则Q(v)-1。（1，3，5…层代表自己，2，4，6…代表对手，如果最终我方获胜，1，3，5都要加一而2，4，6都要减一）。

具体的计算公式如上，每次选孩子时都用上面的公式计算得分。第一项就是这个节点的平均回报(exploit term)和第二项就是explore term，访问次数少的节点更应该被explore。当N(v)=0时第二项值为无穷大，所以如果某个节点有未展开的孩子，总是优先展开，然后才可能重复展开回报高的孩子。

UCT算法的特点如下：

1. Aheuristic：不需要估值函数，因此也就不需要各种启发式规则，领域知识，从而“回避”了围棋估值函数难的问题。
2. Anytime：可以任何时候结束，迭代的次数越多就越准确。
3. Asymmetric：前面我们也分析过了，和人类的搜索类似，搜索树是不对称的，不是固定层次的，而是“重点”搜索promising的子树。

UCT的变种和改进

这里主要关注围棋领域的一些变种和改进。

All Moves As First（AMAF）和Rapid Action Value Estimation（RAVE）

这是很多开源MCTS围棋使用的一个变种。

首先通过UCT的Tree Policy我们选择了C2和A1，然后Default Policy我们选择了B1 A3 C3 最终黑棋获胜。

普通的MCTS会更新C2和A1的N(v)和Q(v)，而AMAF认为：既然在simulation的过程中黑方选择了B1和C3，在root节点时也可以选择B1和C3，那么这次模拟其实也可以认为B1和C3对获胜是有帮助的，那么root节点的B1和C3也有贡献(标志为)，也应该更新统计量，让下次选择它的概率大一点。同理白棋在simulation的时候选择了A3，在C2也可以选择A3（有的那个），那么C2对于白棋失败也是有责任的，那么下次在C2的时候白棋应该避免选择A3。这样一次迭代就能多更新一些节点（那些没有直接Selection的也有一些统计量）。

这个想法对于围棋似乎有些道理（因为不管哪个顺序很可能导致一样的局面，前提是没有吃子），而且实际效果也不错。但是在别的地方是否应该使用就需要看情况了。

这里有两类统计量：直接selection的节点的统计量(A1,C2)和间接selection的节点(B1,C3, A3)。这两种权重应该是不一样的。

所以比较直观的想法是给它们不同的权重 αA+(1−α)U 这就是α-AMAF。

这个权重α是固定的，RAVE认为随着模拟次数的增加α应该减少才对（没有真的模拟是可以用这些间接的统计量，如果有了真的更准确的估计，这些间接的统计量就应该降低权重，这个想法也很自然）。

RAVE使用上面的公式动态调整α，随着v(n)的增加，α的值不断下降。

Simulation的改进

默认的default policy随机的选择走法模拟到结束，这在没有任何先验知识的时候是可以的。但是像我们之前分析的人类在“探索”未知局面时不是随机的“探索”的，也是用一个估值函数指导的，去探索那些更promising的局面。

具体方法很多，比如Contextual Monte Carlo Search，Fill the Board以及各种基于Pattern的方法。细节就不再展开讨论了。

MCTS的并行搜索

(1) Leaf Parallelisation

最简单的是Leaf Parallelisation，一个叶子用多个线程进行多次Simulation，完全不改变之前的算法，把原来的一次Simulation的统计量用多次来代替，这样理论上应该准确不少。但这种并行的问题是需要等待最慢的那个结束才能更新统计量；而且搜索的路径数没有增多。

(2) Root Parallelisation

多个线程各自搜索各自的UCT树，最后投票。

(3) Tree Parallelisation

这是真正的并行搜索，用多个线程同时搜索UCT树。当然统计量的更新需要考虑多线程的问题，比如要加锁。

另外一个问题就是多个线程很可能同时走一样的路径（因为大家都选择目前看起来Promising的孩子），一种方法就是临时的修改virtual loss，比如线程1在搜索孩子a，那么就给它的Q(v)减一个很大的数，这样其它线程就不太可能选择它了。当然线程1搜索完了之后要记得改回来。

《A Lock-free Multithreaded Monte-Carlo Tree Search Algorithm》使用了一种lock-free的算法，这种方法比加锁的方法要快很多，AlphaGo也用了这个方法。

Segal [195] investigates why the parallelisation of MCTS across multiple machines has proven surprisingly difficult. He finds that there is an upper bound on the improvements from additional search in single-threaded scaling for FUEGO, that parallel speedup depends criti- cally on how much time is given to each player, and that MCTS can scale nearly perfectly to at least 64 threads when combined with virtual loss.

Segal研究了为什么多机的MCTS算法很难，并且实验得出结论使用virtual loss的多线程版本能比较完美的scale到64个线程（当然这是单机一个进程的多线程程序）。后面我们讨论AlphaGo的scalable的时候会用到这些结论。

使用了UCT算法之后，计算机围棋的水平能提高到KGS 2d的水平（估计是1k的水平？）。