共计 3773 个字符，预计需要花费 10 分钟才能阅读完成。
本篇文章将实现 AlphaZero 的外围搜索算法：蒙特卡洛树搜寻
蒙特卡洛树搜寻(MCTS)
你可能相熟术语蒙特卡洛[1]，这是一类算法，重复进行随机抽样以取得某个后果。
例如上图，在单位正方形中抉择随机点，计算圆内有多少个点，能够用来预计 pi/ 4 的值
本文中咱们将具体介绍 MCTS 的所有步骤。但首先咱们从更宽泛的了解层面来说，在游戏的 MCTS 中，咱们从给定的棋盘状态开始反复模仿玩法，个别状况下的 MCTS 咱们会始终执行这些模仿直到游戏完结。但 AlphaZero 的[2]MCTS 实现与传统的 MCTS 不同，因为在 AlphaZero 中咱们也有一个神经网络，它正在承受训练，为给定的板子状态提供策略和值。
AlphaZero 中搜索算法的输出是一个棋盘的状态 (比方 σ) 和咱们想要运行 MCTS 的迭代次数(也称为播放次数)。在这个游戏的例子中，搜索算法的输入是从 σ 中抽样一个执行动作的策略。
该树将迭代构建。树的每个节点都蕴含一个棋盘状态和对于在该状态下可能采取的无效操作的信息。
节点由一个状态板和键 - 值对组成，其中键是一个动作元组，对应的值是在父节点的状态上利用该动作元组后取得的节点。子节点是惰性初始化的(即仅在须要时初始化)
一开始，树只有根节点。它将蕴含输出状态 σ 和在 σ 下能够采取的无效动作。
上面是 Node 类的代码。
MCTS的每一次模仿分为 4 个步骤: 抉择 (selection)、开展 expansion)、求值(evaluation) 和回溯(backup)，上面咱们具体进行阐明
抉择
MCTS 算法的第一步是抉择。从根节点开始抉择最佳边，直到达到树的末端(示意游戏完结的终端节点 / 尚未摸索的节点，例如上图中标记为 None 的节点)。
但“最佳边”是什么意思呢? 应该如何遍历树? 如何做到树遍历的形式是在摸索和应用之间获得均衡呢？（这里的摸索也是神经网络主导的）
首先解释下这里的摸索（exploration）和应用（exploitation）的含意：
设想一下：你素来没有吃过豆腐脑，你也不晓得甜的还是咸的好吃（比方对于南方人来说可能都没听有甜的豆腐脑）。所以只能本人尝试，假如吃了一个甜的感觉很好。但当你听到还有咸的的时候，因为还没有尝试过，必定想尝试下，这样找到一个新的口味，这个就是摸索。然而如果假如你一天只能吃一种口味的，而你更新换甜味的，想吃甜的，这就是应用。
简略总结下：抉择的口头的指标都是可能取得踊跃处分的，然而如果口头曾经理解，这就是应用；口头是找到一些能给你带来更好处分的口头（以前没有的），这就是摸索。然而因为一次只能进行一个动作，所以就须要在两者之间获得良好的均衡。
AlphaZero 应用 PUCT(利用于树的预测器相信下限)规定来实现这种均衡。该规定是依据教训设计的，也是受到 Rosin’s work in a bandits-with-predictors setting[3]的工作的推动。DeepMind 最近的一篇论文 [4] 探讨了 PUCT 的一些代替计划。咱们将在前面对于将来方向的局部中探讨这些代替计划。咱们先试着了解 PUCT 规定。
动作值 Q(s, a)示意在状态 s 下通过动作 a 取得的均匀处分。一开始，Q(s, a)是零。这个 action-value 代表咱们在任何给定工夫对处分函数的理解，因而它与应用无关。
假如咱们训练过的神经网络以 0.3 的概率示意咱们应该执行某个动作 a。那么将 0.3 的概率蕴含在 PUCT 规定的摸索局部。状态 s 属于父节点，通过在“s”上执行动作“a”取得的状态属于子节点。然而这样会导致常常拜访 MCTS 中的某个节点，为了防止这种状况并激励摸索其余节点，子节点的拜访计数蕴含在分母中，并应用父节点的总拜访数进行规范化。
为什么要取父节点拜访次数的平方根?PUCT 规定是依据教训设计的，这是作者所尝试的所有抉择中最无效的，也就是说是一个能够配置的超参数。咱们也能够间接将其视为一种对子节点进行归一化的形式：分母中的 N+1 项。
在上图中能够看到超参数 c_puct。这个常数均衡摸索采和应用条件。这个超参数的典型值是 2。
当初曾经对如何取得 PUCT(s, a)有了肯定的理解，让咱们持续 MCTS 中的抉择步骤。
抉择步骤如上面的块所示，即从根节点开始，反复查找具备最大 PUCT 值的子节点，直到达到状态依然为 None(尚未开展 / 初始化)的节点。
consider_node = root// terminal nodes also have a None statewhile consider_node.state is not None:
best_node = find_child_with_maximum_puct_value(consider_node)
consider_node = best_nodeconsider_node has to be expanded下面动图显示了反复查找 pput 值最大的子节点，直到达到状态依然为 None 的节点
开展和求值
在抉择了特定的动作后，下一步就就是开展并对该节点进行求值（因为其状态仍为 None）。这里的开展示意通过初始化选定节点的状态来扩大树。这种新的状态是从游戏规则中取得的。如果它是一个终端节点，咱们将状态保留为 None 并在节点中设置一个标记，将其标记为带有获胜者信息的终端节点。
所选节点的所有新边也被初始化。例如下面动图中显示的树在开展所选节点后将如下图所示。
接下来就是开展节点的计算，评估指玩家在该节点的冀望处分。传统的 MCTS 应用 rollout 策略从扩大节点执行 rollout，以找出游戏完结时的值，这个策略能够是平均随机的。而 AlphaZero 的 MCTS 与传统的 MCTS 不同，在 AlphaZero 的 MCTS 中，应用神经网络的值输入来确定开展节点的值。
比方当评估一个国际象棋的地位时，咱们会在脑海中计算一些走法，而后在计算完结时只应用的直觉来判断后果会有多好。在计算完结时不会像传统的 MCTS 那样进行操作，也不会在游戏完结之前应用随机动作模仿那个操作，咱们只抉择几个咱们认为比拟好的地位进行操作。
上面是代码的实现。
回溯
在对开展的节点进行评估之后，还须要更新从根节点到开展节点的所有节点的 Q 值(由总处分值和总拜访次数实现)。这被称为 MCTS 的回溯（Backup）步骤。
这一点的实现比较简单办法是应用递归地实现选择函数，
开始游戏
下面的四个步骤在肯定次数的迭代中运行。如果它们运行了 1000 次迭代，那么总共将扩大最多 1000 个新节点(咱们之所以说最大值，是因为某些终端节点可能被拜访屡次)。
在这些迭代完结后，察看根节点和它的子节点可能看起来像这样。
这些拜访计数在根节点输入策略。AlphaZero 应用的想法是，如果一个节点被更多地拜访，那么咱们应该调配一个更高的概率来执行给该节点的根节点的动作。
某个动作的输入策略概率值与 N^(1/τ)成正比，其中 N 是通过该动作取得的根节点子节点的拜访次数，τ 是某个温度（temperature）值。
从上图中咱们能够看到，从 AlphaZero 中搜寻取得的每个动作的输入策略与被晋升为 1 / τ 的后果子节点的拜访计数成正比，其中 τ 是某个温度值。τ 的高值将导致更对立的策略。能够在代码中设置为 1。
而后从这个输入策略中抽样一些动作，为给定的状态进行一些操作。应用拜访计数来结构输入策略是正当的，因为应用 PUCT 值来领导蒙特卡罗树搜寻。这些 PUCT 价值观均衡了摸索和应用。向根节点返回更多值的节点将被更频繁地拜访，而一些节点将通过摸索被随机拜访。
这样整个 AlphaZero 的最根本的概念就介绍完了
References
[1] https://en.wikipedia.org/wiki…
[2] 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…
[3] Rosin, C. D. (2011). Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61(3), 203–230. https://doi.org/10.1007/s1047…
[4] Danihelka, I., Guez, A., Schrittwieser, J., & Silver, D. Policy Improvement by planning with Gumbel. Deepmind. Retrieved February 23, 2022, from https://deepmind.com/research…
https://avoid.overfit.cn/post/eac92335f439429d99b4abd58517b899
作者：Bentou
