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

Question

我已经为一个4人游戏实现了MCTS，目前运行良好。但是，如果游戏结束的移动在实际树中而不是在rollout中，我不确定自己是否理解扩展。

在开始时，游戏的胜利/失败位置仅在rollout中找到，我知道如何对其进行评分并将其传播回树上。但是随着游戏的进行，我最终会发现一个叶节点，由UCB1选择的，无法扩展，因为它是一个输掉的位置，没有可能的移动，因此没有任何可以扩展的内容，也没有游戏可供“rollout”。目前，我只将其评分为剩余玩家的“胜利”，并向其传播胜利。

然而，当我查看访问统计数据时，这个节点被重新访问了数千次，显然UCB1选择多次访问此节点，但实际上这有点浪费，我应该向这些“总是赢”的节点反向传播除了单个胜利之外的东西吗？

我已经通过谷歌搜索了很多，但并没有找到太多相关信息，所以我是否有什么误解或遗漏了一些明显的内容？标准的MCTS教程/算法甚至没有提到树中的游戏结束节点作为特殊情况，所以我担心自己可能误解了一些基本的东西。

- Pajh

Answer 1

目前，我只将这个最后的玩家得分为“胜利”，并为他们向后传递了一项胜利。

然而，当我查看访问统计数据时，这个节点被重新访问了成千上万次，显然UCB1选择访问此节点多次，但实际上这有点浪费，我应该传递一些与这些“总是获胜”的节点不同的东西吗？

不，你目前已经做得很正确了。

MCTS基本上将一个节点的价值评估为您通过该节点运行的所有路径的结果的平均值。在现实中，我们通常对极小化-极大化样式的评估感兴趣。

为了使MCTS基于平均值的评估在极限情况下（经过无限时间后）变得等同于极小化-极大化评估，我们依靠选择阶段（例如UCB1），将许多模拟（=选择 +播放阶段）发送到根据极小化评估最佳的路径（S），以便平均评估也倾向于在极限情况下趋近于极小化-极大化评估。

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

---

此答案仅关于基本UCT的实现（使用UCB1进行选择）。有关与问题相关的该基本MCTS实现的更复杂的修改，请参见manlio的答案

- Dennis Soemers

Answer 2

标准的MCTS教程/算法甚至没有将树中的游戏结束节点作为特殊情况进行提及。

有一些MCTS变种可以证明一个位置的博弈论价值。

MCTS-Solver是（相当）知名的：这个变种修改了反向传播和选择步骤，以及选择最终移动的过程。

处理树中出现的终止胜利和失败位置时会有所不同，并且在向上备份这些已被证明的值时会采取特殊措施。

您可以查看：

Monte-Carlo Tree Search Solver by Mark H. M. Winands, Yngvi Björnsson, Jahn Takeshi Saito (part of the Lecture Notes in Computer Science book series volume 5131)

了解详情。

所以我担心我可能误解了某些基本的东西。

虽然长期来看，搭载了UCT公式的MCTS能够收敛到博弈论价值，但基本的MCTS无法证明博弈论价值。

- manlio