AlphaGo两次提前30分钟确信必胜

隔壁他二叔

AlphaGo两次提前30分钟确信必胜

2016-03-12

                               

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

　　比赛之前根据论文里的技术来分析AlphaGo能否战胜李世石，我们可能太过关注深度神经网络而忽视了MCTS的重要性，尤其是它在残局里的重要性。前天比赛结束后我们重新审视了AlphaGo的两大核心技术，认为残局是AlphaGo制胜的关键。昨天晚上看到新闻说AlphaGo在比赛结束前就确认了必胜的结果，更加证实了这个想法可能是对的，所以想把这个观点分享出来。
　　下面是具体的内容：
　　经过第二局比赛之后，我已经变得悲观了。因为我觉得在残局的计算能力上人类与alphago的差距太大了。
　　1. 上帝眼中的围棋
　　从数学上来讲，围棋有个最优的走法，也就是用mini-max搜索到游戏结束时的一条最优路径(也许有多条，但至少有一条)，然后就能知道最优的情况下黑棋胜白棋多少目(也许是白棋胜黑棋？直觉上和经验上来说黑棋先手是占优的，但是好像也没有谁证明过这个问题？)，那么黑棋对白棋的贴目就应该是这个最优值。
　　2. AlphaGo的残局计算
　　和人类相比，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步凭感觉就能找到最优解(或者次优解与最优解的差别很小，但感觉上围棋不像象棋。象棋如果优势，比如比对方多两个兵，那么走一两步缓手(只要别太差，让人吃子了)，最终还是很可能会赢(当然也有某些特殊的局面必须要走的精确)。但围棋如果稍微几个缓手，优势就丢了很多。
　　所以如果残局计算力差太多的话，前中盘有差不太多的话，那么人类是不太可能胜利的。
　　3. AlphaGo的开局呢？
　　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目棋了。
　　4. 那人类的开局呢？
　　我觉得人类超一流的高手可能比alphago强那么一点点(毕竟alphago只是用大量一流高手的对局)，但是在上帝看来可能比随机下棋只是好那么一点点。所以经常会出现这样的情况：这个布局之前很流行，大家都认为很好，但过了若干年后又认为不好了。
　　5. 人类/机器是怎么自学提高自己呢？
　　理论上如果计算和存储资源足够，比如最后10步可以精确计算，那么我们就可以存储所有10步之内结束的局面的结果(有点像残局库)，但是这个局面太多，只能用一个模型来“压缩”这些结果，提取一些重要的feature来代表局面，这些feature可能就是我们说的势啊，厚薄等等(当然也可能机器学到的feature完全不同)。假设这个模型能99%的准确率预测最终得分。然后再计算11步的所有局面(用的是模型来打分，因此准确率99%)，然后又得到更多的训练数据，重新调整模型，这个时候可能就只有98%的准确率了(因为局面变多)，再加上之前累计的误差，总的准确率是99% * 98%，...，然后不断的反向传播到开局。如果这么一算，我们开局第一步能算准的概率基本就是0了。
　　所以我们人类这么几千年这样学习得出的一些经验会经常被推翻，几十年前认为好的开局可能现在认为不好，但过几十年可能又认为好。说白了就是我们离上帝的距离有些太远。
　　6. AlphaGo强在哪？
　　从上面的AlphaGo原理的分析来看，AlphaGo比人类强的也只是在计算力上面，但是围棋的分支因子太大，步数又多，而且估值函数太复杂，所以只能在残局上体现出计算力的优势。而开局甚至中局计算力都不行，因此早期基于mini-max(alpha-beta)的搜索根本不行，后来出现了MCTS，但开局和中局亏得太多，所以基本没到残局就游戏结束了。
　　AlphaGo的特点是开局和中局模拟人类，从上帝的角度来说不一定好，但是至少在人类高手看来还可以(即使会下一些人类认为“业余”的走法，但也不至于太离谱)，只要不在残局前崩盘，输得不太多，那么残局它总是能追回来。
　　7. MCTS和深度神经网络(CNN)哪个重要？
　　因为深度神经网络非常火，大家可能觉得它是AlphaGo能赢的关键，其实我觉得不是这样。

　　根据Tian yuandong和AlphaGo的论文，如果不做任何搜索，只是根据“棋感”(其实就是估值函数)，CNN最好能达到KGS 3d的水平，我估计也就业余1段的水平。而MCTS算法在没有Value Network的情况下在9*9的棋盘上能战胜人类高手，其实这也间接印证了AlphaGo在残局的实力是搜索(计算)起重要作用。原来基于搜索的软件在开局和中局就崩盘或者亏太多了，所以就不能体现搜索的优势了，另外AlphaGo使用了Value Network，这保证即使搜索有一些小问题，从人类学来的棋感也能保证不至于偏差太大。
　　AlphaGo的特点是：开局和中局依靠人类的棋谱学习棋感(可以理解为背棋谱，不过比死记硬背好一点，有一定的泛化能力)，然后残局的计算能力碾压人类，就好像以前的李昌镐，前面看不出什么好来，但官子你就是下不过他，没办法，不服不行。
　　8. AlphaGo能成为围棋上帝吗？
　　我认为AlphaGo离上帝(最优解)其实还是差得老远的，尤其是开局和中局。其实这也间接的说明人类在开局上其实也离最优解差得太远。人类几千年也下不了多少盘棋(而且水平越差的人的棋对整个人类围棋没有太大帮助)，我们认为一个开局是否好，只能更加水平相似的高手下这个布局的胜率来推测它的好坏。但如果我们在最后50步的时候误差就很大，那么往前传播时积累的误差就更大了，我们可能经常忽略了一个看起来不好的走法，而这个走法可能就是“支持”这个开局的关键。
　　当然AlphaGo的残局比人厉害，那么就可以通过自己对弈来学习，然后往前传播误差。
　　但是由于这个问题本质是NP的，即使它用了MCTS的方法来避免“明显不好”的走法。但是由于围棋的复杂性，可能某个“看起来不好”的走法可能恰恰是一个关键的胜负手呢？另外根据之前的分析，即使每步都能99%的准确，那么往前推100步准确的可能性也基本是0了。
　　因此如果人类不能解决NP问题，不能提出计算能力超过图灵机的计算模型，那么人类制造的机器也是不太可能解决这个问题的(当然这只是我的直觉，不知道能不能数学上证明)。不过即使这样，能制造和人类一样，虽然质不能超越人类，但量能超越人类的机器也是很有意义的。
　　9. 怎么能验证你的这些看法？
　　新闻说AlphaGo提前30分钟认为自己必胜，这是个很强有力的证据，我们看看30分钟还有多少棋，可以估算AlphaGo自认为能算准多少步。
　　方法一，看接下来3盘棋，如果都是人类觉得李世石走得还可以或者稍微领先，最后都翻盘，那么就是一个证据。
　　方法二，人类和AlphaGo下开局和中局，然后到了AlphaGo认为可以比较准确计算的时候让它来评估好坏。
　　方法三，找一盘人类认为可以但是被翻盘的局面，然后人类和AlphaGo换个颜色来下，如果还是AlphaGo获胜，那么也是一个证据。
　　方法四，看AlphaGo对自己的打分，是不是有出现过认为自己落后，后来又领先。
　　那么作为人类选手，应该怎么和AlphaGo下棋呢？
　　我觉得可以试试的策略就是中前期利用自己超一流的棋感尽量占优，然后残局导向简单变化的局面。开局不要被怪招吓到，我们认为是弱手就要严厉打击，我觉得机器的开局不怎么样。当然我不懂围棋，只是从程序员的角度的个人看法。

feilia557

就看看，不说话。