详解强化学习多智能体博弈算法——蒙特卡洛树搜索

👆点击“博文视点Broadview”，获取更多书讯

强化学习，除了可以用于单个强化学习智能体和环境的相互作用，也可以用于两个或者多个智能体在某个强化学习环境下的博弈。

关于这种类型的算法，最有名的应该是蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）。

随着AlphaGo和AlphaZero算法在围棋、国际象棋和将棋等棋类领域的广泛应用，并且在这些领域内均取得了相比传统的Alpha-Beta 剪枝算法更加优异的性能，蒙特卡洛树搜索算法作为这些智能体使用的算法也被越来越多的人研究。

该算法曾被应用于《指环王》卡牌游戏中，它可以在游戏难度越高的情况下表现得越厉害！

本文会讨论使用蒙特卡洛树搜索算法的基本原理，并且使用这个算法来实现一个简单的五子棋对弈的强化学习算法。

1

算法原理

对于大多数的棋类游戏，我们可以把游戏过程抽象成在一个博弈树（Game Tree）上进行决策的过程。

其中，游戏树的每个结点相当于棋盘的一个状态，而游戏树的每条边相当于某一个玩家（智能体）做出某一个决策。游戏玩家的对弈过程就相当于在这个博弈树上进行决策，决策目标是使自己得到的回报尽可能大，对方的回报尽可能小。

为了实现这个目标，算法就需要从决策的当前结点出发，穷举（或者启发式的搜索）所有可能的动作，并且得到这些动作的奖励的估计，而且尽可能采取奖励比较大的动作。

这种思想在Alpha-Beta 剪枝算法中得到了很好的体现，而且在一些相对比较复杂的棋类游戏（比如国际象棋）中取得了较好的效果。

著名的深蓝（Deep Blue）计算机上运行的算法就是基于Alpha-Beta剪枝算法，这个算法在有充分的硬件资源的情况下能够做相对比较深的博弈树搜索，而且早在1997年的时候，当时的硬件水平加上Alpha-Beta剪枝算法就能击败当时的世界冠军。

基于博弈树的启发式搜索算法虽然在搜索空间相对较小的棋类游戏中取得了很大成功，但是对于搜索空间很大的棋类游戏，比如围棋，局限于当前的硬件资源，搜索深度并不能达到击败人类的程度。

为了能够在这类项目中达到人类专业选手的水平，基于深度学习的蒙特卡洛树搜索方法被开发出来，主要目的是利用深度学习的模型拟合能力，学习到对弈局面的价值函数和对弈的策略，并且利用深度学习模型在博弈树上进行决策，从而能够达到最大限度利用计算资源，有效搜索当前局面的最优动作的目的。

下面介绍一下基于深度学习模型的蒙特卡洛树搜索算法。

从算法的基本原理上看，AlphaGo算法和AlphaGoZero/AlphaZero算法有一定的区别，其主要表现在是否使用人工收集的数据进行模型训练。

为了简便起见，这里叙述的是AlphaGoZero和AlphaZero使用的蒙特卡洛树搜索算法。这两个算法使用的都是自我对弈的方法进行训练，即使用一个模型来获取当前状态的价值估计和动作的概率估计。

2

算法的基本步骤

一个蒙特卡洛树搜索算法的示意图如下图所示。

其中，博弈树的每个结点代表当前棋局所处的状态，包含当前状态的价值估计、当前结点被选择的先验概率、当前结点被选择的次数、当前结点的父结点（Parent）和当前结点的子结点（Children）。

跟一般的树一样，我们可以定义树的根结点（Root）和叶结点（Leaf），根结点定义为搜索开始的结点，叶结点定义为没有子结点的结点。

从图中可以看出，蒙特卡洛树搜索算法主要可以分四步：

• 选择（Select）
• 扩展和求值（Expand and Evaluate）
• 回溯（Backup）
• 最后的决策（Play）

下面逐一介绍这些步骤的意义和具体的算法细节。

第一步：选择（Select），如上图的红色粗箭头所示，这一步的目标是找到没有被搜索过的叶结点，具体选择的规则由多项式上置信树算法（Polynomial Upper Confidence Tree，PUCT）决定，这个算法具体会根据式（1）给每个子结点计算一个分数，我们会不断选择分数最高的结点，直到到达一个叶结点。

这个分数的意义为：加入父结点的状态为 

，经过父结点的动作

 ，到达一个子结点，那么这个子结点的分数由这个子结点的价值函数 

、这个子结点的先验概率

 、这个子结点被采样到的个数 

和父结点的所有采样个数的和的平方根 

共同决定，式（1）中，

 是一个常数，控制了智能体的探索和利用之间的平衡。

    式（1）

我们知道，一个结点的价值函数代表了这个结点未来有可能收到的奖励的值，所以式（1）的第一项代表某个结点的价值，这个价值越大，表示探索这个结点越有可能获取大的奖励；第二项如果不考虑先验概率（这个概率由深度学习网络产生），那么这个值就和子结点被采样到的次数成反比，如果一个结点很少被采样到，那么第二项的访问次数的比值就会很大，从而就会增加 

的值，让这个结点更容易被采样到。

因此，

 的第一项和第二项分别代表智能体的利用和探索的部分，而 

系数控制了这两个部分之间的平衡，我们可以根据具体的问题来调节这个值的大小，让蒙特卡洛树搜索偏向于探索更好的结点或者探索尽可能多的结点。

第二步：扩展和求值（Expand and Evaluate）。在不断迭代选择了一个叶结点之后，需要考虑的问题是查看叶结点是否可以展开并添加子结点。

因为叶结点代表的是当前博弈（也就是棋盘）的一个状态，这个状态下所有可行的步骤都是由强化学习环境决定的。

也就是说，如果当前叶结点不是最终结点，那么可以根据当前的强化学习环境（棋盘状态）获取当前玩家所有可能的动作状态，并且根据这些状态建立子结点。

在子结点的建立过程中，我们需要考虑一个函数 

，其中

 是棋盘当前状态的特征，

 是当前局势的价值函数， 

对应的是在状态

 情况下，采取动作 

的先验概率。

这样，根据先验概率的值就能新建叶结点用于接下来的搜索。在AlphaGoZero和AlphaZero算法中，  函数

由一个深度学习模型决定，这个模型的输入是棋盘状态的特征对应的张量，输出当前局势的价值 

和所有子结点的先验概率 

。

蒙特卡洛树搜索算法的目的之一就是训练这个深度学习模型，让模型能够根据当前的棋盘状态准确地估计价值和先验概率。

第三步：回溯（Backup）。在扩展了叶结点之后，需要考虑的一步是回溯（Backup）。

因为在刚才的路径中我们从根结点出发得到了一条路径，路径的叶结点更新以后，需要考虑叶结点的扩展对于父结点的影响，这里就要从叶结点出发，反向回溯对应的决策路径，更新对应的价值函数。这里的价值函数使用的是所有到达过的叶结点的价值的平均值，如式（2）所示。

   式（2）

假如最终到达的叶子结点的价值函数的值是 

，如果叶子结点不是最终结点，那么这个值由前面提到的函数 

估计得到，如果叶子结点是最终结点，那么这个值由最后的胜负状态决定，如果是平局，则这个值为0

；如果获胜一方是当前结点的玩家，则这个值为+1

，反之则为-1

。在更新价值函数的同时，我们也需要更新回溯路径上每个结点的访问次数 

，让这个值加一。

第四步：决策（Play）。在蒙特卡洛树搜索算法中，“选择→扩展和求值→回溯”这个过程要重复执行多次，直到到达一个指定的次数。

在这种情况下，我们相当于积累了很多对弈的数据，同时获取了根结点所有可能的子结点的访问次数

，这个访问次数代表不同结点的重要性。

一般来说，访问次数越高，代表当前结点的价值越高，越应该被选择。

根据这个原理，我们就可以估算出根结点的所有子结点的概率 

，这个概率的计算方法如式（3）所示，其中

 是温度系数，对应的访问次数越高，则代表结点的价值越高，越容易被选择。而温度系数越高，则意味着访问次数多的结点和访问次数少的结点的概率差距越大。当温度趋向于零的时候，访问次数最高的结点概率趋向于1

，其他结点的概率趋向于0

。有了这个概率的值，蒙特卡洛树搜索算法就可以根据这个值进行采样，把当前的根结点推进到下一个子结点，这就是决策的过程，在决策后可以继续进行“选择→扩展和求值→回溯”这个循环。

为了增加算法的随机性，AlphaGoZero和AlphaZero的原始文献中给这个概率增加了一个服从狄利克雷分布的噪声

，如式（4）所示，其中

 、

 是可以调节的超参数。

   式（3）

   式（4）

总结一下，蒙特卡洛树搜索算法包含了一系列的决策过程，每个决策过程都会包含多个“选择→扩展和求值→回溯”循环，并且在循环结束的时候计算选择对应的动作概率进行决策，随机采样让根结点向前移动。

在决策到达终点，也就是得到对弈的结果之后，整条决策路径会被保存下来，同时，根据最后博弈的结果会给每个结点赋予一个具体的价值  

，根据结点当前的决策玩家是不是最后的赢家来决定（如果是，则

 ，若不是，则 

，平局

 ）。

结合模型输出的概率

 、价值 

和蒙特卡洛树搜索算法得到的概率

 ，以及模型的参数

 ，我们可以得到最后的损失函数，如式（5）所示。

   式（5）

其中损失函数由三部分组成，第一部分是价值函数的MSE损失函数，目的是为了让模型对于局势的估计尽可能和最后的结果相符；第二部分是交叉熵损失函数，目的是为了模型对概率分布的估计尽可能和蒙特卡洛树搜索算法得到的概率 

相符；第三部分的目的是为了防止模型的过拟合，

 是防止过拟合的常数。通过对公式中描述的损失函数的优化，我们就能得到一个合理的深度学习模型，用这个模型可以帮助我们在博弈树上进行决策。

3

算法使用的模型

下面介绍如何使用PyTorch来实现一个用于五子棋的蒙特卡洛树搜索算法。

为了能够执行蒙特卡洛树搜索算法，首先需要一个五子棋的强化学习环境。这里使用的是Gym Gomoku，读者可以使用pip install gym-gomoku命令进行安装。

因为五子棋的强化学习环境比较简单，有兴趣的读者也可以尝试自己实现一个五子棋的强化学习环境，可以参考前面介绍的“井字棋”的代码，将其扩展到更大的棋盘和更多的连续棋子。

由于蒙特卡洛树搜索算法会用到自我对弈的方法，这个强化学习环境的使用方法和一般的OpenAI Gym强化学习环境有所不同。我们会在用到Gym Gomoku强化学习环境时介绍具体的使用方法。

首先，会构造一个深度学习模型来预测当前状态对应的动作概率分布和价值函数。

在Gym Gomoku的棋盘中，第一个选手所有的落子代表的数字为1

，第二个选手所有的落子代表的数字为2

。根据这个棋盘可以构造对应深度学习模型的输入特征。输入的特征是一个

 的张量，其中 

和

 分别为棋盘的高度和宽度（对于五子棋 

）。

这个张量的第一个维度由四部分组成，第一部分是第一个选手的落子位置（落子为1，不落子为0，下同），第二部分是第二个选手的落子位置，第三部分是最后一步的落子位置，最后一个部分代表最后落子的选手，如果是第一个选手，就是一个矩阵，其元素为全零，否则这个矩阵的元素就全为一。

根据输入特征的大小，我们可以构造对应的深度学习模型，如以下代码所示。

class PolicyValueNet(nn.Module):    def __init__(self, board_size):        super().__init__()

        # 特征提取网络        self.featnet = nn.Sequential(            nn.Conv2d(4, 32, 3, 1, 1),            nn.ReLU(),            nn.Conv2d(32, 64, 3, 1, 1),            nn.ReLU(),            nn.Conv2d(64, 128, 3, 1, 1),            nn.ReLU(),        )

        # 策略网络        self.pnet = nn.Sequential(            nn.Conv2d(128, 4, 1),            nn.ReLU(),            nn.Flatten(),            nn.Linear(4*board_size*board_size, board_size*board_size)        )

        # 价值网络        self.vnet = nn.Sequential(            nn.Conv2d(128, 2, 1),            nn.ReLU(),            nn.Flatten(),            nn.Linear(2*board_size*board_size, 64),            nn.ReLU(),            nn.Linear(64, 1)        )

    def forward(self, x):        feat = self.featnet(x)        prob = self.pnet(feat).softmax(-1)        val = self.vnet(feat).tanh()        return prob, val

    def evaluate(self, x):        with torch.no_grad():            prob, val = self(x)            return prob.squeeze(), val.squeeze()

在代码中，特征提取网络是一个三层的深度卷积网络，策略网络是一个双层的网络，价值网络是一个三层的网络。

其中策略网络的输出与棋盘所有的落点数目相同，也就是 

，价值网络的输出是一个数值。为了能够让策略网络输出正确的概率，我们会使用Softmax函数对输出进行归一化处理。

另外，因为价值网络的输出取值范围为 

，价值网络的输出最后会经过Tanh激活函数。除了前向计算的forward方法（这个方法用于模型的训练），另外有一个evaluate方法，这个方法用来在蒙特卡洛树搜索算法的时候预测对应结点的价值和动作的概率，因为不需要进行梯度反向传播，在evaluate方法中关闭了梯度的计算。

4

算法的博弈树表示

为了能够进行蒙特卡洛树搜索，我们需要定义博弈树的结点。这个结点需要具有以下特征：能够存储价值函数

 ，能够记录结点被访问的次数

 ，以及对应的先验概率

 。这部分代码如下所示。

class TreeNode(object):    def __init__(self, parent, prior):        self.parent = parent # 父结点        self.prior = prior # 先验概率

        self.Q = 0 # 价值函数        self.N = 0 # 访问次数        self.children = {}

    def score(self, c_puct):        # PUCT分数        sqrt_sum = np.sqrt(np.sum([node.N for node in      self.parent.children.values()]))        return self.Q + c_puct*self.prior*sqrt_sum/(1 + self.N)

    def update(self, qval):        # 更新结点信息        self.Q = self.Q*self.N + qval        self.N += 1        self.Q = self.Q/self.N

    def backup(self, qval):        # 回溯        self.update(qval)        if self.parent:            self.parent.backup(-qval)

    def select(self, c_puct):        # 选择        return max(self.children.items(), key=lambda x: x[1].score(c_puct))

    def expand(self, actions, priors):        # 扩展和模拟        for action, prior in zip(actions, priors):            if action not in self.children:                self.children[action] = TreeNode(self, prior)

    @property    def is_root(self):        # 判断是否是根结点        return self.parent is None

    @property    def is_leaf(self):        # 判断是否是叶结点        return len(self.children) == 0

可以看到，我们定义了一个TreeNode类来描述对应的博弈树的结点，除了价值函数等计算中需要用到的信息，还定义了父结点的信息和子结点的信息，其中父结点是一个TreeNode的实例，子结点的信息是一个字典，字典的键是执行的动作，值是动作对应的结点。

有了这些信息之后，我们就可以计算前面介绍的PUCT分数，这个分数的值由式（1）决定，通过score方法计算得到。

在得到PUCT分数之后，算法就可以根据这个分数来选择分数最高的子结点，对应的方法是select。

除了select方法，TreeNode类还定义了expand方法，这个方法输入所有的动作actions和动作对应的先验概率priors，根据这些值来对叶子结点进行扩展，另外还有backup方法，这个方法获得当前结点的价值估计，并且递归地对到达这个结点的路径上的其他结点进行访问次数和价值函数的更新。

为了判断结点的性质，我们还需要有两个方法is_root和is_leaf，分别代表当前的结点是否是根结点和是否是叶子结点。

5

算法的搜索执行过程

在定义完博弈树结点后，我们需要考虑的是如何从博弈树出发执行蒙特卡洛树搜索算法，具体可以参考以下代码。

class MCTSBot(object):    def __init__(self, board_size, c_puct=5.0, nsearch=2000):

        self.board_size = board_size        self.root = TreeNode(None, 1.0)        self.c_puct = c_puct        self.nsearch = nsearch

    def mcts_search(self, state, pvnet):        # 执行蒙特卡洛树搜索        node = self.root

        # 选择        while not node.is_leaf:            action, node = node.select(self.c_puct)            state = state.act(action)

        # 扩展和求值        feature = self.get_feature(state.board, state.color)        feature = torch.tensor(feature).unsqueeze(0)        probs, val = pvnet.evaluate(feature)        actions = state.board.get_legal_action()        probs = probs[actions]

        if state.board.is_terminal():            _, win_color = \                gomoku_util.check_five_in_row(state.board.board_state)            if win_color == 'empty':                val = 0.0            elif win_color == state.color:                val = 1.0            else:                val = -1.0        else:            node.expand(actions, probs)

        # 备份                node.backup(-val)

    def alpha(self, state, pvnet, temperature=1e-3):        # 计算所有子结点的概率        for _ in range(self.nsearch):            self.mcts_search(state, pvnet)

        node_info = [(action, node.N)for action, node in self.root.children.items()]        actions, nvisits = zip(*node_info)        actions = np.array(actions)        probs = np.log(np.array(nvisits)+1e-6)/temperature        probs = softmax(probs)        return actions, probs

    def reset(self):        self.root = TreeNode(None, 1.0)

    def step(self, action):        self.root = self.root.children[action]        self.root.parent= None

整个算法的主体定义在mcsts_search方法中，根据这个方法，我们从根结点出发，不断进行选择，直到到达叶结点，同时使用模型pvnet获取叶结点所在状态的价值和所有可能的子结点的先验概率。

在获取对应的价值后，根据价值进行反向传播，更新对应决策路径上的所有结点，即可完成一次蒙特卡洛搜索。

在完成多次蒙特卡洛搜索之后，我们可以计算根结点的所有子结点的概率，这个概率具体的计算在式（3）中介绍过了。具体计算对应概率的代码在alpha方法中。

需要注意的一点是，在这个方法中并没有直接使用式（1），而是先对所有的访问次数进行对数计算，除以温度的值，然后计算Softmax的归一化概率。

之所以要这么做，是因为当访问次数太多，而温度太小的时候，直接使用式（1）计算概率会导致浮点数溢出，使用Softmax能够有效地避免对应情况的发生。在获取每个子结点（动作）的概率之后，我们可以根据概率采样获取单步的动作，不断进行决策，直到到达最终状态，对应执行决策的方法是step方法。

以上就是蒙特卡洛树搜索算法的整体代码，由于篇幅所限，这里不再详细介绍对应的数据采样和模型训练代码，这部分代码和前面介绍的其他强化学习算法构造损失函数，反向传播并且训练模型的代码类似。有兴趣的读者可以阅读代码ex_6_5.py查看对应的算法实现细节。

本文节选自《深度强化学习算法与实践：基于PyTorch的实现》一书，想要了解更多相关内容，欢迎阅读本书！

▊ 《深度强化学习算法与实践：基于PyTorch的实现》

张校捷 著

• 一本书读懂各种强化学习环境及其使用方法

本书从强化学习的基础知识出发，结合PyTorch深度学习框架，介绍深度强化学习算法各种模型的相关算法原理和基于PyTorch的代码实现。作为一本介绍深度强化学习知识的相关图书，本书介绍了常用的强化学习环境，基于价值网络的强化学习算法和基于策略梯度的强化学习算法，以及一些常用的比较流行的深度强化学习算法（如蒙特卡洛树搜索）等。另外，还介绍了深度强化学习算法在实际问题中的一些应用。

限时五折优惠，扫码即购！

如果喜欢本文欢迎 在看丨留言丨分享至朋友圈 三连
 热文推荐  
想做好分布式架构？这个知识点一定要理解透！
书单 | 突破技术瓶颈，从码农到工匠，一定要看看这几本书！
你的“数学潜意识”原来可以被唤醒！
负载均衡，你想了解的全在这里！

▼点击阅读原文，了解本书详情~