第四局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的范围里面，所以地平线效应的可能性比较低。
知乎上有高人啊，
现在的比分是 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]