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

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

深度学习

最后更新 2020-11-27 19:37 阅读 329

最后更新 2020-11-27 19:37

阅读 329

深度学习

##FlyAI文献翻译
**英文原文：**[：AlphaZero, a novel Reinforcement Learning Algorithm, in JavaScript](https://towardsdatascience.com/alphazero-a-novel-reinforcement-learning-algorithm-deployed-in-javascript-56018503ad18)

> **标签** ：强化学习

In this blog post, you will learn about and implement AlphaZero, an exciting and novel Reinforcement Learning Algorithm, used to beat world-champions in games like [Go](https://en.wikipedia.org/wiki/Go_(game) "Go") and Chess. You will use it to master a pen-and-pencil game ([Dots and Boxes](https://en.wikipedia.org/wiki/Dots_and_Boxes "Dots and Boxes")) and deploy it into a web app, entirely in JavaScript.

AlphaZero’s key and most exciting aspect is its ability to gain superhuman behavior in board games without relying on external knowledge. AlphaZero learns to master the game by playing against itself (self-play) and learning from those experiences.

>在本篇博文中，你将会了解并实现[AlphaZero](https://deepmind.com/blog/article/alphazero-shedding-new-light-grand-games-chess-shogi-and-go "AlphaZero")。AlphaZero是一个令人大开眼界且超乎寻常的强化学习算法，它以绝对的优势战胜了多名围棋以及国际象棋冠军。本文将会带你使用AlphaZero来解决一个益智小游戏（Dots and Boxes）并将其部署成一个纯JavaScript构建的Web应用。

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

![](https://static.leiphone.com/uploads/new/sns/article/202011/1605075233728134.png)

We will leverage a “simplified, highly flexible, commented, and easy to understand implementation” Python version of AlphaZero from [Surag Nair](https://github.com/suragnair "Surag Nair") available in [Github](https://github.com/suragnair/alpha-zero-general "Github").

You can go ahead and play the game [here](https://carlos-aguayo.github.io/alphazero/ "here"). The WebApp and JavaScript implementation are available here. This code was ported from this Python [implementation](https://github.com/carlos-aguayo/alpha-zero-general/tree/dotsandboxes/dotsandboxes "implementation").

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

AlphaZero is described in the paper bySilver, David, et al. “[Mastering the game of Go without human knowledge](https://www.nature.com/articles/nature24270 "Mastering the game of Go without human knowledge")” nature 550.7676 (2017): 354–359.

>我们会借助于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 game

Dots and Boxes is an elementary child’s game with a [surprising level of complexity in it](https://www.amazon.com/Dots-Boxes-Game-Sophisticated-Childs/dp/1138427594 "surprising level of complexity in it").

Two players take turns to place a horizontal or vertical line between two  adjacent dots. The player who completes the fourth side of a 1×1 box scores one point and gets another turn. The game ends when the board is full, and the player with the most points wins.

>##Dots and Boxes小游戏

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

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

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

![](https://static.leiphone.com/uploads/new/sns/article/202011/1605075327546417.png)

##Artificial Intelligence and Board Games

We have pondered for a long time if machines can demonstrate intelligence. How to validate the machine’s ability to exhibit intelligent behavior? A typical way has been playing board games, like Chess, and attempting to gain superhuman behavior to defeat world champions.

>##人工智能与棋盘游戏

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

In 1957, [Herbert Simon predicted that a computer system would beat the world chess champion](https://www.aaas.org/birth-modern-computing "Herbert Simon predicted that a computer system would beat the world chess champion") in ten years. It took much longer than that, but in [May 1997, a computer defeated the Chess world champion, Garry Kasparov](https://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov#1997_rematch "May 1997, a computer defeated the Chess world champion, Garry Kasparov").

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

Despite the remarkable milestone, one can argue whether this computer system was “intelligent”.

These computer systems are composed of three elements:

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

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

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

1. Human-defined [Evaluation Functions](https://en.wikipedia.org/wiki/Evaluation_function "Evaluation Functions").

3. Game tree search algorithms.

5. Very powerful hardware.

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

>2. 博弈树搜索算法；

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

The evaluation function would take the board as an input and return the board’s “value”. A high value indicates a very favorable position for the current player. For example, a chessboard configuration where the player is about to do Checkmate would have a very high value.

Game tree search algorithms (like Minimax) search across all possible moves looking for the one that would guarantee a path to a board configuration with a high value. The search can be made efficient by not visiting configurations where we know that we won’t find a better value. That’s what Alpha–beta pruning does.

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

>博弈树搜索算法（比如 [Minimax](https://en.wikipedia.org/wiki/Minimax "Minimax")）在所有可能的走棋中进行搜索，寻找那些能够确保得到高价值棋盘盘面的路径。对于那些已经明知不可能有效的路径可以直接放弃搜索，从而使算法变得更有效率。这就是 [Alpha-beta剪枝](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning "Alpha-beta剪枝") 的作用。

Finally, add very powerful hardware, and you would have a machine capable of defeating a world champion.

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

What’s the catch? Experienced players [manually craft ](https://www.nytimes.com/1997/05/18/nyregion/what-deep-blue-learned-in-chess-school.html "manually craft ")these evaluation functions. These systems would rely on [openings](https://en.wikipedia.org/wiki/Chess_opening "openings") books indicating the best-known moves. The [middle game](https://en.wikipedia.org/wiki/Chess_middlegame "middle game") would use evaluation functions created by studying games from grandmasters. Then grandmasters would further fine-tune them.

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

For example, we could create an Evaluation Function for the Dots and Boxes game. A reasonable and straightforward evaluation function would be to compare the score. The higher the positive delta in the score, the more favorable the board game is. In most cases, that would work. However, in the Dots and Boxes game, like in many board games, the best moves can involve sacrificing in the short-term to have better gains in the long-term. In the Dots and Boxes game, sometimes it’s better not to score a box to avoid gaining another turn, and instead, force the move back to the opponent. We would then have to tune our evaluation function to consider an increasing number of complex scenarios!

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

The [evaluation function](https://www.sciencedirect.com/science/article/pii/S0004370201001291/pdf "evaluation function") that defeated Kasparov had 8,000 features! And the large majority of those features were created and tuned by hand!

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

So, without belittling an important milestone like defeating a chess world champion, an undesirable aspect was the need to have top-ranked players define these computers’ behavior and manually tweak so many variables.

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

##What’s AlphaZero, and why is it so exciting?

AlphaZero is the first computer system capable of gaining superhuman behavior at games like Chess or Go, defeating world champions, bootstrapped with only the game’s rules and without human domain knowledge.

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

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

Given only the rules of the game, AlphaZero would start playing against  itself. Learning, little by little, strategies and techniques, gaining relatively quickly superhuman behavior.

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

Whereas systems like DeepBlue would require chess experts’ assistance, AlphaZero would become strong by playing against itself. Furthermore, AlphaZero showed superhuman strength not only in Chess but also at [Go](https://en.wikipedia.org/wiki/Go_(game) "Go"). Go is a more complicated game for computers, given its [much larger game space and other factors](https://en.wikipedia.org/wiki/Go_(game)#Software_players "much larger game space and other factors").

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

While humankind has accumulated knowledge in games like[ Go](https://en.wikipedia.org/wiki/Go_%28game%29 " Go") and Chess from millions of games played over thousands of years, AlphaZero, a straightforward algorithm using only the game rules, rediscovered this knowledge and new strategies in a few days.

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

There’s even a [movie](https://www.youtube.com/watch?v=WXuK6gekU1Y "movie") about it.

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

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

##How would AlphaZero learn with just self-play?

Recall that systems like DeepBlue would rely on a human-defined “evaluation function”, which would take as an input the board state and output the “value” of the state.

Nowadays, it’s extremely easy for DeepLearning models to take as an input an image and classify it as a dog or a cat. The idea is to take the board as the input to a DeepLearning model and train it to predict if the  board has a winning or losing configuration.

But to train a Machine Learning, one needs data, lots of data. Where do you get a dataset of games? Simple, we let the computer play against itself, generating a set of games and make a dataset out of it.

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

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

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

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

##AlphaZero training algorithm

The algorithm is straightforward:

Let the computer play against itself several games, recording the board at every move. Once we know the outcome, update all those boards with the given result, “win” or “lose” at the end of the game. We have then built a dataset to give to a Neural Network (NN) and start learning if a given board configuration is a winning or losing one.

Clone the Neural Network. Train the clone using the dataset generated in the previous step.

Have the clone and original Neural Network play against each other.

Pick whatever Neural Network wins, drop the other one.

Go to step 1.

And just like magic, after many iterations, you have a world-class model.  This model managed to outperform the strongest computer chess program in only 4 hours!

>##AlphaZero的训练算法

>这个算法简单明了：

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

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

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

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

>5. 重复第1步。

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

##AlphaZero components

AlphaZero has two components. We already talked about the first one, which is the Neural Network. The second one is the “Monte Carlo Tree Search” or MCTS.

Neural Network (NN). Takes as input the board configuration and outputs the board’s value, plus a probability distribution for all the possible moves.

Monte Carlo Tree Search (MCTS). Ideally, the Neural Network would be enough to choose the next move. We still want to look at as many board configurations as possible and ensure that we are indeed picking the best possible action. MTCS is, like Minimax, an algorithm that will help us look at board configurations. Unlike Minimax, MTCS will help to explore the game tree efficiently.

>##AlphaZero的组件

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

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

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

##Let’s dive into details and determine the next move

t’s easier to follow AlphaZero by first looking at its behavior when determining the next move (competitive mode) and then look at the training routine.

Neural Networks (NNs) are already great at classifying things, like a cat versus a dog. The idea here is simple, can the Neural Network learn to classify a board configuration as a winning versus losing one? More specifically, the Neural Network will predict a value expressing the probability of winning versus losing. Furthermore, it will output a probability distribution over all the possible moves, representing which action we should explore next.

The Neural Network takes the game state as an input and outputs a value and a probability distribution. Specifically for Dots and Boxes, the game state is represented by three elements: First, whether a line has been played or not, using an array of 0 and 1’s for each line across dots. 1 if a player has already colored the line, else 0. Second, if the current move is a pass, third, the score. We can represent all the required information with these three elements to determine a board’s value and predict its next move.

Let’s analyze the following game, where it’s the Blue player’s turn. Blue has two options, follow the top path and lose, or play the bottom path and win.

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

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

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

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

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

![](https://static.leiphone.com/uploads/new/sns/article/202011/1605001487673594.png)

If Blue plays 23 followed by 21, Red wins. Instead, if Blue plays 23 followed by 9, Blue wins. How would AlphaZero find the winning move if it would be playing Blue?

You can reproduce the results seen below by using this notebook.

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

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

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

If we feed that board configuration to the Neural Network, we get an array with move probabilities for each action:

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

```
move_probability[0]: 9.060527501880689e-12
move_probability[1]: 3.9901679182996475e-10
move_probability[2]: 3.0028431828490586e-15
move_probability[3]: 7.959351400188552e-09
move_probability[4]: 5.271672681717021e-11
move_probability[5]: 4.101417122592821e-12
move_probability[6]: 1.2123925357696643e-16
move_probability[7]: 6.445387395019553e-23
move_probability[8]: 2.8522254313207743e-22
move_probability[9]: 0.0002768792328424752
move_probability[10]: 1.179791128073232e-13
move_probability[11]: 5.543385303737047e-13
move_probability[12]: 3.2618200407341646e-07
move_probability[13]: 4.302984970292259e-14
move_probability[14]: 2.7477634988877216e-16
move_probability[15]: 1.3767548163795204e-14
move_probability[16]: 8.998188305575638e-11
move_probability[17]: 7.494002147723222e-07
move_probability[18]: 8.540691764924446e-11
move_probability[19]: 9.55116696843561e-09
move_probability[20]: 4.6348909953086714e-12
move_probability[21]: 0.46076449751853943
move_probability[22]: 2.179317506813483e-20
move_probability[23]: 0.5389575362205505
move_probability[24]: 5.8165523789057046e-15
```
We also get a value for the board configuration:

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

```
-0.99761635
```
You can find the code that generates these values here.

There are a few interesting things from these outputs:

The highest probability moves are 23, 21, and 9, out of the 8 possible moves. If the NN plays 23 or 21, he scores a point. 23 is the winning move and has a slightly higher value (0.53) than the 21’s (0.46).

The NN will output probabilities even for invalid moves. It’s the code’s job to follow the game rules and ensure that we don’t play an invalid action.

The value is -0.99. That indicates that AlphaZero thinks that it has lost the game. The value ranges from -1 (loss) to 1 (win). This value should have been much closer to 1 (win) than -1 (loss) as we know that this is a winning state. Perhaps we need more training rounds to get to a state where AlphaZero would learn the correct value for this board configuration.

It’s tempting to take the Neural Network’s outputs and decide our next move.

In board games (and in life!), players typically see many “moves ahead” when determining their next move. It’s no different here. We use our Neural Network predictions to choose which state to explore next and ignore the ones with low value. Like Minimax, traditional AI game tree search algorithms are inefficient because they have to analyze every single move before going into the next move. Games with even small branching factors make their game space intractable. The branching factor is the number of moves possible. The number of possible moves changes as the game progresses. If so, you calculate an average branching factor. Chess’s average branching factor is 35. Go’s is 250.

This means that, in Chess, just after two moves, there are 1,225 (35²) possible board configurations, whereas, in Go, it would be 62,500 (250²). In Dots and Boxes, for a 3x3 game, the initial branching factor is 24 and decreases with every move (unless it is a pass). So in the middlegame, when the branching factor is 15, there are 2,730 (15*14*13) board configurations after just three moves.

Instead, the NN will guide us and tell us where we should explore and avoid being overwhelmed by many useless paths. The NN is telling us that 23 and 21 are strong moves.

It’s the job of the Monte Carlo Tree Search to do that.

>你可以在[这里](https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L85-L101 "这里")查阅与这些输出相关的代码。

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

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

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

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

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

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

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

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

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

##Monte Carlo Tree Search (MCTS)

The Neural Network has given us an indication for the likely next moves.  The Monte Carlo Tree Search algorithm is the one that will help us traverse the nodes to choose the next move to make.

Take a look at this link for the paper’s graphical description of Monte Carlo Tree Search.

The way that MCTS works is that for a given board, it will run N simulations. N is a parameter of our model. At the end of these simulations, the next move will be the most visited. You can follow along with the code here.

##蒙特卡洛树搜索（MCTS）

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

去这个[链接](https://www.nature.com/articles/nature24270/figures/2 "链接")看看论文中有关蒙特卡洛树搜索的图形化描述。

使用MCTS的具体做法是这样的，给定一个棋面，MCTS共进行N次模拟。N是模型的超参数。N次模拟结束后，下一步的走法将是这N次模拟中所经次数最多的一步。你可以由这里的[代码](https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L37-L48 "代码")一窥究竟：

```
# https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L37-L48    
for i in range(self.args.numMCTSSims):  # self.args.numMCTSSims, the number of MCTS simulations to compute    
self.search(canonicalBoard)  # "search" is a MCTS simulations    
s = self.game.stringRepresentation(canonicalBoard)    
# Count how many times we have visited each node    
counts = [self.Nsa[(s, a)] if (s, a) in self.Nsa else 0 for a in range(self.game.getActionSize())]    
if temp == 0:    
# Pick the node that was visited the most    
bestAs = np.array(np.argwhere(counts == np.max(counts))).flatten()    
bestA = np.random.choice(bestAs)    
probs = [0] * len(counts)    
probs[bestA] = 1    
return probs
```

Running n MCTS Simulations

An MCTS simulation consists of traversing down the game tree, starting from the current board, by selecting the node with the highest “Upper Confidence Bound (UCB)” value (defined below) until we reach a game state that we have not visited before, which is called a “leaf”. This is what the paper refers to as Part A, “Select”.

What’s UCB? It’s Q(s,a) + U(s,a). Where “s” is the state, and “a” is the action. Q(s,a) is the expected value that we expect to get from that state “s” following the action “a”, the same one from Q-Learning. Remember that in this case, the value will have a range from -1 (loss) to 1 (win). U(s, a) ∝ P(s, a) / (1 + N(s, a)). This means that U is proportional to P and N. Where P(s, a) is the prior probability for the tuple (s, a), the value returned by the NN, and N(s, a) is the number of times that we have visited the state s and taken action a.

>进行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 的次数。

```
# Upper Confidence Bound
ucb = Qsa[(s,a)] + Ps[s,a] * sqrt(Ns[s]) / (1 + Nsa[(s,a)]
```
The point of the UCB is to initially prefer actions with high prior probability (P) and low visit count (N), but asymptotically prefer actions with a high action value (Q).

You can follow the code along here.

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

>你不妨看看[这里](https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L108-L125 "这里")的代码好好理解一下。

```
# https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L105-L121    
cur_best = -float('inf')    
best_act = -1    
# pick the action with the highest upper confidence bound    
for a in range(self.game.getActionSize()):    
if valids[a]:    
if (s, a) in self.Qsa:    
u = self.Qsa[(s, a)] + self.args.cpuct * self.Ps[s][a] * math.sqrt(self.Ns[s]) / (    
1 + self.Nsa[(s, a)])    
else:    
u = self.args.cpuct * self.Ps[s][a] * math.sqrt(self.Ns[s] + EPS)  # Q = 0 ?    
if u > cur_best:    
cur_best = u    
best_act = a    
a = best_act    
next_s, next_player = self.game.getNextState(canonicalBoard, 1, a)    
next_s = self.game.getCanonicalForm(next_s, next_player)    
# Recursively visit the node    
v = self.search(next_s)
```
Part A — Select the action with the highest Upper Confidence Bound (UCB)

Once a leaf is found, we run that board through the NN. This is what the  paper calls Part B, “Expand and evaluate”. You can follow along with the code here.

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

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

```
# leaf node    
self.Ps[s], v = self.nnet.predict(canonicalBoard)    
valids = self.game.getValidMoves(canonicalBoard, 1)    
self.Ps[s] = self.Ps[s] * valids  # masking invalid moves    
sum_Ps_s = np.sum(self.Ps[s])    
self.Ps[s] /= sum_Ps_s  # renormalize    
self.Vs[s] = valids    
self.Ns[s] = 0
```

Part B — Expand and Evaluate

Lastly, we will propagate back up the value returned by the NN. That’s what the paper calls Part C “Backup”. You can follow along with the code [here](http://https://github.com/suragnair/alpha-zero-general/blob/5156c7fd1d2f3e5fefe732a4b2e0ffc5b272f819/MCTS.py#L125-L136 "here").

>Part B——扩展与评估

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

```
v = self.search(next_s)

if (s, a) in self.Qsa:
    self.Qsa[(s, a)] = (self.Nsa[(s, a)] * self.Qsa[(s, a)] + v) / (self.Nsa[(s, a)] + 1)
    self.Nsa[(s, a)] += 1
else:
    self.Qsa[(s, a)] = v
    self.Nsa[(s, a)] = 1

self.Ns[s] += 1
return -v
```

>Part C——备份

Determining the next move

Let’s see how AlphaZero determines the next move for the state mentioned above.

>决定下一步如何走

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

![](https://static.leiphone.com/uploads/new/sns/article/202011/1605001487212452.png)

AlphaZero will run 50 Monte Carlo Tree Search Simulations.

You can reproduce the results seen below by using this [notebook.](https://colab.research.google.com/github/carlos-aguayo/carlos-aguayo.github.io/blob/master/alphazero/notebooks/Get%20probabilities%20and%20values.ipynb "notebook.")

These are the paths that follow at each iteration:

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

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

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

```
Simulation #1 -> Expand root node

Simulation #3 -> 21
Simulation #4 -> 9
Simulation #5 -> 17
Simulation #6 -> 12
Simulation #7 -> 19
Simulation #8 -> 3
Simulation #9 -> 18

Simulation #11 -> 21,24

Simulation #13 -> 21,24,23,24

Simulation #16 -> 21,24,9

Simulation #19 -> 21,24,17

Simulation #21 -> 21,24,19

Simulation #23 -> 21,24,18

Simulation #25 -> 21,24,23,24,17

Simulation #28 -> 21,24,3

Simulation #30 -> 21,24,12

Simulation #32 -> 21,24,23,24,12

Simulation #34 -> 21,24,23,24,9,24,17

Simulation #37 -> 21,24,23,24,9,24,19

Simulation #39 -> 21,24,23,24,9,24,18,17,24

Simulation #41 -> 21,24,23,24,9,24,18,17,24,19,24
```
The above means the following: In the first simulation, we haven’t seen that board before and thus is a “leaf” node and “expands” it. Expands means that it evaluates that board with the NN.

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

```
Simulation #1 -> Expand root node
```
In the second simulation, we have already expanded the root node so it’s no longer a “leaf” and so we can search for the node with the highest UCB

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

The action with the highest UCB is 23. It dives into that state, given that it has not seen that state before, and thus it’s a leaf node, it expands it, and the second simulation completes.

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

```
Simulation #2 -> 23
```
In this case, the NN gives a losing value for 23. We discussed this before. The NN could use even more training to learn that it’s indeed a bad state. But for now, this still works, as we will see below.

For the next simulations, at each time, the option with the highest UCB are the remaining options. That’s because after visiting each action, it finds out that it has a low value and, thus, a low UCB.

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

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

```
Simulation #3 -> 21
Simulation #4 -> 9
Simulation #5 -> 17
Simulation #6 -> 12
Simulation #7 -> 19
Simulation #8 -> 3
Simulation #9 -> 18
```
For the next simulations, an exciting pattern starts surfacing. Remember that the winning sequence is 23, 24 (skip), 9.

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

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

```
Simulation #10 -> 23,24
Simulation #11 -> 21,24
Simulation #12 -> 23,24,21
Simulation #13 -> 21,24,23,24
Simulation #14 -> 23,24,9
Simulation #15 -> 23,24,17
Simulation #16 -> 21,24,9
Simulation #17 -> 23,24,12
Simulation #18 -> 23,24,18
Simulation #19 -> 21,24,17
Simulation #20 -> 23,24,21,24,9
Simulation #21 -> 21,24,19
Simulation #22 -> 23,24,3
Simulation #23 -> 21,24,18
Simulation #24 -> 23,24,19
```
In simulations 10 through 24, the MCTS is already focusing its attention on nodes 21 and 23. This makes sense as with either of those two paths,  we score a point.

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

```
Simulation #33 -> 23,24,21,24,9,24,18
Simulation #34 -> 21,24,23,24,9,24,17
Simulation #35 -> 23,24,21,24,9,24,12
Simulation #36 -> 23,24,21,24,9,24,3
Simulation #37 -> 21,24,23,24,9,24,19
Simulation #38 -> 23,24,21,24,9,24,18,17
Simulation #39 -> 21,24,23,24,9,24,18,17,24
Simulation #40 -> 23,24,21,24,9,24,18,17,24,19
Simulation #41 -> 21,24,23,24,9,24,18,17,24,19,24
```
Then in simulations 33 through 41, it starts going deep in the losing combination. Notice an interesting thing. Despite going deep, it never reaches the end of the game as there are still playable moves.

>在第33至第41次模拟中，搜索算法深入探究了那些导致败局的走法。这里要注意到一件有意思的事情。尽管追究得很深，但是搜索算法并没有抵达游戏终局，后面还有可以走的步骤。
```
Simulation #42 -> 23,24,9,21
Simulation #43 -> 23,24,9,18
Simulation #44 -> 23,24,9,17
Simulation #45 -> 23,24,9,19
Simulation #46 -> 23,24,9,12
Simulation #47 -> 23,24,9,21,24
Simulation #48 -> 23,24,9,3
Simulation #49 -> 23,24,9,21,24,18
Simulation #50 -> 23,24,9,21,24,17
```

Then, in simulations 42 to 50, with the NN’s help, it realizes that 23, 24, 21 or 21, 24, 23 are not good options and focus entirely on the winning sequence 23, 24, 9.

After 50 simulations, our time is up, and we need to choose a move. MCTS chooses the move that we visited the most. Here are the number of times that we visited each move (on the first play):

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

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

```
counts[3] = 1
counts[9] = 1
counts[12] = 1
counts[17] = 1
counts[18] = 1
counts[19] = 1
counts[21] = 15
counts[23] = 28
```
Actions 3, 9, 12, 17, 18, and 19 are visited only once in the first 10 simulations. Then the MCTS focused on moves 21 and 23. Visiting action 23 for the last 9 simulations. Given that we visited action 23 the most, 28 times, MCTS returns that as the next move.

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

What are the takeaways?

Through each simulation, the MCTS will rely on the NN to follow the path that seems the most promising, using a combination of the accumulated value (Q), the move prior probability (P) given by the NN, and how often it has visited the node. Or, in other words, the path with the highest UCB.

During each simulation, the MCTS will go as deep as it can until it reaches a board configuration that it hasn’t seen before, and it will rely on the NN to evaluate the board to tell how good that board is.

If we compare it with classical approaches like using Minimax with Alpha-Beta Pruning and an Evaluation function, we can say the following:

In Minimax, the depth is a parameter established by the designer. It will go that deep and then use the evaluation function. Without Alpha-Beta pruning, it would have to visit all the nodes at the given depth, being very inefficient. In the above scenario, with 8 moves left, at depth 3, it would mean evaluating 336 boards. In MTCS, with 50 simulations, we only had to evaluate 50 boards and managed to go much deeper.

Alpha-Beta pruning would have helped us reduce the 336 number. However, it doesn’t allow us to follow an intelligent path.

We rely on the Neural Network to tell us the “value” of a board at all times rather than using a human-defined evaluation function.

It was interesting to see that the NN wasn’t predicting the right values at the initial moves. Nevertheless, it had the correct predictions as we got deeper without going all the way to the end of the game.

Lastly, notice the elegance and simplicity of AlphaZero. Whereas in Alpha-Beta pruning, you have to track an alpha and a beta parameter to know where to prune, and a human-defined evaluation function can be unwieldy. MCTS and NN make everything quite elegant and simple. You can follow all this in JavaScript!

>关键点是什么？

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

>在每一次模拟中，MCTS会尽可能向纵深进行探索直至遇到它从未见过的盘面状态，在这种情况下，它会通过神经网络来评估该盘面状态的优劣。
如果我们将上述方法与使用带有Alpha-Beta剪枝以及一个评价函数的Minimax之类的传统方法进行比较，我们可以发现以下几点：

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

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

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

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

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

##Training the Neural Network

We are missing one last key aspect. How do we train the NN?

Luckily it’s straightforward. We mentioned the steps before:

Let the computer play against itself several games in “training mode”, recording the board at every move. Once we know the outcome, update all those boards with the given result, “win” or “lose” at the end of the game. We have then built a dataset to give to a Neural Network (NN) and start learning if a given board configuration is a winning or losing one.

Clone the Neural Network. Train the clone using the dataset generated in the previous step.

Have the clone and original Neural Network play against each other.

Pick whatever Neural Network wins, drop the other one.

Go to step 1.

What does it mean to play in “training mode”? The difference is a tiny one. When playing in “competitive mode”, we will always pick the move with the highest visit count. Whereas in “training mode”, for a certain number of moves during the beginning of the game, the counts become our probability distribution and encourage exploration. For example, let’s say that there are 3 possible actions and the visit count is [2, 2, 4]. In competitive mode, we would always pick the third action as it has the highest visit count. But in training mode, [2, 2, 4] becomes a probability distribution, 2+2+4 = 8 and thus [2/8, 2/8, 4/8] or [0.25, 0.25, 0.5]. In other words, we will pick the third action 50% of the time, whereas we will explore the first and second actions 25% of the time.

>##训练神经网络

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

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

>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%的概率被选中。

Then let’s use a simple Tic-Tac-Toe game to describe the dataset.

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

![](https://static.leiphone.com/uploads/new/sns/article/202011/1605001485974369.png)

In the above game, the first player, the Xs win.

We can configure the board state by having zero if the square hasn’t been played, 1 if the first player, -1 if the second player has played the square.

For example, the board would be the following:

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

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

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

```
0 0 0    1 0 0     1 0 0     1 0 0     1 0 0     1 0 0
0 0 0 -> 0 0 0 -> -1 0 0 -> -1 1 0 -> -1 1 0 -> -1 1 0
0 0 0    0 0 0     0 0 0     0 0 0    -1 0 0    -1 0 1
```

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

```
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0,-1, 0, 0, 0, 0, 0]
[1, 0, 0,-1, 1, 0, 0, 0, 0]
[1, 0, 0,-1, 1, 0,-1, 0, 0]
[1, 0, 0,-1, 1, 0,-1, 0, 1]
```
Then we have to do two things. First, update each board as if it would be player1’s turn. We will always feed training data to the NN from the  perspective of the first player. In TicTacToe, that’s simple. Every time it was the second player’s turn, we can flip the pieces to become player1’s perspective.

We go from this:

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

>也就是，将：
```
[0, 0, 0, 0, 0, 0, 0, 0, 0]  # Player 1 turn

[1, 0, 0,-1, 0, 0, 0, 0, 0]  # Player 1 turn

[1, 0, 0,-1, 1, 0,-1, 0, 0]  # Player 1 turn
```
>变为：
```
[ 0, 0, 0, 0, 0, 0, 0, 0, 0]  # Player 1 turn
[-1, 0, 0, 0, 0, 0, 0, 0, 0]  # Player 1 turn 
[ 1, 0, 0,-1, 0, 0, 0, 0, 0]  # Player 1 turn
[-1, 0, 0, 1,-1, 0, 0, 0, 0]  # Player 1 turn
[ 1, 0, 0,-1, 1, 0,-1, 0, 0]  # Player 1 turn
[-1, 0, 0, 1,-1, 0, 1, 0,-1]  # Player 1 turn
```

Second, we append the game outcome. Let’s use a “1” if player 1 wins and “0” if it loses.

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

```
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]  # Winning board
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]  # Losing board
[ 1, 0, 0,-1, 0, 0, 0, 0, 0, 1]  # Winning board
[-1, 0, 0, 1,-1, 0, 0, 0, 0, 0]  # Losing board
[ 1, 0, 0,-1, 1, 0,-1, 0, 0, 1]  # Winning board
[-1, 0, 0, 1,-1, 0, 1, 0,-1, 0]  # Losing board

```

The dataset is starting to get some shape! As you can see from the above, we can feed that to a NN to learn in a board is a winning or a losing one, the value.

We are missing the probabilities, though. Where do those come from? Remember that during training mode, we will still run MCTS simulations  at every step. In the same way that we are recording the board configuration, we will record the probabilities.

We then clone the NN and train the clone using this dataset, expecting it to be slightly stronger as it’s using new data. We validate that it’s indeed stronger by having it compete against the original NN. If it wins more than 55% of the time, we consider it stronger and drop the original, and the clone becomes our new NN.

We keep repeating this process, and the NN will keep becoming stronger.

You can see the diagram from the paper here.

How come the dataset has stronger moves to learn from? By learning from the probabilities generated by the MCTS, they will usually select much stronger moves than the raw move probabilities given by the NN. We are feeding the NN knowledge obtained by having the MCTS go deep into many paths!

Use this notebook to train a Dots and Boxes model.

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

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

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

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

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

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

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

Deploying it into a WebApp

A few months ago, I published a blog post that walks you through the process of transforming a Keras or Tensorflow model into JavaScript to be used by Tensorflow.js. We are going to be doing the same here. We will convert the model we trained in Keras to be used in Tensorflow.js.

This notebook converts a pretrained Dots and Boxes model into a Tensorflow.js model.

Once we do that, we can easily load the model in JavaScript, as seen here.

##Conclusion

In this blog post, you learned about AlphaZero, a novel Reinforcement Learning algorithm that can defeat world-champions in two-player, zero-sum board games.

You learned how it uses a Monte Carlo Tree Search along a Neural Network to find the best next move. You also learned how to train this Neural Network.

I hope that you enjoyed this blog post and found it valuable. If so, reach out!

I’m Senior Director of Software Development and Machine Learning Engineer at Appian. I’ve worked at Appian for the last 15 years, and I keep having a blast. This pandemic has not slowed us down, and we’re hiring! Send me a message if you would like to know how we craft software, please our customers and have fun!

将其部署至一个Web应用
几个月前，我发了[一篇博文](https://towardsdatascience.com/deploying-a-simple-machine-learning-model-into-a-webapp-using-tensorflow-js-3609c297fb04 "一篇博文")，带你大致过了一遍使用TensorFlow.js将Keras或者TensorFlow模型部署至JavaScript的过程。这里我们要做的事情大差不差。我们会把用Keras训练得到的模型转换成能够被TensorFlow.js调用的模型。

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

一旦转换完成，这个模型就能够很轻松地使用JavaScript进行调用。不妨看看[这里](https://github.com/carlos-aguayo/carlos-aguayo.github.io/blob/50de28a29d198df07eed60478fcd0e6de8d5913a/alphazero/index.html#L138 "这里")。

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

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

希望本篇博文你能喜欢，或者能够帮到你一点。如果是的话，跟我多多联络啊（[关注我，关注我](https://twitter.com/carlosaguayo81 "关注我，关注我")）！

我是[Appian](https://www.appian.com/ "Appian")公司[软件开发和机器学习工程师](https://www.linkedin.com/in/carlosaguayo "软件开发和机器学习工程师")部门的高级主管。过去15年我都在Appian工作，一直都很开心。眼下这场新冠大流行并没有让我们放慢前进的脚步，我们还在[招聘](https://www.appian.com/careers/ "招聘")！如果你想知道我们是如何制作软件、让客户满意并乐此不疲的，请给我[发消息](https://twitter.com/carlosaguayo81 "发消息")哦！

![](https://static.leiphone.com/uploads/new/sns/article/202011/1605001486922717.png)

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，转载请附上原文出处链接和本声明。
本文链接地址：https://flyai.com/article/770

讨论

500字

表情

每日优质讨论奖励 20FAI

发送

每日优质讨论奖励 20FAI

删除确认

是否删除该条评论？

取消删除