在本文中，咱们将在PyTorch中为Chain Reaction[2]游戏从头开始实现DeepMind的AlphaZero[1]。为了使AlphaZero的学习过程更无效，咱们还将应用一个绝对较新的改良，称为“Playout Cap Randomization”[3]，以及来自[4]的一些其余技术。在训练过程中，将应用并行处理来并行模仿多个游戏，还将通过一些相干的钻研论文探讨AlphaZero的将来倒退方向。

本文目标不是用AlphaZero构建最好的游戏机器人机器人(因为这须要大量的计算资源)，而是构建一个像样的机器人，至多能够击败随机的Agent，以Chain Reaction游戏为例理解AlphaZero是如何工作的。

本节首先解释Chain Reaction游戏是如何工作的。如果你只是想理解AlphaZero的工作原理，请跳过下一节间接转到AlphaZero局部。

Chain Reaction

首先咱们从了解Chain Reaction游戏开始，这是一个完满的信息游戏，通过几步之后的游戏对咱们来说看起来十分凌乱和不可预测。所以我很好奇AlphaZero在这游戏中训练后会有多弱小。Chain Reaction能够在许多玩家中进行，但在本文中将局限于两个玩家。

游戏规则

让咱们从这个游戏的规定开始。有一个M行N列的棋盘，两名玩家。每个玩家都有一种指定的色彩。出于本文的目标，假如咱们有一个红色玩家和一个绿色玩家，红色玩家先走。下图显示了游戏中的一些中间状态。

游戏板（简称黑板）上有M行N列，在上图中，M=N=5。黑板上有M*N = 25个单元格。在游戏开始时，所有的格子都是空的。

这些红色和绿色的圆形物体在游戏中被称为球体。下图显示了咱们在游戏中能够领有的球体(1个，2个或3个，红色或绿色)。

在一次操作中，玩家点击任何空的或色彩或玩家雷同的单元格，它将减少该单元格中的球的数量。上面的动图展现了游戏中的一些动作。

在一个特定的单元格中能够包容多少个球是有限度的。一个单元格最多能够保留“该单元格的正交相邻街坊数-1”。对于两头的单元格，这个数字是3，对于边缘的单元格，这个数字是2，对于角落的单元格，这个数字是1。下图显示了5x5板中每个单元的最大球体数。

但当玩家点击一个曾经领有最多球体数量的单元格时会产生什么呢?那个单元格的球会决裂，把它所有的球推到邻近的单元格里。上面的动图显示了不同品种的球体的宰割。

在决裂过程中，如果相邻单元格蕴含来自其余玩家的球，那么这些球的色彩将扭转为以后玩家的色彩。如下图所示。

决裂后的单元格在其四周减少了球的数量，它能够导致进一步的屡次决裂，开始决裂的连锁反应，这就是游戏名字的由来。单步操作后的连锁反应是这款游戏最终不可预测的起因。

当初咱们晓得了游戏是如何从一个状态倒退到下一个状态的，可能会有决裂;或者在单个单元格中减少一个球体。但玩家如何获胜呢?游戏的指标很简略，玩家必须毁灭棋盘上所有敌人的球。

游戏状态

咱们须要存储什么信息来捕获游戏的状态呢?有两样货色——首先，一个M × N数组，它通知咱们棋盘上每个M*N格子中的球的数量和类型，其次，轮到谁“红”或“绿”。咱们能够用负数来示意红色球的数量，用正数来示意绿色球的数量。下图显示了如何示意状态的示例。

状态转换

咱们晓得了如何示意一个状态，上面要关注一个更重要的问题，在以后状态下，如何失去下一个状态。为了取得下一个状态，须要晓得玩家点击的单元格。咱们称这个单元格为事件单元格。

将在事件单元格上做一些解决，它看起来像这样。咱们将向它增加一个球体，并查看球体的数量是否超过单元格的限度。如果球的数量超过了，咱们就须要把球决裂开。

在决裂的状况下，事件单元格的每个街坊都将取得一个球体，而后咱们将解决这些街坊，依此类推。咱们察看到，咱们首先处理事件单元格，而后处理事件单元格的街坊，而后处理事件单元格街坊的街坊，依此类推。在某个级别i的街坊，能够以任何程序解决;以任何程序解决第I级上所有街坊的最终后果都是雷同的。下图就是一个例子。

两种不同的形式解决同一级别的单元格都会失去雷同的最终状态。第i层的解决程序不重要的起因是，第i层有两种单元格，决裂的单元格和没有决裂的单元格。那些没有决裂的单元格的球数只会减少一个，不论解决程序如何。那些决裂的单元格，只会给i+1级的单元格减少一个球体。也就是说，第i级和第i+1级的单元格汇合总是不相交的，因而第i级所有单元格的相加之和对于第i+1级的每个单元格总是雷同的。

所以实质上是在做广度优先遍历，这能够借助队列来实现状态转换。

实现简略的游戏规则

状态

实现状态示意并不简单。将棋盘信息存储为不同numpy数组中的球的数量和球的色彩。状态示意还包含玩家的回合。

可视化

这些代码，别离应用矩形和圆绘制网格和球体。

控制器

这里是最重要的代码段，即状态转换，即在给定以后状态和事件的状况下取得下一个状态。

有一种状况是，球继续决裂，而其余玩家的球隐没，如下图所示。

这里须要查看玩家是否在广度第一次遍历while循环中博得了游戏。通过跟踪红色和绿色的球体计数(作为myorbs和opporbs)来查看它，并在循环的每次迭代中更新它们。

AlphaZero

AlphaZero到做了什么呢

[5]是了解AlphaZero的一个很好的终点。人类的推理有两种思维模式——一种是慢思维模式，一种是快思维模式。疾速模式由直觉疏导，而慢速模式像传统计算机算法一样明确遵循某些规定或步骤疏导。

在AlphaZero中，疾速模式或直觉都是通过一个神经网络实现的，该神经网络获取棋盘状态并输入一个策略(操作的概率分布)和一个值(通知以后玩家给定棋盘状态有多好的分数);慢速思维模式则通过蒙特卡罗树搜寻实现。

对于一个游戏咱们可能会有一些本人的了解（教训），晓得哪些行为更好，哪些不好。这种最后的了解能够示意为行为的概率分布。咱们会将较高的概率调配给好的口头，而较低的概率调配给坏的口头(好的口头是那些可能带给咱们胜利的口头)。如果咱们没有这样的教训，那么咱们能够从平均概率分布开始。

这个操作上的概率分布就是咱们对于给定状态的“策略”。

有一种办法能够改良这一原始政策——提前思考将来可能采取的口头。从咱们以后的状态登程，咱们能够思考本人能够下什么棋，对手能够下什么棋等等。这种状况下咱们实际上是在探讨树搜寻，这种树搜寻能够通过应用咱们最后的了解来评估两头板的状态(获取值)来改良，并且可能不会破费大量的工夫来摸索具备低值的节点。在实现这个树搜寻之后，将更好地理解在以后棋盘状态下玩什么，或者说咱们失去了一个改良的策略。这整个过程被称为放大，这是AlphaZero应用蒙特卡洛树搜寻实现的。

下一篇文章咱们将具体介绍AlphaZero的一个简略实现。

References

[1] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., & Hassabis, D. (2018). A general reinforcement learning algorithm that Masters Chess, Shogi, and go through self-play. Science, 362(6419), 1140–1144. https://doi.org/10.1126/scien...

[2] https://brilliant.org/wiki/ch...

[3] Wu, D. J. [PDF] accelerating self-play learning in go: Semantic scholar. https://www.semanticscholar.o...

[4] https://medium.com/oracledevs...

[5] “How to Keep Improving When You’re Better Than Any Teacher — Iterated Distillation and Amplification.” YouTube, uploaded by Robert Miles, 3 Nov. 2019, https://www.youtube.com/watch...

[6] Anthony, T., Barber, D., & Tia, Z. Thinking fast and slow with deep learning and Tree Search. https://arxiv.org/pdf/1705.08...

https://avoid.overfit.cn/post/773f735b3f714b8a83bf3f32531510de

作者：Bentou