[转载]AlphaGo 的棋局，与人工智能有关，与人生无关
编者注：本文做者系出门问问 NLP 工程师李理，他在这篇文章详细叙述了AlphaGo 人工智能背后的细节。html
前言：人生如棋程序员
回顾一下个人人生，彷佛和棋是有一些关联的。编者注：本文做者出门问问算法
1997 年中考后的暑假在姑父公司的机房第一次接触电脑，当时应该是 80386 的微机。学习电脑就是学习 DOS 命令和打字，彻底不懂干什么用的，打字尤为是五笔字型，更是学得头疼——王旁青头戋五一，土士二干十寸雨……惟一的乐趣就是趁姑父不在的时候键入 CCH，和电脑下一盘象棋（本文象棋特指中国象棋，若是是国际象棋不会简称象棋）。这个软件的棋力挺强的，至少对于我这样业余水平来讲是这样的。总共下来估计有一二十盘，我赢的次数也只有一两盘，其他的都是输了。我第一步通常走中炮，电脑第一步老是走马，而当第二步我上马的时候，电脑不是走常见的屏风马，而是起横车，另一侧的马都不动。从棋理的角度说，这种布局是有问题的，中路很空虚。可是我却找不到什么破绽，缘由多是中局计算能力相差太远。编程
当时就以为挺神奇的，电脑居然会下棋，并且还这么厉害，心想我之后能不能作一个比它还厉害的软件。api
同年，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 或者更多。
上面的“算法”用上图来讲明。圆形的节点表示“你”面对的局面，而方块的节点表示对手面对的局面。这里是 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 的水平？）。
CNN 和 Move Prediction
以前咱们说了 MCTS 回避了局面估值的问题，可是人类下围棋显然不是这样的，因此真正要下好围棋，如此从模仿人类的角度来讲，这个问题是绕不过去的。人类是怎么学习出不一样局面的细微区别的呢？固然不能由人来提取特征或者须要人来编写估值函数，不然仍是回到以前的老路上了。咱们的机器能自动学习而不须要领域的专家手工编写特征或者规则来实现估值函数呢？
眼下最火热的深度学习也许能够给咱们一条路径（固然可能还有其它路径，但深度学习目前看起来解决 feature 的自动学习是最 promising 的方法之一）。
深度学习和 CNN 简介
在机器学习流行以前，都是基于规则的系统，所以作语音的须要了解语音学，作 NLP 的须要不少语言学知识，作深蓝须要不少国际象棋大师。
而到后来统计方法成为主流以后，领域知识就再也不那么重要，可是咱们仍是须要一些领域知识或者经验来提取合适的 feature，feature 的好坏每每决定了机器学习算法的成败。对于 NLP 来讲，feature 还相对比较好提取，由于语言自己就是高度的抽象；而对于 Speech 或者 Image 来讲，咱们人类本身也很难描述咱们是怎么提取 feature 的。好比咱们识别一只猫，咱们隐隐约约以为猫有两个眼睛一个鼻子有个长尾巴，并且它们之间有必定的空间约束关系，好比两种眼睛到鼻子的距离可能差很少。但怎么用像素来定义”眼睛“呢？若是仔细想一下就会发现很难。固然咱们有不少特征提取的方法，好比提取边缘轮廓等等。
可是人类学习彷佛不须要这么复杂，咱们只要给几张猫的照片给人看，他就能学习到什么是猫。人彷佛能自动”学习“出 feature 来，你给他看了几张猫的照片，而后问题猫有什么特征，他可能会隐隐预定的告诉你猫有什么特征，甚至是猫特有的特征，这些特征豹子或者老虎没有。
深度学习为何最近这么火，其中一个重要的缘由就是不须要（太多）提取 feature。
从机器学习的使用者来讲，咱们之前作的大部分事情是 feature engineering，而后调一些参数，通常是为了防止过拟合。而有了深度学习以后，若是咱们不须要实现一个 CNN 或者 LSTM，那么咱们彷佛什么也不用干。
Deep Neural Network 能自动学习出层次化的 feature
CNN 最先是 Yann Lecun 提出用来解决图像识别的问题的一种深度神经网络。由 Yann LeCun 提出，经过卷积来发现位置无关的 feature，并且这些 feature 的参数是相同的，从而与全链接的神经网络相比大大减小了参数的数量。
CNN 深度神经网络
所以 CNN 很是适合围棋这种 feature 很难提取问题，好比图像识别。用 CNN 来尝试围棋的局面评估彷佛也是很天然的想法。
Move Prediction using CNN
以前也分析过了，围棋搜索若是不到游戏结束，深的局面并不比浅的容易评估，因此咱们不须要展开搜索树，而能够直接评估一个局面下不一样走法的好坏。这样作的好处是很容易得到训练数据。咱们有大量人类围棋高手的对局（海量中等水平的对局），每个局面下“好”的走法直接就可以从高手对局库里获得，认为他们的对局都是“好”的走法。可是要获得一个局面的“绝对”得分却很难，由于咱们只知道一盘对局最终的结果。一盘游戏最终的胜负多是由于布局就下得很好，也多是由于最后的官子阶段下得好，中间具体某个局面的好坏是很难判断的（固然强化学习试图解决这个问题，可是仍是很难的，下面在讨论 AlphaGo 的时候会有涉及）。对于一个局面，若是能知道这个局面下最好的走法（或者几个走法），那么咱们对弈时就直接选择这个走法（固然这个最好的走法可能得分也不好，好比败局已定的状况下怎么走都是输）。
因此大部分研究都是用 CNN 来预测一个局面下最好的走法。【预测走法比估值一个局面容易，若是咱们可以准确估值局面，那么最佳走法就是从走以后的局面中选择对本身最有利的走法。或者用咱们作问答系统经常使用的比喻，预测走法是搜索引擎，局面评估是问答系统。搜索引擎只要把好的排前面就好了（甚至不必定要求排在第一，排在第一页也就差很少了），而问答不只要把好的排前面，并且还要知道这个最“好”的结果是否足够“好”，由于排序的好是相对“好”，问答的好必须是绝对的“好”，是惟一正确答案】。
Van Der Werf 等（2003）
最先用 CNN（固然还有用其它机器学习方法）来预测走法是 2003 年 Van Der Werf 等人的工做，他们用了不少手工构造的 feature 和预处理方法，他们取得了 25%的预测准确率。没有细看论文，在 2006 年 Deep Learning 火以前，因此估计网络的层次很浅。
Sutskever & Nair（2008）
以后在 2008 年，这个时候 Deep 的神经网络已经逐渐流行了。Sutskever & Nair 用来 2 层的 CNN，第一层有 15 个 7*7 的 filter，第二层用了 5*5 的 filter，最后用了一个 softmax 层，输出 19*19，表示每一个可能走法的几率（固然须要后处理去掉不合法或者不合理的走法，好比违反棋规的打劫局面当即提回，或者在本身的眼里下棋）。他们获得了 34%的预测准确率。不过有一点问题就是他们出来使用当前局面，还用了上一步走法（这个走子致使了当前局面，也就是对手的上一步走子），这个多是有问题的，由于实际对局时对手的水平是不能肯定的，用这个 feature 固然能提升“数字”上的准确率，可是对于下棋水平是否有负面影响是很难说的。
Clark & Storkey（2015）
到了 2015 年，计算机的计算能力更强，深度神经网络的层次也愈来愈深，在围棋领域也能看到这种趋势。Clark & Storkey 使用了 8 层的 CNN，用的特征包括最原始的棋子（用了 3 个 feature plane，表示 361 个点是黑棋/白棋/空白），ko（劫）的约束，一个 group（块）的气。包括使用不少 trick 来保证 symmetries（由于围棋的局面旋转 90/180/270/360 度后以及作 180 度的镜像以后应该是同样的）。他们在 GoGoD 数据上的预测准确率达到了 41.1%，在 KGS 数据上的准确率达到 44.4%。GoGoD 上大部分是职业选手的对局，而 KGS 数据有不少业余高手的对局。
Maddison 等（2015）
光是预测准确率，并不能说明下棋的水平。所以 Maddison 等人的工做把 Move Prediction 用到了实际的对弈当中。
他们的 CNN 增长到了 12 层，feature 也有所增长，下面是他们使用的 feature。
第一组 feature 是棋子（Stone）的颜色，和以前同样。
第二组是棋子（所在 group）的气，用 4 个 plane 来表示，分别是 1，2，3 >=4 口气。
第三组是走了这步棋以后的气，用了 6 个 plane，表明 1，2，3，4，5，>=6 口气。
第四组表示这个走法在当前局面是否合法。
第五组表示这个棋子距离当前局面的轮次，好比上一步对手走的就是 1，上上一步本身走的就是 2。由于围棋不少都是局部的战役，因此这个 feature 应该是有用的。
第六组就是表示走这这后能吃对方多少个棋子。
第七组表示走这可否征子成功。
第八组 feature 比较有趣，按照做者的说法就是由于 KGS 的对弈水平良莠不齐，若是只留下高手的对局数据太少，因此用这个 feature。
他们在 KGS 数据上的预测准确率达到 55%。相对于 Clark 等人的工做，Maddison 的工做除了增长了 CNN 的层次（8 到 12），增长的 feature 应该是颇有帮助的，好比 Turns Since，Capture Size 和 Ladder Move。尤为是 Ladder Move，下过围棋的都知道征子可否成功对应是否要走这步棋已经局部的计算很是重要。
根据他们的使用，人类 6d 的预测准确率也只有 52%，因此从预测走法的角度来讲，CNN 的水平已经达到了 6d 的水平。
另外他们还作了实验，证实 Clark 那些用来保证 symmetry 的 tricky 并无什么卵用，直接简单粗暴的把数据作 symmetric 变换后训练就好了。
彻底不用搜索直接用 Move Prediction 的结果下棋，能 97%的比率打败 GnuGo（这个是彻底基于 alpha-beta 搜索的），做者并无说明只用 Move Prediction 的绝对水平，而只是和不好的 GnuGo 比较，因此应该水平不怎么样。
加上 MCTS 以后他们的水平能达到主流 MCTS 的开源软件如 Pachi 和 Fuego 的水平。固然 CNN 的预测相对于 Simulation 来讲是很慢的，他们的 GPU（4 个GeForce GTX Titan Black）评估 128 个局面须要 0.15s，而 CPU（16 Intel Xeon E52643 v2 3.5GHz）每秒能够 simulation 47,000 个局面。因此他们使用了异步的策略，先用先验知识给出一个节点的 N(v),Q(v)，先搜索着，等 GPU 运算完了再用 CNN 预测的胜率更新这些统计量。所以 CPU 和 GPU 的速度须要能大体匹配。
Yuandong Tian & Yan Zhu（2015）
和 Google DeepMind 进行围棋竞赛的主要就是 Facebook Tian yuandong 他们了。在 Google 宣布文章在 Nature 发表的前一天，他们在 arxiv 上发表了本身的工做（https://www.zhihu.com/topic/20038840）。
下面咱们来看看他们的工做（《Better Computer Go Player with Neural Network and Long-Term Prediction》）。
使用的 feature：
除了使用以前工做的标准 feature 以外，他们增长了一些 feature，好比是否边界，距离中心的远近，是否靠近本身与对手的领土（不清楚怎么定义领土的归属的）。此外对于以前的 feature 也进行了压缩，以前都把特征分红黑棋或者白棋，如今直接变成己方和对手，这样把模型从两个变成了一个（以前须要给黑棋和白棋分别训练一个模型）。此外的一个不一样地方就是相似于 Multi-task 的 learning，同时预测将来 3 步棋的走法（而不是 1 步棋走法）。
为了与 Maddison 的工做比较，这里只用了标准的 features，比较的也是将来 1 步棋的准确率，能够发现这个方法仍是有效的（不过我我的以为做者应该本身复现 Maddison 的结果而不是直接用他的结果）
只使用 DCNN 的围棋软件（不用 MCTS 搜索）
darkforest: 标准的 feature,一步的预测，使用 KGS 数据
darkforest1：扩展的 feature,三步预测，使用 GoGoD 数据
darkforest2：基于 darkforest1,fine-tuning 了一下参数。
把它们放到 KGS 上比赛，darkforest 能到 1k-1d 的水平，darkforest1 能到 2d 的水平，darkforest2 能到 3d 的水平【注：KGS 的 3d 应该到不了实际的业余 3 段】，下面是具体的状况。
所以做者认为加入 3 步预测的训练是有效的。
MCTS+DCNN
tree Policy: 走法首先经过 DCNN 排序，而后按顺序选择，除非累计的几率超过 0.8 或者超过必定次数的 top 走法。Expansion 使用的 UCT 算法。
Default Policy:参考的 Pachi 的 tree policy,有 3*3 的 pattern,对手打吃的点（opponent atari point），点眼的检测（detection of nakade points）等。
这个版本的软件叫 darkforest3,在 KGS 上能到 5d 的水平。
弱点
DCNN 预测的 top3/5 的走法可能不包含局部战役的一个关键点，因此它的局部做战能力还比较弱。
对于一些打劫点即便没用，DCNN 仍是会给高分。
当局面很差的状况下，它会越走越差（这是 MCTS 的弱点，由于没有好的走法，模拟出来都是输棋，一些比较顽强的抵抗的走法不能走出来）。
从上面的分析能够看出：DCNN 给出的走法大局观仍是不错的，这正是传统的方法很难解决的问题。局部的做战更多靠计算， MCTS 会有帮助。可是我我的以为 MCTS 搜索到结束，没有必要。一个局部的计算也许能够用传统的 alpha-beta 搜索来解决，好比征子的计算，要看 6 线有没有对手的棋子，另外即便有对手的棋子，也要看位置的高低，这样的计算 DCNN 是无法解决的，须要靠计算。
AlphaGo
终于轮到主角上阵了，您可能不耐烦了。不过有了前面的基础，理解 AlphaGo 就容易多了，这里咱们主要分析 AlphaGo 的创新点。
Policy Network & Value Network
上图是 AlphaGo 所使用的两个网络以及训练过程。和以前的工做比，除了 Policy Network 以外，AlphaGo 多了一个 Value Network。
Policy Network 咱们经过以前的介绍以及了解到了，它的做用是 tree Policy 时候的 Node Selection。（rollout 阶段不能使用 Policy Network，由于 DCNN 的计算速度相对于 Simulation 来讲太慢，因此 AlphaGo 又训练了一个简单的 Rollout Policy，它基于一些 local 的 pattern 之类的 feature 训练了一个线性的 softmax）。
那么 Value Network 又是作什么用的呢？这个 Value Network 就是咱们以前说的不少工做都“回避”的问题——给一个局面打分，就是以前在象棋和 minimax 部分讨论的局面的估值函数，只不过 AlphaGo 是使用深度强化学习 (deep reinforcment learning) 学习出来，而不是像 Deep Blue 或者其它象棋程序那样是人工提取的 feature 甚至手工调整权重（固然 Deep Blue 是不少年前的工做了，如今也有用深度强化学习来搞国际象棋的，好比这篇论文《Giraffe: Using Deep Reinforcement Learning to Play Chess》）。
前面在讨论 Tian 等人的工做时咱们也分析过了，光用 Move Prediction 的软件大局观还不错，可是局部的战术就比较差，由于局部的战术更多靠计算，人类也是这样。围棋因为估值函数比较困难，因此大都是用 MCTS 搜索到游戏结束。可是 MCTS 若是盲目搜索（使用随机的 default policy 去 rollout/playout）确定很差，使用各类领域知识来缩小 rollout 的范围就很是重要。前面咱们也看到，传统的 MCTS 只能到 2d 的水平，而用 DCNN 的 tree policy 的 MCTS 就能到 5d 的水平（若是 default policy 若是能用 DCNN 指导确定更好，惋惜 DCNN 的速度太慢）。
SL Policy Network & Rollout Policy 的训练
这个和以前介绍的差不了太多。AlphaGo 相比以前多了Rollout Policy，以前的 Rollout Policy 大可能是使用手工编制的 pattern，而AlphaGo 用训练 Policy Network 相同的数据训练了一个简单的模型来作 Rollout。
训练数据来自 3 千万的 KGS 的数据，使用了 13 层的 CNN，预测准确率是 57%，这和以前 Tian等人的工做是差很少的。
RL Policy Network & Value Network 的训练
以前训练的 SL Policy Network 优化的目标是预测走法，做者认为人类的走法会在不少 promising 的走法里选择，这不必定能提升 AlphaGo 的下棋水平。为何？文中没有解释，我我的认为多是一个局面（尤为是优点）的状况下有不少走法，有保守一点可是保证能赢一点点的走法，也有激进但须要算度准确的但能赢不少的走法。这取决于我的的能力（好比官子能力怎么样）和当时的状况（包括时间是否宽裕等等）。
因此 AlphaGo 使用强化学习经过本身跟本身对弈来调整参数学习更适合本身的 Policy。
具体的作法是当前版本跟以前的某一个版本（把以前全部版本都保留和不是用最近的一个能够避免 overfitting）对弈，对弈的走法是根据 Policy Network 来选择的，而后根据结果调整参数。这个公式用天然语言来描述就是最终得分 z_t（获胜或者失败），在 t 时刻局面是 s_t 我选择了走法 a_t，P (a_t|s_t) 表示局面 s_t 时选择走法 a_t 的几率，就像神经网络的反向传播算法同样，损失 z_t（或者收益）是要由这个走法来负责的。咱们调整参数的目的就是让这个几率变小。再通俗一点说就是，好比第一步咱们的模型说必须走马（几率是 1），那么若是最终输棋，咱们复盘时可能会以为下次走马的几率应该少一点，因此咱们调整参数让走马的几率小一点（就是这个梯度）。
RL Policy Network 的初始参数就是 SL Policy Network 的参数。最后学到的 RL Policy Network 与 SL Policy Network 对弈，胜率超过 80%。
另外 RL Policy Network 与开源的 Pachi 对弈（这个能到 2d 也就是业余两段的水平），Pachi 每步作 100,000 次 Simulation，RL Policy Network 的胜率超过 85%，这说明不用搜索只用 Move Prediction 能超过 2d 的水平。这和 Tian 等人的工做的结论是一致的，他们的 darkforest2 也只用 Move Prediction 在 KGS 上也能到 3d 的水平。
Value Network 的强化学习训练
一个局面在 policy p 下的估值公式。用通俗的话说就是：在 t 时刻的局面是 s，而后咱们用 p 来下棋直到游戏结束，咱们重复不少次，而后求平均的得分。固然，最理想的状况是咱们能知道双方都是最优策略下的得分，惋惜咱们并不知道，因此只能用咱们以前学到的 SL Policy Network 或者 RL Policy Network 来估计一个局面的得分，而后训练一个 Value Network V(s)。前面咱们也讨论过了，RL Policy Network 胜率更高，而咱们学出来的 Value Network 是用于 rollout 阶段做为先验几率的，因此 AlphaGo 使用了 RL Policy Network 的局面评估来训练 V(s)。
V(s) 的输入时一个局面，输出是一个局面的好坏得分，这是一个回归问题。AlphaGo 使用了和 Policy Network 相同的参数，不过输出是一个值而不是 361 个值（用 softmax 归一化成几率）。
上面的公式说明：V(s) 的参数 theta 就是简单的用梯度降低来训练
不过用一盘对局的全部 (s,v(s)) 训练是有问题的，由于同一盘对局的相邻的局面是很是相关的，相邻的局面只差一个棋子，全部很是容易 overfitting，致使模型“记住”了局面而不是学习到重要的 feature。做者用这样的数据训练了一个模型，在训练数据上的 MSE 只有 0.19，而在测试数据上是 0.37，这明显 overfitting 了。为了解决这个问题，做者用 RL Policy Network 本身跟本身对局了 3 千万次，而后每一个对局随机选择一个局面，这样获得的模型在训练数据和测试数据上的 MSE 是 0.226 和 0.234，从而解决了 overfitting 的问题。
MCTS + Policy & Value Networks
上面花了大力气训练了 SL Policy Network,Rollout Policy 和 Value Network，那么怎么把它们融合到 MCTS 中呢？
一次 MCTS 的 Simulation 能够用上图来讲明，下文加黑的地方是这三个模型被用到的地方。
首先每一个节点表示一个局面，每一条边表示局面+一个合法的走法(s,a)。每条边保存 Q(s,a)，表示 MCTS 当前累计的 reward，N(s,a) 表示这条边的访问次数，P(s,a) 表示先验几率。
Selection
每次 Simulation 使用以下的公式从根节点开始一直选择边直到叶子节点（也就是这条边对于的局面尚未 expand）。
Q(s_t,a) 就是 exploit term，而 u(s_t,a) 就是 explore term，并且是于先验几率 P(s,a) 相关的，优先探索 SL Policy Network 认为好的走法。
Evaluation
对于叶子节点，AlphaGo 不只仅使用 Rollout（使用 Rollout Policy）计算得分，并且也使用 Value Network 打分，最终把两个分数融合起来：
Backup
n 次 Simulation 以后更新统计量（从而影响 Selection），为何是 n 次，这涉及到多线程并行搜索以及运行与 GPU 的 Policy Network 与 Value Network 与 CPU 主搜索线程通讯的问题
Expansion
一个边的访问次数超过必定阈值后展开这个边对应的下一个局面。阈值会动态调整以是的 CPU 和 GPU 的速度能匹配，具体下一节咱们讨论 AlphaGo 的实现细节再说明
AlphaGo 的水平
a 图是用分布式的 AlphaGo，单机版的 AlphaGo，CrazyStone 等主流围棋软件进行比赛，而后使用的是 Elo Rating 的打分。
做者认为 AlphaGo 的水平超过了 FanHui（2p)，所以 AlphaGo 的水平应该达到了 2p（不过不少人认为目前 Fanhui 的水平可能到不了 2p）。
b 图说明了 Policy Network Value Network 和 Rollout 的做用，作了一些实验，去掉一些的状况下棋力的变化，结论固然是三个都很重要。
c 图说明了搜索线程数以及分布式搜索对棋力的提高，这些细节咱们会在下一节再讨论，包括 AlphaGO 的架构能不能再 scalable 到更多机器的集群从而提高棋力。
AlphaGo 的真实棋力
由于 3 月份 AlphaGo 要挑战李世石，因此你们都很关心 AlphaGo 到底到了什么水平。固然它的真实水平只有做者才能知道，我这里都是根据一些新闻的推测。并且从文章提交 Nature 审稿到 3 月份比赛还有一段不短的时间，AlphaGo能不能还有提升也是很是关键。这里我只是推测一下在文章提交 Nature 时候 AlphaGo 的棋力。至于 AlphaGo 棋力可否提升，咱们下一节分析实现细节时再讨论（假设总体架构不变，系统能不能经过增长机器来提升棋力）。
网上不少文章试图经过 AlphaGo 与 fanhui 的对局来估计 AlphaGo 的棋力，我本人不敢发表意见。我只是搜索了一些相关的资料，主要是在弈城上一个叫 DeepMind的 帐号的对局信息来分析的。
好比这篇《金灿佑分析 deepmind 棋谱认为 99%与谷歌团队相关》。做者认为这个帐号就是 AlphaGo。若是猜想正确的话，AlphaGo 当时的棋力在弈城 8d-9d 直接，换成咱们经常使用的 ranking system 的话大概也就是 6d-7d（业余 6 段到 7 段）的水平，若是发挥得好，最多也许能到 1p 的水平，打败 fanhui 也有必定合理性（不少人认为 fanhui 目前实际水平可能已经没有 2p 了，那算 1p 的话也差很少）。
知乎上也有不少讨论，以及这篇《陈经：谷歌围棋算法存在缺陷》，均可以参考。
AlphaGo 的实现细节 Search Algorithm
和以前相似，搜索树的每一个状态是 s，它包含了全部合法走法(s,a)，每条边包含以下的一些统计量：
P(s,a) 是局面 s 下走 a 的先验几率。Wv(s,a) 是 simulation 时 value network 的打分，Wr(s,a) 是 simulation 时 rollout 的打分。Nv(s,a) 和 Nr(s,a) 分别是 simulation 时 value network 和 rollout 通过边 (s,a) 的次数。Q(s,a) 是最终融合了 value network 打分和 rollout 打分的最终得分。
rollout 会模拟一个节点屡次这比较好理解。为何 value network 会给同一个节点打分屡次呢？并且对于一个 DCNN 来讲，给定一个固定的输入 (s,a) P(a|s) 不该该是相同的值吗，计算屡次有什么意义吗？
我刚开始看了半天也没明白，后来看到 Symmetries 那部分才明白。原来 AlphaGo 没有像以前的工做那样除了对称的问题，对于 APV-MCTS（Asynchronous Policy and Value MCTS) 算法，每次通过一个须要 rollout 的 (s,a) 时，会随机的选择 8 个对称方向中的一个，而后计算 p(a|s)，所以须要平均这些 value。计算 Policy Network 的机器会缓存这些值，因此 Nv(s,a) 应该小于等于 8。
Selection(图 a)
从根节点开始使用下面的公式选择 a 直到叶子节点。
图片描述Q(s,a) 初始值为 0，后面 Backup 部分会讲怎么更新 Q(s,a)。
如今咱们先看这个公式，第一部分 Q(s,a) 是 exploit term，第二部分是 explore term。这个公式开始会同时考虑 value 高的和探索次数少的走法，但随着 N(s,a)的增长而更倾向于 value 高的走法。
Evaluation(图c)
叶子节点 sL 被加到一个队列中等到 value network 计算得分（异步的），而后从 sL 开始使用 rollout policy 模拟对局到游戏结束。
Backup(图 d)
在 Simulation 开始以前，把从根一直到 sL 的全部的 (s,a) 增长 virtual loss，这样能够防止（准确的说应该是尽可能不要，原文用的词语是 discourage，固然若是其它走法也都有线程在模拟，那也是能够的）其它搜索线程探索相同的路径。
上面的给 (s,a) 增长 virtual 的 loss，那么根据上面选择的公式，就不太会选中它了。
当模拟结束了，须要把这个 virtual loss 去掉，同时加上此次 Simulation 的得分。
此外，当 GPU 算完 value 的得分后也要更新：
最终算出Q(s,a):
Expansion(图 b)
当一条边 (s,a) 的访问次数 Nr(s,a)【提个小问题，为何是Nr(s,a)而不是Nv(s,a)？】超过一个阈值 Nthr 时会把这条边的局面（其实就是走一下这个走法）s’=f(s,a) 加到搜索树里。
初始化统计量：Nv(s’,a)=0, Nr(s’,a)=0, Wv(s’,a)=0, Wr(s’,a)=0, P(s’,a)=P(a|s’)
因为计算 P(a|s’)须要在 GPU 中利用 SL Policy Network 计算，比较慢，因此先给它一个 place-holder 的值，等到 GPU 那边算完了再更新。
这个 place-holder 的值使用和 rollout policy 相似的一个 tree policy 计算出来的（用的模型了 rollout policy 同样，不过特征稍微丰富一些，后面会在表格中看到），在 GPU 算出真的 P(a|s’) 以前的 selection 都是先用这个 place-holder 值，因此也不能估计的太差。所以 AlphaGO 用了一个比 rollout feature 多一些的模型。
Expansion 的阈值 Nthr 会动态调整，目的是使得计算 Policy Network 的 GPU 可以跟上 CPU 的速度。
Distributed APV-MCTS 算法
一台 Master 机器执行主搜索（搜索树的部分），一个 CPU 集群进行 rollout 的异步计算，一个 GPU 集群进行 Policy 和 Value Network 的异步计算。
整个搜索树都存在 Master 上，它只负责 Selection 和 Place-Holder 先验的计算以及各类统计量的更新。叶子节点发到 CPU 集群进行 rollout 计算，发到 GPU 集群进行 Policy 和 Value Network 的计算。
最终，AlphaGo 选择访问次数最多的走法而不是得分最高的，由于后者对野点(outlier)比较敏感。走完一步以后，以前搜索过的这部分的子树的统计量直接用到下一轮的搜索中，不属于这步走法的子树直接扔掉。另外 AlphaGo 也实现了 Ponder，也就是对手在思考的时候它也进行思考。它思考选择的走法是比较“可疑”的点——最大访问次数不是最高得分的走法。AlphaGo 的时间控制会把思考时间尽可能留在中局，此外 AlphaGo 也会投降——当它发现赢的几率低于 10%，也就是 MAXaQ(s,a) < -0.8。
AlphaGo 并无想常见的围棋那样使用 AMAF 或者 RAVE 启发，由于这些策略并无什么用处，此外也没有使用开局库，动态贴目(dynamic komi)等。
Rollout Policy
使用了两大类 pattern，一种是 response 的 pattern，也就是上一步走法附近的 pattern（通常围棋不少走法都是为了“应付”对手的走子）；另外一种就是非 response 的 pattern，也就是将要走的那个走法附近的 pattern。具体使用的特征见下表。Rollout Policy 比较简单，每一个 CPU 线程每秒能够从空的局面（开局）模拟 1000 个对局。
横线之上的 feature 用来 rollout，全部的 feature 用来计算 place-holder 先验几率。
Symmetries
前面在讲 Search Algorithm 讲过了。
SL Policy Network
SL Policy Network 使用了 29.4 million 局面来训练，这些局面来自 KGS 6d-9d 的 16 万个对局。使用了前 1million 用来测试，后面的 28.4million 用来训练。此外进行了旋转和镜像，把一个局面变成 8 个局面。使用随机梯度降低算法训练，训练的 mini-batch 大小是 16。使用了 50 个 GPU 的DistBelief（并无使用最新的 Tensorflow），花了 3 周的时间来训练了 340million 次训练步骤（每一个 mini-batch 算一个步骤？）
RL Policy Network
每次用并行的进行 n 个游戏，使用当前版本（参数）的 Policy Network 和以前的某一个版本的 Policy Network。当前版本的初始值来自 SL Policy Network。而后用 Policy Gradient 来更新参数，这算一次迭代，通过 500 次迭代以后，就认为获得一个新的版本把它加到 Pool 里用来和当前版本对弈。使用这种方法训练，使用 50 个 GPU，n=128，10,000 次对弈，一天能够训练完成 RL Policy Network。
Value Network
前面说了，训练的关键是要本身模拟对弈而后随机选择局面而不是直接使用 KGS 的对局库来避免 overfitting。
AlphaGo 生成了 3 千万局面，也就是 3 万次模拟对弈，模拟的方法以下：
随机选择一个 time-step U~unif{1,450}
根据 SL Policy Network 走 1，2，… , U-1 步棋
而后第 U 步棋从合法的走法中随机选择
而后用 RL Policy Network 模拟对弈到游戏结束
被做为一个训练数据加到训练集合里。
这个数据是
的一个无偏估计。
最后这个 Value Network 使用了 50 个 GPU 训练了一周，使用的 mini-batch 大小是 32。
Policy/Value Network使用的Features
其实和前面 Tian 的差不太多，多了两个征子相关的 feature，另外增长了一个常量 1 和常量 0 的 plane。
最后一个 feature 是 value network 用的，由于判断局面得分时要知道是谁走的，这个很关键。
神经网络结构 Policy Network
13 层从 CNN，输入时 19*19*48，第一个 hidden 层把输入用零把输入 padding 成 23*23，而后用 k 个 5*5 的 filter，stride 是 1。
2 到 12 层首先用零把输入 padding 成 21*21，而后使用 k 个 5*5 的 filter，stride 依然是 1。
最后一层用一个 1*1 的 filter，而后用一个 softmax。
比赛用的 k=192，文章也作了一些实验对比 k=128,256,384 的状况。
Value Network
14 层的 CNN，前面 12 层和 Policy Network 同样，第 13 层是一个 filter 的卷积层，第 14 层是全链接的 Relu 激活，而后输出层是全链接的 tanh 单元。
不一样分布式版本的水平比较，使用的是 Elo rating 标准。
总结
从上面的细节来看，神经网络的训练其实用的时间和机器很少，真正非资源的仍是在搜索阶段。
最强的 AlphaGo 使用了 64 个搜索线程，1920 个 CPU 的集群和 280 个 GPU 的机器（其实也就二十多台机器）
以前咱们讨论过度布式 MCTS 时说过，MCTS 很难在多机上并行，因此 AlphaGo 仍是在一台机器上实现的 LockFree 的多线程并行，只不过 Rollout 和神经网络计算是在 CPU 和 GPU 集群上进行的。Google 的财力确定不仅二三十台机器，因此分布式 MCTS 的搜索才是最大的瓶颈。若是这个能突破，把机器堆到成百上千台应该仍是能提升很多棋力的。
我我的估计在 3 月与李世石的对弈中这个架构可能还很难有突破，能够加强的是 RL Policy 的自对弈学习，不过这个提高也有限（不然不会只训练一天就中止了，估计也收敛的差很少了）
因此我我的的观点是 3 月份要打败李世石仍是难度比较大的。
人生的棋
以前咱们讨论的都是彻底信息的两人的零和博弈游戏。用的 minimax 也是假设对手都是走最优的走法，但实际比赛中可能并不是如此。
好比为了争胜，咱们可能走一些冒险的策略，这个策略下若是对手走到最佳的走法咱们可能会输。可是因为局面复杂，稍有不慎可能就会走错，那么咱们的目的就达到了。
还有就是多人的博弈，好比斗地主，咱们可能还得对多个对手或者队友建模。好比地主最后一张牌是否要炸，还得看队友的接牌能力。
又好比你陪领导玩斗地主，另一我的明显目的是来给领导送钱的，那么你的策略可能也须要调整。
这可能就是现实世界和人工智能的差异了。有些事情，机器永远也不会懂，好比人生。
对于人生，每一个人都像一颗棋子，那么谁是下棋者呢，他又是和谁在下棋呢？
咱们在下棋的时候更多的考虑是全局的利益，好比用一个兵卒换一个马炮咱们会很是开心，可是做为要牺牲的兵卒来讲呢？一将功成万骨枯。
人生如棋，落子无悔。等到游戏结束的时候咱们来复盘，才能发现当年犯下的错误，不过毕竟于事无补，只能给后人一些经验教训罢了。
http://www.chinaz.com/news/2016/0310/511070_2.shtml
http://blog.sciencenet.cn/blog-1225851-962097.html