AlphaGo两次提前30分钟确信必胜，残局计算能力的差距或是关键

按：作者李理，出门问问NLP工程师。

（via wildfirepr.com）

比赛之前根据论文里的技术来分析AlphaGo能否战胜李世石，我们可能太过关注深度神经网络而忽视了MCTS的重要性，尤其是它在残局里的重要性。前天比赛结束后我们重新审视了AlphaGo的两大核心技术，认为残局是AlphaGo制胜的关键。昨天晚上看到新闻说AlphaGo在比赛结束前就确认了必胜的结果，更加证实了这个想法可能是对的，所以想把这个观点分享出来。

下面是具体的内容：

经过第二局比赛之后，我已经变得悲观了。因为我觉得在残局的计算能力上人类与alphago的差距太大了。

从数学上来讲，围棋有个最优的走法，也就是用mini-max搜索到游戏结束时的一条最优路径（也许有多条，但至少有一条），然后就能知道最优的情况下黑棋胜白棋多少目（也许是白棋胜黑棋？直觉上和经验上来说黑棋先手是占优的，但是好像也没有谁证明过这个问题？），那么黑棋对白棋的贴目就应该是这个最优值。

和人类相比，AlphaGo的残局计算有点太Bug了。

比如说AlphaGo可以计算出最后50步棋（这里只是假设的步数，而且MCTS不是完全搜索所有可能，而是根据先验概率和搜索结果调整策略，搜索“重要”的子树），而人类只能计算最后30步棋。那么即使在第50步的时候人类选手领先10目（已经去掉贴目），那么也只是说人类在100%精确地走好每一步的时候才能胜。但是围棋很复杂，也许走第50步时走个次优的走法，领先就变成了8目，如果再走得缓一点，可能就只领先6目了。而因为人类只能计算最后30步棋，那么这50-31步的一点点失误可能都会造成最终的失利。

当然我对围棋不懂，也许围棋没有想象的复杂，它的估值函数还是比较平滑的，或者在这50-31步中大部分局面都很容易直接找到最优解，但是某些局面就困难一些（也就是关键的点）。但是我觉得这样的关键点还是很多的，因为围棋和象棋不同，围棋随便挪动一个棋子，对全局都是有影响的。象棋虽然在某些特殊情况下一个棋子的位置会影响最后的胜负，但是大部分局面下走一步闲棋影响都不大，尤其是双方棋子较少的中残局。

比如说人类高手的判断局面的准确率是alphago的90%（90%能不计算凭“感觉”直接找到当前局面的最优解，1是AlphaGo的准确度，上帝可能是2？），那么20步全部正确的概率只有0.12（相对于Alphago来说）。如果两个人残局的计算能力差太远，而且积累的优势不是太多的话，除非碰到的残局很简单，第50步-31步凭感觉就能找到最优解（或者次优解与最优解的差别很小，但感觉上围棋不像象棋。象棋如果优势，比如比对方多两个兵，那么走一两步缓手（只要别太差，让人吃子了），最终还是很可能会赢（当然也有某些特殊的局面必须要走的精确）。但围棋如果稍微几个缓手，优势就丢了很多。

所以如果残局计算力差太多的话，前中盘有差不太多的话，那么人类是不太可能胜利的。

AlphaGo的计算有两个关键，一个是Value Network，也就是给定一个局面，不计算，直接判断它的好坏（也就是上帝的视角来看，大家都下得完美，黑棋能比白棋多/少多少目），另外一个就是通过不断的蒙特卡罗模拟比赛到游戏结束(rollout)。

这其实和人类的搜索有些类似：比如当前局面下有10种走法，我们根据好坏(alphago是rollout Policy，这个需要非常快）给它计算一个概率，比如0.4，0.3，0.1，.....，那么它就会以较大的概率选择0.4的走法来尝试，当然也有0.3的概率走第二个。之后每一步都是一样的方法选择走法直到游戏结束，然后就能判断这个游戏结束局面的准确值。比如我方胜利了，那么就会backup回去，让我们下次选择0.4的概率更大一点，也许变成了0.45，0.28， 0.09，...。经过大量的模拟，我们就能知道选择第一个走法的是否“好”。

这两个得分value network（评估局面）和rollout（蛮力计算）是加权平均起来的，论文里好像说最优值是0.5？也就是两个因素都很重要。

所以可以看出，越到后面残局，变化就越少，模拟的步数也越少，就越准确。而开局的话rollout肯定不准，那么更多的是靠人类高手棋谱对局学出来的“大局观”，而越到后面计算就越准了，它就起主要作用了（那理论上是不是两者的权重动态调整会更好？）

所以我觉得AlphaGo的开局在上帝看了应该也是挺弱的，也许上帝在它下了一步之后就呵呵一笑：你输了1目棋了。

我觉得人类超一流的高手可能比alphago强那么一点点（毕竟alphago只是用大量一流高手的对局），但是在上帝看来可能比随机下棋只是好那么一点点。所以经常会出现这样的情况：这个布局之前很流行，大家都认为很好，但过了若干年后又认为不好了。

理论上如果计算和存储资源足够，比如最后10步可以精确计算，那么我们就可以存储所有10步之内结束的局面的结果（有点像残局库），但是这个局面太多，只能用一个模型来“压缩”这些结果，提取一些重要的feature来代表局面，这些feature可能就是我们说的势啊，厚薄等等（当然也可能机器学到的feature完全不同）。假设这个模型能99%的准确率预测最终得分。然后再计算11步的所有局面（用的是模型来打分，因此准确率99%），然后又得到更多的训练数据，重新调整模型，这个时候可能就只有98%的准确率了（因为局面变多），再加上之前累计的误差，总的准确率是99% * 98%，...，然后不断的反向传播到开局。如果这么一算，我们开局第一步能算准的概率基本就是0了。

所以我们人类这么几千年这样学习得出的一些经验会经常被推翻，几十年前认为好的开局可能现在认为不好，但过几十年可能又认为好。说白了就是我们离上帝的距离有些太远。

从上面的AlphaGo原理的分析来看，AlphaGo比人类强的也只是在计算力上面，但是围棋的分支因子太大，步数又多，而且估值函数太复杂，所以只能在残局上体现出计算力的优势。而开局甚至中局计算力都不行，因此早期基于mini-max(alpha-beta)的搜索根本不行，后来出现了MCTS，但开局和中局亏得太多，所以基本没到残局就游戏结束了。

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!