AlphaGo Zero的原理分析.pptx

计算机处理围棋复杂的能力压倒了人类
AlphaGo Zero技术原理分析
陈经
2017年10月
围棋AI是可以理解的
约20篇围棋AI分析文章在观察者网、新浪棋牌发表。
与应氏杯冠军唐韦星九段、吴肇毅九段共同解说AI对人的棋局。
赛前独家预测到了李世石第四局战胜AlphaGo的方式,分析出了AlphaGo的弱点。
通俗分析,不需要太多算法专业知识。
AlphaGo Zero为什么很精彩?
需要了解围棋AI的历史,围棋对计算机曾经多么困难。
2015-2017年AlphaGo数次取得巨大进步,战胜人类,靠的是什么,突破与难点在哪。
AlphaGo Zero从零知识开始学****成功,意义是什么?
围棋是一个优美的数学问题
规则极简单,只需要2条极简单的行棋规则即可。
1. 气尽提子
(否则程序陷入死循环了,需要打劫)
围棋是一个优美的数学问题
由行棋规则可以推出博弈规则:
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剪枝算法,意思是损失巨大的分支就不用搜索