所以我熟悉更基本的树搜索算法，如带极小值的游戏搜索，但我一直在尝试更多地了解蒙特卡洛树搜索算法，并且想知道它如何处理“精确线”。
在国际象棋的背景下，您可能处于 30 次失败但只有 1 条获胜线的位置，MTCS 算法，更具体地说是 UCB1 函数如何处理这个问题？我理解 UCB1 的方式是，它本质上是对其子节点进行某种平均，因此在你有 30 个失败的棋步和一个获胜的棋步的棋行中，UCB1 值应该看起来很低？
我仍在学习 MCTS，但我一直有这个问题，希望有人能解释即使 UCB1 值可能非常低，MCTS 如何仍会收敛到极小值。
任何知识将不胜感激！谢谢
我理解 UCB1 的方式是，它本质上对其子节点进行了一种平均，所以在你有 30 个失败的棋步和一个获胜的棋步的国际象棋行的 UCB1 值应该看起来很低？
从 UCT 公式 w_i/n_i + c*sqrt(ln(N)/n_i) 可以看出，探索项与子访问的平方根 n_i 的倒数成正比。这意味着具有最佳胜率的子节点将受到极大的青睐，因此将有更多的访问量。因此，父节点的 UCT 分数将平均偏重于最佳子节点的获胜率。
这种效应将传播到树上，导致访问次数最多的最佳线路和每个节点的准确获胜率。这样，随着模拟次数的增加，MCTS 会收敛到极小极大结果。
有关更多理论讨论，请参阅基于 Bandit 的蒙特卡洛规划的主要结果：
定理 6考虑一个有限范围的 MDP，其奖励被缩放到位于 [0, 1] 区间内。设 MDP 的范围为 D，每个状态的动作数为 K。考虑算法 UCT，使得 UCB1 的偏差项乘以 D。那么估计的预期收益 Xn 的偏差为 O(log( n)/n)。此外，随着情节的数量增长到无穷大，根处的故障概率以多项式速率收敛到零。
Imran 的回答是正确的，因为从理论的角度来看，通常在MCTS的选择阶段使用的 UCB1 策略最终应该能够处理您描述的那种情况，并且 MCTS（假设我们使用类似 UCB1 的东西）选择阶段）最终会收敛到极小极大评估。
然而，“最终”在这里的意思是“经过无数次 MCTS 迭代”。我们需要无限量的处理时间，因为只有MCTS的选择阶段才能充分处理您描述的情况类型（播出阶段不能），而选择阶段实际上只用于树的缓慢增长部分围绕根节点。因此，如果您描述的情况“位于”相对靠近根节点的位置，那么我们可以预期像 UCB1 这样的策略可以充分处理它们。如果它们离根很深/很远，那么深以至于我们无法在我们拥有的处理时间内将搜索树长得那么远……那么 MCTS 确实不能很好地处理这些情况。
请注意，对于基于 minimax 的方法也可以这样说；如果他们没有设法进行足够深入的搜索，也可能导致评估不佳。不过，在类 minimax 算法的情况下，这个故事往往更加二进制；他们要么设法进行足够深入的搜索以获得良好的评估，要么没有。在 MCTS 的情况下，它最初对这些类型的情况的评估总是很差，随着搜索树的逐渐增长，它可能会逐渐改善。
在实践中，minimax/alpha-beta/相关算法被认为在具有许多“陷阱”情况的游戏中优于基于 MCTS 的方法大约整整十年，就像你描述的情况一样。这包括类似国际象棋的游戏。在同一时期，MCTS 已经在围棋等游戏中更有前途。仅在最近的一篇论文中，MCTS + 深度强化学习 + 大量硬件的组合在类似国际象棋的游戏中击败了基于 minimax 的方法。