蒙特卡洛树搜索

Posted by sjj118 on 2019-01-04

摘要

在完全信息博弈中,极大极小搜索加上 Alpha-Beta 剪枝是最常用的算法,然而,极大极小搜索必须遍历所有的状态,能搜索的深度非常有限,即便加上 Alpha-Beta 剪枝也没有太大的帮助。因此在这篇文章讲介绍另一种更有效的方法——蒙特卡洛树搜索(MCTS),它将更加有选择性的进行搜索,因此能取得更好的效果。我们将先介绍蒙特卡洛树搜索的大体框架,然后详细分析 MCTS 中最重要的多臂老虎机算法(MAB)。

概述

完全信息博弈是生活中非常常见的一种博弈,如围棋、象棋等棋类游戏都属于完全信息博弈。完全信息博弈的特点是每个参与者都了解所有其他参与者的特征、策略及得益函数等方面的准确信息。在一个状态总数有限的完全信息博弈中,理论上可以通过搜索得出必胜走法。然而,各种棋类游戏的总状态数往往非常巨大,比如围棋大约有 \(10^172\) 种不同的状态,我们不可能通过搜索将所有的状态遍历一遍。

极大极小搜索是一种简单但实用的算法。其思路是在搜索达到一定深度时停止搜索,通过估价函数计算当前节点的估价。然后通过递归的方式计算父状态的估价:如果一个状态是对方行棋,则考虑最坏的情况,将子状态中最差的估价作为此状态的估价;如果一个状态是我方行棋,则将子状态中最优的估价作为此状态的估价。最后就可以得到当前所有不同走法的估价,选择最优的一种走法即可。极大极小搜索将估价函数与搜索相结合,解决了无法遍历所有状态的问题,并且一般情况下比直接贪心更优。然而,极大极小搜索本质上还是没有任何启发式的暴力搜索,搜索状态数会随着深度的增加而指数倍的增加,因此在有限的时间内往往无法搜索太多的层数。即便加上 Alpha-Beta 剪枝也只是常数级别的优化,并且其剪枝效果视情况而定。

蒙特卡洛树搜索是一种简单且通用性较强的算法,它的核心思想是通过随机模拟对局来估计胜率,同时运用多臂老虎机算法来维护一棵搜索树 [1]。搜索树的大小与搜索的时间成正比,搜索树越大,效果越好。所以搜索时间的增加往往能使蒙特卡洛树搜索的效果增加明显,而对极大极小搜索则没有太大的作用。击败围棋世界冠军的 AlphaGo 的核心部分便是蒙特卡洛树搜索,可见其潜力之大。在第 2 部分将介绍蒙特卡洛树搜索的整体框架,第 3 部分将介绍蒙特卡洛树搜索中最重要的多臂老虎机问题。

蒙特卡洛树搜索算法框架

蒙特卡洛树搜索通过不断的搜索来构建一棵搜索树,每个节点记录两个值:访问次数和获胜次数。在搜索树的根节点初始化为初始局面后,每次搜索有以下几个步骤:

  • 选择:从根节点开始往下走,每次通过多臂老虎机算法选择一个最优的子节点,直到来到一个存在未扩展子节点的节点,即存在一个还没有被添加到搜索树中的后继状态。

  • 扩展:如果当前节点未被完全扩展,则任选一种没试过的走法并创建一个新的子节点。

  • 模拟:使用快速走子策略(常用随机)进行自我对弈,并将对弈结果反向传播到所有父节点,即访问次数加一,若获胜则获胜次数也加一。

其中,多臂老虎机算法就是以访问次数与获胜次数为依据来选择最优子节点的。

在时间限制内尽量多的执行搜索操作,最后选择一个尝试次数最多的走法。因为尝试次数越多,说明获胜概率的估计越准确,并且只有这个走法足够优秀才会获得多臂老虎机算法这么多次的选择。 注意,蒙特卡洛法与蒙特卡洛树搜索不同。蒙特卡洛法也称统计模拟法,它通过不断的随机模拟来估计概率,与上述算法框架的模拟部分类似。

如果我们直接采用蒙特卡洛法而不构建搜索树,即通过不断随机自我对弈来估算不同走法的胜率,则效果不会很好。因为蒙特卡洛法反应的是状态空间中获胜的局面的比例,不能准确的反应局面的优劣。可能存在一种局面使得大部分的情况会输,但是存在一种必胜的走法。这时蒙特卡洛法就无能为力,而在蒙特卡洛树搜索中,只要有充足的时间,随着搜索树的增大,最终必定会找到那个必胜的走法。

此外,蒙特卡洛树搜索还可以与估价函数相结合。由于完整的一局游戏可能有几十步甚至上百步,完全采取随机策略模拟的话效果可能很差。因此我们可以不随机完整的一局,可以随机走四五步,然后通过估价函数的正负号来判断胜负。

多臂老虎机问题(Multi-Armed Bandit)

多臂老虎机是一个有多个拉杆的赌博机,每一个拉杆的中奖几率是不一样的,现在你可以拉若干次拉杆(假设可以拉的次数远大于拉杆个数),如何最大化获得的收益?显然我们可以将拉拉杆操作分为两种:explore,目的是估算不同拉杆的平均收益;exploit,拉平均收益最大的拉杆来获得最大利益。

可见蒙特卡洛树中选择最优子节点的过程类似于多臂老虎机问题,只不过每个拉杆的收益会随着拉的次数而变化而变化。下面将介绍多臂老虎机问题几种常用算法及它们在蒙特卡洛树搜索中的效果分析比较。

ε-Greedy

如果在生活中碰到这样的问题,一种很常见的方法就是,explore 几次再 exploit 几次。这是一种简单但也比较有效的方法,更加形式化的描述就是:设定概率 ε,每次以 ε 的概率进行 explore,即随机选择一个拉杆,以 1-ε 的概率进行 exploit,即选择预估收益最大的拉杆。

具体操作就是,每次拉的时候就抽一个 0 到 1 的随机数,如果这个数大于 ε,则拉预估中奖概率最大的那个拉杆。如果小于 ε,则随机再选择一个拉杆,得到收益后,更新这个拉杆的预估中奖概率,以便于下次选择做参考。

此外,随着实验次数的增加,预估收益会越来越准确,因此我们希望 explore 越来越少,所以我们可以动态的减少 ε,来获得更好的效果。

上限置信区间(UCB1)

由于我们通过过往拉拉杆的结果来估计一个拉杆的收益,因此一个拉杆被拉的次数越多,则其收益估计越准确,因此我们希望在 explore 时尽量选择那些尝试次数较少的拉杆。而 ε-Greedy 算法在 explore 时是随机的,因此我们引入另一种算法——上限置信区间(Upper Confidence Bound)。根据 Chernoff-Hoeffding Bound 理论,真实的期望与预估期望的差距是随着实验次数呈指数级下降的,因此可以引入 UCB 公式:

\[ X_i=\overline X_i+\lambda \sqrt{\frac{ln(N)}{N_i}} \]

其中,\(\overline X_i\) 代表预估收益,\(\lambda\) 是可调整的参数,\(N\) 是总实验次数,\(N_i\) 是该拉杆尝试的次数。\(\lambda\) 越大则越倾向于 explore,\(\lambda\) 越小则越倾向于 exploit。所谓“置信区间”,即根据预估收益和实验次数猜测真实期望有很大概率落在其中的一个区间,在此处即为 \(\left(\overline X_i-\lambda \sqrt{\frac{ln(N)}{N_i}}, \overline X_i+\lambda \sqrt{\frac{ln(N)}{N_i}}\right)\)\(X_i\) 即为置信区间的上界。

每次拉拉杆前,计算每个拉杆的置信区间上界,选择那个上界最大的拉杆。在此算法中 explore 与 exploit 被结合在了一起。上限置信区间也是蒙特卡洛树搜索中最常用的方法。

比较

在一般的多臂老虎机问题中,如果选取合适的 ε,ε-Greedy 算法是很难被打败的。然而,在蒙特卡洛树搜索中,每一个节点所面对的多臂老虎机问题都是不同的,很难找到一个统一的参数使得它在面对这些不同多臂老虎机问题时都能有比较好的效果。而 UCB1 算法的优点是它比较稳定,在面对各类问题时都能取得比较好的效果,所以 UCB1 算法更适合在蒙特卡洛树搜索中使用。

结论

在这篇文章,我们介绍了蒙特卡洛树搜索和两种多臂老虎机算法,并对它们进行了分析与比较。蒙特卡洛树搜索能够比较简单的实现并且容易的取得比较好的结果,并且仍有很大的可扩展空间。比如 AlphaGo 便与神经网络相结合,训练了一个局面估价网络与快速走子网络,两者相结合最终击败了围棋世界冠军。同时,如何改进多臂老虎机算法使得它更快的找到更优的走法也是未来值得探索的一个问题。

参考文献

[1] Kocsis L , Csaba Szepesvári. Bandit Based Monte-Carlo Planning[J]. Lecture Notes in Computer Science, 2006, 4212:282-293.

[2] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite time analysis of the multi-armed bandit problem. Machine Learning, 47(2-3):235–256, 2002.