5

所以我使用 UCT 在蒙特卡洛树搜索算法中实现了一个转置表。这允许保持游戏状态的累积奖励值，无论在整个树中遇到的位置和次数。这提高了针对特定游戏状态收集的信息的质量。

唉，我注意到这给 UCT 的开发与探索选择阶段带来了一定的问题。简而言之，分配给状态的 UCT 分数考虑了访问父状态的次数与访问子状态（我们正在为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出，在此处输入图像描述当从转置表中拉入一个状态到树的一个新创建的分支时，这个比例完全不正常，子状态已经被访问了很多次（来自其他地方）树）和父状态被访问的次数要少得多，这在技术上应该是不可能的。

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

4

2 回答 2

4

直觉上，我希望您会想尝试以下方法。

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

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

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

不过，我个人没有 MCTS + 转置组合的经验，因此您可能希望进行额外的研究以了解其他人过去的想法。例如有以下论文：

于 2018-05-06T09:37:11.073 回答
1

我已经实现了以下内容，它与国际象棋的 Alpha Zero 风格算法配合得很好：

  • 像使用传统 MCTS 一样构建游戏树。
  • 保持游戏状态的转置表映射到它们的最大访问次数和值总和。
  • 选择一个动作时，检查它是否在其他地方看到的访问次数更多，然后将值平均为(moveValueSum + transpositionValueSum) / (moveVisits + transpositionVisits)。
    • 如果当前操作的访问次数多于转置表中的访问次数，则更新转置表。

这样，我们就不会对一个动作的所有访问进行求和，而是仅将动作值与它的单个访问次数最多的实例进行平均。

于 2020-10-19T21:13:40.440 回答