AlphaGo基本原理：算法每个部分其实都是已有技术

天马行空

2017年03月10日10:47 新浪体育

AlphaGo基本原理

　　继AlphaGo于2015年8月以5-0战胜三届欧洲冠军樊麾、2016年3月以4-1击败世界顶级棋手李世石后，今年1月，AlphGo的升级版本Master横扫各路高手，取得60比0的惊人战绩。20 年前IBM深蓝（Deep Blue）计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，短短2年时间，人工智能在围棋领域又创造了人机对抗历史上的新里程碑。

　　根据谷歌DeepMind团队发表的论文，我们可以窥探到AlphaGo的基本设计思路。任何完全信息博弈都无非是一种搜索。搜索的复杂度取决于搜索空间的宽度（每步的选择多寡）和深度（博弈的步数）。对于围棋，宽度约为250，深度约为150。AlphaGo用价值网络（value network）消减深度，用策略网络（policy network）消减宽度，从而极大地缩小了搜索范围。

　　所谓价值网络， 是用一个“价值”数来评估当前的棋局。如果我们把棋局上所有棋子的位置总和称为一个“状态”，每个状态可能允许若干不同的后续状态。所有可能状态的前后次 序关系就构成了所谓的搜索树。一个暴力的搜索算法会遍历这个搜索树的每一个子树。但是，其实有些状态是较容易判断输赢的，也就是评估其“价值”。我们把这 些状态用价值表示，就可以据此省略了对它所有后续状态的探索，即利用价值网络削减搜索深度。

　　所谓策略，是指在给定棋局，评估每一种应对可能的胜率，从而根据当前盘面状态来选择走棋策略。在数学上，就是估计一个在各个合法位置上下子获胜的可能的概率分布。因为有些下法的获胜概率很低，可忽略，所以用策略评估就可以消减搜索树的宽度。

　　更 通俗地说，所谓“价值”就是能看懂棋局，一眼就能判断某给定棋局是不是能赢，这是个偏宏观的评估。所谓的“策略”，是指在每一步博弈时，各种选择的取舍， 这是个偏微观的评估。AlphaGo利用模拟棋手、强化自我的方法，在宏观（价值评估）和微观（策略评估）两个方面提高了探索的效率。

　　在具体算法上，AlphaGo用深度卷积神经网络（CNN）来训练价值网络和策略网络。棋盘规模是（19×19），棋盘每个位置编码48种经验特征。把这些特征输入模型进行训练，经过层层卷积，更多隐含特征会被利用。

　　基于类似的卷积神经网络结构，AlphaGo先做策略学习（学习如何下子），再做价值学习（学习评估局面）。策略学习也分为两步。第一步是有监督学习，即“打谱”，学习既往的人类棋谱。第二步是强化学习，即“左右互搏”，通过程序的自我博弈来发现能提高胜率的策略（见图1）。

图 1 策略网络和价值网络的训练过程

　　先说“打谱”（有监督学习）。AlphaGo学习了KGS网站上3000万个落子位置。它先随机选择落子位置，利用既往的棋谱来“训练”，试图预测人类最可能在什么位置落子。如果仅用落子历史和位置信息，AlphaGo 的预测成功率是55.7%。如果加上其他特征，预测成功率可以进一步提高到57%。在数学上，打谱是用一种梯度下降算法训练模型。给定一个棋局和一个落子 方式，为了计算人类棋手会有多大概率采用这种下法，AlphaGo用一个13层的卷积网络来训练这个概率的评估。这也是神经网络应用的经典做法，即基于梯 度下降来逼近一个函数的学习，这里函数就是棋手如何落子的概率。

　　再说“左右互搏”（强化学习）。这是在打谱的基础上，让不同下法的程序之间相互博弈。强化学习的策略网络和有监督学习（打谱）的网络结构一样，也同样利用梯度下降的学习方法。区别在于用一个“回报”（赢棋是1，输棋是-1）来奖励那些会导致最终获胜的策略。

　　价值网络的学习和策略网络类似，也用类似结构的卷积神经网络。区别在于网络的输出不是一个落子的概率分布，而是一个可能获胜的数值（即“价值”）。这个训练是一种回归（regression），即调整网络的权重来逼近每一种棋局真实的输赢预测。

　　如 果只是简单地让程序之间自由博弈，可能会导致过拟合：对训练的数据（棋谱）效果很好，但是对于没见过的棋局效果欠佳。这是因为一盘棋内不同的棋局之间是有 依赖关系的，而价值函数并不考虑这些关系。解决方法是用来自不同对弈过程的棋局的落子位置进行训练，避免来自同一棋局的状态之间的“信息污染”（相关 性）。

　　有了策略网络和价值网络，就可以进行策略的搜索了。AlphaGo使用了“蒙特卡洛树搜索”（MCTS）算法。所谓搜索，就是给定一个棋局，确定下一步的落子位置。这分为“往下搜”和“往回看”两个环节。在“往下搜”的环节，对给定的棋局，程序选择最可能获胜的落子位置，然后如此类推，直到搜索树上能分出结果的“叶子”节点。在“往回看”的环节，一个棋局各种不同的演化可能性被综合评估，用于更新搜索树对棋局的评估。

　　为了提高训练效率，AlphaGo利用图形处理器（GPU）运行深度学习算法（训练价值网络和策略网络），利用CPU运行树搜索算法。因为GPU适合做大吞吐量、低逻辑判断的工作，适合深度学习这种数据量大而逻辑简单的算法。中央处理器（CPU）则恰恰相反，适合蒙特卡洛树搜索这种逻辑复杂的算法。

　　本文摘录自《从AlphaGo的成功说起》，作者张梦迪、郑锦光、张强、鲍捷。即将发表于CCF会刊2017年3月号