1

从很多博客和这个https://web.archive.org/web/20160308070346/http://mcts.ai/about/index.html 我们知道 MCTS 算法的过程有 4 个步骤。

  1. 选择：从根节点 R 开始，递归地选择最优子节点，直到到达叶节点 L。

叶节点 L 在这里是什么意思？我认为它应该是一个代表游戏结束状态的节点，或者另一个结束游戏的词。如果 L 不是终端节点（游戏的一个结束状态），我们如何确定选择步骤在节点 L 上停止？

  1. 扩展：如果L不是一个终端节点（即它没有结束游戏）则创建一个或多个子节点并选择一个C。

从这个描述中我意识到我之前的想法显然是错误的。那么如果 L 不是终端节点，则意味着 L 应该有孩子，为什么不在“选择”步骤继续从 L 中寻找孩子呢？在这一步我们有 L 的孩子列表吗？
从这一步本身的描述来看，我们什么时候创建一个子节点，什么时候需要创建多个子节点呢？我们根据什么规则/策略选择节点 C？

  1. 模拟：从 C 运行模拟播放，直到获得结果。

由于第一个问题的混乱，我完全无法理解为什么我们需要模拟游戏。我认为从选择步骤，我们可以到达终端节点，游戏应该在这条路径的节点 L 上结束。我们甚至不需要做“扩展”，因为节点 L 是终端节点。

  1. 反向传播：用模拟结果更新当前移动序列。

美好的。最后一个问题，你从哪里得到这些问题的答案？

谢谢

顺便说一句，我也发布了同样的问题https://ai.stackexchange.com/questions/16606/how-to-understand-the-4-steps-of-monte-carlo-tree-search

4

1 回答 1

2

叶节点 L 在这里是什么意思？

为了解释起见，我假设所选节点的所有子节点都是在算法的扩展阶段添加的。

算法开始时，树仅由根节点（叶节点）形成。

扩展阶段将所有从根可到达的状态添加到树中。现在你有一个更大的树，其中叶子是最后添加的节点（根节点不再是叶子）。

MCTS 政策

在算法的任何给定迭代中，树（图片的灰色区域）都会增长。它的一些叶子可能是终端状态（根据游戏/问题的规则），但它没有被授予。

如果扩展太多，可能会耗尽内存。所以扩展阶段的典型实现只向现有树添加一个节点。

在这种情况下，您可以在未完全展开的情况下更改词叶：

从根节点 R 开始，递归地选择最优子节点，直到到达一个未完全展开的节点 L

我们根据什么规则/策略选择节点 C？

它取决于域。通常你随机选择一个移动/状态。

笔记

  1. 图片来自实时游戏的多目标蒙特卡洛树搜索（Diego Perez、Sanaz Mostaghim、Spyridon Samothrakis、Simon M. Lucas）。
于 2019-11-20T11:50:04.893 回答