来自许多博客和这个 https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html 我们知道MCTS算法的过程有4个步骤。
- Selection: Starting at root node R, recursively select optimal child nodes until a leaf node L is reached.
这里叶子节点L是什么意思?我认为它应该是代表游戏最终状态的节点,或者结束游戏的另一个词。 如果L不是终端节点(游戏的一个结束状态),我们如何决定选择步骤在节点L上停止?
- Expansion: If L is a not a terminal node (i.e. it does not end the game) then create one or more child nodes and select one C.
从这个描述中我意识到我之前的想法显然是错误的。
那么如果 L 不是终端节点,则意味着 L 应该有子节点,为什么不在“选择”步骤中继续从 L 中查找子节点呢?
这一步我们有 L 的子列表吗?
从这一步本身的描述来看,我们什么时候创建一个子节点,什么时候需要创建多个子节点?我们根据什么规则/策略选择节点 C?
- Simulation: Run a simulated playout from C until a result is achieved.
由于第一个问题的困惑,我完全不明白为什么我们需要模拟游戏。我认为从选择步骤开始,我们可以到达终端节点,游戏应该在这条路径的节点L上结束。我们甚至不需要做“扩展”,因为节点L是终端节点。
- Backpropagation: Update the current move sequence with the simulation result.
好吧。最后一个问题,您从哪里得到这些问题的答案?
谢谢
顺便说一句,我也发布了同样的问题https://ai.stackexchange.com/questions/16606/how-to-understand-the-4-steps-of-monte-carlo-tree-search
最佳答案
What does leaf node L mean here?
为了便于解释,我假设所选节点的所有子节点都是在算法的扩展阶段添加的。
当算法开始时,树仅由根节点(叶节点)组成。
扩展阶段添加从根到树可到达的所有状态。现在您有一个更大的树,其中叶子是最后添加的节点(根节点不再是叶子)。
在算法的任何给定迭代中,树(图片的灰色区域)都会生长。它的一些叶子可能是终止状态(根据游戏/问题的规则),但它没有被授予。
如果扩展太多,可能会耗尽内存。因此,扩展阶段的典型实现仅向现有树添加单个节点。
在这种情况下,您可以将单词leaf更改为未完全展开:
Starting at root node R, recursively select optimal child nodes until a not fully expanded node L is reached
Based on what rule/policy do we select node C?
它依赖于域。通常你会随机选择一个移动/状态。
注释
- 图像来自实时游戏的多目标蒙特卡罗树搜索(Diego Perez、Sanaz Mostaghim、Spyridon Samothrakis、Simon M. Lucas)。
关于algorithm - 如何理解蒙特卡洛树搜索的4步,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58911784/