Alphago-zero的基本原理

一．概述围棋起源于3000年前的中国，被认为是世界上最复杂的棋类游戏。围棋规则虽然简单，但是变化无穷，其19*19的棋盘上，差不多有10170种状态，比宇宙中的原子总数还有多。因此能够下好围棋通常认为是智力超群的象征。中国涌现出了许多著名的围棋大师，比如吴清源、聂卫平、古力等，享誉无数。这种变化无穷的游戏吸引了世界上无数人。随着IT信息技术的发展，对于规则明确需要大量计算的棋类游戏而言，是计算机最擅长处理的任务。最著名的例子便是1997年IBM深蓝战胜了当时的国际围棋的世界冠军卡斯帕罗夫。IBM聘请了二十多位世界围棋大师，人工设计了许多针对不同走法的应对策略，并采用了专门设计的芯片和软件。在对弈时候，IBM深蓝凭借着强大的计算能力可以搜寻及估计随后的12步棋，略多于人类的10步。最终深蓝最后战胜了卡斯帕罗夫，成为轰动的世纪新闻。随后，计算机争相在各种棋类游戏中击败了人类，但是仅有围棋例外。因为现有的计算机计算能力无法穷尽搜索围棋的状态空间。既然无法穷尽搜索所有状态空间，所以人们开发了一些启发式的搜索方式。比较有代表性的有：MonteCarlotreesearch(MCTS)，这是Alphago出现之前世界上领先的围棋算法，采用MCTS来评价进行落子选择和评价每个盘面状态的赢棋的概率，每次落子的时候均选择动作价值最大的节点。MCTS在搜索树上不断选择落子、扩充节点、模拟、反馈，最后选择最优的节点来走下一步棋。但是尽管如此，其棋力仍然有限，如著名的Pachi围棋程序仅仅能达到业余2d的水平。CrazyStone是著名的围棋商业程序，其历史上分别使用了强化学习、深度神经网络、MCTS等方法，最高棋力能达到业余6d。同时，Alphago的作者，黄士杰等2015年在ICLR上发表文章[1]，采用了12层卷积神经网络的办法，达到了人类业余6d的水平，并且以97%的概率击败了基于传统搜索的围棋程序GnuGo。2016年是围棋发展史上的重要一年，也是AI发展的里程碑。2016年3月，Alphago以4:1的成绩击败了当时的围棋世界冠军李世石，一时间轰动全球。总的来说，Alphago采用了监督学习+强化学习+MCTS的方法，并在《nature》上发表了论文[2]。二．Alphago的原理图1Alphago的组成框架基于监督学习（Supervisedlearning）的策略网络（SLPolicynetwork）采用了一个含12个卷积层的深度网络，模仿的是人类专家的走棋。他从KGS围棋服务器上使用了16万局棋，近3千万个盘面来进行训练，训练网络包含48个二值平面和192个卷积核，达到了57%的预测围棋专家实际落子的准确率。快速走子网络Rolloutsnetwork采用人工设计的特征，达到快速下棋走子的目的，每步仅需要2us，但是预测围棋专家落子准确率稍低，仅有24.2%。Alphago中的基于强化学习的策略网络（RLPolicynetwork）以SLPolicynetwork的参数进行初始化后，然后强化网络不停的进行自我对弈，来提升棋力。Alphago中的价值网络（Valuenetwork）用来评估当前盘面赢棋的概率。为了防止过拟合Alphago采用了一种复杂的价值网络训练机制。其随机取一个时间步长值U，前U-1步采用Policynetwork来进行生成，第U步随机，后面U+1至收官步T采用强化策略网络（RLPolicynetwork）进行生成，并将（SU+1，ZU+1）存入数据库中。对于非终局步t来说，zt=±r(sT)=±1。同时，计算状态SU+1赢棋概率的预期反馈期望]~,...a,s|[1U1U11PTzEsvUUp。状态S的实际价值vθ(s)≈pv。最后利用随机梯度下降法来最小化(Z-vθ(s))的均方误差MSE，从而达到训练价值网络的作用。价值网络采用的网络结构与SLPolicynetwork相近，同样采用一个12层卷积层，48个二值平面，192个卷积核的深度网络。价值网络的输出为一个赢棋概率标量值。图2Alphago中采用的MCTS框架为了综合几种网络的威力，Alphago采用了MCTS。分为以下几个步骤：1.选择：每次走棋的时候选择动作价值Q和与奖励U之和最大，即（Q+U(P)）达到最大值的落子方式。P由SLpolicynetwork给出，奖励U正比于P，反比于访问次数N。采用这种方式，使得每次落子选择时能够兼顾利用（exploitation）和探索（explore），在利用当前最大动作值Q的时候鼓励选择访问较少的节点，从而有可能探索出最优的走法。2.扩展：当一个从未访问过的叶子节点访问次数超过阈值40的时候。Alphago便扩展出一个新的叶子节点。并用SLpolicynetwork计算出给节点的先验概率P。3.模拟：从树的根root不断向分支上搜索，并用价值网络计算出每个叶子节点的价值Vθ。同时使用快速走子网络Pπ走子到终局，并根据输赢计算出遍历过的支路上每个节点的奖励Z，赢了就是+1，输了就是-1，平是0。4.反馈：根据Vθ和奖励Z计算出每个叶子节点的价值，V(SL)=0.5*Vθ+0.5*ZL。并计算该节点的动作价值Q。niLSViasasNasQ1)(),,(1),(1),(（1）niasasN1),,(1),(1（s,a,i）代表第i次模拟是否在盘面为s时采用动作a,在MCTS上说法为是否通过edge（s,a）。最终MCTS选择节点遍历次数最多的落子方式。三．Alphagozero的原理本文上述内容主要讨论的是和Fanhui对战Alphago版本，和此后出现的Alphago各个版本之间差异如下：1.AlphaGoFan:Nature2016论文描述的版本，5:0胜樊麾，等级分Elo3144。其分布式版本使用了172个GPU。2.AlphaGoLee:就是4:1战胜李世石的版本，比AlphaGoFan等级分大约提高了600分，为3739分。与AlphaGoFan相比，改进有以下几点:a)自我对弈时走子同时打开PolicyNetwork和ValueNetwork;b)Policynetwork和ValueNetwork规模更大，同时网络训练由分布式GPU升级为分布式TPU。3.AlphaGoMaster：等级分Elo4858分，在网络上60:0大胜中日韩顶尖棋手，并在乌镇以3:0战胜柯杰。是AlphaGoLee的升级版本，AlphaGoMaster和AlphaGoLee相比,主要改动有三项：a)合并了PolicyNetwork和ValueNetwork;b)用ResNet替换了CovNet;c)强化学习训练算法从PolicyGradient改为PolicyIteration.4.AlphaGozero：等级分Elo5185分。AlphaGoZero和AlphaGoMaster相比，主要区别是:a)直接使用棋子位置（己方，对手）做神经网络输入，不再使用人工设计的特征，例如:当前位置是否是征子、当前位置吃子和被吃子数目、本块棋的气数等;b)初始训练时不再使用人类棋谱，而是直接从基于围棋规则的随机下法开始强化学习；c)仅使用一个神经网络，而不是像以前一样将policynetworkandvaluenetwork分开；d)简化了MCTS搜索，采用这个唯一的神经网络来进行评估盘面状态和走子。为此作者采用了强化学习，同时配合MCTS搜索。在训练的过程中使得赢棋能力和预测落子准确性稳步提高[3]。5.Alphazero：更加通用的棋类游戏程序。把围棋、国际象棋、日本将棋集于一身，采用一个统一的网络，该网络中已经没有棋子的概念。AlphaZero在8个小时训练击败AlphaGoLee；用4小时训练击败世界顶级的国际象棋程序Stockfish；用2小时训练击败世界顶级将棋程序Elmo。这是继AlphaGoZero的研究问世之后，一个更强、更加通用的版本。相比于AlphaGoZero，有几点不同：a)首先AlphaGoZero是在假设结果为赢/输二元的情况下，对获胜概率进行估计和优化。而AlphaZero会将平局或其他潜在结果纳入考虑，对结果进行估计和优化;b)AlphaGo和AlphaGoZero会旋转棋盘位置进行数据增强，而AlphaZero不会;c)AlphaZero只维护单一的一个神经网络，这个神经网络不断更新;4)AlphaZero中，所有对弈都重复使用相同的超参数，因此无需进行针对特定某种游戏的调整[4]。由于Alpagozero与Alphazero在围棋原理上并没有太大差异，因此后文只是主要介绍AlphagoZero。AlphagoZero的伟大之处就是摆脱了人类知识的限制，仅仅依靠规则，从0开始训练，从而达到了登峰造极的地步。这种无师自通的学习方式对整个AI具有里程碑式的意义。并且在今后的研究中，我们可以将这种能力泛化到其他领域中，相信可能会取得巨大的突破。之前的AlphaGo版本首先基于人类围棋比赛来训练如何学习围棋。但AlphaGoZero跳过了这一步，从完全随机的开始来学习围棋。通过这种方式，它快速超越了人类棋手的水平，经过3天的训练后以100:0的比分打败了之前曾战胜世界冠军的AlphaGoLee。AlphaGoZero利用了新型的强化学习算法，在训练过程中它是自己的老师。该系统的神经网络最初时对围棋一无所知，初始时只能通过随机走子并反馈输赢结果来进行自我学习。它通过将深度神经网络与MCTS相结合进行自我对弈。在自我对弈的过程中随着神经网络的参数更新，Alphagozero变得越来越强。并且由于网络的简化和算法效率的提升，使得计算资源需求量大大下降。AlphagoLee采用了48块谷歌TPU，但Alphagozero只采用了4块TPU。但是根据权威人士估算，实际在自我训练（self-play）时可能使用上千块TPU（Alphzero实际使用了5000块）。个人普通电脑上想训练出AlphaGoZero的模型需要1700年[5]。1.AlphaGoZero中的强化学习原理Alphagozero使用一个包含参数θ的神经网络fθ。该神经网络以当前盘面和历史走子作为输入。原文中作者提取了17个通道的19*19二值图像作为特征输入，其中有八个通道是当前己方当前盘面Xt加上此前七步棋走法Xt−1...Xt−7。还有八个通道是对手棋子盘面Yt加上之前七步棋走法Yt−1...Yt−7。第17个通道C表示当前行棋方，如果轮黑方行棋，整个19*19通道的取值就是1,如果轮白方行棋，则为0。最后将这17个平面串联起来，st=[Xt;Yt;Xt−1;Yt−1;...;Xt−7;Yt−7;C]。该神经网络输出(p,v)=fθ(s)。向量p表示选择每个落子a（包括pass）的概率：pa=Pr（a|s）。值v是标量，估计当前玩家从盘面状态s获胜的概率。该神经网络使用了许多含卷积层的残差块，批量归一化技术和非线性整流器（relu）。AlphaGoZero使用了一个新奇的强化学习算法来进行自我学习的（self-play）。在每个状态s，执行MCTS搜索，由神经网络fθ指导。MCTS输出搜索树上每个节点落子的概率π。其通常比神经网络fθ（s）输出的原始落子概率p更好。因此MCTS可以认为是一个增强版本的落子选择器。同时，MCTS选择每个落子，并且返回胜利者z进行价值网络性能评估—这样MCTS可以作为策略评估器。文中强化学习的主要思想就是循环使用落子选择器和策略评估器，该神经网络的参数不断更新，使得网络输出的(p,v)=fθ(s)更加接近MCTS输出的落子概率π和self-play的胜者z，即(p,v)→（π，z）。更新后的参数在self-play的下一次迭代中继续使用，使得后续的搜索更加强大。其原理如图3所示：图3AlphaGoZero中的强化学习原理图3（a）表示AlphaGoZero程序进行自我对弈时生成盘面状态s1;...;sT（t表示非终结步，T表示终结落子）。与此同时执行MCTS，进行落子选择，即at∼π