montecarlo - 蒙特卡罗搜索树是如何工作的？

Question

尝试使用像这样的 YouTube 视频和论文来学习 MCST。

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

然而，除了高级理论解释之外，我并没有多少运气来理解细节。这是上面论文的一些引述和我的问题。

选择阶段:MCTS 迭代选择当前状态得分最高的子节点。如果当前状态是根节点，那么这些 child 首先来自哪里？你不会有一棵只有一个根节点的树吗？只有一个根节点，您是否会立即进入扩展和模拟阶段？

如果 MCTS 在选择阶段选择得分最高的子节点，那么在沿着树的级别向下时，您永远不会探索其他子节点甚至可能是全新的子节点？

节点的扩展阶段如何发生？上图中，为什么不选择叶子节点而是决定给叶子节点添加一个兄弟节点呢？

在模拟阶段，随机策略用于为双方玩家选择合法的移动，直到游戏结束。这种随机策略是否是一种硬编码行为，并且您基本上是在模拟中掷骰子以选择每个玩家之间轮流直到最后的可能 Action 之一？

我理解的方式是从单个根节点开始，通过重复上述阶段将树构建到一定深度。然后你选择第二级得分最好的 child 作为你的下一步。您愿意构建的树的大小基本上是您的硬 AI 响应要求，对吗？因为在构建树时，游戏将停止并计算这棵树。

Answer 1

1. 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?

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

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

2. 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?

选择步骤使用的“分数”通常不应只是通过该节点的所有模拟结果的平均值。它通常应该是一个由两部分组成的分数； “探索”部分，对于相对不常访问的节点来说很高，而“利用”部分，对于到目前为止似乎是好的移动节点(其中许多模拟通过该节点以胜利结束)对于允许选择移动的玩家)。您链接的论文的第 3.4 节对此进行了描述。 W(s, a) / N(s, a) 是exploitation 部分(简单的平均分)， B(s, a) 是exploration 部分。

3. 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?

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

4. 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 发挥良好的作用。

5. 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 不会统一探索树的所有部分到相同的深度。它倾向于探索看起来有趣的部分(强移动)而不是看起来无趣的部分(弱移动)。因此，通常您不会真正使用深度限制。相反，您将使用时间限制(例如，继续运行迭代，直到您花费 1 秒、5 秒或 1 分钟，或您允许的任何处理时间)，或迭代计数限制(例如，允许它运行 10K 或 50K 或您喜欢的任意数量的模拟)。