MCTS:如何从根中选择最终动作

人工智能 算法 蒙特卡罗树搜索 蒙特卡罗方法 规划 树搜索
2021-10-22 02:00:42

当分配给蒙特卡洛树搜索的时间用完时,应该从根中选择什么动作?

程序最终在实际游戏中执行的游戏动作,是与被探索最多的孩子对应的动作。

基本算法涉及迭代构建搜索树,直到达到某个预定义的计算预算(通常是时间、内存或迭代约束),此时停止搜索并返回性能最佳的根操作。

[...] 整体搜索的结果 a(BESTCHILD(v0)) 是导致根节点 v0 的最佳子节点的操作 a,其中“最佳”的确切定义由实现定义。

[...] 一旦搜索中断或达到计算预算,搜索就会终止,并且通过某种机制选择根节点 t0 的动作 a。Schadd [188] 根据 Chaslot 等人 [60] 的工作,描述了选择获胜动作的四个标准:

  1. Max child:选择奖励最高的根孩子。

  2. 健壮的孩子:选择访问最多的根孩子。

  3. Max-Robust child : 选择访问次数和奖励都最高的根子节点。如果不存在,则继续搜索,直到达到可接受的访问次数 [70]。

  4. Secure child:选择最大化置信下限的孩子。

[...]一旦达到一些计算预算,算法就会终止并返回找到的最佳移动,对应于具有最高访问计数的根的子节点。

在这种情况下,整体搜索的返回值是 a(BESTCHILD(v0,0)),它将给出导致孩子获得最高奖励的动作 a,因为在最后一次调用中,探索参数 c 设置为 0根节点 v0. 该算法可以改为返回导致访问量最大的孩子的动作;这两个选项通常会 - 但并非总是如此!– 描述相同的动作。如果访问次数最多的根动作不是具有最高奖励的动作,则在围棋程序 ERICA 中通过继续搜索来解决这种潜在的差异。这将 ERICA 对抗 GNU GO 的胜率从 47% 提高到了 55% [107]。

但他们的算法 2 使用与内部节点选择策略相同的标准:

argmaxvQ(v)N(v)+c2lnN(v)N(v)

这既不是最大的孩子也不是健壮的孩子!这种情况非常令人困惑,我想知道现在哪种方法被认为是最成功/最合适的。

1个回答

到目前为止,最常用的策略是选择访问次数最多的孩子。如您链接的 2008 年论文中所述。在您链接的 2012 年论文中,这也是所谓的“健壮的孩子”。

在 2012 年论文的算法 2 中,他们实际上使用了最高的平均奖励,对应于“Max child”。看起来他们正在使用 UCB1 策略,但实际上他们使用的值为0为探索参数c,这使得整个平方根项退出。这也在报价末尾的文本中进行了解释。但通常情况下,稳健的孩子/最大访问次数表现更好。

蒙特卡洛树搜索的渐进策略是与 2008 年不同的论文,其中对这些策略进行了一些试验。通常,他们的表现相似,但如果有任何差异,一个健壮的孩子往往是最好的。