当叶子的模拟计数为零时，MCTS 的初始 UCT 值应该是多少？无限？

人工智能 蒙特卡罗树搜索 置信上限 树搜索
2021-11-02 13:01:14

我正在实施蒙特卡洛树搜索算法，其中选择过程是通过上置信界公式完成的：

def uct(state):
        log_n = math.log(state.parent.sim_count) 
        explore_term = self.exploration_weight * math.sqrt(log_n / state.sim_count)
        exploit_term = (state.win_count / state.sim_count)

        return exploit_term + explore_term

但是，当节点的 sim_count 为 0 时，我无法选择 UCT 的初始值。我尝试使用 +inf （这将是合适的，因为从正面接近 lim -> 0 会给出无穷大），但这只是意味着算法将始终选择一个未探索的孩子。

你会建议什么作为 uct 的初始值？

先感谢您！

1个回答

赋值∞到未访问的节点确实是“默认”或最基本的选择，它确实确保搜索不会再次访问一个节点，如果它还有没有访问过的兄弟节点。但文献中也尝试了许多其他类型的价值观。

Gelly 和 Wang 在“Exploration exploit in Go: UCT for Monte-Carlo Go”中将参数称为“First-play Urgency”（FPU），并确实将其视为超参数；他们只是尝试了各种不同的值，发现有些值比其他值更好。

您可能要考虑的其他更具体的值（但在大多数情况下，如果没有经验评估，我们不能真正说出哪个比其他哪个更好）是：

  • 损失的价值；将没有任何访问的节点视为丢失节点可能是您可以选择的最“悲观”的初始化。论文中没有很清楚地描述它，但有一些证据表明 AlphaGo Zero 和 AlphaZero 使用了它。不过，这些不仅仅是普通的 UCT，这些程序具有训练有素的深度神经网络，可以为行动提出额外的建议。如果您没有如此强大的神经网络来在您的选择中引入额外的偏差，我不建议将未访问的节点视为丢失节点。
  • 平局的价值；将未访问的节点视为平局意味着您可以优先考虑重新访问看起来像获胜节点的节点，但不会优先考虑重新访问看起来像失败节点的节点。
  • 胜利的价值；这可能会在实践中产生类似的行为，作为∞
  • 反向传播到父节点的平均值（校正玩家移动颜色的差异）；您可以优先考虑重新访问此子树中性能优于平均水平的节点，但不会优先考虑重新访问此子树中性能低于平均水平的节点
其它你可能感兴趣的问题
上一篇自学和迁移学习有什么关系？ 下一篇机器学习的非负矩阵分解已经过时了吗？