最强通用棋类AI，AlphaZero强化学习算法解读

译者：AI研习社（Champagne Jin）

双语原文链接：AlphaZero, a novel Reinforcement Learning Algorithm, in JavaScript

在本篇博文中，你将会了解并实现AlphaZero。AlphaZero是一个令人大开眼界且超乎寻常的强化学习算法，它以绝对的优势战胜了多名围棋以及国际象棋冠军。本文将会带你使用AlphaZero来解决一个益智小游戏（Dots and Boxes）并将其部署成一个纯JavaScript构建的Web应用。

AlphaZero最关键也是最令人诧异的一点，就是其能够在不依赖于外部先验知识的情况下在棋盘类游戏中获得超越人类的表现。AlphaZero通过自我博弈汲取经验知识来不断精通游戏。

我们会借助于Github上由Surag Nair开发的一个“简化后的、高度灵活的、经过注释的且易于理解的”Python版AlphaZero来进行该项目。

你大可以先去这里玩一玩这个游戏。而Web应用以及具体的JavaScript实现代码可以在这里获取得到。这份代码是从该Python实现中移植过来的。

https://carlos-aguayo.github.io/alphazero/  

有关AlphaZero的原理，你可以阅读这篇由Silver，David等人撰写的论文：“Mastering the game of Go without human knowledge” nature 550.7676 (2017): 354–359.

Dots and Boxes小游戏

Dots and Boxes是一个常见的儿童益智游戏，不过其具有令人讶异的复杂度。

该游戏中，两名玩家轮流在两个相邻点之间放置一条水平或垂直线。如果某个 1×1 的小正方形的 4 条边都被连上了，那么补齐这个小方块的一方就获得 1 分，得分的玩家被奖励多走一步，再连一条线。当棋盘已满时，游戏结束，并且得分最高的玩家获胜。

（译者注：这个游戏相当有意思，建议先去玩玩看，点这里。能不能战胜AlphaZero就看你了！）

人工智能与棋盘游戏

机器是否能够产生智能，我们已经为此思考了很久很久。那么，该如何验证机器具有智能呢？一个常用方法就是玩棋盘游戏，比如国际象棋，看看其是否具有超人的能力，甚至击败世界冠军。

1957年，Herbert Simon预言计算机系统能够在十年内击败国际象棋冠军。虽说实际上花的时间长了点，但是在1997年5月，计算机击败了当时的国际象棋冠军——Garry Kasparov。

（译者注：战胜Kasparov的机器被命名为DeepBlue，意为“深蓝”）

尽管这一里程碑事件意义非凡，但人们仍可以争论这一计算机系统是否“智能”。

这一类计算机系统由以下三个组件构成：

1. 人为定义的评价函数；

2. 博弈树搜索算法；

3. 极为强悍的硬件设备。

评价函数会将棋盘盘面作为输入并输出该盘面的“价值”。高价值表示当前玩家处于非常有利的位置。例如，在国际象棋棋盘上，玩家即将进行“将死”时就会对应一个非常高的值。

博弈树搜索算法（比如 Minimax）在所有可能的走棋中进行搜索，寻找那些能够确保得到高价值棋盘盘面的路径。对于那些已经明知不可能有效的路径可以直接放弃搜索，从而使算法变得更有效率。这就是 Alpha-beta剪枝 的作用。

最后，搭配上异常强悍的硬件，你就将拥有一台能够打败国际象棋世界冠军的机器。

问题在哪儿？经验丰富的棋手人为地精心调制这些评价函数。这些计算机系统还依赖于一本本记录着最佳走棋的开局棋谱。游戏中局，还会用到通过研究大师们的博弈而精心构造的评价函数。这些函数还会经由象棋大师们进一步的优化调整。

例如，我们完全就可以为 Dots and Boxes 构造一个评价函数。一个合理而直接的选择就是做一个得分的比较。得分的正向差值越大，游戏盘面就对我们越有利。大多数情况下，这是可行的。然而，在 Dots and Boxes 中，就像许多其他棋盘类游戏一样，最佳的走法可能需要牺牲短期利益来换取长期利益。在 Dots and Boxes 游戏中，有时最好不要急于得分并获得额外先手，相反，要迫使对手走某一步棋。因此，我们必须考虑大量复杂场景并精心调制评价函数！

击败Kasparov的评价函数需要识别多达8000个盘面特征！而且其中绝大多数都是手动描述并调整的！

所以，倒也不是贬低这个击败国际象棋世界冠军重要里程碑的意思，只是，需要顶级玩家来定义这些计算机的行为并手动调整如此多的变量实在是有够折腾人的。

AlphaZero是什么？为何它如此令人心潮澎湃？

AlphaZero是首个能够在国际象棋、围棋等游戏中达到超越人类水平、击败世界冠军的计算机系统，且它仅依赖于游戏规则，无需任何人类先验知识。

仅凭给定的游戏规则，AlphaZero即可进行自我博弈。逐步习得游戏策略与技巧，很快即可获得超人的表现。

像DeepBlue这样的系统会需要国际象棋专家的协助，而AlphaZero却是凭借自我博弈来变强大的。不单单是在国际象棋上，哪怕是围棋，AlphaZero同样表现出超越人类的强大统治力。考虑到围棋相较于其他棋盘游戏更大的博弈空间等因素，对计算机来说，围棋是个极为复杂的游戏。

人类从几千年来数百万次的博弈中方才积累了诸如围棋和国际象棋等游戏的技艺，而AlphaZero，一个仅使用游戏规则信息的算法，却能够在几天时间内重新寻获这些知识并发现新的游戏策略。

甚至还有一部关于它的纪录片。

（译者注：这部纪录片很值得一看，无法访问YouTube的同学可以在B站观看，链接在此。不过需要注明的是，本纪录片中实际上使用的是AlphaGo算法，而非AlphaZero，准确来说，AlphaZero是AlphaGo的进阶版本，全名为AlphaGo Zero。纪录片中与李世石博弈的AlphaGo在跟AlphaGo Zero 博弈时，0-100全负，并且，AlphaGo Zero在训练中未使用任何手工设计的特征或者围棋领域的专业知识，仅仅以历史棋面作为输入，其训练数据全部来自于自我博弈。可谓恐怖如斯！）

AlphaZero是怎么做到仅凭自我博弈就习得技艺的呢？

回想一下，像DeepBlue那样依赖于人为定义的“评价函数”的系统会把棋盘的盘面状态作为输入，再输出该状态的“价值”。

如今，对于深度学习模型来说，输入一张照片然后识别出照片里是猫还是狗简直简单到爆了。那么有个想法就是，把棋盘盘面作为一个深度学习模型的输入并且训练它，让它预测这样的盘面布置是会输还是会赢。

但是，要训练一个机器学习模型，就需要数据，海量的数据。从哪儿能得到那么多棋局博弈的数据呢？很简单，我们就让电脑自己跟自己下着玩儿，生成一堆棋局，然后再把它们做成一个数据集用来训练。

AlphaZero的训练算法

这个算法简单明了：

1. 让计算机自我博弈数局，记录每一步走棋。一旦胜负已分，就给之前的每一步走棋打上标签——棋面最终是“赢”或是“输”。如此一来，我们就获得了一个可以用于神经网络（Neural Network，NN）训练的数据集，让该网络学会判断给定棋面是“赢面”还是“输面”；

2. 复制这个神经网络。用上一步得到的数据集训练该克隆网络；

3. 让克隆网络与原始神经网络互相博弈；

4. 上一步中获胜的网络留下，败者弃之；

5. 重复第1步。

呼哈，就像是魔法似的，经过多轮迭代后，你就将获得一个世界级模型。这个模型在短短4小时内便超越了最强大的计算机象棋程序。

AlphaZero的组件

AlphaZero由两部分构成。我们已经提及了第一部分，就是神经网络。第二部分则是“蒙特卡洛树搜索（Monte Carlo Tree Search）”，或者简称MCTS。

1. 神经网络（NN）。以棋面作为输入，输出该棋面的“价值”，外加所有可能走法的概率分布。

2. 蒙特卡洛树搜索（MCTS）。理想情况下，使用神经网络就足以选择下一步走法了。不过，我们仍然希望考虑尽可能多的棋面，并确保我们的的确确选择了最好的走法。MTCS和Minimax一样，是一种可以帮助我们寻找可能棋面的算法。与Minimax不同的是，MTCS能够帮助我们更加高效地搜寻博弈树。

让我们深入细节，看一看下一步走棋究竟是如何得到的

我们不妨先看看AlphaZero在决定下一步走棋（竞技模式）时具体干了什么，然后再去探究它的训练过程，这样可以帮助我们更容易地理解AlphaZero。

神经网络在分类这件事儿上表现得异常出色，例如区分猫跟狗。所以这里的想法很简单直接，神经网络能学会区分棋局输赢的类别吗？更具体地来说，就是让神经网络预测一个表示棋局输赢概率的数值。此外，它还将输出所有可能走法的概率分布，来表示我们下一步应该如何决策。

神经网络将博弈状态作为输入并输出一个输赢概率数值以及所有可能走法的概率分布。对于Dots and boxes这个小游戏来说，游戏状态由三个元素表示：首先，某一条线是否已被占用，这可以用一个含有0与1的数组来表示，如果玩家已经画了某条线，则置其为1，否则为0；第二，当前的走法是否是空过；第三，双方玩家的得分。我们可以用这三个元素来表示所有需要的信息，用其计算当前盘面的价值并预测下一步的走法。

让我们分析一下下图中的博弈情形，该轮轮到蓝色玩家走。蓝色方有两个选择，按照图中上面的走法来画线就会输，按照下面的走法就会赢。

  （译者注：左下角是每根线的编号。如果你刚刚已经在网页上跟AlphaZero玩过这个游戏了，那么相信这张图是很容易理解的。上方第一种走法只顾眼前短期利益，最终葬送好局。）

如果蓝色方走23再走21，那么红色方必赢。然而，如果蓝色方走23后再走9，那蓝色方就赢了。要是AlphaZero在蓝色方，它怎么知道哪一种走法能够赢下来呢？

你可以用这个在线notebook复现我们即将呈现的效果。

将棋面送入神经网络，我们就能得到下一步走在不同位置的概率：

同时，我们还能得到当前棋局的赢面有多大：

你可以在这里查阅与这些输出相关的代码。

这些输出值有一些很有意思的地方，我们来细品一下：

1. 在所有可能画线的位置，23号、21号以及9号的概率值最大。如果神经网络选择在23号以及21号位置处画线，那么它就能够得到1分。另外，23号才是能够赢下来的走法，而相应地，从网络输出的概率来看，23号位置的概率（0.53）恰好比21号的（0.46）稍微高一点儿。

2. 神经网络也会给不能够画线的位置输出一个概率值。虽然如此，但是代码上还是要进行限制，以确保计算机不会在不合规则的位置画线。

3. 棋面的输赢概率为-0.99。这意味着AlphaZero认为它已经输掉游戏了。这个概率值的范围是-1（输）到1（赢）。这个值本应该很接近于1（赢）而不是-1（输）的，毕竟我们知道目前这个局面赢面很大。也许我们应该多训练几轮来让AlphaZero准确预估棋面的输赢概率。

我们很容易利用神经网络的输出来决定下一步的走法。

在棋盘游戏中（现实生活中也是），玩家在决定下一步怎么走的时候往往会“多想几步”。AlphaZero也一样。我们用神经网络来选择最佳的下一步走法后，其余低概率的位置就被忽略掉了。像Minimax这一类传统的AI博弈树搜索算法效率都很低，因为这些算法在做出最终选择前需要穷尽每一种走法。即使是带有较少分支因子的游戏也会使其博弈搜索空间变得像是脱缰的野马似的难以驾驭。分支因子就是所有可能的走法的数量。这个数量会随着游戏的进行不断变化。因此，你可以试着计算一个平均分支因子数，国际象棋的平均分支因子是35，而围棋则是250。

这意味着，在国际象棋中，仅走两步就有1,225（35²）种可能的棋面，而在围棋中，这个数字会变成62,500（250²）。在Dots and Boxes游戏中，对于一个3×3大小的棋盘，初始的分支因子数是24，随着棋盘不断被填充，这个数字会不断减少（除非空过）。所以，在行至中局，分支因子变为15的时候，仅走3步就会有多达2730（15*14*13）种可能的棋面。

现在，时代变了，神经网络将指导并告诉我们哪些博弈路径值得探索，从而避免被许多无用的搜索路径所淹没。现在神经网络告诉我们23号和21号都是非常值得一探究竟的走法。

接着，蒙特卡洛树搜索算法就将登场啦！

蒙特卡洛树搜索（MCTS）

神经网络为我们指示了下一步可能的走法。蒙特卡洛树搜索算法将帮助我们遍历这些节点来最终选择下一步的走法。

去这个链接看看论文中有关蒙特卡洛树搜索的图形化描述。

使用MCTS的具体做法是这样的，给定一个棋面，MCTS共进行N次模拟。N是模型的超参数。N次模拟结束后，下一步的走法将是这N次模拟中所经次数最多的一步。你可以由这里的代码一窥究竟：

进行N次MCTS模拟

一次MCTS模拟从当前的棋盘状态出发，沿着博弈树中具有最大“置信区间上界（UCB）”值（后文会给出定义）的节点不断向下追溯，直到遇到之前从未见过的棋盘状态，也叫做“叶子”状态。这就是原论文中Part A所谓的“选择（Select）”。

置信区间上界是什么呢？用数学形式来说就是 Q(s, a) + U(s, a)。其中 s 是状态，a 是走法。Q(s, a) 是我们希望由走法“a”构成状态“s”能够获得的期望值，与Q-Learning中的期望值一致。记住了，在这种情况下，该值的范围是-1（输）到1（赢）。U(s, a) ∝ P(s, a) / (1 + N(s, a))。这意味着U正比于P和N。其中，P(s, a) 是元组 (s, a) 的先验概率值，这个值是从神经网络那里得到的，而 N(s, a) 是已经访问过状态 s 与对应的走法 a 的次数。

UCB的要点在于，其起初更倾向于具有较高先验概率（P）和较低访问次数（N）的走法，但渐渐地会倾向于具有较高动作价值（Q）的走法。

你不妨看看这里的代码好好理解一下。

Part A——选择具有最高置信区间上界值的走法

一旦找到一个叶子状态，就把这个棋面状态送入神经网络。这是论文中称作的Part B，“扩展与评估”。且看代码。

Part B——扩展与评估

最后，我们将传回神经网络返回的值。这就是论文所说的Part C——“备份”。您可以在此处看到相关代码。

Part C——备份

决定下一步如何走

让我们来看看AlphaZero面对上文提及的棋面时会决定如何走。

AlphaZero会进行50次蒙特卡洛树搜索模拟。

你可以用这个在线notebook复现下面展示的结果。

下面展示的就是每次迭代的路径：

上面显示的结果的意思是：在第一次模拟中，由于算法之前并未见过这个棋面，因此输入的棋面实际上是一个“叶子”状态节点，需要先“扩展”这个节点。所谓扩展就是把棋面送到神经网络里对每个位置进行概率评估。

在第二次模拟中，因为上步我们已经扩展了根节点，因此它不再是一个“叶子”节点了，就此，我们可以对具有最高置信区间上界值的节点进行搜索：

具有最大置信区间上界值的是23号位置。搜索算法深入在23号位置画线的状态，由于这个状态在之前搜索算法也没见过，因此这也是个“叶子”节点状态，搜索算法会“扩展”这个状态。就这样，第二次模拟也完成啦。

这个时候，还记得上面神经网络输出的输赢概率吗，神经网络认为在23号位置画线必输无疑。神经网络可以进行更多轮的训练来确保这的确是个很差的走法。不过目前来说，这就足够了，我们后面会认识到这一点的。

接下来的模拟中，会依次搜索剩下的走法中具有最大置信区间上界的状态，不过只有下面给出的这些。因为在访问完以下这些走法之后，搜索算法会发现剩下的状态都具有很低的概率，也就是说其置信区间上界都很低，也就不必搜索了。

在之后的模拟中，一个令人兴奋的模式逐渐揭开面纱。记住，能够赢下来的走法序列是23，24（对应空过），9。

（译者注：填上23号之后，由于补全了一个正方形，因此对方空过。这里给出的序列是两方的走法序列。）

在第10至第24次模拟中，很明显，MCTS已经把注意力放在了21号节点与23号节点上。这说得通，因为这两种走法都能让我方得1分。

在第33至第41次模拟中，搜索算法深入探究了那些导致败局的走法。这里要注意到一件有意思的事情。尽管追究得很深，但是搜索算法并没有抵达游戏终局，后面还有可以走的步骤。

接着，在第42次至第50次模拟中，通过神经网络的场外援助，搜索算法意识到了23，24，21或者21，24，23都不是好的走法，这下子，它全然投入到能够获胜的走法序列：23，24，9。

在50次模拟后，是时候做出决定了。MCTS选择了其访问次数最多的位置。下面列出了每个走法的访问次数（只统计路径中的第一个位置）：

3，9，12，17，18以及19号位置只在最初10次模拟中访问了1次。接着MCTS专注于21和23号位置，且在最后9次模拟中都先走23号。因为23号位置被访问次数最多，达到了28次之多，因此MCTS最终返回23作为下一步的走法。

关键点是什么？

1. 通过每一次模拟，MCTS依靠神经网络， 使用累计价值（Q）、神经网络给出的走法先验概率（P）以及访问对应节点的频率这些数字的组合，沿着最有希望获胜的路径（换句话说，也就是具有最高置信区间上界的路径）进行探索。

2. 在每一次模拟中，MCTS会尽可能向纵深进行探索直至遇到它从未见过的盘面状态，在这种情况下，它会通过神经网络来评估该盘面状态的优劣。

如果我们将上述方法与使用带有Alpha-Beta剪枝以及一个评价函数的Minimax之类的传统方法进行比较，我们可以发现以下几点：

1. 在Minimax中，博弈树的搜索深度是由算法设计者自行设定的。它无论如何都会搜索到那个深度，然后用那个可爱的评价函数进行盘面评估。要是没有Alpha-Beta剪枝的话，它就得访问给定深度下所有可能的盘面节点，极为低效。在上面的情形中，如果还可以走8步，要搜索的深度为3，就意味着总共需要评估336个盘面状态。使用MCTS，仅仅用了50次模拟，也就是50次评估，而且在搜索中还尽可能搜索得足够深。

2. Alpha-Beta剪枝能够帮助我们将336这个数字减少。然而，却并不能帮我们找到一条优良的博弈路径。

3. 我们是一直在用神经网络来对盘面进行评估的，而不是某个认为定义的评价函数。

4. 很有意思的是，在起初几步中，神经网络并没有做出正确的盘面评估。然而，随着在博弈树中搜索的深度提升，它自动修正了它的输出，而且搜索并未抵达游戏终局。

5. 最后，要注意到AlphaZero的优雅与简洁。而在Alpha-Beta剪枝中，你的不断跟踪alpha和beta参数来知悉哪些路径被砍掉了，你还得用一个人为定义的评价函数，更不要说这个函数又笨重又丑陋。MCTS与NN让所有这一切都变得异常优雅与简洁。你甚至可以在JavaScript中把这一切都搞定！

训练神经网络

至此，我们还缺最后一个关键部分。究竟该如何训练这个神经网络呢？

不要害怕，嘻嘻，贼简单。我们之前提到的步骤是：

1. 让计算机在“训练模式”下自我博弈数局，记录每一步走棋。一旦胜负已分，就给之前的每一步走棋打上标签——棋面最终是“赢”或是“输”。如此一来，我们就获得了一个可以用于神经网络（Neural Network，NN）训练的数据集，让该网络学会判断给定棋面是“赢面”还是“输面”；

2. 复制神经网络。用上一步得到的数据集训练该克隆网络；

3. 让克隆网络与原始神经网络互相博弈；

4. 上一步中获胜的网络留下，败者弃之；

5. 重复第1步。

什么叫在“训练模式”下进行博弈呢？这个区别非常细微。当在“竞技模式”下博弈时，我们会选择访问次数最多的走法。而在“训练模式”下，在游戏刚开始的一定步数内，我们会将不同走法的访问次数变成概率分布，以此鼓励网络对不同的走法进行探索。举个例子，假设有3中可能的走法，对应的访问次数分别是[2, 2, 4]。那么在竞技模式中，由于第三种走法的访问次数最多，所以我们就选择第三种走法。但是在训练模式中，我们会将[2, 2, 4]变成一个概率分布，因为2+2+4=8，因此概率分布就是[2/8, 2/8, 4/8] 或者说是 [0.25, 0.25, 0.5]。换句话说，我们在50%的情况下会选择第三种走法，而第一以及第二种走法有25%的概率被选中。

接着，我们用一个简单的井字棋来描述一下数据集的构建。

在上面这副图片中，1号玩家执X获胜。

我们可以将盘面中未落子的地方记作0，1号玩家打X的位置记作1，2号玩家打圈的地方记作-1。

那么，上图中的棋盘各个盘面就可以变成下边这样：

或者，我们将盘面降为一维表示，就是这样：

然后我们要做两件事情。第一件事，找到所有属于1号玩家轮次的棋盘盘面。我们只会给神经网络喂入1号玩家的相关盘面数据。在井字棋中，很容易就能挑选出来。而2号玩家轮次的那些盘面，直接将其数据取相反数，使其变为1号玩家视角下的盘面状态。

也就是，将：

变为：

第二件事，我们对获得的每一条数据向后增加1位数据，“1”表示1号玩家赢，“-1”表示1号玩家输。如此一来，数据就变成了：

嗯，这个数据集现在有模有样了呢！你看，这样一来，我们就获得了一批用于训练神经网络的数据，并让神经网络学习判断盘面的输赢。

哦，我们好像漏掉了概率。那些不同走法的概率分布怎么得到呢？记住了，在训练模式下，我们每一步也还是会进行MCTS模拟的。正如我们会记录下不同的盘面，我们也会将对应的概率进行记录。

然后我们就会复制（或者说是克隆）神经网络，并用新获得的数据训练这个克隆网络，我们所期望的，是用上新获得的数据后，这个克隆网络可以变得更强一点儿。通过与原始网络进行对抗，我们可以验证其是否真的变强了。如果克隆网络的胜率超过55%，我们就把原始网络丢掉，这个克隆网络便可取而代之。

这个过程会一直重复下去，神经网络也在这个过程中不断变强。

你可以在这儿看到论文中的相关图表。

数据集中如何包含更多更具代表性的数据呢？相较于神经网络输出的原始走法概率分布，数据集会倾向于根据MCTS生成的概率来选择更具借鉴性的走法。通过让MCTS搜索足够多较深的博弈路径，神经网络可以获取更优质的数据并更加高效地学习。

试试看用这个Colab Notebook训练一个Dots and Boxes模型吧。

将其部署至一个Web应用

几个月前，我发了一篇博文，带你大致过了一遍使用TensorFlow.js将Keras或者TensorFlow模型部署至JavaScript的过程。这里我们要做的事情大差不差。我们会把用Keras训练得到的模型转换成能够被TensorFlow.js调用的模型。

这个Notebook展示了如何将一个预训练的Dots and Boxes博弈模型转换为一个TensorFlow.js模型。

一旦转换完成，这个模型就能够很轻松地使用JavaScript进行调用。不妨看看这里。

结论

在本篇博文中，你认识了AlphaZero，一个能够在双方零和博弈的棋盘游戏中战胜世界冠军的强化学习算法。

你也了解了它是如何使用蒙特卡洛树搜索算法以及神经网络来找到最佳的下一步走法，以及如何训练这样一个神经网络。

AI研习社是AI学术青年和AI开发者技术交流的在线社区。我们与高校、学术机构和产业界合作，通过提供学习、实战和求职服务，为AI学术青年和开发者的交流互助和职业发展打造一站式平台，致力成为中国最大的科技创新人才聚集地。

如果，你也是位热爱分享的AI爱好者。欢迎与译站一起，学习新知，分享成长。