如何理解蒙特卡洛树搜索的 4 个步骤

人工智能 算法 蒙特卡罗树搜索
2021-10-19 07:34:27

从很多博客和这个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. 反向传播:用模拟结果更新当前移动序列。美好的。

最后一个问题,你从哪里得到这些问题的答案?

谢谢

2个回答

想象一个具有非常明确的第一步的游戏,例如如果你赢得掷硬币选择先走的游戏会带来明显的优势。

在这种情况下,标准 MCTS 几乎不会沿着在赢球时分叉的树的一侧进行探索 > 让对手开始步骤,因为在这个分裂中游戏其余部分的基本模拟很快就会显示出当你总是在什么时候开始时获得的巨大收益你赢了掷硬币。

结果,您最终会得到一棵树,在赢得折腾方面几乎没有扩展> 让您的对手进入,因为您从最高级节点执行的每个模拟步骤都以比替代方案更差的预期结果值结束在树的另一边,你做正确的移动总是先玩。

让你的对手开始的这些节点具有巨大的潜在子树(因为如果你的对手开始,整个游戏仍然需要进行),但很少搜索它们。结果,在树的这一侧,您将有许多带有大(但尚未探索,在该侧的基本早期模拟之外)子树的叶节点,如果您修改了探索与探索算法,您可以搜索这些子树.

作为一个基本示例,以下面 wiki 示例的第一层最右侧的 0/3 节点为例,尽管可能有许多后续子节点,但与更有希望的 7/10 和 3/8 节点相比,它得到的关注要少得多它可以探索。如果你把这个节点作为你的 L 节点,你会扩展它你还没有搜索到的子节点,从而找出更多关于为什么树的这一边是坏的,并相应地更新我们现在更细粒度的概率,就像它为这里的 3/3 节点:

在此处输入图像描述

在观看@Philip 发布 youtube.com/watch?v=UXW2yZndl7U 的视频后,我还想回答我的问题。但仍然感谢@Philip 的回答,这很有帮助。

“叶”节点的定义。

关键是what tree is the host/owner of a "leaf" node这个问题。通过“扩展”步骤,我们实际上是在用 MCTS 创建一棵树。树,“叶子”节点的所有者,应该是我们正在构建的树,而不是我们头脑中的游戏状态树(或者它太大而无法填充我们的头脑,游戏状态树实际上不存在)。然后我们可以理解,“叶”节点是我们正在构建的树中没有任何子节点的节点。一旦我们得到这个问题的答案,其他问题就可以自动回答了。