A Survey of Monte Carlo Tree Search Methods -- Part 3

Posted by Rasin on April 25, 2021

变种

传统的游戏AI研究专注于双人玩家的零和回合交替游戏,离散的动作空间,确定的状态转换和完美的信息。尽管MCTS已广泛应用于此类游戏,但它也已应用于其他领域类型,例如单人游戏和计划问题,多人游戏,实时游戏以及具有不确定性或同时移动的游戏。 本节介绍了采用MCTS适应这些领域的方法,以及采用了MCTS的思想而又不严格遵循其概述的算法。

Flat UCB

Flat UCB 被提出时是将搜索树的叶节点当作是单个多臂赌博机问题。与flat Monte Carlo 搜索不同的是,动作是根据状态均匀采样的,不需要构建树。在某些 UCT 过于乐观的最坏情况下, Flat UCB 保留了标准 UCT 的适应性,同时改善了其遗憾的边界。

平滑树的赌博机算法 (BAST)

BAST 是由 Flat UCB 改进而来,它使用关于奖励平滑度的假设来识别和忽略具有次高置信度的次优分支。将 BAST 应用于 Lipschitz 函数逼近,当允许无限迭代时,唯一无限扩展的分支是最佳分支。这与普通的 UCT 相反,后者可以无限扩展所有分支。

MCTS中的学习

MCTS可以看作是强化学习算法的一种,因此可以考虑其与时差学习的关系。

时差学习 (TDL)

TDL算法一般不构建树,当所有的状态值能直接被存储在表格里时,MCTSTDL才会相等。MCTS 根据当前状态值来决定下一步,而 TDL学习每个状态的长期值来指导未来的行为。Silver 提出了结合了MCTS与TDL的算法,使用永久性和临时性存储器的概念来区分两种类型的状态值估计。TDL可以学习启发式值函数以通知树策略或模拟策略。

使用时差的蒙特卡洛

Osaki将提出的 TDMC(λ)称为是一种 “在非终结位置中使用获胜概率作为替代奖励的强化学习的新方法 “。

基于赌博机的主动学习 (BAAL)

Rolet提出了 BAAL来强调系数数据应用中的小样本训练集的问题。主动学习的概念在有限资源下被形式化为有限视野强化学习问题,目的是使泛化误差最小。将主动学习视为单人游戏,可以通过结合UCT和台球算法来估计最佳策略。

单人MCTS (SP-MCTS)

SP-MCTS 是一个蒙特卡洛的单玩家变种,其变化是在UCB方程的后面加了第三项,表示每个节点”可能的偏差”,表示为:

\[\sqrt{\sigma^2 + \frac{D}{n_i}}\]

其中,\(\sigma^2\) 是指节点模拟结果的方差,\(n_i\)是节点的访问次数,\(D\)是常量。\(\frac{D}{n_i}\)可以被视为人为地增加不常访问节点地标准差,以便将此类节点地奖励视为不那么确定。与朴素 UCT的另一区别是在模拟时使用启发式的缺省策略。

Schadd指出,在某些情况下,如果 SP-MCTS自身陷入局部最大值,则需要进行元搜索(一种使用其他搜索过程来获得答案的高级搜索方式)。他们发现,使用不同的随机种子定期重新开始搜索,并在所有运行过程中存储最佳的解决方案,则大大提高了 SameGame 玩家的性能。

关于将标准 UCT 带入单人游戏中,Bjornsson 和 Finnsson指出如果同级的兄弟比较弱的话,平均的模拟结果可以将强力的游玩路线隐藏起来,而偏向于所有的游玩路线都具有中等强度的区域。为了解决这个问题,他们建议除了平均结果之外,还要跟踪每个节点上的最大模拟结果,单平均值仍在搜索过程中使用。另一个修改意见是,当模拟找到一条强力路线是,它将其全部存储在树中。对于多玩家的游戏来说这是有害的行为,因为如此强壮的游玩路线可能依赖于不现实的假设,即对手打出了较弱的一手。但对于担任游戏来说并不是问题。

特征 UCT 选择 (FUSE)

FUSEUCT对特征选择的组合优化问题的适应。选择可用特征的子集的问题被视为单人游戏,其状态是特征的所有可能子集,其动作包括选择一个特征并将其添加到该子集中。

为了处理该游戏的大分支因素,FUSE使用 UCB1-TunedRAVEFUSE还使用特定于游戏的近似值的奖励函数,并根据树中的深度调整在模拟过程中选择停止特征的概率。

多人MCTS

Minimax 搜索的核心假设是搜索参与者试图最大化其奖励。在二人零和游戏中,这等同于说每个玩家都试图最大化自己的奖励。但是,在两个以上的玩家的游戏中,这种等效性不一定成立。

将MCTS应用于多人游戏的最简单想法是 maxn:每个节点都存储一个奖励向量,而决策程序则寻求使用合适的奖励向量的分量来最大化 UCB计算值。 Sturtevant表明,UCT的这种变体已经收敛到最佳平衡策略,尽管该策略并非是完全的 maxn策略,因为其可以混合使用。

Cazenave 将 UCT的多种变体应用于多人围棋游戏,并考虑了玩家在联盟中行动的可能性。搜索本身使用上述的 maxn方法,但在模拟过程中增加了一条规则,以避免打出不利于联盟其他成员的行动,并且使用了一种不同的计分系统,联盟成员的宝石也算是自己的宝石。