【转载】AlphaGo原理解析
这些天都在没日没夜地关注一个话题，谷歌人工智能程序AlphaGo（国内网友亲切地称为“阿尔法狗”）以5:0击败欧洲职业围棋冠军樊麾二段，并在和世界冠军的比赛中2:0领先。 什么！！ 19年前计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，现在计算机又要来攻克围棋了吗！？ 虚竹在天龙八部里自填一子，无意中以“自杀”破解“珍笼”棋局，逍遥子方才亲传掌门之位。难道以后“阿尔法狗”要出任逍遥派掌门了？ 1933年，东渡日本19岁的吴清源迎战当时的日本棋坛霸主、已经60岁的本因坊秀哉，开局三招即是日本人从未见过的三三、星、天元布阵，快速进击逼得对方连连暂停“打卦”和弟子商量应对之策。随后以“新布局”开创棋坛新纪元。难道阿尔法狗会再造一个“新新布局”？ 作为一个关心人工智能和人类命运的理科生，近些天刷了好些报道，记者们说“阿尔法狗是个‘价值神经网络’和‘策略神经网’络综合蒙特卡洛搜索树的程序”，但我觉得光知道这些概念是不够的。我想看看“阿尔法狗”的庐山真面目。 准备好棋盘和脑容量，一起来探索吧？ 围棋棋盘是19x19路，所以一共是361个交叉点，每个交叉点有三种状态，可以用1表示黑子，-1表示白字，0表示无子，考虑到每个位置还可能有落子的时间、这个位置的气等其他信息，我们可以用一个361 * n维的向量来表示一个棋盘的状态。我们把一个棋盘状态向量记为s。 当状态s下，我们暂时不考虑无法落子的地方，可供下一步落子的空间也是361个。我们把下一步的落子的行动也用361维的向量来表示，记为a。 这样，设计一个围棋人工智能的程序，就转换成为了，任意给定一个s状态，寻找最好的应对策略a，让你的程序按照这个策略走，最后获得棋盘上最大的地盘。 如果你想要设计一个特别牛逼惊世骇俗的围棋程序，你会从哪里开始呢？对于在谷歌DeepMind工作的黄士杰和他的小伙伴而言，第一招是： 蒙特卡洛搜索树（Monte-Carlo Tree Search）是一种“大智若愚”的方法。面对一个空白棋盘S0，黄士杰的老师Coulum最初对围棋一无所知，便假设所有落子方法分值都相等，设为1。然后扔了一个骰子，从361种落子方法中随机选择一个走法a0。Coulum想象自己落子之后，棋盘状态变成S1，然后继续假设对手也和自己一样二逼，对方也扔了一个筛子，随便瞎走了一步，这时棋盘状态变成S2，于是这两个二逼青年一直扔骰子下棋，一路走到Sn，最后肯定也能分出一个胜负r，赢了就r记为1，输了则为0，假设这第一次r=1。这样Coulum便算是在心中模拟了完整的一盘围棋。 Coulum心想，这样随机扔骰子也能赢？运气不错啊，那把刚才那个落子方法（S0,a0）记下来，分值提高一些： 我刚才从（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()来扔。 如果某一步被随机到很多次，就应该主要依据模拟得到的概率而非P_human。 所以P_human的初始分会被打个折扣： 这样就既可以用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匹配起来就得到了一系列，设定目标为最后的总得分r，我们可以训练一个神经网络去拟合在状态s下，做动作a的总得分。下一次玩游戏的时候，我们就可以根据当前状态s，去选择最后总得分最大的动作a。通过不断玩游戏，我们对下总得分的估计就会越来越准确，游戏也玩儿得越来越好。 打砖块游戏有一个秘诀：把球打到墙的后面去，球就会自己反弹得分。强化学习的程序在玩了600盘以后，学到这个秘诀：球快要把墙打穿的时候评价函数v的分值就会急剧上升。 机器学习的开山鼻祖Samuel早在1967年就用自对弈的方法来学习国际跳棋[7]，而之前的蒙特卡洛搜索树也是一个自对弈的过程。但是现在黄士杰不仅有一个从人类对弈中学习出的P_human这样一个高起点，而且有一个神经网络可以从对弈样本中学习，有理由相信这次会有更好的结果。 黄士杰准备在MCTS框架之上融合局面评估函数v()。这次还是用P_human作为初始分开局，每局选择分数最高的方案落子，下到第L步之后，改用P_human_fast把剩下的棋局走完，同时调用v(SL)，评估局面的获胜概率。然后按照如下规则更新整个树的分数： 前两项和原来一样，如果待更新的节点就是叶子节点，那局面评估分就是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)的越来越精确的估计，但即使引入了“左右互搏”来强化学习，黄士杰和团队仍然做了大量的细节工作。所以只有一步一个脚印，面对挑战不断拆解，用耐心与细心，还有辛勤的汗水，才能取得一点又一点的进步，而这些进步积累在一起，终于让计算机达到并超过了人类职业选手的水平。
新版“阿尔法围棋”的发展阶段有哪些？
英国“深度思维”公司开发出了“阿尔法围棋”。该公司将“阿尔法围棋”的发展分为四个阶段:第一个版本是“阿尔法围棋-樊”,它在2015年战胜欧洲围棋冠军樊麾,标志着人工智能首次战胜人类职业棋手第二个版本是“阿尔法围棋-李”,它在2016年战胜曾多次夺得世界冠军的韩国棋手李世石,标志着人工智能战胜人类顶级棋手;第三个版本是“阿尔法围棋-大师”,在今年战胜现在世界排名第一的柯洁,并在与多位有世界冠军头衔的人类棋手“群战”中完胜。第四个版本,即最新的“阿尔法围棋-零”摆脱了这个限制,研究人员没有给它除棋盘和棋子之外的任何输入,它完全是“从零开始”,自己与自己对弈,通过更为优秀的算法,取得飞速进步。开始学习围棋3天后,“阿尔法围棋-零”就以100比0的成绩战胜了“阿尔法围棋-李”;40天后,它又战胜了在所有人类高手看来已不可企及的“阿尔法围棋-大师”。研究人员认为,从需要预先输入人类知识,到能完全依靠自己摸索,“阿尔法围棋”的进步标志着人工智能的巨大突破,因为这意味着人工智能可以更好地进入对它来说本是一片空白的领域。“深度思维”公司首席执行官哈萨比斯说,他希望人工智能的这种进步能够被用于分析蛋白质结构、设计新材料等领域,为人们的生活带来积极有益的影响。
到底是什么让AlphaGo变得如此成功
AlphaGo这个系统主要由几个部分组成：走棋网络(Policy Network)，给定当前局面，预测/采样下一步的走棋。快速走子(Fast rollout)，目标和1一样，但在适当牺牲走棋质量的条件下，速度要比1快1000倍。估值网络(Value Network)，给定当前局面，估计是白胜还是黑胜。蒙特卡罗树搜索(Monte Carlo Tree Search，MCTS)，把以上这三个部分连起来，形成一个完整的系统。我们的DarkForest和AlphaGo同样是用4搭建的系统。DarkForest较AlphaGo而言，在训练时加强了1，而少了2和3，然后以开源软件Pachi的缺省策略 (default policy)部分替代了2的功能。以下介绍下各部分。1、走棋网络走棋网络把当前局面作为输入，预测/采样下一步的走棋。它的预测不只给出最强的一手，而是对棋盘上所有可能的下一着给一个分数。棋盘上有361个点，它就给出361个数，好招的分数比坏招要高。DarkForest在这部分有创新，通过在训练时预测三步而非一步，提高了策略输出的质量，和他们在使用增强学习进行自我对局后得到的走棋网络(RL network)的效果相当。当然，他们并没有在最后的系统中使用增强学习后的网络，而是用了直接通过训练学习到的网络(SL network)，理由是RL network输出的走棋缺乏变化，对搜索不利。有意思的是在AlphaGo为了速度上的考虑，只用了宽度为192的网络，而并没有使用最好的宽度为384的网络(见图2(a))，所以要是GPU更快一点(或者更多一点)，AlphaGo肯定是会变得更强的。所谓的0.1秒走一步，就是纯粹用这样的网络，下出有最高置信度的合法着法。这种做法一点也没有做搜索，但是大局观非常强，不会陷入局部战斗中，说它建模了“棋感”一点也没有错。我们把DarkForest的走棋网络直接放上KGS就有3d的水平，让所有人都惊叹了下。可以说，这一波围棋AI的突破，主要得益于走棋网络的突破。这个在以前是不可想像的，以前用的是基于规则，或者基于局部形状再加上简单线性分类器训练的走子生成法，需要慢慢调参数年，才有进步。当然，只用走棋网络问题也很多，就我们在DarkForest上看到的来说，会不顾大小无谓争劫，会无谓脱先，不顾局部死活，对杀出错，等等。有点像高手不经认真思考的随手棋。因为走棋网络没有价值判断功能，只是凭“直觉”在下棋，只有在加了搜索之后，电脑才有价值判断的能力。2、快速走子那有了走棋网络，为什么还要做快速走子呢？有两个原因，首先走棋网络的运行速度是比较慢的，AlphaGo说是3毫秒，我们这里也差不多，而快速走子能做到几微秒级别，差了1000倍。所以在走棋网络没有返回的时候让CPU不闲着先搜索起来是很重要的，等到网络返回更好的着法后，再更新对应的着法信息。其次，快速走子可以用来评估盘面。由于天文数字般的可能局面数，围棋的搜索是毫无希望走到底的，搜索到一定程度就要对现有局面做个估分。在没有估值网络的时候，不像国象可以通过算棋子的分数来对盘面做比较精确的估值，围棋盘面的估计得要通过模拟走子来进行，从当前盘面一路走到底，不考虑岔路地算出胜负，然后把胜负值作为当前盘面价值的一个估计。这里有个需要权衡的地方：在同等时间下，模拟走子的质量高，单次估值精度高但走子速度慢；模拟走子速度快乃至使用随机走子，虽然单次估值精度低，但可以多模拟几次算平均值，效果未必不好。所以说，如果有一个质量高又速度快的走子策略，那对于棋力的提高是非常有帮助的。为了达到这个目标，神经网络的模型就显得太慢，还是要用传统的局部特征匹配(local pattern matching)加线性回归(logistic regression)的方法，这办法虽然不新但非常好使，几乎所有的广告推荐，竞价排名，新闻排序，都是用的它。与更为传统的基于规则的方案相比，它在吸纳了众多高手对局之后就具备了用梯度下降法自动调参的能力，所以性能提高起来会更快更省心。AlphaGo用这个办法达到了2微秒的走子速度和24.2%的走子准确率。24.2%的意思是说它的最好预测和围棋高手的下子有0.242的概率是重合的，相比之下，走棋网络在GPU上用2毫秒能达到57%的准确率。这里，我们就看到了走子速度和精度的权衡。和训练深度学习模型不同，快速走子用到了局部特征匹配，自然需要一些围棋的领域知识来选择局部特征。对此AlphaGo只提供了局部特征的数目(见Extended Table 4)，而没有说明特征的具体细节。我最近也实验了他们的办法，达到了25.1%的准确率和4-5微秒的走子速度，然而全系统整合下来并没有复现他们的水平。我感觉上24.2%并不能完全概括他们快速走子的棋力，因为只要走错关键的一步，局面判断就完全错误了；而图2(b)更能体现他们快速走子对盘面形势估计的精确度，要能达到他们图2(b)这样的水准，比简单地匹配24.2%要做更多的工作，而他们并未在文章中强调这一点。在AlphaGo有了快速走子之后，不需要走棋网络和估值网络，不借助任何深度学习和GPU的帮助，不使用增强学习，在单机上就已经达到了3d的水平(见Extended Table 7倒数第二行)，这是相当厉害的了。任何使用传统方法在单机上达到这个水平的围棋程序，都需要花费数年的时间。在AlphaGo之前，Aja Huang曾经自己写过非常不错的围棋程序，在这方面相信是有很多的积累的。3、估值网络AlphaGo的估值网络可以说是锦上添花的部分，从Fig 2(b)和Extended Table 7来看，没有它AlphaGo也不会变得太弱，至少还是会在7d-8d的水平。少了估值网络，等级分少了480分，但是少了走棋网络，等级分就会少掉800至1000分。特别有意思的是，如果只用估值网络来评估局面(2177)，那其效果还不及只用快速走子(2416)，只有将两个合起来才有更大的提高。我的猜测是，估值网络和快速走子对盘面估计是互补的，在棋局一开始时，大家下得比较和气，估值网络会比较重要；但在有复杂的死活或是对杀时，通过快速走子来估计盘面就变得更重要了。考虑到估值网络是整个系统中最难训练的部分(需要三千万局自我对局)，我猜测它是最晚做出来并且最有可能能进一步提高的。关于估值网络训练数据的生成，值得注意的是文章中的附录小字部分。与走棋网络不同，每一盘棋只取一个样本来训练以避免过拟合，不然对同一对局而言输入稍有不同而输出都相同，对训练是非常不利的。这就是为什么需要三千万局，而非三千万个盘面的原因。对于每局自我对局，取样本是很有讲究的，先用SL network保证走棋的多样性，然后随机走子，取盘面，然后用更精确的RL network走到底以得到最正确的胜负估计。当然这样做的效果比用单一网络相比好多少，我不好说。一个让我吃惊的地方是，他们完全没有做任何局部死活/对杀分析，纯粹是用暴力训练法训练出一个相当不错的估值网络。这在一定程度上说明深度卷积网络(DCNN)有自动将问题分解成子问题，并分别解决的能力。另外，我猜测他们在取训练样本时，判定最终胜负用的是中国规则。所以说三月和李世石对局的时候也要求用中国规则，不然如果换成别的规则，就需要重新训练估值网络(虽然我估计结果差距不会太大)。至于为什么一开始就用的中国规则，我的猜测是编程非常方便(我在写DarkForest的时候也是这样觉得的)。4、蒙特卡罗树搜索这部分基本用的是传统方法，没有太多可以评论的，他们用的是带先验的UCT，即先考虑DCNN认为比较好的着法，然后等到每个着法探索次数多了，选择更相信探索得来的胜率值。而DarkForest则直接选了DCNN推荐的前3或是前5的着法进行搜索。我初步试验下来效果差不多，当然他们的办法更灵活些，在允许使用大量搜索次数的情况下，他们的办法可以找到一些DCNN认为不好但却对局面至关重要的着法。一个有趣的地方是在每次搜索到叶子节点时，没有立即展开叶子节点，而是等到访问次数到达一定数目(40)才展开，这样避免产生太多的分支，分散搜索的注意力，也能节省GPU的宝贵资源，同时在展开时，对叶节点的盘面估值会更准确些。除此之外，他们也用了一些技巧，以在搜索一开始时，避免多个线程同时搜索一路变化，这部分我们在DarkForest中也注意到了，并且做了改进。5、总结总的来说，这整篇文章是一个系统性的工作，而不是一两个小点有了突破就能达到的胜利。在成功背后，是作者们，特别是两位第一作者David Silver和Aja Huang，在博士阶段及毕业以后五年以上的积累，非一朝一夕所能完成的。他们能做出AlphaGo并享有现在的荣誉，是实至名归的。从以上分析也可以看出，与之前的围棋系统相比，AlphaGo较少依赖围棋的领域知识，但还远未达到通用系统的程度。职业棋手可以在看过了寥寥几局之后明白对手的风格并采取相应策略，一位资深游戏玩家也可以在玩一个新游戏几次后很快上手，但到目前为止，人工智能系统要达到人类水平，还是需要大量样本的训练的。可以说，没有千年来众多棋手在围棋上的积累，就没有围棋AI的今天。
阿尔法围棋究竟什么样
人工智能“阿尔法围棋”（AlphaGo）挑战顶尖围棋手李世石一事广受瞩目，引发众多讨论。与人类决战智慧之巅的“阿尔法围棋”究竟什么样？
让我们从名字开始来了解它。 AlphaGo由两部分组成，Alpha对应希腊语的首字母，也就是常说的“阿尔法”，Go是日语中对围棋的称呼。因此，许多人称之为“阿尔法围棋”，还有人根据发音亲昵地叫它“阿尔法狗”或“阿狗”。
它出生在英国。2010年，德米什·哈萨比斯等人在伦敦创建了“深度思维”公司，该公司开发出“阿尔法围棋”软件。 2014年，美国谷歌公司收购了“深度思维”，因此它现在也许可以算是美国籍。
那“阿尔法围棋”究竟长什么样？很可惜，“深度思维”公司的官方网站说，该软件的代码并不开放下载。
内行总是能看出些门道。美国脸书公司“黑暗森林”围棋软件的开发者田渊栋在网上发表分析文章说：“‘阿尔法围棋’这个系统主要由几个部分组成：1，走棋网络，给定当前局面，预测／采样下一步的走棋。2，快速走子，目标和1一样，但在适当牺牲走棋质量的条件下，速度要比1快1000倍。 3，估值网络，给定当前局面，估计是白胜还是黑胜。 4，蒙特卡罗树搜索，把以上这3个部分连起来，形成一个完整的系统。 ”
