Monte Carlo 树搜索算法中的转置 table 对 UCT 分数的意外影响
Transposition table in Monte Carlo Tree Search algorithm unintended effect on UCT score
所以我使用 UCT 在 Monte Carlo 树搜索算法中实现了转置 table。这允许保留游戏状态的累积奖励值，无论在何处以及在整个树中遇到多少次。这提高了在特定游戏状态下收集的信息的质量。
唉，我注意到这在 UCT 的开发与探索选择阶段造成了一定的问题。简而言之，分配给一个州的 UCT 分数考虑了访问父州的次数与访问子州（我们为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出， 当从转置 table 拉入状态到新创建的树分支时，该比率完全不正常，子状态已被访问很多次（从树中的其他地方）并且访问父状态的次数要少得多，这在技术上应该是不可能的。
因此，使用转置 table 并保留状态的累积奖励值有助于算法的开发部分做出更好的选择，但同时它使算法的开发部分倾斜潜在有害的方式。您知道有什么方法可以解决这个意外问题吗？
凭直觉，我预计您会想尝试以下方法。
对于 UCT 的 利用 部分，您需要存储和使用 child 个节点的平均分数 W / V。这个平均值可以通过换位共享。因此，在您的示例中，您不一定要单独共享 W = 300 和 V = 600，而只是共享平均分数 W / V = 300 / 600 = 0.5。这意味着，由于换位，您可以共享更准确的分数估计（基于更大样本量的估计）。
对于 UCT 的 探索 部分，我想你会想要使用 parent 节点的统计信息 "from the perspective"（你不需要的地方有转置），而不是 child 节点（这是树中其他地方节点的转置）。当 select 要转到哪个 child 节点时，不是使用 child 节点的访问计数，这意味着您将使用 [=] 中每个 state + action 对收集的访问计数59=]节点.
例如，假设我们在您写 V: 2, W: 300 的节点中（将此节点称为 P），我们必须 select a child节点。更标准的实现将遍历 children，并使用 child 节点的访问计数。在您的情况下，我认为最好在节点 P 中遍历 actions，并跟踪这些操作的访问次数而不是 child 个节点。在 P 中，您还没有采取导致转置 child 节点的操作，因此 (P + action) 对的访问计数仍为 0。
虽然我个人没有使用 MCTS + 换位组合的经验，因此您可能希望进行额外的研究以了解其他人过去的想法。例如有以下论文：
我已经实现了以下与国际象棋的 Alpha Zero 风格算法配合良好的算法：
- 像传统 MCTS 一样构建游戏树。
- 保持换位 table 从游戏状态映射到它们的最大访问次数和价值总和。
- 选择一个动作时，检查它是否在其他访问次数较多的地方看到，取平均值为
(moveValueSum + transpositionValueSum) / (moveVisits + transpositionVisits)。
- 如果当前操作的访问次数多于换位 table 中的访问次数，则更新换位 table。
这样我们就不会对某个操作的所有访问进行求和，而只会将操作值与访问次数最多的单个实例进行平均。
所以我使用 UCT 在 Monte Carlo 树搜索算法中实现了转置 table。这允许保留游戏状态的累积奖励值，无论在何处以及在整个树中遇到多少次。这提高了在特定游戏状态下收集的信息的质量。
唉，我注意到这在 UCT 的开发与探索选择阶段造成了一定的问题。简而言之，分配给一个州的 UCT 分数考虑了访问父州的次数与访问子州（我们为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出，
因此，使用转置 table 并保留状态的累积奖励值有助于算法的开发部分做出更好的选择，但同时它使算法的开发部分倾斜潜在有害的方式。您知道有什么方法可以解决这个意外问题吗？
凭直觉，我预计您会想尝试以下方法。
对于 UCT 的 利用 部分，您需要存储和使用 child 个节点的平均分数 W / V。这个平均值可以通过换位共享。因此，在您的示例中，您不一定要单独共享 W = 300 和 V = 600，而只是共享平均分数 W / V = 300 / 600 = 0.5。这意味着，由于换位，您可以共享更准确的分数估计（基于更大样本量的估计）。
对于 UCT 的 探索 部分，我想你会想要使用 parent 节点的统计信息 "from the perspective"（你不需要的地方有转置），而不是 child 节点（这是树中其他地方节点的转置）。当 select 要转到哪个 child 节点时，不是使用 child 节点的访问计数，这意味着您将使用 [=] 中每个 state + action 对收集的访问计数59=]节点.
例如，假设我们在您写 V: 2, W: 300 的节点中（将此节点称为 P），我们必须 select a child节点。更标准的实现将遍历 children，并使用 child 节点的访问计数。在您的情况下，我认为最好在节点 P 中遍历 actions，并跟踪这些操作的访问次数而不是 child 个节点。在 P 中，您还没有采取导致转置 child 节点的操作，因此 (P + action) 对的访问计数仍为 0。
虽然我个人没有使用 MCTS + 换位组合的经验，因此您可能希望进行额外的研究以了解其他人过去的想法。例如有以下论文：
我已经实现了以下与国际象棋的 Alpha Zero 风格算法配合良好的算法：
- 像传统 MCTS 一样构建游戏树。
- 保持换位 table 从游戏状态映射到它们的最大访问次数和价值总和。
- 选择一个动作时，检查它是否在其他访问次数较多的地方看到，取平均值为
(moveValueSum + transpositionValueSum) / (moveVisits + transpositionVisits)。- 如果当前操作的访问次数多于换位 table 中的访问次数，则更新换位 table。
这样我们就不会对某个操作的所有访问进行求和，而只会将操作值与访问次数最多的单个实例进行平均。