MCTS UCT与评分系统

Question

MCTS UCT与评分系统

artificial-intelligencemontecarlo

7

我正在尝试通过蒙特卡罗树搜索解决2048的变体。我发现UCT可以在探索/利用之间取得一些权衡。我的唯一问题是，我看到的所有版本都假定分数是胜率。如何使其适应一个分数是最后状态下板子价值的游戏，因此从1-MAX而不是胜利开始的游戏？

我可以通过除以MAX使用常数c来归一化分数，但这会使游戏早期过度探索（因为您获得了较差的平均分数），并在游戏后期过度利用。

- Atol

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tubeliar · Accepted Answer

大部分文献都假设你的游戏是赢或输，并授予0或1分的分数，当平均游戏次数时，将成为胜率。然后，勘探参数C通常设置为sqrt(2)，这对于UCB在赌博机问题中是最优的。

为了找出一个好的普遍C值，你需要退一步看看UCT实际上在做什么。如果你树中的一个节点在一个模拟中得分异常低，那么利用就说你不应该再选择它。但是你只玩了那个节点一次，所以它可能只是运气不好。为了承认这一点，你会给那个节点一个奖金。多少？足以使它成为可行的选择，即使它的平均分数是最低的，其他节点有可能获得最高的平均分数。因为有了足够多的玩法，可能会发现你的不良节点确实是一个偶然事件，而且该节点实际上具有良好的得分可靠性。当然，如果你获得更多的低分，那么它可能不是运气不好，所以它不应该得到更多的模拟。

因此，在得分从0到1的情况下，sqrt(2)的C值是一个很好的值。如果你的游戏有一个最大可达分数，那么你可以通过将max除以得分并强制你的得分为0-1范围来使你的得分标准化，以适应sqrt(2)的C值。或者，你不标准化得分，但是将C乘以你的最大得分。效果相同：UCT探索奖励足够大，可以给予不利地位的节点某些模拟和证明自己的机会。

还有一种动态设置C的替代方法，这给了我很好的结果。当你玩的时候，你会跟踪每个节点（和子树）中看到的最高和最低分数。这是可能的分数范围，这为您提供了一个提示，说明为了给未经探索的不利节点一个公平的机会，C应该有多大。每次我进入树并选择一个新的根时，我都会将C调整为新根的sqrt(2)*score range。此外，随着模拟完成并且它们的分数变成新的最高或最低分数，我也会以同样的方式调整C。通过在玩耍的同时不断调整C，但也选取一个新的根，您可以使C尽可能大地收敛，但也使其尽可能小地快速收敛。请注意，最小分数与最大分数一样重要：如果每次模拟都至少获得某个分数，则C不需要克服它。只有最大值和最小值之间的差异才重要。