播放是从蒙特卡洛树搜索中的叶子还是叶子的子节点开始的?

人工智能 蒙特卡罗树搜索
2021-11-07 13:31:33

在 Wikipedia 上,描述了 MCTS 算法

选择:从根开始R并选择连续的子节点直到一个叶子节点L到达了。叶是尚未启动模拟(播放)的任何节点。

扩展:创建一个(或多个)子节点并选择节点C从其中之一。子节点是从定义的游戏位置开始的任何有效移动L.

模拟:从节点完成一次随机播放C.

为什么播放从第一片叶子的孩子开始,而不是叶子本身?并且树叶不是永远像树叶一样粘在一起吗,因为播放总是从他们的孩子开始,而不是他们?或者叶子是否被认为已经从它“初始化”了一个“播放初始化”,即使它从它的孩子开始?

1个回答

注意:他们对选择阶段的描述实际上与“标准实现”不匹配。他们声明根据选择策略遍历树,直到到达叶节点。我不同意这一点。标准实现是遍历树,直到到达一个节点,在该节点中仍然存在没有为其创建子节点的合法行为(尚未“完全展开”的节点)。

这两者仅在扩张策略是立即完全扩张的情况下是等价的,即立即为所有合法行为创建新节点。L. 有了这样的扩张策略,L会立即从叶节点变成完全展开的节点。但这不是“标准实现”。最常见的扩展策略是每次迭代只向树中添加一个新节点。

L表示在选择阶段结束时到达的节点。标准实现确实是先以某种方式扩展,从而产生一个新的孩子CL, 然后开始播放L向前。

并且树叶不是永远像树叶一样粘在一起吗,因为播放总是从他们的孩子开始,而不是他们?

不,只要添加新的孩子CL,L根据定义不再是叶节点;叶节点定义为没有子节点的节点。下次 MCTS 决定遍历树的同一部分时,L就像任何其他内部节点一样,C将是一个叶节点,我们可能会在未来的扩展阶段在其下方添加另一个节点。或者,当然,也有可能在未来的迭代中,我们的选择阶段仍然以L尽管它不再(不再)是叶子,但如果它仍然有未扩展的节点C(未来的兄弟姐妹C)。

为什么播放从第一片叶子的孩子开始,而不是叶子本身?

这是因为我们通常需要一种与播放机制略有不同的机制来选择要扩展的节点。最常见的(或者至少是最简单直接的)播放机制是从所有合法行为中随机均匀地选择行为选择新节点的最常见(或至少是最简单直接)的机制C添加到L是仅从那些尚未添加儿童的法律行为中统一随机选择L. 由于这些机制不同,我们无法在L并声明播放的第一个动作是生成新节点的动作C; 我们必须使用(稍微)不同的实现。