蒙特卡洛树搜索算法中的转置表对 UCT 分数产生意外影响

Question

因此，我使用 UCT 在蒙特卡罗树搜索算法中实现了转置表。这允许保持游戏状态的累积奖励值，无论在整个树中在何处以及多少次遇到它。这提高了收集到的特定游戏状态信息的质量。

唉，我注意到这给 UCT 的开发与探索选择阶段带来了某些问题。简而言之，分配给某个州的 UCT 分数会考虑访问父州的次数与访问子州（我们为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出，当将状态从转置表拉入树的新创建的分支时，该比率完全不正常，子状态已被访问大量次（从树中的其他位置）并且父状态已被访问被访问的次数要少得多，这在技术上应该是不可能的。

因此，使用换位表并保留状态的累积奖励值有助于算法的利用部分做出更好的选择，但同时它会以潜在有害的方式扭曲算法的利用部分。您知道有什么方法可以解决这个意外问题吗？

Answer 1

直觉上，我希望您会想尝试以下操作。

对于UCT 的利用部分，您需要存储并使用W / V子节点的平均分数。这个平均值可以通过换位来共享。因此，在您的示例中，您不一定要单独共享 和W = 300，V = 600而只需共享平均分数W / V = 300 / 600 = 0.5。这意味着，借助换位，您可以共享更准确的分数估计（基于更大样本量的估计）。

对于UCT 的探索部分，我认为您需要“从父节点（没有转置）的角度”使用统计数据，而不是子节点（这是其他地方的节点的转置）在树上）。在选择要转到哪个子节点时，您将使用state + action父节点中每对收集的访问计数，而不是使用子节点的访问计数。

例如，假设我们位于您编写的节点中V: 2, W: 300（将该节点称为P），并且我们必须选择一个子节点。更标准的实现将循环子节点，并使用子节点的访问计数。在您的情况下，我认为最好是循环遍历节点中的操作P，并跟踪这些操作而不是子节点的访问计数。在 中P，您还没有采取导致转置子节点的操作，因此该对的访问计数(P + action)仍将为 0。

不过，我个人没有 MCTS + 换位组合的经验，因此您可能希望进行额外的研究，看看其他人过去提出了什么。例如有以下论文：

• 蒙特卡罗树搜索中的转置和移动组
• BTT-Go：一种使用转置表来减少蒙特卡罗树搜索中的模拟和监督的围棋代理
• 如果你环顾四周，可能还会有更多，但不确定。