AlphaGo Zero的原理分析

1、计算机处理围棋复杂的能力压倒了人类,AlphaGo Zero技术原理分析 陈经 2017年10月,围棋AI是可以理解的 约20篇围棋AI分析文章在观察者网、新浪棋牌发表。 与应氏杯冠军唐韦星九段、吴肇毅九段共同解说AI对人的棋局。 赛前独家预测到了李世石第四局战胜AlphaGo的方式，分析出了AlphaGo的弱点。 通俗分析，不需要太多算法专业知识。,AlphaGo Zero为什么很精彩？ 需要了解围棋AI的历史，围棋对计算机曾经多么困难。 2015-2017年AlphaGo数次取得巨大进步，战胜人类，靠的是什么，突破与难点在哪。 AlphaGo Zero从零知识开始学习成功，意义是什么？,围

2、棋是一个优美的数学问题 规则极简单，只需要2条极简单的行棋规则即可。 1. 气尽提子 2.禁止同形再现（否则程序陷入死循环了，需要打劫）,围棋是一个优美的数学问题 由行棋规则可以推出博弈规则： 1. 双方占地，能生存的棋子和围住的空归本方。都不下了就终局数目。 2. 双方游戏目标是多占地。至此已经可以进行游戏与优化了，是一个博弈问题。 3. 博弈论的均衡解：双方最完美的行棋达成的平衡。 数学问题：双方分享N*N个点，双方博弈均衡值是多少？N=5已经解决。 五路棋盘均衡解：黑方25个点全得。七路棋盘均衡解推测为黑29子白20子（李喆六段）。,围棋是一个优美的数学问题 围棋是宇宙数学中天然存在的游

3、戏，人类只是发现（非发明）了它。 胜负规则是人类强加的：贴目。 1. 比赛棋盘19*19共361个交叉点：黑占182、183、184、185、186. 2. 双方数子结果的和一定为361： 白占179、178、177、176、175. 3. 现在黑184则负，185则胜，这是为了分出胜负强加的。 4. AI认为，中国规则数子是自然的，容易程序实现，AI是中国规则最坚定支持者。 5. 日韩规则数目，定义不完全甚至是错误的，是人强加的，AI无法理解。 日韩规则：强行规定盘角曲四是死棋。“劫尽棋亡”逻辑错误，双活需要实战解决。,围棋是一个优美的数学问题 东西方对围棋不同的理解 东方（中日韩）：围棋是

4、文化艺术，是竞技，代表国家荣耀。爱好者普遍认为，围棋有深奥的战略与战术，能开发智力，非常有意思。专业与业余高手很多。 西方：围棋是数学问题。国际象棋爱好者多，能领会围棋的优美与深奥的人少。主要把围棋看成数学问题，围棋高手极少。,“国际象棋是一种仅仅局限于这个世界的游戏，而围棋则有些不象是从地球上诞生的。如果哪一天我们发现有一种天外文明和我们玩同一种游戏，那一定是围棋，决不会有任何疑问。”-伊曼纽尔拉斯克，1894年26岁时成为国际象棋历史上第二位世界冠军，五次卫冕。 1909年研究围棋一年后，伊曼纽尔拉斯克被日本高手让九子吃光。但是他说：“围棋是数学思维的理想游戏，而东方从来没有第一流的数学家

5、，我敢肯定我们能够在围棋上战胜他们”。他的本意是去日本学棋，打败日本高手，因第一次世界大战未能成行。,博弈论与计算机算法对国际象棋与围棋的理解：完全博弈树 开盘是根节点，按不同的下一招，分出多个分支。 叶子节点不再需要分支：国际象棋死棋或和局，围棋终局数子。 所有可能的局面都会出现在这个完全博弈树中。 策梅罗定理（1913）：每个节点都有确定的博弈结论，黑方必胜、白方必胜、或和棋。 国际象棋：应该是双方和棋（顶级AI超过90%和棋），但不是证明。 围棋：如果均衡贴目，双方和棋（如黑184白177的均衡结果）。偏离均衡贴目，一方必胜（贴7目半执白有优势，贴5目半执黑优势）。,国际象棋局面数：约1

6、046 围棋合法局面数：简单计算是3361。精确数值是171位数（2015）。 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935 局面数都是天文数字，到现在都不可能破解，只能想办法设计实际的搜索算法。国际跳棋已经破解。,国际象棋等传统棋类算法的核心概念：局面评估函数 局面评估函数可以静态计算（仅依赖当前局

7、面），不用往前搜索。 局面评估函数和真实的局面情况，存在误差，如将黑胜的结果误判为白胜。好的函数误差小，适应性强（没有明显bug，常见局面不出错）。 从一个节点往下搜索是改善这个节点评分的办法：多算胜，少算不胜。 利用局面评估函数进行搜索优化，是棋类博弈算法的核心工作。如Alpha-Beta剪枝算法，意思是损失巨大的分支就不用搜索了。,国际象棋AI战胜人类棋手：符合人类直觉的传统算法 局面评估剪枝，搜索优化。将搜索树规模降到计算机算力之内。 搜索代码+人类知识库开局库。硬件工程师+软件算法工程师+专业棋手。 国际象棋AI的算法和人类弈棋思维差不多，但算得快、算得深。 计算机国际象棋80、90年

8、代就有相当实力，因为没围棋那么复杂。 现在人类还有希望和AI下和，国际象棋的复杂人还算能应付。,人类高手应对围棋复杂的办法：优秀的直觉 围棋高手识别局面，根据局部棋形产生直觉选点：很多情况只此一手。 围棋高手的计算结果一般就是第一直觉。10秒的快棋水平与慢棋相差不大。 国际象棋高手更依赖于计算与评估，围棋局面评估极难，人类高手靠直觉。 围棋高手强调计算：局部死活、局部得失的验证，是对第一直觉的验算。 围棋高手的局势评估会起关键作用，但并不是每一招都进行。感觉需要了才进行数目、手割之类的评估。评估不准确，不同棋手观点对立。 计算、局势评估是顶尖高手之间的竞争。高手靠直觉随手下也能胜低手，柯洁15

9、秒快棋让二子胜职业低段，让先胜世界冠军。,围棋的复杂并不仅是局面数众多：深层次的复杂 1. 非线性（子力位置稍不同就局势大变） 2. 死活，局部死活、大龙对杀。弃子，吃了未必胜。 3. 打劫，两手劫、万年劫、多重劫争。 4. 复杂死活、复杂劫争、大对杀、大弃子、耍大龙等局面，是围棋艺术必不可少的精华。 围棋的局面评估极其复杂困难，人类没有什么好办法,2006年前的早期围棋AI: 棋力极弱 代表程序：手谈，中山大学化学退休教授陈志行用汇编语言开发。 业余高手都能让10多个子，引发bug甚至20个子以上（GnuGo）。 类似国际象棋搜索算法框架，但开局库、分支策略、局面评估各方面都差。 致命弱点：

10、人写代码评估局面，棋子对周边的影响累加等简单错误逻辑。 次要弱点：根据棋形产生候选点，时有错漏。 搜索效果极差：冠军程序手谈是不搜索的！ 多年无进展，业界认为围棋AI难度极高，是完全信息博弈问题的终极挑战。,带来研发活力的突破：蒙特卡洛树形搜索 写代码评估局势极其困难，死路一条，强写出来也极弱。 革命性的思想：蒙特卡洛树形搜索（MCTS，Monte-Carlo Tree Search，2006） 到叶子结点就roll out（黑白轮流快速下完数子出胜负结果）。 终局精确数子+多次随机模拟 = 局势评估（胜率） 人不可能用这种方法下棋，计算机特有的优势。但快速下完也易出bug。 全局思维、多次模

11、拟统计结果，大局观已经强于人类不可靠的直觉。,Remi Coulom,基于MCTS的围棋AI的实力 代表程序日本的Zen，可以战胜一般业余棋手，不如业余高手（2011）。 业余棋手感到兴奋，对围棋AI兴趣上升，积极对战（KGS）。 2015年11月，连笑七段让四子、五子轻松战胜计算机围棋冠军Dolbram。 职业棋界兴趣不大，认为AI战胜人类还很遥远。聂卫平、俞斌：100年。 围棋AI研发者信心上升，感觉到了希望。乐观认为10-20年。,围棋AI战胜人类的导火索：深度学习 图像识别领域的深度学习出现突破。（DCNN，2012-2015） 将棋盘理解成图像，建模人类高手直觉，直接产生少数候选点-

12、策略网络。 不需要写代码，用几十万局的棋局样本深度学习训练出来（2015）。 策略网络是图像识别软硬件技术进步的自然发展，高水平围棋AI的开发变容易了。 人类高手脑神经为什么能产生优秀的直觉选点？不清楚。AI的神经网络为什么能模仿人类的优秀直觉？黑盒子。解释不清，但就是管用。,围棋AI战胜人类的最重要最根本技术突破：价值网络 真正疯狂的想法：用多层神经网络（DCNN）进行局势评估-价值网络 用静态的神经网络，直接给出局面的胜率？人脑肯定做不了，电脑能行？ 完全出人意料：神经网络居然能做成价值网络这种人脑都不行的事！ 怎么做的？疯狂的办法：海量服务器生成2000万局独立棋局。,David Sil

13、ver,AlphaGo开发过程中的最强力武器：强化学习 机器海量自我对弈，根据结果修改自己的神经网络系数：机器独特的学习优势。 强化学习是学习过程，在下棋的时候没有用到。背后海量的资源用于学习。 Deepmind的特点与思维方法是依靠机器自己改进，而非人工写代码解决问题。 强化学习如何进行很自由，新领域能作出非常多改进，效率提升潜力很大。,Demis Hassabis,AlphaGo战胜李世石的工具总结：综合优化多于创新 策略网络提供优秀的选点（另有一个快速的策略网络用于fast-rollout） 价值网络判断叶子节点胜率，叶子节点fast-rollout模拟至终局报告结果 局面评估 = 0.

14、5*价值网络 + 0.5*fast-rollout （价值网络还是有缺陷） MCTS总领整个搜索框架，48个TPU海量模拟终局，疯狂搜索提升棋力。 人类高手10万局棋谱2000万手深度学习训练出策略网络，准备征子等盘面特征。 谷歌海量服务器生成2000万局训练出价值网络，自我对弈强化学习不断改善。 IBM深蓝模式，软硬全面提升。每个技术都有人想过，但加在一起做到极致。,AlphaGo-Lee为什么出了bug？ 框架很复杂，技术环节很多，强行拼在一起，用强机保证整体效果。 策略网络、价值网络、fast-rollout三大模块都不是太可靠。用MCTS互补不足。 框架性错误，总有一定概率没补上，都失

15、效了，就出bug了。 绝艺、DeepZenGo也经常出类似死活错误。怎么也修不好，只是降低出错概率。 AlphaGo-Lee其实也是陷入瓶颈，修不好，强化学习也提升不了实力了。 Master是如何对人类63胜不出bug的？业界都非常有兴趣，在等新论文。,Master是真正的突破，AlphaGo Zero在论文中风光 自然新论文，Master的架构突破是最关键的，有真正的干货。 AlphaGo Zero用的就是Master硬件配置、网络架构、搜索框架、强化学习方法。 Master：架构突破、棋力突破、消除bug。AlphaGo Zero：把结果做得更漂亮。 Master网络结构的关键提升 1.

16、从AlphaGo Lee的conv变到resnet，网络层数从12大幅增加至40。 2. 把价值与策略网络合并成一个，二者其实是基于对盘面同样的理解。 二者各自能带来600分的等级分增幅。这个等级分增幅需要强化学习来实现。,Master的强化学习的重大提升 策略网络的自学：网络的直接输出，不如MCTS搜索后输出的选择，可以自学。 价值网络的自学：网络直接给出的胜率，不如MCTS搜索下完后的对局结果。 需要改变网络结构、扩大网络层数，才能实施这种高效自学习。 成果1：Master富于创新，发现很多人类想不到但是效果却不错的招法。 成果2：Master的价值网络持续突飞猛进，自然而然在搜索中主打消

17、除了bug。 成果3：搜索速度在价值网络主导下大大加快，将TPU从48个减成4个都足够了。 成果4：学习效率大增，学习时间大幅缩短。以前训练二个月的一周就行。,再从Master改进，AlphaGo Zero水到渠成 从零知识开始学，脱离人类棋谱影响。自然论文最大看点。 训练策略价值合一的网络时，取消人工实现的特征，直接训练出来，更为自然。 取消搜索框架中的rollout，价值网络足够强大不需要了，架构更简单。 围棋的知识结构，强大的策略价值网络，都从强化学习中来，浑然天成。 以实际成果证明，之前认为从零开始训练不可能成功是错误的。 人类棋谱并不是必须的，甚至是有害的。,AlphaGo Zero

18、从零开始学习能够成功的原因 围棋漂亮的规则形成的数学空间，人类难以掌握，无法找到有效的局面评估方法。 Master找到的网络结构，能很好的抓住围棋状态空间的特征。 这是出人意料的。 AlphaGo Zero的训练极为高效，490万局就训练成功。说明围棋的状态空间很优美。 围棋不仅规则漂亮，围棋AI的算法也优美漂亮：从零开始，自己训练就什么都有了。 人类以为的围棋的复杂，是对人类。但不要以为这种复杂AI应付不了。,围棋AI的历史回顾 1. 用传统搜索算法，但局面评估毫无办法，棋力极弱不值一提。 2. 搜索引入MCTS中rollout的怪招，取得了突破，但也埋下了bug。 3. 超强的价值网络解决了局面评估问题，回归传统算法高效搜索，去掉了bug。 4. 围棋AI碾压人类高手，一是计算机搜索算力强大，二是价