MCTS UCT与评分系统

Question

我正在尝试通过蒙特卡洛树搜索来解决2048的一个变体。我发现UCT是一种在探索/开发之间进行权衡的好方法。

我唯一的问题是，我见过的所有版本都假设得分是一个胜率。我如何使它适应这样一种游戏，在这种游戏中，得分是棋盘在最后一个状态下的值，因此从1-MAX开始，而不是胜利。

​

​

我可以用常数c除以MAX来归一化分数，但它会在游戏的早期阶段过度探索(因为你得到的平均分数很差)，并在游戏后期过度利用。

Answer 1

事实上，大多数文献都假设您的游戏要么输了，要么赢了，并给出了0或1的分数，当在玩的游戏数量上取平均值时，这将转化为win 。然后，通常将探测参数C设置为sqrt(2)，这对于bandit问题中的UCB是最优的。

要找出一个好的C通常是什么，你必须后退一步，看看UCT到底在做什么。如果树中的一个节点在它的一次推出中得分非常低，那么利用漏洞就会告诉你永远不应该再选择它。但您只玩过该节点一次，所以它可能只是坏运气。要确认这一点，您需要给该节点一个奖励。多少钱？这足以使它成为一个可行的选择，即使它的平均分数是最低的，并且其他节点具有最高的平均分数可能的。因为有了足够多的游戏，可能会证明你的坏节点的推出确实是一个偶然的机会，而这个节点实际上是相当可靠的，得分很高。当然，如果你得到了更多的坏分数，那么它可能不会是坏运气，所以它不值得更多的推出。

因此，对于分数从0到1的情况，sqrt(2)的C是一个很好的值。如果您的游戏有一个最大可达到的分数，那么您可以通过除以最大值来归一化您的分数，并将您的分数强制到0-1范围内，以适应sqrt(2)的C。或者，您可以不对分数进行归一化，但是将C乘以您的最大分数。效果是一样的: UCT探索奖励足够大，给你的失败者节点一些展示和证明自己的机会。

有一种动态设置C的的替代方法，它给了我很好的结果。当您玩游戏时，您将跟踪您在每个节点(和子树)中所见过的最高和最低分数。这是得分的范围，这给了你一个提示，为了给没有被充分探索的失败者节点一个公平的机会，C应该有多大。每次我下降到树中并选择一个新的根时，我将C调整为sqrt(2) *新根的得分范围。此外，随着展示的完成和他们的分数被证明是一个新的最高或最低分数，我以同样的方式调整C。通过不断地调整C，在你玩的时候，而且当你选择一个新的根时，你可以保持C的与收敛所需的一样大，但保持尽可能小以收敛快速的。请注意，最小分数和最大分数一样重要:如果每次推出都会产生最小分数，那么C就不需要克服它。只有max和min之间的差异才是重要的。