蒙特卡洛树是什么算法？

蒙特卡罗树搜索(MCTS)将逐步建立一个不对称的树。它可以分为四个步骤并反复迭代:

(1)选择

从根节点，也就是决策情境R出发，选择一个最急需扩展的节点T；情况R是要检查的第一个节点。如果被查节点有一步棋M没有求值，那么被查节点执行M后得到的新情况就是我们需要展开T的；如果已评估了检查情境中的所有可行棋步，则使用ucb公式获得一个具有最大ucb值的可行棋步，并再次检查由该棋步产生的新情境；如果检查的情况是游戏已经结束的游戏情况，则直接执行步骤4；通过反复检查，我们最终在树的底部得到最后检查的情况C和未评估的移动M，并执行步骤2。

(2)扩张

对于此时内存中存在的场景C，添加一个子节点。这个子节点是情境C执行move M，也就是t得到的。

(3)模拟

从情况t开始，双方开始随机落定。最后得到一个结果(赢/输)来更新T节点的胜率。

(4)反向传播

T模拟结束后，其父节点C及其所有祖先节点依次更新胜率。一个节点的胜率是其所有子节点的平均胜率。它从T开始，传播回根节点R，所以路径上所有节点的胜率都会更新。