AlphaGo的基本原理.docx

AlphaGo的基本原理AlphaGo的基本原理 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（AlphaGo的基本原理）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为AlphaGo的基本原理的全部内容。AlphaGo的基本原理 全世界只有3.14 % 的人关注了数据与算法之美继 AlphaGo于2015年8月以50战胜三届欧洲冠军樊麾、2016年3月以41击败世界顶级棋手李世石后，今年1月，AlphGo的升级版本Master横扫各路高手，取得60比0的惊人战绩.20 年前IBM深蓝（Deep Blue)计算机击败国际象棋冠军卡斯帕罗夫的情景还历历在目，短短2年时间，人工智能在围棋领域又创造了人机对抗历史上的新里程碑。根据谷歌DeepMind团队发表的论文,我们可以窥探到AlphaGo的基本设计思路.任何完全信息博弈都无非是一种搜索.搜索的复杂度取决于搜索空间的宽度（每步的选择多寡)和深度(博弈的步数）。对于围棋，宽度约为250，深度约为150。AlphaGo用价值网络（value network)消减深度,用策略网络(policy network)消减宽度,从而极大地缩小了搜索范围。所谓价值网络，是用一个“价值数来评估当前的棋局。如果我们把棋局上所有棋子的位置总和称为一个“状态”，每个状态可能允许若干不同的后续状态。所有可能状态的前后次序关系就构成了所谓的搜索树。一个暴力的搜索算法会遍历这个搜索树的每一个子树.但是，其实有些状态是较容易判断输赢的,也就是评估其“价值”。我们把这些状态用价值表示，就可以据此省略了对它所有后续状态的探索,即利用价值网络削减搜索深度。所谓策略,是指在给定棋局,评估每一种应对可能的胜率，从而根据当前盘面状态来选择走棋策略。在数学上，就是估计一个在各个合法位置上下子获胜的可能的概率分布。因为有些下法的获胜概率很低，可忽略，所以用策略评估就可以消减搜索树的宽度。 更通俗地说，所谓“价值就是能看懂棋局，一眼就能判断某给定棋局是不是能赢，这是个偏宏观的评估.所谓的“策略”，是指在每一步博弈时，各种选择的取舍，这是个偏微观的评估。AlphaGo利用模拟棋手、强化自我的方法，在宏观（价值评估）和微观(策略评估）两个方面提高了探索的效率。在具体算法上，AlphaGo用深度卷积神经网络（CNN）来训练价值网络和策略网络。棋盘规模是（1919），棋盘每个位置编码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月号）-用数据解决不可能-听说,关注这个号的人运气都不会太差噢