Monte Carlo 树搜索 - 处理游戏结束节点
Monte Carlo tree search - handling game ending nodes
我已经为一款运行良好的 4 人游戏实施了 MCTS，但我不确定当游戏结束移动在实际树中而不是在推出时我是否理解扩展。
游戏开始时 winning/losing 位置仅在 rollout 中找到，我了解如何对这些进行评分并将它们传播回树中。但是随着游戏的进行，我最终找到了一个由 UCB1 选择的叶子节点，它不能扩展，因为它是一个失败的位置，不允许移动，所以没有什么可以扩展的，也没有游戏可以 'rollout' .目前，我只是为剩下的最后一名玩家将其评分为 'win'，并为他们反向传播胜利。
然而，当我查看访问统计时，这个节点被重新访问了数千次，所以显然 UCB1 'chooses' 访问了这个节点很多次，但这真的有点浪费，我应该回来吗-为这些 'always win' 个节点传播除单次胜利以外的其他内容？
我很好地 Google 搜索了这个，但真的找不到太多提及它的地方，所以我是误会了什么还是遗漏了一些明显的东西，none 'standard' MCTS tutorials/algorithms 甚至提到树中的游戏结束节点作为特殊情况，所以我担心我误解了一些基本的东西。
At the moment I just score this as a 'win' for the last remaining player and backpropagate a win for them.
However when I look at the visit stats this node gets revisited thousands of time, so obviously UCB1 'chooses' to visit this node many times, but really this is a bit of a waste, should I be back-propagating something other than a single win for these 'always win' nodes?
不，您目前所做的是正确的。
MCTS 本质上将节点的值评估为您通过该节点 运行 的所有路径的结果的平均值。实际上，我们通常对极小极大式评估感兴趣。
为了使 MCTS 的基于平均的评估在极限（在无限量的时间之后）变得等于最小最大评估，我们依靠选择阶段（例如 UCB1）发送这么多 模拟（= 选择 + 播放阶段） 根据极小极大评估的最佳路径，平均评估在极限情况下也倾向于极小极大评估。
假设，例如，根节点下面直接有一个获胜节点。这是你的情况的一个极端例子，在选择阶段已经到达终端节点，之后不需要播放。根节点的 minimax 评估将是一个胜利，因为我们可以一步直接获得胜利。这意味着我们希望基于平均的 MCTS 评分也非常接近根节点的获胜评估。这意味着我们希望选择阶段将绝大多数模拟立即发送到该节点。如果例如99%的模拟马上从根节点走到这个获胜节点，根节点的平均评价也会变得非常接近获胜，而这正是我们所需要的。
这个答案只是关于基本UCT（MCTS with UCB1 for Selection）的实现。有关与问题相关的基本 MCTS 实现的更复杂修改，请参阅
none of the 'standard' MCTS tutorials/algorithms even mention game ending nodes in the tree as special cases
有MCTS变体可以证明一个位置的游戏理论价值。
MCTS-Solver 是（相当）众所周知的：反向传播和选择步骤已针对此变体进行了修改，以及选择最后一步的过程
玩
树中出现的终端赢利和亏损位置的处理方式不同，在树上支持这些已证明的值时会采取特殊规定。
你可以看看：
Monte-Carlo Tree Search Solver Mark H. M. Winands、Yngvi Björnsson、Jahn Takeshi Saito（计算机科学丛书第 5131 卷讲义的一部分）
了解详情。
so I'm worried I've misunderstood something fundamental.
虽然在很长的运行 MCTS中配备了UCT公式能够收敛到博弈论值，但是基本的MCTS无法证明博弈论值。
我已经为一款运行良好的 4 人游戏实施了 MCTS，但我不确定当游戏结束移动在实际树中而不是在推出时我是否理解扩展。
游戏开始时 winning/losing 位置仅在 rollout 中找到，我了解如何对这些进行评分并将它们传播回树中。但是随着游戏的进行，我最终找到了一个由 UCB1 选择的叶子节点，它不能扩展，因为它是一个失败的位置，不允许移动，所以没有什么可以扩展的，也没有游戏可以 'rollout' .目前，我只是为剩下的最后一名玩家将其评分为 'win'，并为他们反向传播胜利。
然而，当我查看访问统计时，这个节点被重新访问了数千次，所以显然 UCB1 'chooses' 访问了这个节点很多次，但这真的有点浪费，我应该回来吗-为这些 'always win' 个节点传播除单次胜利以外的其他内容？
我很好地 Google 搜索了这个，但真的找不到太多提及它的地方，所以我是误会了什么还是遗漏了一些明显的东西，none 'standard' MCTS tutorials/algorithms 甚至提到树中的游戏结束节点作为特殊情况，所以我担心我误解了一些基本的东西。
At the moment I just score this as a 'win' for the last remaining player and backpropagate a win for them.
However when I look at the visit stats this node gets revisited thousands of time, so obviously UCB1 'chooses' to visit this node many times, but really this is a bit of a waste, should I be back-propagating something other than a single win for these 'always win' nodes?
不，您目前所做的是正确的。
MCTS 本质上将节点的值评估为您通过该节点 运行 的所有路径的结果的平均值。实际上，我们通常对极小极大式评估感兴趣。
为了使 MCTS 的基于平均的评估在极限（在无限量的时间之后）变得等于最小最大评估，我们依靠选择阶段（例如 UCB1）发送这么多 模拟（= 选择 + 播放阶段） 根据极小极大评估的最佳路径，平均评估在极限情况下也倾向于极小极大评估。
假设，例如，根节点下面直接有一个获胜节点。这是你的情况的一个极端例子，在选择阶段已经到达终端节点，之后不需要播放。根节点的 minimax 评估将是一个胜利，因为我们可以一步直接获得胜利。这意味着我们希望基于平均的 MCTS 评分也非常接近根节点的获胜评估。这意味着我们希望选择阶段将绝大多数模拟立即发送到该节点。如果例如99%的模拟马上从根节点走到这个获胜节点，根节点的平均评价也会变得非常接近获胜，而这正是我们所需要的。
这个答案只是关于基本UCT（MCTS with UCB1 for Selection）的实现。有关与问题相关的基本 MCTS 实现的更复杂修改，请参阅
none of the 'standard' MCTS tutorials/algorithms even mention game ending nodes in the tree as special cases
有MCTS变体可以证明一个位置的游戏理论价值。
MCTS-Solver 是（相当）众所周知的：反向传播和选择步骤已针对此变体进行了修改，以及选择最后一步的过程 玩
树中出现的终端赢利和亏损位置的处理方式不同，在树上支持这些已证明的值时会采取特殊规定。
你可以看看：
Monte-Carlo Tree Search Solver Mark H. M. Winands、Yngvi Björnsson、Jahn Takeshi Saito（计算机科学丛书第 5131 卷讲义的一部分）
了解详情。
so I'm worried I've misunderstood something fundamental.
虽然在很长的运行 MCTS中配备了UCT公式能够收敛到博弈论值，但是基本的MCTS无法证明博弈论值。