蒙特卡洛树搜索¶
蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）是一种用于决策和优化问题的启发式搜索算法，特别适用于那些状态空间巨大且难以穷尽的复杂问题。
基本原理¶
蒙特卡洛树搜索通过模拟对弈来决定下一步的决策动作，但不是模拟所有动作，而是选择胜率较高的节点进行模拟，并且向后多模拟几步，最后找到最佳的决策动作。也就是说，蒙特卡洛树搜索建立了一个决策树，由胜率较高的节点组成。
蒙特卡洛树搜索的实现一般包括如下四步：
- 选择（Selection）：从根节点开始，根据一定的策略（比如 UCT 策略），向下选择子节点，直至找到叶子节点。
- 扩展（Expansion）：对叶子节点进行扩展，生成新的子节点。例如通过神经网络生成多个可能的动作。
- 模拟（Simulation）：对扩展生成的子节点进行模拟对弈，得到该节点的胜负结果。可以采用随机模拟，也可以使用神经网络模型进行快速评估。
- 反向传播（Backpropagation）：将模拟得到的胜负结果反向传播回所有经过的节点，更新模拟对弈次数、胜负次数等信息。
示例¶
假设下图中的节点代表一个棋盘状态，根节点的决策已经进行到了左一的情况，现在要决定下一步的动作。
- 选择：从根节点出发，由于子节点都已经模拟过，基于 UCT 计算各个节点的分数，选择最大的
7/10节点。继续向下选择直至3/3叶子节点。 - 扩展：因为
3/3没有子节点，所以在其下添加新的子节点。假设输入策略神经网络后输出了多个较好的动作，0/0节点为其中之一。 - 模拟：从
0/0节点开始，采用随机落子或者神经网络模型快速落子策略，进行模拟对弈，并得到最终的结果为0/1。 - 反向传播：将该结果反向传播回从
3/3到根节点经过的节点，更新模拟对弈次数、胜负次数等信息。
至此，一轮迭代结束。
UCT¶
UCT 算法（Upper Confidence Bound for Trees），即上限置信区间算法，在决策时，平衡了探索（exploration）和利用（exploitation）：
\[\frac{w_i}{n_i} + C \sqrt{\frac{\ln N_i}{n_i}}\]
其中，\(w_i\) 为节点当前的胜利次数，\(n_i\) 为节点当前的模拟次数，\(N_i\) 为父节点当前总的模拟次数，\(C\) 为探索参数，通常取 \(\sqrt{2}\)。