AlphaGo 的棋局，与人工智能有关，与人生无关

首先人的搜索肯定不是之前的固定层次的搜索的，很多“明显”不“好”的局面可能就只搜索很浅的层次，而不那么“明显”的局面可能需要搜索更深的层次（之前我们讨论过这里隐含了一个假设：深的局面比浅的局面容易评估，对于象棋这是比较明显的），“好”的局面也需要多搜索几层确保不会“看走眼”。

MCTS 其实有类似的思想：我们着重搜索更 urgent 的孩子，所谓 urgent，就是更 promising 的孩子。当然偶尔也要看看那些不那么 promising 的孩子，说不定是潜力股。这其实就有之前讨论的 exploit 和 explore 的平衡的问题。

另外 MCTS 直接 Simulation 到对局的结束，“回避”了局面评估的难题（不过这个问题最终还是绕不过去的，我们下面会再讨论）。

既然是 exploit 和 explore 的问题，那么之前我们讨论的 UCB 就可以直接用上了，把 UCB 用到 MCTS 就是 UCT 算法（注意： MCTS 其实是一族算法的统称，不同的 tree Policy 和 Default Policy 就是不同的 MCTS 算法）.

UCT 算法

Selection 和 Expansion 的公式如上，和 UCB 很类似，只是多了一个常量 Cp，用来平衡 exploit 和 explore。

每个节点 v 都有两个值，N(v) 和 Q(v)，代表 v 访问过的次数（每次迭代都是从 root 到结束状态的一条 Path，这条 Path 上的每个点都被 visit 一次）和 v 的回报，如果这次 simulation 己方获胜，则 Q(v)+1，否则 Q(v)-1。（1，3，5…层代表自己， 2，4，6…代表对手，如果最终我方获胜，1，3，5 都要加一而 2，4，6 都要减一）。

具体的计算公式如上，每次选孩子时都用上面的公式计算得分。第一项就是这个节点的平均回报 (exploit term) 和第二项就是 explore term，访问次数少的节点更应该被 explore。当 N(v)=0 时第二项值为无穷大，所以如果某个节点有未展开的孩子，总是优先展开，然后才可能重复展开回报高的孩子。

UCT 算法的特点如下：

1.Aheuristic：不需要估值函数，因此也就不需要各种启发式规则，领域知识，从而“回避”了围棋估值函数难的问题。

2.Anytime：可以任何时候结束，迭代的次数越多就越准确。

3.Asymmetric：前面我们也分析过了，和人类的搜索类似，搜索树是不对称的，不是固定层次的，而是“重点”搜索 promising 的子树。

UCT 的变种和改进

这里主要关注围棋领域的一些变种和改进。

All Moves As First（AMAF）和 Rapid Action Value Estimation（RAVE）

这是很多开源 MCTS 围棋使用的一个变种。

首先通过 UCT 的 tree Policy 我们选择了 C2 和 A1，然后 Default Policy 我们选择了 B1 A3 C3 最终黑棋获胜。

普通的 MCTS 会更新 C2 和 A1 的 N(v) 和 Q(v)，而 AMAF 认为：既然在 simulation 的过程中黑方选择了 B1 和 C3，在 root 节点时也可以选择 B1 和 C3，那么这次模拟其实也可以认为 B1 和 C3 对获胜是有帮助的，那么 root 节点的 B1 和 C3也 有贡献（标志为），也应该更新统计量，让下次选择它的概率大一点。同理白棋在 simulation 的时候选择了 A3，在 C2 也可以选择 A3（有的那个），那么 C2 对于白棋失败也是有责任的，那么下次在 C2 的时候白棋应该避免选择 A3。这样一次迭代就能多更新一些节点（那些没有直接 Selection 的也有一些统计量）。

这个想法对于围棋似乎有些道理（因为不管哪个顺序很可能导致一样的局面，前提是没有吃子），而且实际效果也不错。但是在别的地方是否应该使用就需要看情况了。

这里有两类统计量：直接 selection 的节点的统计量 (A1,C2) 和间接 selection 的节点 (B1,C3, A3)。这两种权重应该是不一样的。

所以比较直观的想法是给它们不同的权重 αA+(1−α)U 这就是 α-AMAF。

这个权重 α 是固定的，RAVE 认为随着模拟次数的增加 α 应该减少才对（没有真的模拟是可以用这些间接的统计量，如果有了真的更准确的估计，这些间接的统计量就应该降低权重，这个想法也很自然）。

RAVE 使用上面的公式动态调整 α，随着 v(n) 的增加，α 的值不断下降。

Simulation 的改进

默认的 default policy 随机的选择走法模拟到结束，这在没有任何先验知识的时候是可以的。但是像我们之前分析的人类在“探索”未知局面时不是随机的“探索”的，也是用一个估值函数指导的，去探索那些更 promising 的局面。

具体方法很多，比如 Contextual Monte Carlo Search，Fill the Board 以及各种基于 Pattern 的方法。细节就不再展开讨论了。

MCTS 的并行搜索

(1) Leaf Parallelisation

最简单的是 Leaf Parallelisation，一个叶子用多个线程进行多次 Simulation，完全不改变之前的算法，把原来的一次 Simulation 的统计量用多次来代替，这样理论上应该准确不少。但这种并行的问题是需要等待最慢的那个结束才能更新统计量；而且搜索的路径数没有增多。

(2) Root Parallelisation

多个线程各自搜索各自的 UCT 树，最后投票。

(3) tree Parallelisation

这是真正的并行搜索，用多个线程同时搜索 UCT 树。当然统计量的更新需要考虑多线程的问题，比如要加锁。

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!