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

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

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

但是，除了高级的理论解释之外，我对细节的了解还不够运气。以下是上述论文的引文和我的问题。

选择阶段:MCTS迭代选择当前状态中得分最高的子节点。如果当前状态是根节点，那么这些子代首先来自何处？您是否不会有一棵只有一个根节点的树？仅使用一个根节点，您是否立即进入扩展和仿真阶段？

如果MCTS在“选择”阶段选择了得分最高的子节点，那么您在降落到树的层次上时是否从未探索其他子节点，甚至可能是全新的子节点？

节点的扩展阶段如何发生？在上图中，为什么不选择叶子节点，而是决定向该叶子节点添加同级？

在模拟阶段，随机策略用于选择两个玩家的合法举动，直到游戏终止。这种随机策略是一种硬编码的行为吗？您基本上是在模拟中掷骰子，以选择每个玩家之间轮流玩到最后的可能举动之一吗？

我理解的方式是从单个根节点开始，通过重复上述阶段，将树构造到一定深度。然后，在第二步中选择得分最高的孩子作为下一步。您愿意构建的树的大小基本上就是您对AI的严格响应能力要求吧？由于在构建树时，游戏将停止并计算该树。

最佳答案

选择阶段:MCTS迭代选择当前状态中得分最高的子节点。如果当前状态是根节点，那么这些子代首先来自何处？您是否不会有一棵只有一个根节点的树？仅使用一个根节点，您是否立即进入扩展和仿真阶段？

选择步骤通常实现为实际上不选择树中实际存在的节点(已通过扩展步骤创建)。通常可以在与您当前节点匹配的游戏状态的所有可能的后继状态中进行选择。

因此，从一开始，当您只有一个根节点时，您将希望“选择”步骤仍然能够从所有可能的后续游戏状态中选择一个(即使它们在树中没有匹配的节点)然而)。通常，对于尚未访问过的游戏状态(树中还没有节点)，您会希望获得很高的分数(无限，或一些非常大的常数)。这样，您的选择步骤将始终在没有匹配节点的任何状态中随机选择，并且仅在所有可能的游戏状态在树中都具有匹配节点的情况下，才真正使用探索与开发权衡。

如果MCTS在“选择”阶段选择了得分最高的子节点，那么您在降落到树的层次上时是否从未探索其他子节点，甚至可能是全新的子节点？

选择步骤使用的“分数”通常不应仅是通过该节点的所有模拟结果的平均值。它通常应该是一个由两部分组成的分数； “探索”部分对于访问较少的节点来说是很高的，而“剥削”部分对于到目前为止看来是好的举动来说很高(其中，通过该节点的许多模拟都以获胜告终)允许选择行动的球员)。您链接的论文的第3.4节对此进行了描述。 W(s, a) / N(s, a)是开发部分(仅是平均分数)，而B(s, a)是开发部分。

节点的扩展阶段如何发生？在上图中，为什么不选择叶子节点，而是决定向该叶子节点添加同级？

扩展步骤通常实现为简单地添加与选择步骤选择的最终游戏状态相对应的节点(在我回答第一个问题之后，选择步骤将始终以选择一个从未选择过的游戏状态结束) 。

在模拟阶段，随机策略用于选择两个玩家的合法举动，直到游戏终止。这种随机策略是一种硬编码的行为吗？您基本上是在模拟中掷骰子，以选择每个玩家之间轮流玩到最后的可能举动之一吗？

实际上，最直接(也可能是最常见)的实现是完全随机进行的。但是也可以以不同的方式执行此操作。例如，您可以使用试探法对某些操作产生偏见。通常，完全随机播放的速度更快，使您可以在相同的处理时间内运行更多的模拟。但是，这通常也意味着每个单独的模拟信息量都较少，这意味着您实际上需要运行更多的模拟才能使MCTS正常运行。

我理解的方式是从单个根节点开始，通过重复上述阶段，将树构造到一定深度。然后，在第二步中选择得分最高的孩子作为下一步。您愿意构建的树的大小基本上就是您对AI的严格响应能力要求吧？由于在构建树时，游戏将停止并计算该树。

MCTS不会将树的所有部分统一探索到相同的深度。它倾向于探索似乎有趣(强动作)的部分比似乎不有趣(弱动作)的部分更深。因此，通常您不会真正使用深度限制。取而代之的是，您将使用时间限制(例如，持续运行迭代，直到花费了1秒，5秒或1分钟，或者您允许的任何处理时间)，或者使用了迭代计数限制(例如，允许它运行10K或50K或您喜欢的任意数量的仿真)。