AlphaGo 的棋局，与人工智能有关，与人生无关
|
一种策略(Policy)的 Regret （损失）为：
(from A Survey of Monte Carlo tree Search Methods) 我觉得 mu_j 应该放到求和符号里面的。 不要被数学公式吓到了，用自然语言描述就是：最理想的情况是 n 次都试均值最大的那个手臂(mu star)，不过我们并不知道，E[Tj(n)] 是这个策略下选择第 j 个手臂的期望。那么 R 就是期望的损失，如果我们的策略非常理想，这个策略只尝试最好的手臂，其它不试，那么 R 就是 0。 但是这样的理想情况存在吗？很明显不太可能存在（存在的一种情况是k个手臂的均值一样）。那么我们的策略应该尽量减少这个损失。 Lai and Robbins 证明了这个损失的下界是 logn，也就是说不存在更好的策略，它的损失比 logn 小（这类似于算法的大 O 表示法）。 所以我们的目标是寻找一种算法，它的损失是 logn 的。 UCB 就是其中的一种算法：
每次决策之前，它都用上面的公式计算每个手臂的 UCB 值，然后选中最大的那个手臂。公式右边的第一项是 exploit 项，是第 j 个手臂的平均回报的估计。这个值越大我们就越有可能再次选中它。第二项是 explore 项，n_j 是第 j 个手臂的尝试次数，n_j 越小这个值就越大，也就是说尝试次数越少的我们就越应该多尝试。当 n_j=0 时，第二项为无穷大，所以这个算法会首先尝试完所有的手臂（explore），然后才会选择回报最大的那个(exploit)，试了之后这个手臂的平均值可能变化，而且 n_j 增加，explore 值变小，接着可能还是试最大的那个，也可能是第二大的，这要看具体情况。 我们来分析一些极端的情况，一种情况是最好的（假设下标是 k)比第二好的要好很多，那么第一项占主导，那么稳定了之后大部分尝试都是最好的这个，当然随着 n_k 的增加 explore 项在减少(其它手表不变)，所以偶尔也试试其它手臂，但其它手臂的回报很少，所以很快又会回到第 k 个手臂。但是不管怎么样，即使 n 趋于无穷大，偶尔也会尝试一下其它的手臂的。不过因为大部分时间都在第 k 个手臂上，所以直觉上这个策略还是可以的。 另一种极端就是 k 个手臂都差不多（比如都是一样的回报），那么 exploit 项大家都差不多，起决定作用的就是 explore 项，那么就是平均的尝试这些手臂，由于 k 各手臂回报差不多，所以这个策略也还不错。 出于中间的情况就是有一些好的和一些差的，那么根据分析，大部分尝试都是在好的手臂上，偶尔也会试一试差的，所以策略的结果也不会太差。 当然这个只是简单的直觉的分析，事实上可以证明这个算法的 regret 是 logn 的，具体证明细节请参看论文《Finite-time Analysis of the Multiarmed Bandit Problem》。 MCTS（Monte Carlo tree Search）和 UCT（Upper Confidence Bound for trees）
(from A Survey of Monte Carlo tree Search Methods) MCTS 算法就是从根节点（当前待评估局面）开始不断构建搜索树的过程。具体可以分成 4 个步骤，如上图所示。 1. Selection 使用一种 Policy 从根节点开始，选择一个最“紧急”(urgent)的需要展开(expand)的可以展开(expandable)的节点。 说起来有点绕口，可以展开的节点是非叶子节点（非游戏结束局面），而且至少还有一个孩子没有搜索过。比如上图展示的选择过程，最终选择到的节点不一定是叶子节点（只有它还有没有搜索过的孩子就行）。具体的选择策略我们下面会讨论。 2. Expansion 选中节点的一个或者多个孩子被展开并加入搜索树，上图的 Expansion 部分展示了展开一个孩子并加入搜索树的过程。 3. Simulation 从这个展开的孩子开始模拟对局到结束，模拟使用的策略叫 Default Policy。 4. Backpropagation 游戏结束有个得分（胜负），这个得分从展开的孩子往上回溯到根节点，更新这些节点的统计量，这些统计量会影响下一次迭代算法的 Selection 和 Expansion。 经过足够多次数的迭代之后（或者时间用完），我们根据某种策略选择根节点最好的一个孩子（比如访问次数最多，得分最高等等）。 上面的算法有两个 policy：tree policy 和 default policy。tree policy 决定怎么选择节点以及展开；而 default policy 用于 simulation（也有文献叫 playout，就是玩下去直到游戏结束) 在讨论 MCTS 和 UCT 之前，我们来分析一下人在下棋时的搜索过程。 首先人的搜索肯定不是之前的固定层次的搜索的，很多“明显”不“好”的局面可能就只搜索很浅的层次，而不那么“明显”的局面可能需要搜索更深的层次（之前我们讨论过这里隐含了一个假设：深的局面比浅的局面容易评估，对于象棋这是比较明显的），“好”的局面也需要多搜索几层确保不会“看走眼”。 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。 （编辑：PHP编程网 - 湛江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
