AlphaGoZero的原理分析.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/11/4,#,计算机处理围棋复杂的能力压倒了人类,AlphaGo Zero,技术原理分析,陈经,2017,年,10,月,围棋,AI,是可以理解的,约,20,篇围棋,AI,分析文章在观察者网、新浪棋牌发表。,与应氏杯冠军唐韦星九段、吴肇毅九段共同解说,AI,对人的棋局。,赛前独家预测到了李世石第四局战胜,AlphaGo,的方式，分析出了,AlphaGo,的弱点。,通俗分析，不需要太多算法专业知识。,AlphaGo Zero,为什么很精彩？,需要了解围棋,AI,的历史，围棋对计算机曾经多么困难。,2015-2017,年,AlphaGo,数次取得巨大进步，战胜人类，靠的是什么，突破与难点在哪。,AlphaGo Zero,从零知识开始学习成功，意义是什么？,围棋是一个优美的数学问题,规则极简单，只需要,2,条极简单的行棋规则即可。,1.,气尽提子,2.,禁止同形再现（否则程序陷入死循环了，需要打劫）,围棋是一个优美的数学问题,由行棋规则可以推出博弈规则：,1.,双方占地，能生存的棋子和围住的空归本方。都不下了就终局数目。,2.,双方游戏目标是多占地。至此已经可以进行游戏与优化了，是一个博弈问题。,3.,博弈论的均衡解：双方最完美的行棋达成的平衡。,数学问题：双方分享,N*N,个点，双方博弈均衡值是多少？,N=5,已经解决。,五路棋盘均衡解：黑方,25,个点全得。七路棋盘均衡解推测为黑,29,子白,20,子（李喆六段）。,围棋是一个优美的数学问题,围棋是宇宙数学中天然存在的游戏，人类只是发现（非发明）了它。,胜负规则是人类强加的：贴目。,1.,比赛棋盘,19*19,共,361,个交叉点：黑占,182,、,183,、,184,、,185,、,186.,2.,双方数子结果的和一定为,361,：白占,179,、,178,、,177,、,176,、,175.,3.,现在黑,184,则负，,185,则胜，这是为了分出胜负强加的。,4.AI,认为，中国规则数子是自然的，容易程序实现，,AI,是中国规则最坚定支持者。,5.,日韩规则数目，定义不完全甚至是错误的，是人强加的，,AI,无法理解。,日韩规则：强行规定盘角曲四是死棋。,“,劫尽棋亡,”,逻辑错误，双活需要实战解决。,围棋是一个优美的数学问题,东西方对围棋不同的理解,东方（中日韩）：围棋是文化艺术，是竞技，代表国家荣耀。爱好者普遍认为，围棋有深奥的战略与战术，能开发智力，非常有意思。专业与业余高手很多。,西方：围棋是数学问题。国际象棋爱好者多，能领会围棋的优美与深奥的人少。主要把围棋看成数学问题，围棋高手极少。,“,国际象棋是一种仅仅局限于这个世界的游戏，而围棋则有些不象是从地球上诞生的。如果哪一天我们发现有一种天外文明和我们玩同一种游戏，那一定是围棋，决不会有任何疑问。,”-伊曼纽尔拉斯克，1894年26岁时成为国际象棋历史上第二位世界冠军，五次卫冕。,1909年研究围棋一年后，伊曼纽尔拉斯克被日本高手让九子吃光。但是他说：,“,围棋是数学思维的理想游戏，而东方从来没有第一流的数学家，我敢肯定我们能够在围棋上战胜他们”。他的本意是去日本学棋，打败日本高手，因第一次世界大战未能成行。,博弈论与计算机算法对国际象棋与围棋的理解：,完全博弈树,开盘是根节点，按不同的下一招，分出多个分支。,叶子节点不再需要分支：国际象棋死棋或和局，围棋终局数子。,所有可能的局面都会出现在这个完全博弈树中。,策梅罗定理（,1913,）：每个节点都有确定的博弈结论，黑方必胜、白方必胜、或和棋。,国际象棋：应该是双方和棋（顶级,AI,超过,90%,和棋），但不是证明。,围棋：如果均衡贴目，双方和棋（如黑,184,白,177,的均衡结果）。偏离均衡贴目，一方必胜（贴,7,目半执白有优势，贴,5,目半执黑优势）。,国际象棋局面数：约,1046,围棋合法局面数：简单计算是,3361,。精确数值是,171,位数（,2015,）。,208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935,局面数都是天文数字，到现在都不可能破解，只能想办法设计实际的搜索算法。国际跳棋已经破解。,国际象棋等传统棋类算法的核心概念：,局面评估函数,局面评估函数可以静态计算（仅依赖当前局面），不用往前搜索。,局面评估函数和真实的局面情况，存在误差，如将黑胜的结果误判为白胜。好的函数误差小，适应性强（没有明显,bug,，常见局面不出错）。,从一个节点往下搜索是改善这个节点评分的办法：多算胜，少算不胜。,利用局面评估函数进行搜索优化，是棋类博弈算法的核心工作。如Alpha-Beta剪枝算法，意思是损失巨大的分支就不用搜索了。,国际象棋,AI,战胜人类棋手：符合人类直觉的,传统算法,局面评估剪枝，搜索优化。将搜索树规模降到计算机算力之内。,搜索代码,+,人类知识库开局库。硬件工程师,+,软件算法工程师,+,专业棋手。,国际象棋,AI,的算法和人类弈棋思维差不多，但算得快、算得深。,计算机国际象棋,80,、,90,年代就有相当实力，因为没围棋那么复杂。,现在人类还有希望和,AI,下和，国际象棋的复杂人还算能应付。,人类高手应对围棋复杂的办法：优秀的直觉,围棋高手识别局面，根据局部棋形产生直觉选点：很多情况只此一手。,围棋高手的计算结果一般就是第一直觉。,10,秒的快棋水平与慢棋相差不大。,国际象棋高手更依赖于计算与评估，,围棋局面评估极难，人类高手靠直觉。,围棋高手强调计算：局部死活、局部得失的验证，是对第一直觉的验算。,围棋高手的局势评估会起关键作用，但并不是每一招都进行。感觉需要了才进行数目、手割之类的评估。评估不准确，不同棋手观点对立。,计算、局势评估是顶尖高手之间的竞争。高手靠直觉随手下也能胜低手，柯洁,15,秒快棋让二子胜职业低段，让先胜世界冠军。,围棋的复杂并不仅是局面数众多：,深层次的复杂,1.,非线性（子力位置稍不同就局势大变）,2.,死活，局部死活、大龙对杀。弃子，吃了未必胜。,3.,打劫，两手劫、万年劫、多重劫争。,4.,复杂死活、复杂劫争、大对杀、大弃子、耍大龙等局面，是围棋艺术必不可少的精华。,围棋的局面评估,极其复杂困难,，人类没有什么好办法,2006,年前的早期围棋,AI:,棋力极弱,代表程序：手谈，中山大学化学退休教授陈志行用汇编语言开发。,业余高手都能让,10,多个子，引发,bug,甚至,20,个子以上（,GnuGo,）。,类似国际象棋搜索算法框架，但开局库、分支策略、局面评估各方面都差。,致命弱点：人写代码评估局面，棋子对周边的影响累加等简单错误逻辑。,次要弱点：根据棋形产生候选点，时有错漏。,搜索效果极差：冠军程序手谈是不搜索的！,多年无进展，业界认为围棋,AI,难度极高，是完全信息博弈问题的终极挑战。,带来研发活力的突破：,蒙特卡洛树形搜索,写代码评估局势极其困难，死路一条，强写出来也极弱。,革命性的思想：蒙特卡洛树形搜索（,MCTS,，,Monte-Carlo Tree Search,，,2006,）,到叶子结点就,roll out,（黑白轮流快速下完数子出胜负结果）。,终局精确数子,+,多次随机模拟,=,局势评估（胜率）,人不可能用这种方法下棋，计算机特有的优势。但快速下完也易出,bug,。,全局思维、多次模拟统计结果，大局观已经强于人类不可靠的直觉。,Remi Coulom,基于,MCTS,的围棋,AI,的实力,代表程序日本的,Zen,，可以战胜一般业余棋手，不如业余高手,（,2011,）,。,业余棋手感到兴奋，对围棋,AI,兴趣上升，积极对战（,KGS,）。,2015,年,11,月，连笑七段让四子、五子轻松战胜计算机围棋冠军,Dolbram,。,职业棋界兴趣不大，认为,AI,战胜人类还很遥远。聂卫平、俞斌：,100,年。,围棋,AI,研发者信心上升，感觉到了希望。乐观认为,10-20,年。,围棋,AI,战胜人类的导火索：深度学习,图像识别领域的深度学习出现突破。（,DCNN,，,2012-2015,）,将棋盘理解成图像，建模人类高手直觉，直接产生少数候选点,-,策略网络。,不需要写代码，用几十万局的棋局样本深度学习训练出来（,2015,）。,策略网络是图像识别软硬件技术进步的自然发展，高水平围棋,AI,的开发变容易了。,人类高手脑神经为什么能产生优秀的直觉选点？不清楚。,AI,的神经网络为什么能模仿人类的优秀直觉？黑盒子。解释不清，但就是管用。,围棋,AI,战胜人类的最重要最根本技术突破：价值网络,真正疯狂的想法：用多层神经网络（,DCNN,）进行局势评估,-,价值网络,用静态的神经网络，直接给出局面的胜率？人脑肯定做不了，电脑能行？,完全出人意料：神经网络居然能做成价值网络这种人脑都不行的事！,怎么做的？疯狂的办法：海量服务器生成,2000,万局独立棋局。,David Silver,AlphaGo,开发过程中的最强力武器：强化学习,机器海量自我对弈，根据结果修改自己的神经网络系数：机器独特的学习优势。,强化学习是学习过程，在下棋的时候没有用到。背后海量的资源用于学习。,Deepmind,的特点与思维方法是依靠机器自己改进，而非人工写代码解决问题。,强化学习如何进行很自由，新领域能作出非常多改进，效率提升潜力很大。,Demis Hassabis,AlphaGo,战胜李世石的工具总结：综合优化多于,创新,策略网络提供优秀的选点（另有一个快速的策略网络用于,fast-rollout,）,价值网络判断叶子节点胜率，,叶子节点,fast-rollout,模拟至终局报告结果,局面评估,=0.5*,价值网络,+0.5*fast-rollout,（价值网络还是有缺陷）,MCTS,总领整个搜索框架，,48,个,TPU,海量模拟终局，疯狂搜索提升棋力。,人类高手,10,万局棋谱,2000,万手深度学习训练出策略网络，准备征子等盘面特征。,谷歌海量服务器生成,2000,万局训练出价值网络，,自我对弈强化学习不断改善。,IBM,深蓝模式，软硬全面提升。每个技术都有人想过，但加在一起做到极致。,AlphaGo-Lee,为什么出了,bug,？,框架很复杂，技术环节很多，强行拼在一起，用强机保证整体效果。,策略网络、价值网络、,fast-rollout,三大模块都不是太可靠。用,MCTS,互补不足。,框架性错误，总有一定概率没补上，都失效了，就出,bug,了。,绝艺、,DeepZenGo,也经常出类似死活错误。怎么也修不好，只是降低出错概率。,AlphaGo-Lee,其实也是陷入瓶颈，修不好，强化学习也提升不了实力了。,Master,是如何对人类,63,胜不出,bug,的？业界都非常有兴趣，在等新论文。,Master,是真正的突破，,AlphaGo Zero,在论文中风光,自然新论文，,Master,的架构突破是最关键的，有真正的干货。,AlphaGo Zero,用的就是,Master,硬件配置、网络架构、搜索框架、强化学习方法。,Master,：架构突破、棋力突破、消除,bug,。,AlphaGo Zero,：把结果做得更漂亮。,Master,网络结构的关键提升,1.,从,AlphaGo Lee,的,conv,变到,resnet,，网络层数从,12,大幅增加至,40,。,2.,把价值与策略网络合并成一个，二者其实是基于对盘面同样的理解。,二者各自能带来,600,分的等级分增幅。这个等级分增幅需要强化学习来实现。,Master,的强化学习的重大提升,策略网络的自学：网络的直接输出，不如,MCTS,搜索后输出的选择，可以自学。,价值网络的自学：网络直接给出的胜率，不如,MCTS,搜索下完后的对局结果。,需要改变网络结构、扩大网络层数，才能实施这种高效自学习。,成果,1,：,Master,富于创新，发现很多人类想不到但是效果却不错的招法。,成果,2,：,Master,的价值网络持续突飞猛进，自然而然在搜索中主打消除了,bug,。,成果,3,：搜索速度在价值网络主导下大大加快，将,TPU,从,48,个减成,4,个都足够了。,成果,4,：学习效率大增，学习时间大幅缩短。以前训练二个月的一周就行。,再从,Master,改进，,AlphaGo Zero,水到渠成,从零知识开始学，脱离人类棋谱影响。自然论文最大看点。,训练策略价值合一的网络时，取消人工实现的特征，直接训练出来，更为自然。,取消搜索框架中的,rollout,，价值网络足够强大不需要了，架构更简单。,围棋的知识结构，强大的策略价值网络，都从强化学习中来，浑然天成。,以实际成果证明，之前认为从零开始训练不可能成功是错误的。,人类棋谱并不是必须的，甚至是有害的。,AlphaGo Zero,从零开始学习能够成功的原因,围棋漂亮的规则形成的数学空间，人类难以掌握，无法找到有效的局面评估方法。,Master,找到的网络结构，能很好的抓住围棋状态空间的特征。这是出人意料的。,AlphaGo,Zero,的训练极为高效，,490,万局就训练成功。说明围棋的状态空间很优美。,围棋不仅规则漂亮，围棋,AI,的算法也优美漂亮：从零开始，自己训练就什么都有了。,人类以为的围棋的复杂，是对人类。但不要以为这种复杂,AI,应付不了。,围棋AI的历史,回顾,1.,用传统搜索算法，但,局面评估毫无办法,，棋力极弱不值一提。,2.,搜索,引入MCTS,中,rollout的,怪,招,，取得了突破，但也埋下了,bug,。,3.,超,强的,价值网络,解决了局面评估问题，回归传统算法高效,搜索，去掉了,bug,。,4.,围棋,AI,碾压人类高手，一是计算机搜索算力强大，二是价值网络有效评估局面。,5.AlphaGo Zero,下棋时象国际象棋,AI,，但是背后的神经网络与强化学习是全新的。,6.,下棋需要,4,个,TPU,，但是学习训练需要海量的算力（可能要一万个,GPU,）。,AlphaGo,还只是完全信息博弈非常强大,AlphaGo,的新进展：用到星际争霸上成果出人意料地小。（,2017,年,8,月）,从零知识开始自学习打星际争霸：完全不会打，只会逃跑。,学习人类高手操作自学习提升：被暴雪最弱的内置,AI,消灭前，能造,7,、,8,个兵。,对人类而言很复杂的围棋，对机器自学习是单一任务，有办法破解。,对人类不难的星际争霸，对机器而言步骤太多，自学习找不到目标失败。,Q&A,