AlphaGo对局李世石两周年纪：AI程序攻克围棋的算法秘密

本篇文章9365字，读完约23分钟

这篇文章的主要特征是谷歌深度思维团队开发的alphago，Go ai。它在2016年击败世界顶尖棋手李世石的壮举引起了广泛关注。围棋是一种古老的棋盘游戏，每一步都有很多选择。因此，下一个位置非常重要，这就要求棋手有很强的直觉和抽象思维能力。正因为如此，人们一直认为只有人类擅长围棋。大多数研究人员甚至认为，具有这种思维能力的人工智能需要几十年才能出现。但是现在距离阿尔法戈对阵李世石已经两年了(3月8日-3月15日)，这篇文章就是为了纪念这个伟大的日子！

但更可怕的是阿尔法戈并没有停止前进。八个月后，它在一个围棋网站上以大师的名义与来自世界各地的冠军玩家玩了60套职业游戏，并赢得了一场全面的胜利。

这当然是人工智能领域的一大成就，并在全世界引起了新的讨论热潮。我们应该对人工智能的发展速度感到兴奋还是担忧？

今天，基于deepmind在《自然》杂志上发表的原始研究论文，我们将逐段对其内容进行简单明了的解释，并详细介绍alphago是什么以及它是如何工作的。我也希望读完这篇文章后，每个人都不会再被标题所抛出的耸人听闻的标题所吓倒，而是真正为人工智能的发展感到兴奋。

当然，你不需要掌握围棋技巧，你也可以理解这篇文章的观点。事实上，我只读过在线百科全书中关于围棋的一点点说明。相反，我实际上会用基本的象棋例子来解释相关的算法。每个人只需要知道两人棋盘游戏的基本规则，这样每个玩家就可以轮流行动，最终会产生一个赢家。此外，你不需要知道任何关于物理或数学的知识。

尽可能降低入门门槛的目的是让刚接触机器学习或神经网络的朋友更容易。本文还刻意降低了表达的复杂度，希望大家能尽可能的关注内容本身。

内容摘要

众所周知，alphago项目的目标是建立一个人工智能程序，并确保它能够在围棋领域与世界顶尖的人类玩家竞争。

为了理解围棋带来的挑战，让我们来谈谈另一个类似的象棋游戏。早在20世纪90年代初，ibm就创造了深蓝电脑(Deep Blue Computer)，击败了国际象棋比赛的伟大世界冠军加里卢卡斯帕罗夫(Gary Lu Kasparov)。深蓝是如何做到这一点的？

事实上，深蓝使用了一种非常暴力的方法。在游戏的每一步，深蓝都将考虑所有可能的合理举措，并沿着每一步进行探索，以分析未来的变化。在这样的前瞻性分析下，计算结果很快形成一棵巨大的决策树。之后，深蓝将沿着树结构返回原点，观察哪些移动最有可能带来积极的结果。然而，什么是积极的结果呢？事实上，许多优秀的棋手都为深蓝精心设计了棋艺策略，旨在帮助他做出更好的决策。例如，是保护国王还是在磁盘上的其他地方获得优势？他们为此建立了一个特定的评估算法，以便比较不同磁盘位置的优缺点(ibm以硬编码的形式将专家的象棋策略引入到评估函数中)。最后，深蓝会相应地选择精心设计的招式。在下一轮，整个过程再次重复。

这意味着深蓝将在每一步之前考虑数百万个理论位置。因此，深蓝最令人印象深刻的性能不在于人工智能软件，而在于它的硬件。ibm声称深蓝是当时市场上最强大的计算机之一。它每秒可以计算2亿个磁盘位置。

现在让我们回到开始。围棋显然更开放，所以如果你在这里重复深蓝策略，你根本不会得到理想的效果。因为每一步都有太多可选择的位置，电脑根本无法涵盖这么多潜在的可能性。例如，在国际象棋的开始阶段，只有20种可能的玩法；然而，在围棋方面，第一手玩家将有361个可能的落点，这个选择范围在整个游戏中已经非常广泛。

这就是所谓的巨大的空搜索室。此外，在围棋中，在正式阶段判断某个特定盘位的优劣并不容易，双方甚至需要安排一段时间才能最终决定谁是赢家。但是有没有一种神奇的方法让电脑在围棋领域取得成就呢？答案是肯定的，深入学习可以完成这项艰巨的任务！

因此，在这项研究中，deepmind使用神经网络来完成以下两项任务。他们训练了一组策略神经网络来决定在特定的盘位置中哪一个是最明智的选择(这类似于遵循某种直觉策略来选择移动位置)。此外，他们还训练了一组价值神经网络来估计特定盘布局对玩家的有利程度(或者这个位置对赢得游戏的目标的实际影响)。首先，他们使用人类象棋来训练这些神经网络(这是最传统但非常有效的监督学习方法)。经过这样的训练，我们的人工智能可以在一定程度上模仿人类下棋的方式。此时，它就像一个菜鸟级别的人类玩家。然后，为了进一步训练神经网络，deepmind让ai自己玩游戏几百万次(也就是强化学习的一部分)。这样，通过更充分的练习，ai的棋力得到了极大的提高。

有了这两个网络，deepmind的人工智能方案就足以拥有与之前最先进的围棋程序相当的棋艺水平。两者的区别在于，最初的程序使用了更流行的预设游戏算法，即蒙特卡罗树搜索(mcts)，这将在后面详细介绍。

但显然，我们还没有谈到真正的核心。Deepmind的人工智能方案不仅依赖于策略和估价网络，而且没有使用这两个网络来代替蒙特卡罗树搜索；相反，它使用神经网络来进一步提高mcts算法的有效性。实际结果确实令人满意，mcts的表现达到了超人的高度。这种改进的mcts变体是alphago，它成功地击败了李世石，成为人工智能发展史上最大的突破之一。

现在我们真正开始理解论文的内容，首先是游戏策略中使用的蒙特卡罗树搜索算法。其实说到这一点，每个人都有一个基本的了解，这足以顺利理解这篇文章的内容。但如果你想深入了解更多细节，请参考以下精彩视频和博客文章:

1.由udacity提供的短片系列(youtube/watch？v=onbysen2_ea)

2.解读杰夫·布拉德伯里的mcts(杰夫·布拉德伯里/帖子/2015/09/蒙特卡洛介绍-树搜索/)

由fullstack学院提供的Mcts教程(youtube/watch？v = FBS 4 lang s8m)

让我们回忆一下这篇文章的第一段。如上所述，深蓝计算机是如何构建包含数百万个磁盘位置和每一步棋步的决策树的？计算机需要模拟、观察和比较每个可能的着陆点。这是一个简单而直接的方法。如果普通软件工程师必须设计一个象棋程序，他们可能会选择类似的解决方案。

但是让我们想想人类是如何下棋的。假设你处于比赛的某个阶段。根据游戏规则，你可以做出十几个不同的选择，比如在这里移动棋子或者在那里移动皇后。然而，你真的列出了你脑子里能想到的所有动作并从这个长长的列表中选择吗？不，不，你会凭直觉将可行范围缩小到至少几个关键步骤(这里，假设你已经提出了三个明智的步骤)，然后考虑如果你选择其中一个，董事会的情况会如何变化。对于每一个动作，你可能需要15到20秒来考虑，但是请注意，在这15秒内，我们不会非常准确地推断下一个对抗和变化。事实上，人类经常会不假思索地放弃一些直觉选择(当然，优秀的玩家会比普通玩家想得更深更远)。其原因是你的时间有限，你无法准确预测对手会概述什么样的后续策略。因此，你只能让你的直觉指引你。我把这部分思维过程称为传播，所以请以后注意。

在完成了几个明智的步骤后，你最终决定放弃这个头痛的问题，采取最科学的步骤。

之后，对手会做出相应的反应。这一步可能超出了你的预期，这意味着你对下一步做什么更有信心。换句话说，你不必花太多时间在后续的传播上。或者，你的对手可能玩了一个聪明的把戏，这导致你被迫防守，不得不更仔细地考虑你的下一个选择。

游戏是这样进行的，随着情况的发展，你可以更容易地预测每一步的结果，传播时间也会相应缩短。

我之所以说了这么多，是希望用一种简单的方式告诉大家mcts算法的功能。它通过重复构建移动和位置搜索树来模拟上述思维过程。然而，它的创新之处在于mcts算法不会在每个位置执行潜在的移动(不同于深蓝)；相反，它会选择一小组合理的动作，并更聪明地探索它们。在勘探的过程中，它会将这些移动引起的情况变化分散开来，并根据计算结果进行比较。

(嗯，只要你理解了上面的内容，这篇文章的阅读基本上是符合标准的。(

现在，让我们回到报纸本身。围棋是一个完美的信息游戏。也就是说，从理论角度来看，无论你处于这种游戏的哪个阶段(即使你刚刚走出一两步)，每个人都有可能准确地猜测谁最终会赢或输(假设两个玩家都以完美的方式玩完整个游戏)。我不知道是谁提出了这个基本理论，但作为这个研究项目的前提，它确实很重要。

换句话说，在游戏状态下，我们可以使用函数v*(s)来预测最终结果，比如你赢得这场游戏的概率，范围从0到1。深度思维研究人员称之为最佳估计函数。因为一些盘位置比其他盘位置更可能带来获胜结果，所以前者可能比其他位置具有更高的估计。让我再强调一次，估计赢得比赛的概率值= 0比1。

但是别担心。假设一个叫foma的女孩坐在你旁边。她会告诉你这个决定是会导致你一举一动的胜利还是失败。你赢了，你处理了，还是你处理了？我认为这样的提示不会对你的移动选择有太大帮助，而且很烦人。相反，真正有帮助的是勾勒出所有可能的移动树以及这些移动将导致的状态。然后，foma会告诉你哪些州会把你推向胜利，哪些会导致整个树形结构的失败。突然间，foma成了你的完美伴侣，而不是烦人的面试官。这里，foma将是您的最佳估计函数v*(s)。以前，人们总是认为像Go这样的游戏不能像foma那样有一个准确的估值函数，因为有太多的不确定性。

然而，即使你真的有foma，她对所有可能的盘面位置的估计在真实的游戏中也不一定有效。因为在像国际象棋或围棋这样的游戏中，如前所述，即使你想在七八步之后预测整体情况，太多的可能性会使foma花费大量时间来获得分析结果。

换句话说，仅有foma是不够的。每个人都需要进一步缩小明智举措的具体范围，并据此推断出下一个趋势。那么我们的程序如何做到这一点呢？卢莎在这里首次亮相。卢莎是一位相当有技巧的棋手。她花了几十年时间观察象棋大师。她可以观察你的盘面位置，快速思考你能做出的所有合理选择，并告诉你职业球员做出各种判断的可能性。因此，如果你在一个特定的时间点有50个可能的移动选项，鲁萨会告诉你职业玩家选择每个选项的具体概率。当然，一些明智的举动有较高的概率，而其他无意义的举动有很低的概率。她是你的战略职能，p(as)。对于给定的状态s，她可以为你提供职业玩家可能做出的所有选择的相应概率。

接下来，你可以在鲁萨的帮助下找到更合理的棋步，foma会告诉我们这些棋步对游戏结果的实际影响。在这种情况下，你可以选择foma与路萨协商给出建议，或者路萨可以先给出建议，然后foma可以评估结果。接下来，选择一些选项进行后续影响分析，然后foma和lusha继续进行预测指导。这样，我们将能够更有效地掌握磁盘情况的趋势。这就是减少搜索空.的实际意义利用foma和lusha的预测结果，给出了象棋水平上的概率权衡，从而缩小了进一步探索的范围。这个系统被称为蒙特卡洛滚动。接下来，当你回到当前的走势时，你将能够得到与各种选项相对应的平均估值结论，并找到最合适的位置。然而，到目前为止，由于这两种功能的实际制导能力仍然较弱，其在Go中的性能仍然较差。

但没关系。

首先，给出一个具体的解释。在MCT中，初期的foma和lusha还不够熟练。然而，玩的游戏越多，它们预测可靠结果和玩家位置的能力就越强。文章指出，缩小高概率动作的具体范围实际上是一个复杂的表达，而鲁萨实际上通过提供职业选手的概率来帮助缩小要考虑的选项。以前的工作主要是利用这项技术来提供强大而成熟的人工智能玩家解决方案，具有简单的策略功能。

是的，卷积神经网络非常适合图像处理任务。而且，由于神经网络需要特定的输入内容并给出相应的输出结果，它实际上相当于一个函数。这意味着我们可以使用神经网络作为一个高度复杂的函数。从这个想法出发，我们可以传输一个磁盘位置图像，神经网络可以自己判断当前的情况。这样，所创建的神经网络将具有非常准确的策略和评估能力。

接下来，我们将讨论foma和luha的具体训练方法。为了训练策略网络(负责预测职业棋手的位置)，我们只需要将人类的游戏分数作为素材，并将其用于传统的监督学习。

此外，我们还希望建立一个略有不同版本的战略网络；它应该更小更快。你可以想象，如果鲁萨非常有经验，处理每一个地点的时间会相应地延长。在这种情况下，虽然她可以更好地缩小合理的范围，整个过程将会重复，所以可能会花太长时间。因此，我们需要为这项工作培养一个更快的战略网络(我们称之为卢莎的弟弟，杰瑞？就这么说吧。接下来，一旦人类玩家的数据被用来训练一个满足需求的策略网络，我们就可以让卢莎在围棋棋盘上与自己较量，以获得更多的练习机会。这是强化学习的体现，以建立一个更强大的战略网络版本。

之后，我们需要训练foma评估:确定获胜的概率。人工智能会在模拟环境中反复练习，并观察其最终结果吗？从错误中学习更好更先进的经验。

由于篇幅所限，这里我就不详细介绍网络培训模式了。您可以在本文末尾提供的论文链接中找到更多详细信息(请参考方法部分)。事实上，本文的主要目的不是解释研究人员如何加强对这些神经网络的学习。在之前发表的一篇文章中，deepmind已经谈到他们如何使用强化学习技术来教人工智能掌握Atari游戏。因此，在本文中，我只在内容总结中提到一点相关内容。同样，alphago最大的创新是deepmind研究人员使用强化学习和神经网络来改进流行的游戏算法MCT。强化学习确实是一个很酷的工具。研究人员在常规的监督训练后使用强化学习来微调策略和估计函数神经网络。然而，这篇研究论文的主要目的是证明这个工具的多功能性和卓越性，而不是教你如何在实践中使用它。

好了，现在每个人都应该对阿尔法戈有一个相对完整的印象。下面，我们将进一步讨论前面提到的各种问题。当然，涉及一些看似危险的数学公式和表达式是不可避免的，但是相信我，它们都很简单(我会详细解释)。因此，请放松。心态。

因此，第一步是训练我们的策略神经网络(lusha)，它负责预测职业运动员可能做出的判断。神经网络的目标是使人工智能发挥类似人类专家的作用。这种卷积神经网络(如前所述，这种特殊的神经网络非常擅长图像处理)采用电路板布局来简化图像内容。我们可以将整流器非线性添加到网络架构的每一层，这将使整个网络能够学习更复杂的技能。如果你以前训练过神经网络，你可能对relu layer并不陌生。这里我们也使用relu层。

这里，训练数据以随机磁盘位置对的形式存在，而标签是人类做出的选择。这部分训练采用传统的监督学习。

在这里，深度思维使用随机梯度上升。这是一个反向传播算法。这样，我们希望充分发挥奖励功能。奖励函数表示人类专家做出不同动作预测的概率；我们的目标是尽可能增加这种可能性。然而，在实际的网络训练中，我们通常只需要尽可能地减少缺失函数，这实质上是为了减少预测结果和实际标签之间的误差/差异，这就是所谓的梯度下降。在研究论文的实际实现部分，他们确实使用了传统的梯度下降法。你可以很容易地找到缺失的功能，而不是奖励功能，并通过尽可能减少后者来最大化前者。

这个策略网络有13层，我们称之为sl策略网络(sl代表监督学习)。它使用的数据来自一个受欢迎的网站，数百万用户在那里玩围棋。那么，sl政策网络的实际表现如何？

首先，其围棋水平高于其他研究者的早期发展成果。至于传播策略，你可能记得我们之前提到过，研究人员训练了一种更快版本的鲁萨，我们称之为杰瑞。在这里，杰瑞负责扮演他的角色。如你所见，杰里的准确率只有鲁萨的一半，但他的速度快了几千倍！当我们应用mcts算法时，jerry将帮助我们更快地完成后续情况变化的模拟。

要理解下一节的内容，你不能理解精读，但你需要同意我的解释是真实有效的前提。如果你想探索更多的细节并尝试，你可能需要先阅读一些关于强化学习的背景信息。

一旦你有了这个sl网络，下一步就是使用人类玩家的判断数据以监督的方式训练他们。之后，就是不断磨练判断能力的自我游戏。具体的实现方法也很简单。选择sl策略网络，将其保存在文件中，然后制作副本。

然后，你可以使用强化学习来微调它。这样，网络可以直面自己，并从结果中学习。

然而，这种训练方法有一个问题。

如果他在练习中只面对同一个对手，而对手一直在训练，他可能不会获得新的学习经验。换句话说，网络学到的只是如何打败对方，而不是真正掌握围棋的奥秘。是的，这是过度适应的问题:你在面对某个对手时表现不错，但你可能没有能力对付所有类型的球员。那么，我们如何解决这个问题呢？

答案很简单。当我们微调一个神经网络时，它将成为另一个风格稍有不同的玩家。这样，我们就可以把每一个版本的神经网络保存在一个玩家列表中，并保证每个玩家的表现都是不同的。好，在下一个神经网络训练过程中，我们可以从列表中随机选择不同的版本作为对抗对象。尽管它们来自同一组神经网络，但它们的性能略有不同。你训练的越多，你的版本就越多。问题解决了！

在这个训练过程中，指导训练过程的唯一目标是赢得比赛。此时，我们不再需要在网络上进行有针对性的培训，例如在磁盘上获取更多的位置。我们只需要提供所有可能的合理选择，你必须赢得以下目标。正因为如此，强化学习是如此强大，它可以用来训练任何游戏策略或评估网络，而不仅仅是围棋。

在这里，deepmind研究人员在不使用任何mcts算法的情况下测试了这个rl策略网络的准确性。正如我们之前提到的，这个网络可以直接获得盘面位置并考虑职业玩家的判断概率。到目前为止，它已经能够独立玩游戏了。因此，经过强化学习和微调的网络战争已经战胜了只使用人类象棋进行训练的监督学习网络。不仅如此，它还可以击败其他强大的围棋程序。

必须强调的是，即使在训练这套强化学习策略网络之前，监督学习策略网络已经有了超越现有技术的游戏水平，现在我们更进一步了！更重要的是，我们甚至不需要使用其他辅助方案，如估价网络。

至此，我们终于完成了鲁萨的训练。接下来，回到foma，它代表了最优估值函数v*(s)，也就是说，只有当两个玩家都完美地执行了他们的预期判断，她才能提供在当前盘的情况下获胜的可能性。显然，为了训练神经网络作为我们的估计函数，我们需要一个完美的对手。不幸的是，我们目前没有这样的对手。因此，我们派出了最强大的玩家rl策略网络。

它将提取当前的磁盘状态，然后输出你赢得这场游戏的概率。每个游戏状态都将作为一个数据样本，并用于以标签的形式标注游戏结果。因此，在50次亏损之后，我们获得了50个估值预测样本。

但这种做法实际上很幼稚。毕竟，我们不能也不应该把游戏中所有的50次都加到数据集中。

换句话说，我们必须仔细选择训练数据集，以避免过度拟合。每次一个玩家倒下，它将会对应一个新的位置，所以每次一个玩家倒下在围棋中是非常相似的。如果将所有选定的状态都添加到具有相同标签的训练数据中，则内容中会有大量的重复，这将不可避免地导致过度拟合。为了防止这种情况发生，我们只能选择那些更有代表性的游戏状态。例如，我们可以在游戏过程中只选择五个状态，而不是全部50个状态添加到训练数据集中。Deepmind从3000万个不同的游戏中提取了3000万个状态，从而减少了重复数据的可能性。事实证明，这种做法非常有效！

现在，让我们来谈谈这个概念:我们可以用两种方法来评估磁盘位置的价值。首先是选择最佳的估计函数(即之前已经训练过的函数)。另一种是利用现有策略(lusha)直接推断出盘面情况，并预测今年秋季带来的最终结果。显然，真正的游戏很少完全按照我们的计划进行。然而，deepmind仍然比较这两种方法的实际效果。此外，您可以混合这两个选项。稍后，我们将学习这个混合参数，所以请记住这个重要的概念。

在这里，我们的神经网络将试图给出最近的最佳估计函数，其效果甚至比数千次模拟获得的传播策略更好！Foma在这里的表现真的很棒。另一方面，deepmind也试图使用Luscharl策略，其精确度加倍，但速度极慢，这需要数千次模拟才能得出最终效果略好于foma的结论。但是它只是稍微好一点，而且速度太慢了。因此，foma赢得了比赛，她证明了自己有不可替代的价值。

现在，我们已经完成了战略和评估功能的培训，然后我们可以将它与mcts相结合，从而带来我们以前的世界冠军，大量的大师，一代人的突破，以及重268磅的alphaaaa go！

在这一节中，我们应该对mcts算法的工作原理有更深的理解。请不要担心，到目前为止提到的所有内容应该足以支持您顺利掌握相关内容。我们唯一需要注意的是我们如何使用策略概率和估值方法。在传播过程中，我们将两者结合起来，以缩小每次我们抛弃孩子时需要探索的具体范围。Q(s，a)表示估计函数，u(s，a)表示该位置的保存概率。我将在下面详细解释。

此外，应该注意的是，策略网络使用监督学习来预测职业玩家的判断。它不仅可以提供概率最高的选项，还可以提供每个选项的具体概率。这个概率可以存储在每个判断中。在这里，deepmind将其称为先验概率，并使用它来选择需要探索的选项。基本上，为了决定我们是否需要探索一个特定的选项，我们需要考虑以下两点:第一，我们通过这一步取得胜利的可能性有多大？是的，我们已经有一个评估网络可以回答这个问题。第二个问题是，职业球员考虑这一举措的可能性有多大？如果职业玩家不太可能考虑这一举措，我们为什么要浪费时间去探索呢？结论的这一部分由政策网络提供。(

接下来，我们来谈谈混合参数。如上所述，为了评估每个磁盘位置，我们有两个选项:第一，直接使用已用于评估磁盘状态的评估网络。其次，我们也可以利用现有的策略网络来快速推断游戏情况(假设对方玩家也采用符合预测的较低方法)，从而判断我们是输还是赢。一般来说，估计函数的效果优于传统的扩展函数。在这里，将两者结合将能够提供每个预测的权重估计，例如，55-50、46-60等等。如果你把估价X作为一个百分比，另一个项目是(100-x)%。这就是混合参数的含义。实际效果将在后面解释。

每次传播后，每个人都可以用模拟中获得的任何信息更新搜索树，从而进一步增强未来模拟的智慧。所有模拟完成后，您可以选择最佳选项。

让我们看看有趣的结论！

请记住，rl微调策略神经网络比sl人力培训策略神经网络具有更好的判断效果。然而，当它被添加到alphago的mcts算法中时，人工训练神经网络反过来超过了微调神经网络。同时，在评价函数方面(可以理解为在无限逼近中提供完美的判断)，使用rl策略进行foma训练比使用sl策略能带来更多的实际效果。

执行上述评估需要大量的计算资源，我们必须拿出盒子底部的硬东西来修复这些该死的程序。

但深层思维的含义实际上是

呵呵，和我们的节目相比，以前的围棋节目简直是落了孩子们的水平。

这里，让我们回到混合参数。在评估位置时，评估功能和传播比任何一个都重要。其余的是对深度思维的深入解释，揭示了一个有趣的结论！

请再读一遍红色下划线的句子。我相信每个人都能理解这句话基本上是对整个研究项目的全面总结。

来源：搜狐微门户