machine-learning - MCTS 如何与 'precise lines' 配合使用

Question

所以我熟悉更基本的树搜索算法，例如带有极小极大的游戏搜索，但我一直在尝试了解有关蒙特卡洛树搜索算法的更多信息，并且想知道它如何处理“精确线”。

在国际象棋中，您可能会遇到 30 次失败但有 1 条获胜路线的情况，MTCS 算法(更具体地说是 UCB1 函数)将如何处理这种情况？我理解 UCB1 的方式是，它本质上是对其子节点进行某种平均，因此，有 30 次失败的棋步和 1 次获胜的棋局的 UCB1 值应该低得令人迷惑？

我仍在学习 MCTS，但我一直有这个问题，并希望有人能够解释 MCTS 如何仍然收敛到极小极大，即使 UCB1 值可能非常低。

任何知识将不胜感激!谢谢

Answer 1

Imran 的答案是正确的，因为从理论角度来看，通常在 MCTS 的选择阶段使用的 UCB1 策略应该最终能够处理您描述的各种情况，并且 MCTS(假设我们在选择阶段使用类似 UCB1 的东西)将最终收敛到极小极大评估。

但是，这里的“最终”表示“经过无数次 MCTS 迭代之后”。我们需要无限量的处理时间，因为只有 MCTS 的选择阶段能够充分处理您描述的情况类型(播放阶段不能)，而< em>选择阶段实际上仅用于根节点周围树的缓慢生长部分。因此，如果您描述的情况“位于”相对靠近根节点的位置，那么我们可以预期像 UCB1 这样的策略可以充分处理它们。如果它们非常深/离根很​​远，深到我们无法在处理时间内将搜索树增长到那么远......那么 MCTS 确实不能很好地处理这些情况。

请注意，对于基于极小极大的方法也可以说类似的事情；如果他们搜索得不够深入，也可能导致评价不佳。不过，在类似极小极大算法的情况下，这个故事往往更加二元化。他们要么设法足够深入地搜索良好的评估，要么就没有。就 MCTS 而言，它最初总是对这些类型的情况评估不佳，并且可能会随着搜索树的逐渐增长而逐渐改善。

实际上，在大约整整十年的时间里，在具有许多“陷阱”情况(如您所描述的情况)的游戏中，极小极大/α-β/相关算法被认为优于基于 MCTS 的方法。这包括类似国际象棋的游戏。在同一时期，MCTS 在围棋等游戏中已经更有前景。仅在 a recent paper MCTS + 深度强化学习 + 大量硬件的组合在类似国际象棋的游戏中击败了基于极小极大的方法。