js遍历树节点下的所有⼦节点_「详细原理」蒙特卡洛树搜索
⼊门教程
本⽂是对 Monte Carlo Tree Search – beginners guide 这篇⽂章的⽂章⼤体翻译，以及对其代码的解释。烧烤菜
1 引⾔
蒙特卡洛树搜索在2006年被Rémi Coulom第⼀次提出，应⽤于Crazy Stone的围棋游戏。
Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search
蒙特卡洛树搜索⼤概的思想就是给定⼀个游戏状态，去选择⼀个最佳的策略/动作。
1.1 有限双⼈零和序贯博弈
蒙特卡洛树搜索实际上是⼀个应⽤⾮常⼴泛的博弈框架，这⾥我们将其应⽤于 有限双⼈序贯零和博弈 问题中。像围棋、象棋、Tic-Tac-Toe都是有限双⼈序贯零和博弈游戏。
1.2 怎样去表⽰⼀个游戏?
50字简短个人工作总结
我们采⽤ 博弈树 (Game Tree)来表⽰⼀个游戏：每个结点都代表⼀个 状态 (state)，从⼀个 结点 (node)移动⼀步，将会到达它的 ⼦节点(children node)。⼦节点的个数叫作 分⽀因⼦ (branching factor)。 根节点 (Root node)表⽰初始状态(initial state)。 终⽌节点(terminal nodes)没有⼦节点了。
在 tic-tac-toe 游戏中表⽰如下图所⽰：
每次都是从 初始状态 、树的 根结点 开始。在 tic-tac-toe 游戏⾥⾯初始状态就是⼀张空的棋盘。
从⼀个节点转移到另⼀个节点叫作⼀个 move 。
分⽀因⼦ (branching factor)， tic-tac-toe 中树越深，分⽀因⼦也越少，也就是 children node 的数量越少。
游戏结束表⽰ 终⽌节点 。
从根节点到终⽌节点⼀次表⽰⼀个单个游戏 playout 。
你不需要关系你是怎么来到这个 node ，只需要做好之后的事情就好了。
1.3 最佳策略是什么？minimax和alpha-beta剪枝
我们希望找到的就是 最佳策略 ( the most promising next move )。如果你知道对⼿的策略那你可以争对这个策略求解，但是⼤多数情况下是不知道对⼿的策略的，所以我们需要⽤ minimax 的⽅法，假设你的对⼿是⾮常机智的，每次他都会采取最佳策略。
假设A与B博弈，A期望最⼤化⾃⼰的收益，因为是零和博弈，所以B期望A的收益最⼩，Minimax算法可描述为如下形式：
血糖值和 是玩家 和 的效益函数。
天下没有不散的宴席move 表⽰从当前状态 和采取的动作 转移到下⼀个状态。
eval 评估最终的游戏分数。
是最终的游戏状态。
简单地说，就是给定⼀个状态 期望找到⼀个动作 在对⼿最⼩化你的奖励的同时找到⼀个最⼤化⾃⼰的奖励。
Minimax 算法最⼤的弱点 就是需要扩展整棵树，对于⾼分⽀因⼦的游戏，像围棋、象棋这种，算法就很难处理。
对于上述问题的⼀种解决⽅法就是扩展树结构到⼀定的阈值深度( expand our game tree only up to certain threshold depth d )。因此我们需要⼀个评估函数，评估 ⾮终⽌节点 。这对于我们⼈类来说依据当前棋势判断谁输谁赢是很容易做到的。计算机的解决⽅法可以参考原⽂中的：
Chess position evaluation with convolutional neural network in Julia
另⼀种解决树扩展太⼤的⽅法就是 alpha-beta剪枝算法 。它会避免⼀些分⽀的展开，它最好的结果就是与minimax算法效果相同，因为它减少了搜索空间。
2 蒙特卡洛树搜索(MCTS)基本概念
蒙特卡洛通过多次模拟仿真，预测出最佳策略。最核⼼的东西就是搜索。搜索是对整棵博弈树的组合遍历，单次的遍历是从根结点开始，到⼀个未完全展开的节点(a node that is not full expanded)。未完全展开的意思就是它⾄少有⼀个孩⼦节点未被访问，或者称作未被探索过。当遇到未被完全展开过的节点，选择它的⼀个未被访问的childre node做根结点，进⾏⼀次模拟(a single playout/simulation)。仿真的结果反向传播(propagated back)⽤于更新当前树的根结点，并更新博弈树节点的统计信息。当整棵博弈树搜索结束后，就相当于拿到了这颗博弈树的策略。
我们再理解⼀下以下⼏个关键概念：
怎么解释 展开 或 未完全展开 (not fully unexpanded)的博弈树节点？
搜索过程中的 遍历 (traver down)是什么?⼦节点如何选择？
什么是 模拟仿真 (simulation)?
什么是 反向传播 (backpropagation)?
扩展的树节点中反向传播、更新哪些统计( statistics )信息？
素炒油麦菜的做法怎么依据策略(博弈树)选择动作？
2.1 模拟/Simulation/Playout
关于情感的作文
Playout/simulation是与游戏交互的⼀个过程，从当前节点移动到终⽌节点。在simulation过程中move的选择基于rollout policy function：
Rollout Policy也被称作快速⾛⼦策略，基于⼀个状态 选择⼀个动作 。为了让这个策略能够simulation快，⼀般选⽤随机分布(uniform random)。如下图所⽰
2.1.1 Alpha Zero中的Playout/Simulation
在AlphaGo Zero⾥⾯DeepMind‘s直接⽤⼀个CNN残差⽹络输出position evaluation和moves probability。
2.2 博弈树节点的扩展-全扩展、访问节点
⼀个节点如果被访问过了，意味着某个某个simulation是以它为起点的。如果⼀个节点的所有⼦节点都被访问过了，那这个节点就称为是完全扩展的，否则就是未完全扩展的。如下图对⽐所⽰：
在实际过程中，⼀开始根节点的所有⼦节点都未被访问，从中选⼀个，第⼀次simulation就开始了。
Simulation过程中rollout policy选择⼦节点是不被考虑为这个⼦节点被访问过了， 只有Simulation开始的节点被标记为访问过的 。
2.3 反向传播Simulation结果
从⼀个近期访问过的节点(有时候也叫做叶结点(left node))做Simulation，当他Simulation完成之后，得出来的结果就需要反向传播回当前博弈树的根结点，Simulation开始的那个节点被标记为访问过了。
反向传播是从叶结点(simulation 开始的那个节点)到根结点。在这条路径上所有的节点统计信息都会被计算更新。
2.4 Nodes’ statistics
拿到simulation的结果主要更新两个量：所有的simulation reward 和所有节点 (包括simulation开始的那个节点)的访问次数 。
在家练瑜伽- 表⽰⼀个节点 的 simulation reward和 ，最简单形式的就是所有考虑的节点的模拟结果之和。
- 表⽰节点的另⼀个属性，表⽰这个节点在反向传播路径中的次数(也表⽰它有多少次参与了total simulation reward)的计算。
2.5 遍历博弈树
搜索开始时，没有被访问过的节点将会⾸先被选中，然后simulation，结果反向传播给根结点，之后根节点就可以被认为是全展开的。
为了选出我们路径上的下⼀个节点来开始下⼀次模拟，我们需要考虑 的所有⼦节点 , , , 和其本⾝节点 的信息，如下图所⽰：
当前的状态被标记为蓝⾊，上图它是全展开的，因此它被访问过了并且存储了节点的统计信息：总的仿真回报和访问次数，它的⼦节点也具备这些信息。这些值组成了我们最后⼀个部分：树的置信度上界(Upper Confidence Bound applied to Trees，UCT)。
2.6 置信度上界
UCT是蒙特卡罗树搜索中的⼀个核⼼函数，⽤来选择下⼀个节点进⾏遍历：
蒙特卡洛树搜索的过程中选UCT最⼤的那个遍历。
UCT 中第⼀部分是 ，也被称作 exploitation component ，可以看作是⼦节点 的胜率估计(总收益/总次数=平均每次的收益)。
看起来这⼀项已经有⾜够说服⼒，因为只要选择胜率⾼的下⼀步即可，但是为什么不能只⽤这⼀个成分呢？这是因为这种贪婪⽅式的搜索会很快导致游戏结束，这往往会导致搜索不充分，错过最优解。因此UCT中的第⼆项称为exploration component。这个成分更倾向于那些未被探索的节点( 较⼩)。在蒙特卡洛树搜索过程中第⼆项的取值趋势⼤概如下图所⽰，随着迭代次数的增加其值也下降：
参数
⽤于平衡MCTS中的exploitation和exploration。
2.6.1 UCT in Alpha Go and Alpha Zero
在AlphaGo Lee和Alpha Zero算法⾥⾯，UCT公式如下：
是来⾃策略⽹络的move先验概率，策略⽹络是从状态得到move分布的函数，⽬的是为了提升探索的效率。
当游戏视⾓发⽣变化的时候exploitation component 也会发⽣变化。
室内有氧运动2.6.2 Alpha Go和Alpha Zero中的策略⽹络
在 AlphaGo 算法⾥，有两个policy⽹络：
SL Policy Network ：基于⼈类数据的监督学习所得的⽹络。
RL Policy Network ：基于强化学习⾃我博弈改进SL Policy Network。
Interestingly – in Deepmind’s Monte Carlo Tree Search variant – SL Policy Network output is chon for prior move probability estimation as it performs better in practice (authors suggest that human-bad data is richer in exploratory moves). What is the purpo of the RL Policy Network then? The stronger RL Policy Network is ud to generate 30 mln positions datat for Value Network training (the one ud for game state evaluation)
在Alpha Zero⾥⾯只有⼀个⽹络 ，它不仅是值⽹络还是策略⽹络。 It is trained entirely via lf-play starting from random initialization. There is a number of networks trained in parallel and the best one is chon for training data generation every checkpoint after evaluation against best current neural network.
2.7 终⽌MCTS
我们应该什么时候结束MCTS过程？如果你开始玩，那么你的“思考时间”可能是有限的(“thinking time” is probably limited)，计算
能⼒也是有限的(computational capacity has its boundaries, too)。因此最保险的做法是在你资源允许的情况下尽可能全展开遍历搜
索。
当MSCT程序结束时，最佳的移动通常是访问次数最多的那个节点。因为在多次访问的情况下，评估它的 值必须很⾼。
当你使⽤蒙特卡洛树搜索选择了⼀个动作，在对⼿眼⾥，你的这个选择将会变成状态的⼀部分。反过来对你也是⼀样的，当对⼿选择了⼀个状态之后，你的蒙特卡洛树搜索就可以开始⼯作了。利⽤之前的统计信息直接搜索就可以得出结果了。
3 MCTS总结
def monte_carlo_tree_arch(root): while resources_left(time, computational power): leaf = traver(root) # leaf = unvisited node simulation_re
