当分配给蒙特卡洛树搜索的时间用完时,应该从根中选择什么动作?
最初的UCT 论文(2006 年)
bestAction
在他们的算法中说。蒙特卡洛树搜索:游戏 AI 的新框架(2008) 说
程序最终在实际游戏中执行的游戏动作,是与被探索最多的孩子对应的动作。
- 蒙特卡洛树搜索方法调查(2012) 说
基本算法涉及迭代构建搜索树,直到达到某个预定义的计算预算(通常是时间、内存或迭代约束),此时停止搜索并返回性能最佳的根操作。
[...] 整体搜索的结果 a(BESTCHILD(v0)) 是导致根节点 v0 的最佳子节点的操作 a,其中“最佳”的确切定义由实现定义。
[...] 一旦搜索中断或达到计算预算,搜索就会终止,并且通过某种机制选择根节点 t0 的动作 a。Schadd [188] 根据 Chaslot 等人 [60] 的工作,描述了选择获胜动作的四个标准:
Max child:选择奖励最高的根孩子。
健壮的孩子:选择访问最多的根孩子。
Max-Robust child : 选择访问次数和奖励都最高的根子节点。如果不存在,则继续搜索,直到达到可接受的访问次数 [70]。
Secure child:选择最大化置信下限的孩子。
[...]一旦达到一些计算预算,算法就会终止并返回找到的最佳移动,对应于具有最高访问计数的根的子节点。
在这种情况下,整体搜索的返回值是 a(BESTCHILD(v0,0)),它将给出导致孩子获得最高奖励的动作 a,因为在最后一次调用中,探索参数 c 设置为 0根节点 v0. 该算法可以改为返回导致访问量最大的孩子的动作;这两个选项通常会 - 但并非总是如此!– 描述相同的动作。如果访问次数最多的根动作不是具有最高奖励的动作,则在围棋程序 ERICA 中通过继续搜索来解决这种潜在的差异。这将 ERICA 对抗 GNU GO 的胜率从 47% 提高到了 55% [107]。
但他们的算法 2 使用与内部节点选择策略相同的标准:
这既不是最大的孩子也不是健壮的孩子!这种情况非常令人困惑,我想知道现在哪种方法被认为是最成功/最合适的。