蒙特卡洛树搜索简介
Kotori Y 22 Posts
 2021-11-14 02:31 2021-11-15 12:23      

蒙特卡洛树搜索（Monte Carlo tree search, MCTS）是一种用于某些决策过程的启发式搜索算法，尤其是在棋类对决游戏中得到广泛的应用

0. 前言

早在1997年IBM的深蓝(Deep Blue)凭借暴力枚举战胜当时的国际象棋世界冠军卡斯巴罗夫，尽显暴力美学。之后，计算机在各种棋类运动中横扫人类冠军，除了围棋。因为围棋的搜索空间实在是太大了，大约为（19X19的棋盘，忽略吃子），就算是现在最强的超级计算机也无法穷举出全部的空间，因此需要一个优化的搜索算法来解决这个问题。终于，在2016年3 月，由Deepmind研发的 ALphaGo 4-1 击败了李世乭，并且在一年后 AlphaGo Zero又以100-0 击败了它的前辈。其中使用的搜索算法就是蒙特卡洛树搜索。本文章将以井字棋为例讲解MCTS。

蒙特卡洛并不是哪个数学家而是一个赌场

1. 树

1.1 定义

在介绍MCTS之前，先简单解释一下什么是“树”。在计算机科学中，树（英语：tree）是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

  • 每个节点都只有有限个子节点或无子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；
  • 树里面没有环路(cycle)

1.2 树的术语

  1. 节点的度：一个节点含有的子树的个数称为该节点的度；
  2. 树的度：一棵树中，最大的节点度称为树的度；
  3. 叶节点或终端节点：度为零的节点；
  4. 非终端节点或分支节点：度不为零的节点；
  5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
  7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  9. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
  10. 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
  11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
  12. 节点的祖先：从根到该节点所经分支上的所有节点；
  13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  14. 森林：由m（m>=0）棵互不相交的树的集合称为森林；

2. 蒙特卡洛树搜索

2.1 节点的属性

对于井字棋游戏，可以表示为下图。对于每一步的棋局可以看成是上一步的子节点，即一个节点表示一个游戏状态，这些子节点又有子节点，所有的井字棋游戏状态都可以被这样表示，于是它们就构成了一个树。对于围棋或者其他更复杂的棋类也是一样，只不过这个树会更大、更复杂。蒙特卡洛树搜索就是要在这样一个树中搜索出下一步在哪个位置下棋最有可能获胜，即根节点的哪个子节点获胜概率最高。

在蒙特卡洛树搜索中，我们将节点记作 𝑣v，在搜索过程中需要记录节点的访问次数和累计奖励，它们的表示符号如下：

  1. ：节点 的访问次数，节点在搜索过程中被访问多少次，该值就是多少。
  2. ：节点 的累计奖励，即节点在反向传播过程中获得的所有奖励(reward)求和。

所谓的奖励(reward)是一个数值，游戏结束时若获胜，奖励为 1，若失败，奖励为 0。

2.2 搜索过程

MCTS其主要分为四步：选择(Selection)，拓展(Expansion)，模拟(Simulation)，反向传播(Backpropagation). 将MTCS看成一个黑箱的话，那么这么黑箱的输入就是上一步的棋局，通过重复执行上面的四步，来得到输出——下一步的应该下在哪里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MCTS:
    def __init__(self):
        ...
        
    def select(self):
        ...

    def expand(self):
        ...
        
    def simulate(self):
        ...

    def backpropogate(self):
        ...

2.2.1 选择与扩展

对于棋类游戏，首先需要解决的问题是对给定的父节点，应该访问哪个子节点用于下一个子节点用于评估，这就是MCTS中的选择阶段。在MCTS中，首先从一个非叶节点(就是输入)出发，根据一定的策略，向下选择一个节点进行访问，若被选择的节点未被访问过，则执行扩展；若被选择的节点已被访问，则访问该节点，并继续向下选择节点进行访问，直到遇见未被访问的节点，或遇见终止节点(游戏结束)。所谓访问，就是把选择步骤中遇到的未访问节点添加到树中，然后对该节点执行模拟。

选择的策略由该公式确定，对当前节点的每个子节点计算如下公式，并选择计算结果最大的节点。

其中，表示父节点，表示子节点，是一个常数。 越大，就越偏向于探索；越小，就越偏向于利用。具体的任务中，该公式可以进行适当的调整。

从上面公式可以看出，一个子节点若从来没有被选中，那它的评估值就是。那么，选择-扩展就可以看成：

  1. 若一个父节点有未被选择的子节点，则访问这个子节点，对他进行后续的模拟以及反向传播；
  2. 如果所有子节点都被访问，则用上面的公式计算出选择哪个子节点，并枚举这个子节点的所有子节点，重复过程1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def _select_policy(self, node: TreeNode, explorationValue):  # 选择node的子节点的策略
    best_score = float("-inf")
    best_nodes = []

    for child in node.children.values():
        score = node.state.getCurrentPlayer() * child.total_reward / child.n_visited + \
                explorationValue * math.sqrt(2 * math.log(node.n_visited) / child.n_visited)

        if score > best_score:
            best_score = score
            best_nodes = [child]

        elif score == best_score:
            best_nodes.append(child)

    return random.choice(best_nodes)

def select(self, node: TreeNode):
    while not node.isTerminal:  # 判断是否结束
        if not node.isFullyExpanded:  # 判断node是否还有子节点
            return self.expand(node)  # 没有则向下扩展
        node = self._select_policy(node, self.explorationConstant)  

    return node
  
def expand(self, node: TreeNode):  # 扩展一个子节点
    actions = node.state.getPossibleActions()
    for action in actions:
        if action not in node.children:
            newNode = TreeNode(node.state.takeAction(action), node)
            node.children[action] = newNode
            if len(actions) == len(node.children):
                node.isFullyExpanded = True
            return newNode

2.2.2 模拟与反向传播

对于上上述两步中获得的节点，使用某种策略进行模型，得到一个奖励值（一般越大越好）。接下来就是最重要的一步，使用该子节点的的奖励值，更新路径上所有父节点的访问次数与累计奖励。

我们在回头看一下选择策略的公式

可以看到，式中第一项其实就是该节点在前面的过程中获得的平均奖励，自然第一项的值越大，在现有的知识下，选择该节点更有可能获胜。式中第二项，当该节点访问次数占父节点次数的比例越小时，该值越大，表示该节点访问次数很少，可以多进行尝试，获取新的知识，它们也可能获得更丰厚的回报。于是就是控制这两者重要程度的参数。

1
2
3
4
5
6
7
8
9
@abstractmethod
def rollout(self, state):  # 根据需求自行编辑
    return float

def backpropogate(self, node, reward):
    while node is not None:
        node.n_visited += 1
        node.total_reward += reward
        node = node.parent

2.2.3 搜索结束

MCTS 的整个过程就是这样，那么什么时候结束呢？一般设置以下两个终止条件。

  1. 设置最大根节点搜索次数，达到该次数后结束搜索。
  2. 设置最大搜索时间，超过时间后结束搜索。

最后将输入节点的平均奖励最大的子节点输出，作为输出。并作为下一次的输入。

2.2.4 流程图

在线测试

基于JS和MCTS实现的井字棋AI：链接；源码

参考资料

  1. 蒙特卡洛树搜索-wikipedia
  2. 树 (数据结构)-wikipedia
  3. 蒙特卡洛树搜索 MCTS 入门-iqhy’s Blog
  • Post title：蒙特卡洛树搜索简介
  • Post author：Kotori Y
  • Create time：2021-11-14 02:31
  • Update time：2021-11-15 12:23
  • Post link：https://blog.iamkotori.com/2021/11/14/蒙特卡洛树搜简介及应用/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments