蒙特卡洛树搜索 MCTS：博弈与规划的经典算法

UCT(i) = (W_i / N_i) + C * sqrt( ln(N_n) / N_i )

- `W_i`：节点 i 的获胜次数（模拟胜场）。
- `N_i`：节点 i 的访问次数。
- `N_n`：父节点 n 的访问次数。
- `C`：勘探参数（常数，通常取 √2 左右）。

公式的第一部分 `W_i / N_i` 是胜率，代表对该节点的“利用”。第二部分是置信区间，访问次数越少的节点该值越大，从而鼓励“勘探”。通过调节 `C` 可以改变探索的激进程度。

在选择时，从根节点开始，每步都选择 UCT 值最大的子节点，直至到达一个存在未扩展动作的节点（或终端节点）。

### 扩展：增加一个新叶子

当选择到达一个节点时，如果它不是游戏的结束状态，并且还有未被尝试过的合法动作，我们就从该节点扩展出一个新的子节点。通常每次只扩展一个节点，将这个新节点加入树中。

常见的做法是随机从未尝试的动作中选取一个，创建对应的状态节点。这样树就“长大”了一点。

### 模拟：快速评估局面

从新扩展的节点出发，采用一种默认策略（Rollout Policy）快速走完整个游戏，得到一个最终结果。默认策略通常非常简单，比如完全随机走子，或者在特定游戏中加入一些简单的启发式规则，以兼顾速度与合理性。

模拟过程不生成新的树节点，仅利用原有的游戏规则快速推进，所以也称为“走子策略”或“Rollout”。模拟结束后返回结果：胜利（+1）、失败（0）或平局（+0.5）。

### 回溯：更新信任度

得到模拟结果后，从新节点开始，沿着其祖先节点向上追溯直到根节点。每经过一个节点，将其访问次数 `N` 加 1，并将其获胜次数 `W` 根据结果累加（通常从当前玩家视角考虑胜负，需要对胜负进行适当映射，以保持统计的对称性）。

例如，如果当前节点代表玩家 A 的局面，而模拟结果是玩家 A 获胜，则该节点的胜场 +1；若失败则不加；若平局则加 0.5。这样回溯后，每个节点的统计值能正确反映从该节点出发的对局优势。

## MCTS 的完整流程伪代码

下面是一个简洁的伪代码，帮助理解算法整体循环：

function MCTS(root_state): 创建根节点 Root，状态 = root_state while 计算资源未耗尽: node = Root state = clone(root_state)

    // 选择
    while node 已完全展开 且 非终端:
        node = 选择 UCT 最高的子节点
        state = 执行该子节点对应的动作

    // 扩展
    if state 不是终局:
        从未尝试的动作中选一个 action
        state = state.apply(action)
        node = node.add_child(action, state)

    // 模拟
    sim_state = clone(state)
    while sim_state 非终局:
        sim_state = 执行默认策略动作
    reward = 从 node 的玩家视角评估 sim_state 的结果

    // 回溯
    while node 不为空:
        node.visits += 1
        node.wins += reward
        根据视角转换 reward 给上一级玩家
        node = node.parent

return 选择 Root 下访问次数最多的动作