一张图解AlphaGo原理及弱点
2016-03-23 郑宇，张钧波 CKDD
作者简介：
郑宇，博士, Editor-in-Chief of ACM Transactions on Intelligent Systems and Technology， ACM数据挖掘中国分会秘书长。
张钧波，博士，ACM数据挖掘中国分会会员，从事深度神经网络相关研究。
--------------------------------------
近期AlphaGo在人机围棋比赛中连胜李世石3局，体现了人工智能在围棋领域的突破，作为人工智能领域的工作者，我们深感欣慰。其实质是深度学习网络（CNN）跟蒙特卡罗搜索树(MCTS)结合的胜利，是人类智慧的进步。不少所谓的“砖”家开始鼓吹机器战胜人类、甚至人类将被机器统治等无知言论，让人实在看不下去。作为围棋爱好者和人工智能领域工作者，我们觉得是时候跟大家讲讲AlphaGo的原理及其弱点了。
可以很负责任的告诉大家，AlphaGo还没有完全攻克围棋这个难题，职业棋手也并非没有希望赢Go了，更不能说机器战胜了人类。AlphaGo未来需要走的路还很长。如果有中国职业棋手想挑战AlphaGo，我们愿意为其组建最顶尖（且懂围棋）的人工智能专家顾问团，助其取胜AlphaGo。
虽然网上技术贴不少，但还没有一篇文章完全讲清楚AphaGo的原理，Nature上刊登的文章也缺乏一张刨解全局的图（加之用英文描述，同学们很难理解透彻）。以下是我跟张钧波博士在多次阅读原文并收集了大量其他资料后，一起完成的一张图，解释了AlphaGo的原理，看完后大家自然知道其弱点在何处了。
图1、AlphaGo的原理图 (作者为本图花费大量心血，版权归两位作者所有，欢迎转发，但请勿盗图)
AlphaGo总体上包含离线学习（图1上半部分）和在线对弈（图1下半部分）两个过程。
离线学习过程分为三个训练阶段。
- 第一阶段：利用16万多幅专业棋手对局的棋谱来训练两个网络。一个是基于全局特征和深度卷积网络（CNN）训练出来的策略网络（Policy Network）。其主要作用是给定当前盘面状态作为输入，输出下一步棋在棋盘其它空地上的落子概率。另一个是利用局部特征和线性模型训练出来的快速走棋策略（Rollout Policy)。策略网络速度较慢，但精度较高；快速走棋策略反之。
- 第二阶段：利用第t轮的策略网络与先前训练好的策略网络互相对弈，利用增强式学习来修正第t轮的策略网络的参数，最终得到增强的策略网络。这部分被很多“砖”家极大的鼓吹，但实际上应该存在理论上的瓶颈（提升能力有限）。这就好比2个6岁的小孩不断对弈，其水平就会达到职业9段？
- 第三阶段：先利用普通的策略网络来生成棋局的前U-1步（U是一个属于[1, 450]的随机变量），然后利用随机采样来决定第U步的位置（这是为了增加棋的多样性，防止过拟合）。随后，利用增强的策略网络来完成后面的自我对弈过程，直至棋局结束分出胜负。此后，第U步的盘面作为特征输入，胜负作为label，学习一个价值网络（Value Network），用于判断结果的输赢概率。价值网络其实是AlphaGo的一大创新，围棋最为困难的地方在于很难根据当前的局势来判断最后的结果，这点职业棋手也很难掌握。通过大量的自我对弈，AlphaGo产生了3000万盘棋局，用来训练价值网络。但由于围棋的搜索空间太大，3000万盘棋局也不能帮AlphaGo完全攻克这个问题。
在线对弈过程包括以下5个关键步骤：其核心思想实在蒙特卡罗搜索树（MCTS）中嵌入了深度神经网络来减少搜索空间。AlphaGo并没有具备真正的思维能力。
- 根据当前盘面已经落子的情况提取相应特征；
- 利用策略网络估计出棋盘其他空地的落子概率；
- 根据落子概率来计算此处往下发展的权重，初始值为落子概率本身（如0.18）。实际情况可能是一个以概率值为输入的函数，此处为了理解简便。
- 利用价值网络和快速走棋网络分别判断局势，两个局势得分相加为此处最后走棋获胜的得分。这里使用快速走棋策略是一个用速度来换取量的方法，从被判断的位置出发，快速行棋至最后，每一次行棋结束后都会有个输赢结果，然后综合统计这个节点对应的胜率。而价值网络只要根据当前的状态便可直接评估出最后的结果。两者各有优缺点、互补。
- 利用第四步计算的得分来更新之前那个走棋位置的权重（如从0.18变成了0.12）；此后，从权重最大的0.15那条边开始继续搜索和更新。这些权重的更新过程应该是可以并行的。当某个节点的被访问次数超过了一定的门限值，则在蒙特卡罗树上进一步展开下一级别的搜索（如图2所示）。
图2、MCTS拓展下一级节点
AlphaGo的弱点在哪里？
- 攻其策略网络，加大搜索空间。进入中盘后，职业选手如能建立起比较复杂的局面，每一步棋都牵连很多个局部棋的命运（避免单块、局部作战），则AlphaGo需要搜索空间则急剧加大，短时间内得到的解的精度就会大打折扣。通俗地说，非常复杂的变化，人算不清楚，现阶段计算机的计算力更没办法。李世石九段的第四局棋就有这个意思。此处左右上下共5块黑白棋都相互关联到一起，白1下后，黑棋需要考虑很多地方。很多地方都需要在MCTS上进行更深入的搜索。为了在一定的时间内有结果，只能放弃搜索精度。
图3、李世石对AlphaGo第四盘棋棋谱
- 攻其价值网络，万劫不复：AlphaGo的价值网络极大地提高了之前单纯依靠MCTS来做局势判断的精度，但离准确判断围棋局势还有不小的差距。神经网络还不能完全避免在某些时候出现一些怪异（甚至错误）的判断，更何况其训练样本还远远不足。这也是为什么有了价值网络还仍然需要依靠快速走棋来判断局势。大家都曾经怀疑过AlphaGo的打劫能力，也感觉到了AlphaGo有躲避打劫的迹象。实际上南京大学的周志华教授曾经撰文指出打劫会让价值网络崩溃的问题，原理不再重复。不能说AlphaGo不会打劫，而是害怕在棋局早期的多劫并存。即，打劫要乘早，太晚了搜索空间变小，即便价值网络失效，还可以靠快速走棋网络来弥补。开劫应该以在刚刚进入中盘时期为好（太早劫财还不够），并且保持长时间不消劫，最好在盘面上能同时有两处以上打劫。没有了价值网络的AlphaGo其实水平也就职业3-5段左右。
结束语
- AlphaGo已经达到了顶尖棋手的水平，但还不能说彻底打败了人类！
- AlphaGo体现了人类智慧的进步，但其本身并没有思维和智慧！
- 数据+计算资源+计算方法 共同推动了人工智能在围棋项目的进步！
长按以下二维码关注KDD China
阅读原文
微信扫一扫
关注该公众号