蒙特卡洛树搜索 - 处理游戏结束节点

Question

我已经为 4 人游戏实现了 MCTS，该游戏运行良好，但当游戏结束移动位于实际树中而不是在推出中时，我不确定我是否理解扩展。

在游戏开始时，游戏获胜/失败的位置只能在推出中找到，我了解如何对这些进行评分并将它们传播回树上。但随着游戏的进行，我最终找到了一个由 UCB1 选择的叶节点，它无法扩展，因为它是一个失败的位置，不允许任何移动，因此没有任何东西可以扩展，也没有游戏可以“推出”。目前，我只是将此视为最后剩下的玩家的“胜利”，并为他们反向传播胜利。

然而，当我查看访问统计信息时，该节点被重新访问了数千次，因此显然 UCB1“选择”多次访问该节点，但实际上这有点浪费，我是否应该反向传播除单个节点之外的其他内容赢得这些“永远获胜”的节点？

我对此进行了很好的谷歌搜索，但找不到太多提及它的内容，所以我是否误解了某些东西或遗漏了一些明显的东西，“标准”MCTS教程/算法甚至没有提到树中的游戏结束节点作为特殊情况，所以我担心我误解了一些基本的东西。

Answer 1

目前，我只是将此视为最后剩下的玩家的“胜利”，并为他们反向传播胜利。

然而，当我查看访问统计信息时，该节点被重新访问了数千次，因此显然 UCB1“选择”多次访问该节点，但实际上这有点浪费，我是否应该反向传播除单个节点之外的其他内容赢得这些“永远获胜”的节点？

不，您目前所做的事情是正确的。

MCTS 本质上将节点的值评估为经过该节点的所有路径的结果的平均值。实际上，我们通常对极小极大式评估感兴趣。

为了使 MCTS 的基于平均值的评估变得等于极限内的极小极大评估（无限长的时间后），我们依靠选择阶段（例如 UCB1）发送如此多的模拟（= 选择 + 播放阶段）根据最小最大评估，平均评估在极限情况下也趋向于最小最大评估，沿着该路径是最佳的。

例如，假设根节点正下方有一个获胜节点。这是您的情况的一个极端示例，其中在选择阶段已经到达终端节点，并且之后不需要播放。根节点的极小极大评估将是胜利，因为我们可以直接一步获得胜利。这意味着我们希望 MCTS 的基于平均的评分也变得非常接近根节点的获胜评估。这意味着我们希望选择阶段将绝大多数模拟立即发送到该节点。例如，如果所有模拟的 99% 立即从根节点转到该获胜节点，则根节点的平均评估也将变得非常接近获胜，而这正是我们所需要的。

这个答案只是关于基本UCT（MCTS with UCB1 for Selection）的实现。有关与该问题相关的基本 MCTS 实现的更复杂的修改，请参阅manlio 的答案