搜索
计算机处理围棋复杂的能力压倒了人类AlphaGoZero技术原理分析陈经2017年10月围棋AI是可以理解的•约20篇围棋AI分析文章在观察者网、新浪棋牌发表。•与应氏杯冠军唐韦星九段、吴肇毅九段共同解说AI对人的棋局。•赛前独家预测到了李世石第四局战胜AlphaGo的方式，分析出了AlphaGo的弱点。•通俗分析，不需要太多算法专业知识。AlphaGoZero为什么很精彩？•需要了解围棋AI的历史，围棋对计算机曾经多么困难。•2015-2017年AlphaGo数次取得巨大进步，战胜人类，靠的是什么，突破与难点在哪。•AlphaGoZero从零知识开始学习成功，意义是什么？围棋是一个优美的数学问题规则极简单，只需要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目半执黑优势）。•国际象棋局面数：约10^46•围棋合法局面数：简单计算是3^361。精确数值是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-CarloTreeSearch，2006）•到叶子结点就rollout（黑白轮流快速下完数子出胜负结果）。•终局精确数子+多次随机模拟=局势评估（胜率）•人不可能用这种方法下棋，计算机特有的优势。但快速下完也易出bug。•全局思维、多次模拟统计结果，大局观已经强于人类不可靠的直觉。RemiCoulom基于MCTS的围棋AI的实力•代表程序日本的Zen，可以战胜一般业余棋手，不如业余高手（2011）。•业余棋手感到兴奋，对围棋AI兴趣上升，积极对战（KGS）。•2015年11月，连笑七段让四子、五子轻松战胜计算机围棋冠军Dolbram。•职业棋界兴趣不大，认为AI战胜人类还很遥远。聂卫平、俞斌：100年。•围棋AI研发者信心上升，感觉到了希望。乐观认为10-20年。围棋AI战胜人类的导火索：深度学习•图像识别领域的深度学习出现突破。（DCNN，2012-2015）•将棋盘理解成图像，建模人类高手直觉，直接产生少数候选点--策略网络。•不需要写代码，用几十万局的棋局样本深度学习训练出来（2015）。•策略网络是图像识别软硬件技术进步的自然发展，高水平围棋AI的开发变容易了。•人类高手脑神经为什么能产生优秀的直觉选点？不清楚。AI的神经网络为什么能模仿人类的优秀直觉？黑盒子。解释不清，但就是管用。围棋AI战胜人类的最重要最根本技术突破：价值网络•真正疯狂的想法：用多层神经网络（DCNN）进行局势评估--价值网络•用静态的神经网络，直接给出局面的胜率？人脑肯定做不了，电脑能行？•完全出人意料：神经网络居然能做成价值网络这种人脑都不行的事！•怎么做的？疯狂的办法：海量服务器生成2000万局独立棋局。DavidSilverAlphaGo开发过程中的最强力武器：强化学习•机器海量自我对弈，根据结果修改自己的神经网络系数：机器独特的学习优势。•强化学习是学习过程，在下棋的时候没有用到。背后海量的资源用于学习。•Deepmind的特点与思维方法是依靠机器自己改进，而非人工写代码解决问题。•强化学习如何进行很自由，新领域能作出非常多改进，效率提升潜力很大。DemisHassabisAlphaGo战胜李世石的工具总结：综合优化多于创新•策略网络提供优秀的选点（另有一个快速的策略网络用于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是真正的突破，AlphaGoZero在论文中风光•《自然》新论文，Master的架构突破是最关键的，有真正的干货。•AlphaGoZero用的就是Master硬件配置、网络架构、搜索框架、强化学习方法。•Master：架构突破、棋力突破、消除bug。AlphaGoZero：把结果做得更漂亮。Master网络结构的关键提升•1.从AlphaGoLee的conv变到resnet，网络层数从12大幅增加至40。•2.把价值与策略网络合并成一个，二者其实是基于对盘面同样的理解。•二者各自能带来600分的等级分增幅。这个等级分增幅需要强化学习来实现。Master的强化学习的重大提升•策略网络的自学：网络的直接输出，不如MCTS搜索后输出的选择，可以自学。•价值网络的自学：网络直接给出的胜率，不如MCTS搜索下完后的对局结果。•需要改变网络结构、扩大网络层数，才能实施这种高效自学习。•成果1：Master富于创新，发现很多人类想不到但是效果却不错的招法。•成果2：Master的价值网络持续突飞猛进，自然而然在搜索中主打消除了bug。•成果3：搜索速度在价值网络主导下大大加快，将TPU从48个减成4个都足够了。•成果4：学习效率大增，学习时间大幅缩短。以前训练二个月的一周就行。再从Master改进，AlphaGoZero水到渠成•从零知识开始学，脱离人类棋谱影响。《自然》论文最大看点。•训练策略价值合一的网络时，取消人工实现的特征，直接训练出来，更为自然。•取消搜索框架中的rollout，价值网络足够强大不需要了，架构更简单。•围棋的知识结构，强大的策略价值网络，都从强化学习中来，浑然天成。•以实际成果证明，之前认为从零开始训练不可能成功是错误的。•人类棋谱并不是