AlphaGo外传——机器学习与算法智能

阿狗数学的远房亲戚AlphaGo，即阿尔法围棋，相信大家都不陌生。它是由谷歌旗下的DeepMind公司创始人Demis Hassabis领导的团队开发的人工智能程序。这个程序在2016年和2017年出尽风头，它让围棋高手陷入窘境，让围观者叠声惋惜，让天才对未来忧心忡忡。下面我们就来剖析一下AlphaGo的类脑机制，看看它的智商到底有多高，因何取得如此战绩。

2015年10月，AlphaGo的初始版本AlphaGo Fan以5比的傲人战绩击败欧洲围棋三连冠棋手樊麾，首胜围棋职业选手，并将天才棋手Fan的落败记入史册。

2016年3月，升级版AlphaGo Lee与围棋世界冠军、职业九段棋手李世石对战，并以4比1的比分获胜；2016年末至2017年初，再次升级的新版AlphaGo Master在中国棋类网站上以“大师”（Master）为注册帐号与中日韩数十位围棋高手进行快棋对决，连战60局未尝一败。

2017年5月，在中国乌镇围棋峰会上，AlphaGo Master与排名世界第一的棋手柯洁对决3局，无一败北。见好就收，功成名就的AlphaGo团队宣布不再参加围棋比赛，退出了被自己横扫的人类围棋圈。围棋界普遍认为，AlphaGo的棋力已经超过了人类顶级职业棋手的水平。然而，我们要讲的故事还远远没有结束。

2017年10月18日，DeepMind公司发布了AlphaGo的最新版本AlphaGo Zero。这个Zero经过三天三夜的训练，就以100比的离奇战绩击溃Lee。再经过近四十天的训练，它又击败了Master。Zero最引人注目的不仅仅在于它的战绩，更在于它完全脱离了人类棋谱，仅仅依靠自我训练，并且以更少的计算力度“超越”了前辈。AlphaGo神奇战绩的秘密都藏在它的脑组织——算法之中。

根据AlphaGo团队发表的首篇论文，任何完全信息博弈都是一种搜索，而搜索的复杂性则由搜索空间的宽度与深度决定。对围棋来说，搜索宽度约为250，深度约为150。AlphaGo的早期版本，包括Lee和Master，其主要原理是深度学习、强化学习与蒙特卡罗树搜索。

深度学习主要在于建立两个受过训练的模型网络：价值网络和策略网络。AlphaGo利用价值网络来削减搜索的深度，利用策略网络来削减搜索的宽度，从而极大地缩小了搜索空间。

价值网络是一种用来评估、度量当前棋盘状态的神经网络。它的输入是棋盘中19*19个点的状态，输出是获胜的期望值。理论上总存在一个高级函数，它可以用来计算这个期望值。但遗憾的是，目前还没有找到计算期望值的高级函数，所以人们只能用多层的神经元网络来拟合这个函数。对某些棋盘状态输赢是很容易判断的，因而它们的后续状态并不需要继续探索。价值网络的目的就是通过确定那些输赢容易判断的棋盘状态来削减搜索深度。

策略网络则是一种根据当前的棋盘状态，评估每种着子的胜率，并从中选择最大胜率着子的神经网络。其实这就是给出选择可能着子的概率分布。同样，也存在一个高级函数，它可以用来计算所述概率分布。也出于同样原因，人们只能利用多层神经元网络来拟合所述高级函数。因为有些着子获胜概率极低，可以忽略，因此可以利用策略网络确定可忽略的着子来削减搜索宽度。

AlphaGo具体使用深度卷积神经网络（CNNs）来训练价值网络与策略网络。神经网络是用来模拟人类或动物大脑，利用多个神经元共同计算逼近某种复杂函数的方法。任何一种价值判断都可以理解为某种从输入到输出的多元函数。数学上已经证明，使用神经网络可以无限逼近上述多元函数。由于围棋盘可以看作一幅19*19的图像，所以AlphaGo团队选择了适合处理图像的深度（即多层的）卷积神经网络来构建价值网络与策略网络。

基于深度卷积神经网络，AlphaGo先进行策略网络学习，再进行价值网络学习。策略网络学习又分为两步，第一步是有监督的学习，即学习人类的既往棋谱，也就是KGS围棋平台上的3000万个着子位置。AlphaGo会随机选择着子位置，利用以往的棋谱来预测人类棋手可能的应对着子位置，从而判断每种着子的胜率。如果仅使用着子历史和位置信息，预测成功率为55.7%；加上其他因素，成功率可以提高到57%。第二步是强化学习，即在监督学习策略网络的基础上，不断让当前策略网络与前一策略网络进行对弈，并利用输赢不同的反馈来优化策略网络。价值网络训练与策略网络训练类似，不过输出的是获胜的概率。

除了策略网络和价值网络，AlphaGo还有一个重要组成部分：快速着子分析模块。该模块与监督学习策略网络一样，由人类棋谱训练而来，可以看作是一个简化版的监督学习策略网络，用于快速得到蒙特卡罗树搜索过程中节点的模拟胜率。

在通过深度学习与强化学习完成价值网络、策略网络与快速着子分析模块的构建后，AlphaGo通过蒙特卡罗树搜索来实现思考搜索，其过程大致如下。

首先假定当前棋局状态为S，并且对每种可能的着子a，都有着子价值Q(S,a)、初始概率P(S,a)及访问次数N(S,a)。然后针对当前棋局，蒙特卡罗树搜索不断地进行棋局模拟。

在一次棋局模拟过程中，假设从根节点(S,a)出发到达第t个节点时的棋局状态是S(t)，这时在所有可能的着子a中找出着子a(t)，使得Q(S(t),a)+u(S(t),a)最大。式中的Q(S(t),a)为当前节点的着子价值，它是由之前所有经过该节点的棋局模拟的最终胜率求平均得到，而且u(S(t),a)正比于P(S(t),a)/[1+N(S(t),a)]，其中初始概率P(S(t),a)为通过策略网络得到的获胜概率，访问次数N(S(t),a)为到目前为止所有棋局模拟过程中经过节点(S(t),a)的次数（这里引入节点访问次数是为了鼓励尝试新的节点）。

之后将着子a(t)作为棋局模拟的下一节点，并重复这一过程直至一个从未展开过的节点，该节点的子节点的初始概率在之前的棋局模拟中尚未计算。接下来对该节点的所有子节点计算最终胜率和初始概率，其中最终胜率是由通过价值网络得到的获胜概率与通过快速着子分析模块多次模拟棋局得到的模拟胜率加权平均所得到的。在选定最佳着子后，利用该着子的最终胜率，对当前棋局模拟经过的所有节点的着子价值与访问次数进行更新。最后，完成本次棋局模拟，并开始下一次棋局模拟。

在蒙特卡罗树搜索结束之后，由于每次棋盘模拟都是选择最佳节点，AlphaGo会选择根节点下访问次数最多的子节点作为下一步的着子节点。至于蒙特卡罗树搜索什么时候终止，这要看AlphaGo有多少时间来走下一步棋。

以上是AlphaGo在Zero之前的几个版本所使用的算法。而在2017年10月推出的Zero与前辈相比，棋力有了很大提高，当然所用的算法也有很大改善。下面我们来看一下Zero的算法有哪些改进。

首先，取代之前同时使用策略网络与价值网络，Zero使用同一神经网络，输入棋局状态和历史着子，输出当前棋局的获胜概率以及选择可能着子的概率分布。然后，不再进行监督学习，Zero只进行强化学习，抛弃了人类棋局经验。之后，与以前的需要在棋局之前进行训练的强化学习网络不同，Zero可以直接通过棋局进行自我训练。

最后，Zero在棋局中使用改进后的蒙特卡罗树搜索来实现思考过程。之前的棋局模拟是在到达未展开的节点时结束，而改进后的棋局模拟在下列三种情形发生时也会结束：对手认输，得到的最终胜率低于阈值，棋局模拟长度达到所规定的最大长度。在每次棋局模拟结束，Zero还会根据棋局模拟结果与神经网络计算结果来调整神经网络的参数，更新神经网络并开始下一轮棋局模拟。

Zero在不断与自己对弈的过程中，获得了许多关于围棋博弈的新知识，并纠正了一些人类有关围棋博弈的错误观念。换句话说，Zero在探索围棋博弈的过程中，大大提高了自身的博弈能力，其围棋博弈技术与策略在某些方面已经超越了人类。目前尚无合理的解释，Zero是如何在如此短的时间内达到了如此高的水平。

在围棋领域AlphaGo虽然已经在某种程度上超越了人类，可是它已经坚定地退出了围棋界，人们再也无法看到它与人类交手的场景。然而我们有足够的理由相信，其他类似于AlphaGo的人工智能程序譬如BetaOx（百牛），还会出现，还会在不远的将来让许多其他领域的天才在与其挑战中一败涂地。更令人担忧的是，人工智能会不会使很多职业人士失去自己热爱的工作，无奈地离开自己的工作岗位？我们是应该期待还是拒绝人工智能时代的到来呢？

（本文参考了AlphaGo团队的两篇论文《Mastering the game of Go with deep neural networks and tree search》、《Mastering the game of Go without human knowledge》，张梦迪等人的《从AlphaGo的成功说起》，赵浩彤的《科普一下AlphaGo的论文算法并谈谈自己的思考》和陈老师与待字闺中的《AlphaGo其实挺“笨”的》等著作。文中的图片均来自网络及所列参考文献。）