蒙特卡洛搜索树如何工作？

Question

尝试使用YouTube视频和论文来学习MCST。

http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf

但是我没有多少运气的理解超越了高层次的理论解释的细节。以下是上述论文中的一些引用以及我有的问题。

1. 选择阶段：MCTS反复选择当前状态的得分最高的子节点。如果当前状态是根节点，那么这些孩子从哪里来的呢？难道你没有一个只有一个根节点的树开始？只有一个根节点，您是否马上进入扩展和模拟阶段？

2. 如果MCTS在选择阶段选择得分最高的孩子节点，那么您从来不会去探索其他孩子，甚至可能是一个全新的孩子，同时沿着树的高度往下走？

3. 节点的扩展阶段如何发生？在上图中，为什么不选择叶节点，而是决定将叶节点添加到叶节点？

4. 在模拟阶段，使用随机策略为两个玩家选择合法移动，直到游戏结束。这个随机策略是一种硬编码的行为，你基本上在模拟中掷骰子，以便在每个玩家之间轮流选择其中一种可能的动作，直到最后？

5. 我明白这一点的方法是从单个根节点开始，并通过重复上述步骤将树构建到特定深度。然后你选择第二级别中得分最高的孩子作为下一步。你愿意构建的树的大小基本上是你的硬性AI响应要求吗？由于在构建树时，游戏将停止并计算该树。

Answer 1

基本上，蒙特卡罗是：随机尝试多次（*），然后保持导致大多数时间最佳结果的举措。

（*）：次数和深度取决于您想要达到的决定的速度。

所以根节点永远是当前的游戏状态与直接的孩子是你的可能的举措。 如果你可以做2个动作（是/否，左/右，...），那么你有2个子节点。

如果你不能做任何动作（这可能发生取决于游戏），那么你没有任何决定，然后蒙特卡洛对此举毫无用处。

如果您有X个可能的移动（国际象棋游戏），那么每个可能的移动都是直接的子节点。然后，（在2人游戏中），evey等级是交替的“你的动作”，“对手动作”等等。

如何遍历树应该是随机的（统一的）。

你的移动1

他移动4（随机移动子级2）

你的移动3（子级1的随机移动）（子级的随机移动3） - >赢yay

选择一个参考最大深度，并评估你赢或输的次数（或者如果游戏没有在X深度之后完成，那么有一个评估函数）。

你重复操作的y倍的（即相当大），并且选择直接子节点（又名：你的举动），导致你赢得大部分的时间。

这是评估哪些移动你应该做的现在。之后，对手移动，轮到你了。因此，您必须重新创建一棵树，并将根节点作为新的当前情况，并重新使用蒙特卡罗技术来猜测您最可能采取的行动。等等。

Answer 2

1. 选择阶段：MCTS反复选择当前状态的得分最高的子节点。如果当前状态是根节点，那么这些孩子从哪里来的呢？难道你没有一个只有一个根节点的树开始？只有一个根节点，您是否马上进入扩展和模拟阶段？

选择步骤通常实施不实际这实际上存在于树节点中选择（已经通过扩展步骤中创建）。它通常被ipmlemented选择匹配你当前节点的游戏状态的所有可能的后继状态。因此，在刚开始的时候，当你只有一个根节点时，你会希望你的选择步骤仍然能够从所有可能的后继游戏状态中选择一个（即使它们没有匹配树中的节点）。通常情况下，对于尚未访问过的游戏状态（在树中没有节点），您需要非常高的分数（无限大，或者一些非常大的常数）。这样，你的选择步骤将总是随机地在没有匹配节点的状态中进行选择，并且只有在所有可能的游戏状态在树中具有匹配节点的情况下才真正使用探索与利用权衡。

如果MCTS选择在选择阶段得分最高的子节点，你永远探索其他的孩子甚至可能是一个全新的孩子，而下降树的水平？

的“”得分'使用选择步骤通常应不只是模拟通过该节点的去所有结果的平均值。它通常应该是一个由两部分组成的分数;一个“探索”部分，对于已经很少被访问的节点来说是很高的，还有一个“开发”部分，对于目前看起来是很好的移动的节点来说是很高的（这里很多仿真都以一个胜利结束对于允许选择移动的玩家来说）。这在您链接的论文的第3.4节中有描述。 W(s, a)/N(s, a)是开发部分（简单的平均分数），而B(s, a)是探索部分。

1. 节点的扩展阶段如何发生？在上图中，为什么不选择叶节点，而是决定将叶节点添加到叶节点？

膨胀处理通常被实现简单的添加相应于由选择步骤选择的最后一场比赛状态的节点（以下是我回答你的第一个问题，在选择步骤总是会选择一个游戏结束以前从未选择的状态）。

1. 在模拟阶段，使用随机策略为两个玩家选择合法移动，直到游戏结束。这个随机策略是一种硬编码的行为，你基本上在模拟中掷骰子，以便在每个玩家之间轮流选择其中一种可能的动作，直到最后？

最直接的（也可能是最常见的）实现的确是完全随机播放。尽管如此，也可以做到这一点。例如，您可以使用启发式方法为某些操作创建偏向。通常，完全随机播放速度更快，可以让您在相同的处理时间内运行更多模拟。但是，它通常也意味着每个单独的模拟信息都较少，这意味着您实际上需要运行更多的MCTS模拟才能发挥出色。

我明白这是你开始在一个根节点和通过重复上述相在构造树到一定深度的方式。然后你选择第二级别中得分最高的孩子作为下一步。你愿意构建的树的大小基本上是你的硬性AI响应要求吗？由于在构建树时，游戏将停止并计算该树。

MCTS不统一探索树的所有部分到相同的深度。它倾向于探索看起来比较有趣的部分（强烈的动作），比看起来没有兴趣的部分（弱动作）更深。所以，通常你不会真的使用深度限制。相反，您可以使用时间限制（例如，持续运行迭代，直到您花费1秒，5秒或1分钟，或者您允许的任何处理时间量）或迭代次数限制（例如，允许它运行10K或50K或任意数量的仿真）。