algorithm - 蒙特卡洛树搜索算法中的转置表对 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 中遍历 actions，并跟踪这些操作的访问次数而不是子项的访问次数节点。在 P 中，您还没有采取导致转置子节点的操作，因此 (P + action) 对的访问计数仍将为 0 .

---

虽然我个人没有使用 MCTS + 换位组合的经验，因此您可能希望进行额外的研究以了解其他人过去的想法。例如有以下论文:

• Transpositions and Move Groups in Monte Carlo Tree Search
• BTT-Go: An Agent for Go That Uses a Transposition Table to Reducethe Simulations and the Supervision in the Monte-Carlo Tree Search
• 如果你环顾四周，可能会有更多，不确定。