AlphaGo-Zero的原理分析演示幻灯片.ppt

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