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  策略网络和价值网络的训练过程
图 1 策略网络和价值网络的训练过程

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

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

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

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

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

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

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

标签: AlphaGo算法李世石

相关阅读:

加载中,请稍候...

推荐阅读

加载中,请稍候...