带有评分系统的MCTS UCT

Question

我正在尝试通过蒙特卡洛树搜索解决2048的变体形式。我发现，UCT可能是在勘探/开发之间进行权衡的好方法。

我唯一的问题是，我所见过的所有版本都假定分数是获胜百分比。我该如何适应分数为最后状态的棋盘值的游戏，从而从1-MAX而不是获胜。

我可以使用常数c除以MAX来归一化分数，但随后它会在游戏早期阶段超重探索（因为平均得分不佳），而在游戏后期则超重利用。

Answer 1

事实上，大多数文献都假设你的游戏要么输了，要么赢了，并授予0 或 1的分数，当对所玩游戏的数量进行平均时，这将变成获胜率。然后，探索参数 C 通常设置为 sqrt(2)，这对于老虎机问题中的 UCB 来说是最佳的。

要了解什么是好的 C，您必须退后一步，看看 UCT 真正在做什么。如果树中的一个节点在一次部署中得分特别差，那么利用就会表明您永远不应该再次选择它。但你只玩过该节点一次，所以可能只是运气不好。为了承认这一点，您给该节点一个奖励。多少？即使它的平均得分是最低的，而其他节点的平均得分可能最高，也足以使其成为可行的选择。因为经过足够多的游戏，可能会发现你的坏节点的一次推出确实是一次侥幸，而且该节点实际上非常可靠，得分很高。当然，如果你得到更多的坏分数，那么它可能并不是运气不好，所以它不值得更多的推出。

因此，分数范围为 0 到 1 时，sqrt(2) 的 C 是一个不错的值。如果您的游戏有可达到的最大分数，那么您可以通过除以最大值来标准化您的分数，并将您的分数强制在 0-1 范围内以适应 sqrt(2) 的 C。或者，您不标准化分数，而是将 C 乘以您的最高分数。效果是一样的：UCT 探索奖励足够大，可以为你的失败者节点提供一些展示机会和证明自己的机会。

有一种动态设置 C的替代方法给了我很好的结果。当你玩的时候，你会记录你在每个节点（和子树）中看到的最高和最低分数。这是可能的分数范围，这会提示您 C 应该有多大，以便为未充分探索的弱势节点提供公平的机会。每次我下降到树中并选择一个新根时，我都会将 C 调整为sqrt(2) *新根的分数范围。此外，当推出完成并且他们的分数成为新的最高或最低分数时，我以相同的方式调整 C。通过在玩游戏时以及选择新的根时以这种方式不断调整 C，您可以使 C 保持尽可能大的收敛速度，但又尽可能小以快速收敛。请注意，最低分数与最高分数一样重要：如果每次推出都会至少产生某个分数，那么 C 就不需要克服它。只有最大和最小之间的差异才重要。