Monte Carlo 搜索树如何工作？
How does Monte Carlo Search Tree work?
尝试使用像这样的 YouTube 视频和论文来学习 MCST。
http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf
但是，除了高级理论解释之外，我并没有太多运气来理解细节。以下是上述论文的一些引述和我的问题。
选择阶段：MCTS迭代select当前状态的最高得分child节点。如果当前状态是根节点，那么这些 children 最初是从哪里来的呢？难道你不会有一棵只有一个根节点的树开始吗？只有一个根节点，您是否立即进入扩展和模拟阶段？
如果 MCTS select 是选择阶段得分最高的 child 节点，你永远不会探索其他 children 甚至可能是一个全新的 child 沿着树的层级往下走？
节点的扩展阶段是如何发生的？上图中，为什么不选择叶子节点，而是决定在叶子节点上加一个兄弟？
在模拟阶段，随机策略用于 select 双方玩家的合法移动，直到游戏结束。这种随机策略是 hard-coded 行为吗？您基本上是在模拟中掷骰子，以选择每个玩家之间轮流直到结束的可能动作之一？
我的理解是从单个根节点开始，通过重复上述阶段将树构建到一定深度。然后你选择第二关得分最高的child作为你的下一步。您愿意构建的树的大小基本上就是您对硬 AI 响应能力的要求，对吧？因为在构建树时，游戏将暂停并计算这棵树。
基本上，Monte Carlo 是：随机尝试多次 (*)，然后在大多数情况下保持导致最佳结果的移动。
(*) : 次数和深度取决于你想要达到的决定的速度。
所以 根节点 始终是当前游戏状态，直接子节点是 你的 可能的移动。
如果你可以做 2 个动作（yes/no，left/right，...）那么你有 2 个子节点。
如果你不能做任何动作（这取决于游戏可能会发生）那么你没有任何决定可以做出，那么Montec Carlo对这一步没有用。
如果你有 X 种可能的走法（国际象棋游戏），那么每一种可能的走法都是一个直接子节点。
然后，（在 2 人游戏中），每个关卡交替出现“你的动作”、“对手的动作”等等。
如何遍历树应该是随机的（均匀的）。
Your move 1 (random move of sub-level 1)
His move 4 (random move of sub-level 2)
Your move 3 (random move of sub-level 3) -> win yay
选择一个参考的最大深度，评估你输了多少次（或者有一个评估函数，如果游戏在X深度之后还没有结束）。
您重复操作 Y 次（相当大）并且您 select 导致您在大多数时候获胜的直接子节点（又名：您的移动）。
这是为了评估您应该现在采取哪一步。在此之后，对手移动，又轮到你了。所以你必须重新创建一棵树，根节点是新的当前情况，并重做 Monte Carlo 技术来猜测你最好的可能移动是什么。等等。
- Selection Phase: MCTS iteratively selects the highest scoring child node of the current state. If the current state is the root node, where did these children come from in the first place? Wouldn't you have a tree with just a single root node to begin with? With just a single root node, do you get into Expansion and Simulation phase right away?
通常实现 selection 步骤不是在树中真正存在的节点（通过扩展步骤创建）中实际选择。通常需要在匹配您当前节点的游戏状态的所有可能后继状态中进行选择。
因此，在一开始，当您只有一个根节点时，您会希望您的选择步骤仍然能够 select 所有可能的后续游戏状态中的一个（即使它们树中还没有匹配的节点）。通常，对于从未访问过的游戏状态（树中还没有节点），您会希望获得非常高的分数（无限或某个非常大的常数）。这样，您的选择步骤将始终随机 select 在任何还没有匹配节点的状态中，并且仅在所有可能的游戏状态都已经具有匹配节点的情况下才真正使用探索与利用权衡树中的节点。
- If MCTS selects the highest scoring child node in Selection phase, you never explore other children or possibly even a brand new child whilst going down the levels of the tree?
选择步骤使用的“'score'”通常不应只是通过该节点的所有模拟结果的平均值。它通常应该是一个由两部分组成的分数；一个 "exploration" 部分，对于相对不经常访问的节点来说是高的，以及一个 "exploitation" 部分，对于到目前为止看起来是好的移动的节点来说是高的（许多模拟通过该节点以允许选择下一步行动的玩家获胜而告终）。这在您链接的论文的第 3.4 节中有所描述。 W(s, a) / N(s, a)是exploitation部分（简单平均分），B(s, a)是exploration部分
- How does the Expansion phase happen for a node? In the diagram above, why did it not choose leaf node but decided to add a sibling to the leaf node?
扩展步骤通常被实施为简单地添加一个节点，该节点对应于选择步骤 select 的最终游戏状态（根据我对您的第一个问题的回答，选择步骤将始终以 select正在select之前从未被编辑过的一种游戏状态。
- During the Simulation phase, stochastic policy is used to select legal moves for both players until the game terminates. Is this stochastic policy a hard-coded behavior and you are basically rolling a dice in the simulation to choose one of the possible moves taking turns between each player until the end?
最直接（也可能是最常见）的实现确实是完全随机播放。不过，也可以以不同的方式执行此操作。例如，您可以使用启发式方法对某些行为产生偏见。通常，完全随机播放速度更快，允许您在相同的处理时间内进行 运行 次更多模拟。然而，这通常也意味着每个单独的模拟信息较少，这意味着您实际上需要 运行 更多模拟才能让 MCTS 发挥良好。
- The way I understand this is you start at a single root node and by repeating the above phases you construct the tree to a certain depth. Then you choose the child with the best score at the second level as your next move. The size of the tree you are willing to construct is basically your hard AI responsiveness requirement right? Since while the tree is being constructed the game will stall and compute this tree.
MCTS 不会统一探索树的所有部分到相同的深度。它倾向于探索看起来有趣的部分（强移动）比看起来无趣的部分（弱移动）更深入。因此，通常您不会真正使用深度限制。相反，您将使用时间限制（例如，保持 运行ning 次迭代，直到您花费 1 秒、5 秒或 1 分钟，或您允许的任何处理时间），或迭代计数限制（例如，允许它 运行 10K 或 50K 或您喜欢的任意数量的模拟）。
尝试使用像这样的 YouTube 视频和论文来学习 MCST。
http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf
但是，除了高级理论解释之外，我并没有太多运气来理解细节。以下是上述论文的一些引述和我的问题。
选择阶段：MCTS迭代select当前状态的最高得分child节点。如果当前状态是根节点，那么这些 children 最初是从哪里来的呢？难道你不会有一棵只有一个根节点的树开始吗？只有一个根节点，您是否立即进入扩展和模拟阶段？
如果 MCTS select 是选择阶段得分最高的 child 节点，你永远不会探索其他 children 甚至可能是一个全新的 child 沿着树的层级往下走？
节点的扩展阶段是如何发生的？上图中，为什么不选择叶子节点，而是决定在叶子节点上加一个兄弟？
在模拟阶段，随机策略用于 select 双方玩家的合法移动，直到游戏结束。这种随机策略是 hard-coded 行为吗？您基本上是在模拟中掷骰子，以选择每个玩家之间轮流直到结束的可能动作之一？
我的理解是从单个根节点开始，通过重复上述阶段将树构建到一定深度。然后你选择第二关得分最高的child作为你的下一步。您愿意构建的树的大小基本上就是您对硬 AI 响应能力的要求，对吧？因为在构建树时，游戏将暂停并计算这棵树。
基本上，Monte Carlo 是：随机尝试多次 (*)，然后在大多数情况下保持导致最佳结果的移动。
(*) : 次数和深度取决于你想要达到的决定的速度。
所以 根节点 始终是当前游戏状态，直接子节点是 你的 可能的移动。 如果你可以做 2 个动作（yes/no，left/right，...）那么你有 2 个子节点。
如果你不能做任何动作（这取决于游戏可能会发生）那么你没有任何决定可以做出，那么Montec Carlo对这一步没有用。
如果你有 X 种可能的走法（国际象棋游戏），那么每一种可能的走法都是一个直接子节点。
然后，（在 2 人游戏中），每个关卡交替出现“你的动作”、“对手的动作”等等。
如何遍历树应该是随机的（均匀的）。
Your move 1 (random move of sub-level 1)
His move 4 (random move of sub-level 2)
Your move 3 (random move of sub-level 3) -> win yay
选择一个参考的最大深度，评估你输了多少次（或者有一个评估函数，如果游戏在X深度之后还没有结束）。
您重复操作 Y 次（相当大）并且您 select 导致您在大多数时候获胜的直接子节点（又名：您的移动）。
这是为了评估您应该现在采取哪一步。在此之后，对手移动，又轮到你了。所以你必须重新创建一棵树，根节点是新的当前情况，并重做 Monte Carlo 技术来猜测你最好的可能移动是什么。等等。
- Selection Phase: MCTS iteratively selects the highest scoring child node of the current state. If the current state is the root node, where did these children come from in the first place? Wouldn't you have a tree with just a single root node to begin with? With just a single root node, do you get into Expansion and Simulation phase right away?
通常实现 selection 步骤不是在树中真正存在的节点（通过扩展步骤创建）中实际选择。通常需要在匹配您当前节点的游戏状态的所有可能后继状态中进行选择。
因此，在一开始，当您只有一个根节点时，您会希望您的选择步骤仍然能够 select 所有可能的后续游戏状态中的一个（即使它们树中还没有匹配的节点）。通常，对于从未访问过的游戏状态（树中还没有节点），您会希望获得非常高的分数（无限或某个非常大的常数）。这样，您的选择步骤将始终随机 select 在任何还没有匹配节点的状态中，并且仅在所有可能的游戏状态都已经具有匹配节点的情况下才真正使用探索与利用权衡树中的节点。
- If MCTS selects the highest scoring child node in Selection phase, you never explore other children or possibly even a brand new child whilst going down the levels of the tree?
选择步骤使用的“'score'”通常不应只是通过该节点的所有模拟结果的平均值。它通常应该是一个由两部分组成的分数；一个 "exploration" 部分，对于相对不经常访问的节点来说是高的，以及一个 "exploitation" 部分，对于到目前为止看起来是好的移动的节点来说是高的（许多模拟通过该节点以允许选择下一步行动的玩家获胜而告终）。这在您链接的论文的第 3.4 节中有所描述。 W(s, a) / N(s, a)是exploitation部分（简单平均分），B(s, a)是exploration部分
- How does the Expansion phase happen for a node? In the diagram above, why did it not choose leaf node but decided to add a sibling to the leaf node?
扩展步骤通常被实施为简单地添加一个节点，该节点对应于选择步骤 select 的最终游戏状态（根据我对您的第一个问题的回答，选择步骤将始终以 select正在select之前从未被编辑过的一种游戏状态。
- During the Simulation phase, stochastic policy is used to select legal moves for both players until the game terminates. Is this stochastic policy a hard-coded behavior and you are basically rolling a dice in the simulation to choose one of the possible moves taking turns between each player until the end?
最直接（也可能是最常见）的实现确实是完全随机播放。不过，也可以以不同的方式执行此操作。例如，您可以使用启发式方法对某些行为产生偏见。通常，完全随机播放速度更快，允许您在相同的处理时间内进行 运行 次更多模拟。然而，这通常也意味着每个单独的模拟信息较少，这意味着您实际上需要 运行 更多模拟才能让 MCTS 发挥良好。
- The way I understand this is you start at a single root node and by repeating the above phases you construct the tree to a certain depth. Then you choose the child with the best score at the second level as your next move. The size of the tree you are willing to construct is basically your hard AI responsiveness requirement right? Since while the tree is being constructed the game will stall and compute this tree.
MCTS 不会统一探索树的所有部分到相同的深度。它倾向于探索看起来有趣的部分（强移动）比看起来无趣的部分（弱移动）更深入。因此，通常您不会真正使用深度限制。相反，您将使用时间限制（例如，保持 运行ning 次迭代，直到您花费 1 秒、5 秒或 1 分钟，或您允许的任何处理时间），或迭代计数限制（例如，允许它 运行 10K 或 50K 或您喜欢的任意数量的模拟）。