一、目标

一种启发式的搜索算法，在搜索空间巨大的场景下比较有效

算法完成后得到一棵树，这棵树可以实现：给定一个游戏状态，直接选择**的下一步

二、算法四阶段

1、选择（Selection）

父节点选择UCB值最大的子节点作为当前节点
UCB=Vi‾+c2lnNniUCB=\overline{V_{i}} +c\sqrt{\frac{2lnN}{n_{i}}} UCB=Vi​​+cni​2lnN​​
其中，c通常取2。

nin_{i}ni​代表 iii 节点被选择的次数，NNN代表其父节点被选择的次数。

Vi‾\overline{V_{i}}Vi​​ 代表 iii 节点的平均价值大小（例如 iii 节点 Vi=v,ni=3V_{i}=v,n_{i}=3Vi​=v,ni​=3，则Vi‾=v/3\overline{V_{i}}=v/3Vi​​=v/3）。

2、扩展（Expansion）

为当前节点创建一个或多个子节点（子节点代表当前节点下可采取的动作）

3、仿真（Simulation/Rollout）

在某一节点用随机策略进行模拟（rollout）

def Rollout(S_i): # S_i = 当前状态While True: # S_i达到终止条件/状态(下棋中某方获胜或平局)if S_i a terimal state: # 返回结果valuereturn value(S_i) # 还未终止，则# 随机选择一个当前状态下的可用动作A_i = random(available_action(S_i)) # 在当前状态下采取动作，得到新的状态S_i = simulate(A_i, S_i)

4、反向传播（Backpropagation）

得到模拟结果后不断反向更新父节点

三、运行过程

n代表当前节点被探索的次数。

则运行过程如下：

1、选择节点

• 当前节点是叶节点，则选择该节点
• 当前节点有孩子，孩子中UCB值最大的作为选择的节点

2、节点扩展 + 模拟

• 若选择的节点未模拟过（n=0），则进行模拟，得到结果后更新该节点 n=1 , value=结果数值。
• 若选择的节点模拟过（n≠0），则扩展节点。添加在该节点下所有可采取的动作，作为孩子
  • 选择第一个孩子作为当前节点，进行模拟

def Rollout(S_i): # S_i = 当前状态While True: # S_i达到终止条件/状态(下棋中某方获胜或平局)if S_i a terimal state: # 返回结果valuereturn value(S_i) # 还未终止，则# 随机选择一个当前状态下的可用动作A_i = random(available_action(S_i)) # 在当前状态下采取动作，得到新的状态S_i = simulate(A_i, S_i)

3、反向传播

• 当孩子得到 Vc=v,nc+=1V_{c}=v,n_{c}+=1Vc​=v,nc​+=1，反向传播到父节点，父节点 Vp+=v,np+=1V_{p}+=v,n_{p}+=1Vp​+=v,np​+=1，直至传播到根节点。

三、实例

具体样例可参考博客蒙特卡洛树搜索（MCTS）详解、蒙特卡洛树搜索 MCTS 入门或b站视频AI如何下棋？直观了解蒙特卡洛树搜索MCTS！！！