-
陈经:AlphaGo升级成Master后的算法框架分析
关键字: 围棋AlphaGoMaster算法框架局面评估函数的作用
从算法上来说,高水平国际象棋AI的关键是人工植入的一些国际象棋相关的领域知识,加上传统的计算机搜索高效剪枝算法。值得注意的是,AlphaGo以及之前所有高水平AI如ZEN和CrazyStone都采用MCTS(蒙特卡洛树形搜索),而最高水平的国际象棋AI是不用的。MCTS是CrazyStone的作者法国人Remi Coulom 在2006年最先提出的,是上一次围棋人工智能算法取得巨大进步能够战胜一般业余棋手的关键技术突破。
但MCTS其实是传统搜索技术没有办法解决围棋问题时,想出来的变通办法,并不是说它比传统搜索技术更先进。实际MCTS随机模拟,并不是太严谨,它是成千上万次模拟,每次模拟都下至终局数子确定胜负统计各种选择的胜率。这是一个对人类棋手来说相当不自然的方法,可以预期人类绝对不会用这种办法去下棋。
国际象棋也可以用MCTS去做,但没有必要。谷歌团队有人用深度学习和MCTS做了国际象棋程序,但是棋力仅仅是国际大师,并没有特别厉害。高水平国际象棋算法的核心技术,是极为精细的“局面评估函数”。而这早在几十年前,就是人工智能博弈算法的核心问题。国际象棋的局面评估函数很好理解,基本想法是对皇后、车、马、象、兵根据战斗力大小给出不同的分值,对王给出一个超级大的分值死了就是最差的局面。一个局面就是棋子的分值和。
但这只是最原始的想法,子力的搭配、兵阵的形状、棋子的位置更为关键,象棋中的弃子攻杀极为常见。这需要国际象棋专业人士进行极为专业细致的估值调整。国际象棋AI的水平高低基本由它的局面评估函数决定。有了好用的局面评估函数以后,再以此为基础,展开一个你一步我一步的指数扩展的博弈搜索树。在这个搜索树上,利用每个局面计算出来的分值,进行一些专业的高效率“剪枝”(如Alpha-Beta剪枝算法)操作,缩小树的规模,用有限的计算资源尽可能地搜索更多的棋步,又不发生漏算。
图为搜索树示例,方块和圆圈是两个对手,每一条线代表下出一招。局面评估后,棋手要遵守MIN-MAX的原则,要“诚实”地认为对手能下出最强应对再去想自己的招。有局面评估分数的叶子节点其实不用都搜索到,因为理论上有剪枝算法证明不用搜索了。如一下被人吃掉一个大子,又得不到补偿的分枝就不用继续往下推了。这些搜索技术发展到很复杂了,但都属于传统的搜索技术,是人可以信服的逻辑。
国际象棋与中国象棋AI发展到水平很高后,棋手们真的感觉到了电脑的深不可测,就是有时电脑会下出人类难于理解的“AI棋”。人类对手互相下,出了招以后,人就会想对手这是想干什么,水平相当的对手仔细思考后总是能发现对手的战术意图,如设个套双吃对手的马和车,如果对手防着了,就能吃个兵。而“AI棋”的特征是,它背后并不是一条或者少数几条战术意图,而是有一个庞大的搜索树支持,人类对手作出任何应对,它都能在几手、十几手后占得优势,整个战略并不能用几句话解释清楚,可能需要写一篇几千字的文章。
这种“AI棋”要思考非常周密深远,人类选手很难下出来。近年来中国象棋成绩最好的是王天一,他的棋艺特点就是主动用软件进行训练,和上一辈高手方法不同。王天一下出来的招有时就象AI,以致于有些高手风言风语影射他用软件作弊引发风波,我认为应该是训练方法不同导致的。国际象棋界对软件的重视与应用比中国象棋界要强得多,重大比赛时,一堆人用软件分析双方的着手好坏,直接作为判据,增加了比赛的可看性。
软件能下出“AI棋”,是因为经过硬件以及算法的持续提升,程序的搜索能力终于突破了人类的脑力限制,经过高效剪枝后,几千万次搜索可以连续推理多步并覆盖各个分枝,在深度与广度方面都超过人类,可以说搜索能力已经超过人类。
其实最初的围棋AI也是用这个思路开发的,也是建立搜索树,在叶子节点上搞局面评估函数计算。但是围棋的评估函数特别难搞,初级的程序一般用黑白子对周边空点的“控制力”之类的原始逻辑进行估值,差错特别大,估值极为离谱,棋力极低。无论怎么人工加调整,也搞不好,各种棋形实在是太复杂。很长时间围棋AI没有实质进步,受限于评估函数极差的能力,搜索能力极差。
实在是没有办法了,才搞出MCTS这种非自然的随机下至终局统计胜率的办法。MCTS部分解决了估值精确性问题,因为下到终局数子是准确的,只要模拟的次数足够多,有理论证明可以逼近最优解。用这种变通的办法绕开了局面评估这个博弈搜索的核心问题。以此为基础,以ZEN为代表的几个程序,在根据棋形走子选点上下了苦功,终于取得了棋力突破,能够战胜一般业余棋手。
接下来自然的发展就是用深度学习对人类高手的选点直觉建模,就是“策略网络”。这次突破引入了机器学习技术,不需要开发者辛苦写代码了,高水平围棋AI的开发变容易了。即使这样,由于评估函数没有取得突破,仍然需要MCTS来进行胜率统计,棋力仍然受限,只相当于业余高手。
“价值网络”横空出世
AlphaGo在局面评估函数上作出了尝试性的创新,用深度学习技术开发出了“价值网络”。它的特点是,局面评分也是胜率,而不是领先多少目这种较为自然的优势计算。但是从《自然》论文以及版本V13与V18的表现来看,这时的价值网络并不是太准确,不能单独使用,应该是一个经常出错的函数。论文中提到,叶子节点胜率评估是把价值网络和MCTS下至终局混合使用,各占0.5权重。这个意思是说,AlphaGo会象国际象棋搜索算法一样,展开一个叶子节点很多的树。
在叶子节点上,用价值网络算出一个胜率,再从叶子节点开始黑白双方一直轮流走子终局得出胜负。两者都要参考,0.5是一个经验性的数据,这样棋力最高。这其实是一个权宜之计,价值网络会出错,模拟走子终局也并不可靠,通过混合想互相弥补一下,但并不能解决太多问题。最终棋力还是需要靠MCTS海量模拟试错,模拟到新的关键分枝提升棋力。所以版本V18特别需要海量计算,每步需要的时间相对长,需要的CPU与GPU个数也不少,谷歌甚至开发了特别的TPU进行深度神经网络并行计算提高计算速度。
整个《自然》论文给人的感觉是,AlphaGo在围棋AI的工程实施的各个环节都精益求精做到最好,最后的棋力并不能简单地归因于一两个技术突破。算法研发与软件工程硬件开发多个环节都不计成本地投入,需要一个人数不小的精英团队全力支持,也需要大公司的财力与硬件支持。V13与V18更多给人的感觉是工程成就,之前的围棋AI开发者基本是两三个人的小团队小成本开发,提出了各式各样的算法思想,AlphaGo来了个集大成,终于取得了棋力突破。
-
本文仅代表作者个人观点。
- 请支持独立网站,转发请注明本文链接:
- 责任编辑:武守哲
-
“美国首次暂停,以色列深感担忧” 评论 105习近平抵达巴黎开始对法国进行国事访问 评论 41刚有“明显进展”,巴以停火又陷僵局 评论 34他在以色列监狱中死亡,联合国官员:极度震惊 评论 286俄方通缉泽连斯基等乌军政要员,乌方回应 评论 232最新闻 Hot
-
他也要对TikTok“真香”了?
-
内塔尼亚胡:任何国际机构都无法阻止以色列“自卫”
-
“美国首次暂停,以色列深感担忧”
-
他窜台炒作:特朗普胜选后将一如既往“挺台”
-
刚有“明显进展”,巴以停火又陷僵局
-
他“替”乌克兰宣布新反攻:2025年发动
-
“欧盟正游说中国:别‘报复’,得特别保护”
-
俄方通缉泽连斯基等乌军政要员,乌方回应
-
“没有沙以关系正常化,就没有美沙防务协议”
-
他在以色列监狱中死亡,联合国官员:极度震惊
-
“丢473个议席!40年来最差”
-
加拿大逮捕3名印度人,印度外长回应
-
国际刑事法院忍无可忍:再威胁试试
-
澳大利亚“设卡”,中国在非洲淘到“白金”
-
“半数以上AI最热门领域,中国研究领先”
-
省级督察组现场核实情况,遭故意封路阻挠
-