财迷心窍 发表于 2016-3-14 20:07:11

第四局AlphaGo乱下的原因分析

本帖最后由 财迷心窍 于 2016-3-14 20:33 编辑

尽管小李第四局赢了,但我还是要说他这盘棋我完全看不下去,估计下过棋的同学们都有同感吧。
挖确实是妙手,但其实如果电脑应对正确还是要输——这点周睿羊、王檄在讲棋的时候就说了——开劫让白棋联络就是了,然后右边黑棋跑出来。
第四局电脑的败因是自己,在挖后连续的莫名其妙的走棋。
第四局最大的意义是证明了,电脑的计算也是有极限会漏算,再次证明了围棋和国际象棋的不同。电脑象棋是真正的算清了,电脑围棋不是。
我最赞赏的柯洁的说法,可以输棋但别跪舔电脑——特别是对于职业棋手。其实第一局第二局的左下,电脑都明显出问题手导致亏损。

关于第四局电脑为何会走,田渊栋博士(facebook 围棋程序DarkForest的作者,和狗属于同类的新一代电脑围棋程序)的观点如下:


注:田博士以前分析过,AlphaGo有两个走子策略,一个是自学习的新一代程序DCNN?,一个是加强的上一代程序(快速走子?)。新策略是学习的产品类似于靠棋感下棋,而老策略类似于靠计算下棋,而根据局面不同新策略和老策略是有权重调整的。单独使用两个策略都可以到达弈城3D的水平。我的理解是AlphaGo是靠两个走子策略提供思路,靠蒙特卡罗搜索进行计算,而那个3000万盘训练的估值网络Value Network是为了简化搜索时间提高搜索质量用的。

著作权归作者所有。
商业转载请联系作者获得授权,非商业转载请注明出处。
作者:田渊栋
链接:http://zhuanlan.zhihu.com/yuandong/20644427
来源:知乎

第四局李世石的78手L11挖被大家誉为“神之一手”,在DarkForest的策略网络输出里排第31位,而J11靠排第10位。因此我觉得可能是AlphaGo没有算到这一步。如果对方下了一手机器没算到的棋,则蒙特卡罗(MCTS)搜索树会清空,然后重新开始搜索,不应该会太快做出结论。李喆六段告诉我K10这一手是秒下,那有可能是时间管理子系统在搜索树清空时有程序上的漏洞,因此过早地将搜索结果返回了。MCTS在一开始搜索的时候,因为模拟次数不够多,每步的胜率方差非常大,所以返回一个不够好的着法如K10是很正常的(在DarkForest里面这着排在前四)。这个比较容易修正。 另一种可能是,AlphaGo的估值网络出了问题。因为估值网络的权重是0.5,而不管快速走子从一个局面开始重复了多少次,它的权值也是0.5。对于一个局面,估值网络只得到一个数,而从这个局面往下走子,走多后会得到很多个数,统计上应该更为重要,但是AlphaGo不是这样想的,两边各自算得胜率后直接对半平均了。所以如果估值网络对某个局面得到的结果不对,则会极大地影响对该局面的胜率估计。注意这里得到很多个数的原因是按照文章,叶结点在积累了一定盘数后(40)才展开,而不是第一次访问就展开,以提高DCNN的效率。DarkForest没有用到估值网络,在L11的挖之后正确地返回了L12和L10这两个应手,据李喆六段说,都是正确的应手,这间接支持了这个推断。AlphaGo在87手之后才意识到自己已经大大落后,可能也是由于同样的问题,比如说把右边的黑大龙看成活的。那为什么估值网络会出问题呢?可能是用于训练估值网络的自学习(Self-Play)的样本分布有盲点。为了提高样本生成速度,AlphaGo的自学习样本是通过用两个纯粹的DCNN互搏来生成的(完全没有搜索),而DCNN下出来的棋因为是纯模式识别,一个大问题是死活不正确,经常是在死棋里面下子。如果黑白两方都犯了死活不分的毛病,然后一方比如说白侥幸胜了,那估值网络就会认为方才白的死棋局面是好的。这样估值网络就会染上同样毛病,在中盘复杂的对杀局面中判断失误。若是这种情况就不好处理,AlphaGo下一局可能还会有同样的问题。这里可以看到,电脑本身也不是靠穷举来下棋的,围棋毕竟太复杂,每一步都要剪枝,离当前局面近的仔细剪(用DCNN),离当前局面远的快速剪(快速走子),直到终局得到胜负为止。剪枝的好坏直接关系到棋力的高低,DCNN只是一个有大局观的非常好的剪枝手段,它的盲点也会通过败着反映出来。关于DCNN+MCTS打劫。首先因为MCTS是全局估计分数的,劫争本身和其它局面在程序看来没有本质区别,都只是一步棋而已。劫的特殊性在DarkForest上表现为碰到有劫可提的情况时,DCNN经常会以非常高的概率(0.8以上)返回提劫这一手。可能的原因是,劫点是作为单独的特征输入的,所以DCNN学习到了它和输出(提劫)的强关联性。这样在MCTS搜索时会强烈偏向这一手。这在很多情况下是正确的,但有时劫很小可以不予理会,或者碰到两个或者多个劫需要放弃一个,那“遇劫必提”的偏向性就会给搜索带来麻烦。有时连环劫电脑反复提就是这个原因。AlphaGo可能会有这个问题,或者是反向的问题(比如说提劫概率很小),这样在下棋时大家就会感觉到它在避免开劫,或者在含劫的变化中计算失误。关于地平线效应(Horizon Effect)。国象的AI里面会有这个效应,比如说只搜索10步,计算到别人的后被自己的后吃了结束,然后用简单的加和法估计下盘面发现自己多个后特别爽,觉得这个分支特别好。其实再往下走一步自己的后也被别人吃了,或者掉入陷阱,这样就误算盘面价值。但是围棋因为每次模拟都是走到底的,可能前30步是用DCNN,之后就是用快速走子,虽然走子质量上有差距,但是大方向上不会错,所以地平线效应在某种程度上是减弱了。而且这次AlphaGo的失误在20步以内,应该还在DCNN的范围里面,所以地平线效应的可能性比较低。


财迷心窍 发表于 2016-3-14 22:59:53

知乎上有高人啊,

现在的比分是 0:2,小李的状态很不佳,这次也完全可能被零封。但目前的 AlphaGo,可能并非人类不可战胜。

UPDATE:第四盘,电脑盲点出来了。我在下面说过,逻辑性是 DNN 的盲点,可以误导 MCTS 的展开,某些怪招是走入了错误的变化,而不全是什么神之一手天外飞仙。同时 AlphaGo 也会出现盲区。正是如此。之前我在这里还说 Google 很鸡贼,不公开 AlphaGo 失败的棋谱,也不开放任何对弈,避免显示自己的弱点,下面不时有人出来喷“凭什么要求Google公布”云云,言辞非常不客气,我就编辑掉并关闭评论了,各位现在理解了吗。许多做机器学习的朋友不了解电脑围棋,如果真研究过近年来的电脑围棋文献,会发现和跑个 ImageNet 的程度不一样,需要的逻辑知识更丰富。电脑围棋未来会完美战胜人类棋手(且必须加入更多Domain-dependent的方法),但恐怕不是今天。NOT TODAY。我们看看 Google DeepMind 的 Hassabis 怎么说吧:
@demishassabis 26m26 minutes ago
Lee Sedol is playing brilliantly! #AlphaGo thought it was doing well, but got
confused on move 87. We are in trouble now...
@demishassabis 7m7 minutes ago
Mistake was on move 79, but #AlphaGo only came to that realisation on around
move 87
这就正是我在此所说的“电脑吃惊”。其实即使对于AI研究,最完美的情况也并不是碾压李世石,而是我们看到人机之间的此消彼长,互相学习。围棋是一个极其有趣的问题,希望看到它能为AI研究贡献更多世界的奥秘,而不是如此轻易地被彻底解决。


AlphaGo的核心是 MCTS + DNN + RL。之前没有说 RL,但它其实是很有意思的部分,因为在从前的对弈程序研究中,RL 的效果一般并不好。RL 的弱点是 overfit,也就是虽然小道消息公布目前这个版本的 AlphaGo 面对去年的战胜樊麾的版本的胜率是 100%,估计 ELO 分已经超出 4000,号称天下无敌,但这里面实际是会有很大的水分的可能。在其他棋类的例子上,有这样的例子: RL 后的程序秒杀 RL 前的程序,但面对其它不同棋风程序的胜率反而略微降低。下面我们看 MCTS 和 DNN 的缺陷。
================================================

身为人类,恰好对于电脑围棋、General Game Playing、机器学习有过一点研究,希望在此为形势不利的一方支招。冀望研究AI的朋友们此时都开放一点,告诉公众和棋手,目前AI所存在的缺陷,而不是有意无意地只想搞个大新闻。很理解Google等公司作为利益相关者,大谈AI的长处,不会自揭短板。Google这次取得的成就也非常伟大。但即便从公司利益出发,现在为人类棋手支招,事实上也有利于进一步促进AI水平的提高。如果人类不在最佳状态,那么对于机器的测试又如何能测试出机器的极限?下文如有错漏,请各位不吝补充。

1) 复杂的劫争、复杂的对杀(Semeai)、"看似有利实际不成立的棋"、"看似不利实际合理的棋"(做过对弈程序的朋友会清楚,这些反应出来就是"漏看","过分乐观")等等,一言喻之,所谓 trap,一直是蒙特卡洛树搜索(MCTS)甚至对弈树搜索的软肋,如 International Conference on Computers and Games 2013 论文集中,多篇都讨论过这类缺陷的表现。

AlphaGo 通过运用深度神经网络评估和选点、tree与playout的知识共享、历史知识共享、暴力增加搜索速度和节点数,等等,弥补了大部分"漏看"的情况,但"漏看"仍会存在。对于围棋,尤其如此。

这首先来自于,由于对弈树太大,所以MCTS在每一层都会尽快选中少数点集中搜索。如果一开始的选点全部或大部分错了,根据合格的MCTS的设计,仍然可以在后续搜索中找回正确的选点,但需要的时间会很多,有可能就会漏看;其次,在playout中,也同样会有覆盖不够的盲点,影响局面评估。

一个具体的例子。AlphaGo 在局势均衡时,出现的怪招,如果是在短兵相接的情况下出现的,一部分会是算路极深的妙手,但也会有一些属于这样的误算(就是没看到后续双方的正解,而是陷入了错误的变化),表现出来就是损棋。后文会继续谈电脑的怪招问题。

2) 同样,深度神经网络(DNN)也存在盲点,且这种盲点属于此方法的根本问题,现阶段无可能解决。下面是一个普通人不了解的事情:DNN与目前的绝大多数机器学习算法,所学习到的,其实都是统计知识,而不是精确的逻辑知识。

举个图像识别的例子。给DNN一群人在一起的照片,DNN现在可以数出里面有多少个人,且有时比人类还要强。比如只露了某个身体部位,也可能识别出来。但是,也永远会有人类看上去一目了然,但DNN识别错误的情况,因为DNN完全没有办法学到什么是人的精确定义!

这方面经典的文章是 Deep neural networks are easily fooled: High confidence predictions for unrecognizable images ,下图左边精心构造的噪音图像会被DNN以非常高的置信度判定为存在某某物品(有趣的是,可以在右边看到,我们也可以构造出“有点像这个物品”的假图像,说明DNN学到了许多东西,只是不精确)。

如果我们拿到 AlphaGo 的网络权重数据,同样可以构造许多类似的欺骗局面。但是,我们拿不到。不过,目前看来,这种问题已经在对局中显现了。

一个典型的例子是布局部分,所谓的"走错定式"。

与普通人的想象不一样,DNN虽然学习过无数局棋谱,但是绝不会简单地死记硬背棋谱。这是DNN的胜利,它有能力大致学习到棋谱中所反应的更有趣的精神,如布局的方向选择,某个局部和另一个局部之间的联系,等等;而另一方面,DNN所学习到的围棋知识,也存在着同样的"不精确性"与"逻辑性缺陷",正如雾里看花。

那么,布局走错次序、走错位置、不同布局的杂糅等等,在了解的人看来,就很可能是DNN的签名(MCTS也有类似的缺陷,因为在它看来布局的许多不同位置的胜率都差不多,结果实际行棋就会有不精细之处)。人类所应该做的,就是不要想太多,按照棋理与布局理论给予还击(是的,人类的布局理论一定还有缺陷,但以 AlphaGo 目前的水准,恐怕还达不到这一层)。 ——我的观点有了专业人士的赞同

如果不了解这件事,把电脑想得太神秘莫测,只求稳,如小李在第二局的一些应对,则会正中电脑的下怀,把自己绕进去了。关于此,柯棋渣的直播和孟主播的复盘 围棋TV_极速点评之人机大战特别版都说得很好。

电脑的某些怪招,也同样是这么来的,不一定都是什么天外飞仙。此前举的复杂劫争、对杀等等,也存在精密的逻辑成分(如每个劫材的精确大小、先后手,全棋盘各个局部之间的复杂关系,等等),会是电脑的弱项。另一方面,官子部分虽然也要精确算,但以 AlphaGo 目前的运算能力恐已足以暴力搜索解决(团队应该会在此时接入精确的搜索树而非蒙特卡洛树),不能指望它出错了(看似出错的地方,都是棋局大幅领先时MCTS的签名而已,不改变胜负)。

3) 关键的部分来了。怎么应对 AlphaGo?

单从对局来说:

第一,自己不能出错,每步棋要达到 80 分的质量。 因为电脑抓漏抓棋形缺陷等等的能力有时会很强(就看MCTS是否刚好考虑到了那个变化),不能给它机会。

第二,如果看到 AlphaGo 的怪招(特别是棋局开局与中前期的怪招),先想想是否是自己看漏了,如果似乎不是,那么不要把它想得太高明,应该用正常的方法反击,而不要心虚求稳。这样才可慢慢积聚起优势。否则就是安乐死,仿佛不知道输在哪里。

第三,同样,AlphaGo的行棋有时会有不精细之处。发现时,都应积极抓住处理。

第四,一些需要了解的地方:

1. 从 AlphaGo 的 DNN 设计来看,它会略微更喜欢走离 自己上一手 / 对方上一手 很近的点。

2. 目前的MCTS算法,电脑容易略微高估自己,低估人的战斗能力和活棋能力。如果人表现得好,电脑是会吃惊的(评论有朋友问什么叫电脑吃惊,这个做过对弈程序的朋友都知道,就是起初认为局势一片大好的评估函数,突然就开始急转直下了,哈哈)。

3. 许多人都已经知道,目前的电脑围棋程序在领先的时候都会求稳,下缓手(因为实际测试,这样的胜率确实更高)。

以上是对局的方面。而更重要的事情是在对局之外。

上面是媒体报道使用的一张图片。这张图片看了令人觉得挺难过。李世石和从前的卡斯帕罗夫一样,现在面对的心理压力,前所未有的巨大。希望能有机器学习专家找到李世石,介绍 AlphaGo 的算法和可能存在的缺陷,让他能够调整状态,奋力再战!

此次对局,是 AlphaGo 在暗,人类棋手在明。AlphaGo 看过所有人类棋手的棋谱,而人类棋手却始终蒙在鼓里。有些不厚道的是,Google 故意放烟雾弹,只公布了去年的较弱的版本的对局谱,并且绝不谈最新版本的棋力情况,有心理战的嫌疑。

这并不改变 Google 取得了伟大成就的事实,不过也留下了口实。心理因素,对于人类而言太重要了。打个比方,如果换成爱虐电脑,与机器斗争经验丰富的罗洗河,局面会是如何,会比较有趣。

如果 Google 不是仅仅为了追求宣传效应,那么建议在此次或此一系列对局事件后,开放与 AlphaGo 对弈的接口,让所有人类顶尖棋手前来实验。即使收费,也会有许多人愿意。

人类的学习能力,在许多方面仍然远强于机器学习。通过反复测试,完全可能试出 AlphaGo 的缺陷,学会 AlphaGo 学习棋谱与自我对局所生成的经验(DNN 里面的经验也是有办法直接显示给人类的,不是纯粹的黑箱)。这与象棋的情况不同。围棋很特殊,可以说是最适合人类的一种棋类,比象棋等要适合得多。樊麾在与 AlphaGo 多次对弈后长棋了,其他人类棋手也会有类似的发现。电脑能进步,人也一样。一个强大的对手,可以推动围棋的新发展。

(要找到AlphaGo 的缺陷所在,最直接的,是看 AlphaGo 自我对弈的棋谱。自我对弈,就总有一方会输,那么就看看是如何输的。说起这个,许多人可能不知道,对局程序里有大量的内部信息,比如程序估计的选点,每个点的胜率,以及每个点的变化图解。如果再略微分析一下,还可以显示程序认为哪里是局势的关键点,哪里已经尘埃落定,哪里是未来可能争斗最激烈的区域,以及DNN的形式判断理由,等等等等。如果 Google 愿意把这些数据显示出来,那就更有意思了。)

行文至此,东方渐白。我相信在围棋这个毕竟是人类创造的棋盘游戏上,机器在不久的将来会彻底战胜人类,断绝一切幻想,正如现在的象棋,但我只想说,NOT TODAY!如果您同意本文的意见,请记得给本文 up vote 一下吧,对,就是点一下左上角那个向上的剪头。

何况,这只是 AI 漫漫长路的一个小小驿站。别的不说,前沿的理论数学的证明,很难想象现在的 AI 怎么理解,更不谈怎么推导。代数拓扑和代数几何有希望。数论最难。更简单的例子,AI 什么时候能写出我们在这里的回帖?目前的电脑架构,恐怕希望不大。生物计算机,量子计算机,分子计算机,可能才是正解。不说了,先睡了...

彭博 于 2016年3月11日晨


补充:

对于电脑围棋关注过很多年,大部分这方面的文献都读过,也写过程序。此处写下的 MCTS 和 DNN 的漏洞,既是许多文献的意见,也是自己的经验所得。如果哪位有不同意见,很欢迎指正。

但是,这里的所有评论,居然没有一个人正面谈论这个问题(如这些漏洞是否存在,该如何解决),一群人去争论些边边角角的杂事,如 Google 是否应该公开权重公开棋谱之类,有没有可能解读出权重里面的信息等等,各路人瞎吵,令人无语。这是新一代的中医vs西医之争吗?信噪比太低了,全清空罢。

最后,点名批评之前评论中的许多人,学了一点机器学习课本知识,就开始 show,太可怕了。世界很复杂,我们都还得虚心学习一个。实际的问题千变万化,不是课本可以涵盖。是的,我对于喜欢人身攻击的人就是这么不留情。讨论问题很好,有些人一上来就人身攻击,这是什么路数?

我还搜索了一下,好像很多人都在知乎吐槽喷子,还有人总结说喷子最喜欢抓住他们懂的那点东西死缠烂打。比如 MCTS 这么简单,但对于机器博弈又极其重要的东西,他们很多就不懂,很多课本也不教,所以他们就啥都不会说。关于本文说的主要论题,他们也啥都不会说(真令人失望),就会反复纠缠一些细节。很多时候,我特别特别不想回他们的评论,因为感觉在免费教他们。但是看他们在下面吧,又觉得很容易误导观众(他们会互相点赞!很牛的),怎么办呢?现在我学会了,就是拉黑+关闭评论......

作者:Peng Bo
链接:https://www.zhihu.com/question/39906815/answer/90194733
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
页: [1]
查看完整版本: 第四局AlphaGo乱下的原因分析