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