蒙特卡洛树搜索在围棋中的应用

  对于围棋这种指数级搜索空间中，使用蒙特卡洛树搜索MCTS能够将有限的算力集中到最有希望的子树上。

MCTS核心思想

graph LR
    A(选择\n selection) --> B(扩展\n expansion)
    B --> C(模拟\n simulation)
    C --> D(回溯\n backpropagation)
    D --> |重复多次| A

选择

  从根节点开始，根据UCB公式计算得到最大值的子节点。然后选择那个节点，不断向下搜索，知道到达底部的叶节点并等待下一步操作。

$$
UCB(child) = \overline{V_i} + c \cdot P \cdot \sqrt{\frac{\ln{N_{parent}}}{N_{child}}}

$$

• $\overline{V_i}$：子节点的平均价值，比如围棋中的胜率
• $P$：策略网络的先验概率
• $N_{parent}$：父节点已经被访问的总次数
• $N_{child}$: 子节点被访问的次数

  前一项代表这个分支的已知表现，后一项代表未来存在的可能。

扩展

  到达叶节点后，如果还没有到达终止状态。那么就需要对这个节点进行扩展，根据策略扩展出一个或多个节点，然后顺着这个新节点进入下一个状态。

模拟

  基于目前状态，用某种策略进行模拟，例如贪心策略，直到游戏结束产生结果。

回溯

  根据模拟出来的结果，从叶节点开始反向传播，更新所有节点的信息。

流程图

graph TD
    A(开始) --> B(进入当前节点)
    B --> C{当前节点是叶节点吗}
    C --> |NO|D(当前节点选择为子节点中UCB值最大的)
    C --> |YES|E{这个节点未被访问过？}
    D --> C
    E --> |YES|F(进行推演)
    E --> |NO|G(将当前节点下所有可能的新状态加入树中)
    G --> H(当前节点变成第一个子节点)
    H --> I(推演)

以AlphaGo Zero为例的应用

  在AlphaGo Zero中，使用价值网络直接评估叶节点来代替随机推演。这相较于传统的MCTS速度更快，使用神经网络对局面打分也能够体现对于局面的理解程度。但是其难点也就随之体现——如何找到一个有效的价值判断网络。

  假设在有一个足够强大的价值网络的情况下，模拟一次走棋的完整过程。

search_move(steps, board, color, curstep)
  └─ MCTS.search()
        for i in range(100):
            ① node, path = 选择()      # UCB 到叶节点
            ② _expand(node)            # 策略网络展开子节点
            ③ value = _evaluate(node)  # 立即评估这 1 个叶节点（1 次查询）
            ④ 回溯(path, value)        # 立即更新路径
        return _select_best()

  对于这个还可以再优化一下，利用GPU强并行的特性，将价值判断的过程优化为批量判断，这样可以进一步减少算法时间。

search_move(steps, board, color, curstep)
  └─ MCTS.search()
       for i in range(mcts_simulations):
           ① _select_leaf()    # UCB 到叶节点 + 虚拟访问
           ② _expand()         # 策略网络先验 → 子节点
           ③ 积累 pending 叶节点
           ④ 批量评估（积累够 batch 或最后一轮）:
                _evaluate_batch()   # get_value_batch / 价值网络批量
                → _backprop()       # 更新路径
           ⑤ 可视化快照 + 步进（可选）
       _select_best()  # 访问次数最多 → 落子