3

我已经为一个运行良好的 4 人游戏实现了 MCTS,但是当游戏结束移动在实际树中而不是在部署中时,我不确定我是否理解扩展。

一开始,游戏的赢/输位置只能在推出时找到,我知道如何对这些进行评分并将它们传播到树上。但是随着游戏的进行,我最终找到了一个由 UCB1 选择的无法扩展的叶节点,因为它是一个失败的位置,不允许任何移动,所以没有什么可以扩展,也没有游戏可以“推出”。目前,我只是将这作为最后一名剩余球员的“胜利”得分,并为他们反向传播胜利。

但是,当我查看访问统计信息时,该节点被重新访问了数千次,因此显然 UCB1 多次“选择”访问该节点,但这确实有点浪费,我是否应该反向传播其他东西而不是单个赢得这些“永远赢”的节点?

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

4

2 回答 2

2

目前,我只是将这作为最后一名剩余球员的“胜利”得分,并为他们反向传播胜利。

但是,当我查看访问统计信息时,该节点被重新访问了数千次,因此显然 UCB1 多次“选择”访问该节点,但这确实有点浪费,我是否应该反向传播其他东西而不是单个赢得这些“永远赢”的节点?

不,您目前已经在做的事情是正确的。

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

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

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


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

于 2018-06-11T14:33:06.643 回答
1

没有一个“标准”MCTS 教程/算法甚至提到树中的游戏结束节点作为特殊情况

有一些 MCTS 变体能够证明一个位置的博弈论价值。

MCTS-Solver(相当)众所周知:反向传播和选择步骤已针对此变体进行了修改,以及选择最终移动的过程。

树中出现的最终赢和输位置的处理方式不同,并且在将这些经过验证的值支持到树上时采取了特殊规定。

你可以看看:

蒙特卡罗树搜索求解器,作者:Mark HM Winands、Yngvi Björnsson、Jahn Takeshi Saito(计算机科学系列丛书第 5131 卷讲义的一部分)

详情。

所以我担心我误解了一些基本的东西。

虽然从长远来看,配备UCT公式的MCTS能够收敛到博弈论的价值,但基本的MCTS无法证明博弈论的价值。

于 2018-06-13T11:47:42.070 回答