逐渐扩展的策略

10.2　逐渐扩展的策略

在蒙特卡洛博弈树的扩展过程中，对叶子节点的每一个子节点都按照同等概率进行模拟是一件很奢侈的事情。对于靠近根节点的节点，我们还是有希望对扩展开的节点再次访问到的；但是对于距离根节点相对较远的节点，访问到的次数其实很有限。比如对于围棋的一个当前的盘面状态，在十几层之后的节点有超过十个以上的叶子节点的情况其实相当普遍，但是对于距离根节点这么遥远的节点而言，访问过三五次已经实属不易了，对于十多个子节点而言，这三五次的访问可以说是完全撞运气的，如果把这有限次的机会浪费在不是那么有价值的节点上，那么就完全是在浪费计算性能；但是如果这有限次的机会被用在了很好的节点上，那么这个评估就可以说是非常有效的。

对于本身不是那么有价值的分支，我们在模拟中把它判断成好的概率非常之小，当然如果误判，那么就是致命的影响，而如果在模拟中验证了这个分支是坏的，我们也不能说这个节点就是不好的，因为好的节点我们根本没有去试探过。但是对于一个分支如果本身就是好的，如果通过验证之后，发现它是好的，那么我们无疑坚定了自己的信心；如果验证后发现不那么好，程序就会认为这个节点不怎么样。

我们将上面的论述用表10.1的形式表示出来，通过对比可以发现，对于距离根节点较远，只有少数几次可能被访问到的节点，如果被选择的分支恰巧是通常意义上较好的节点的话，那么我们无疑可以获得有价值的信息；但是如果把这有限的机会用在不太好的分支上的话，那么我们对该节点的评价则是没什么意义的。

表10.1　对节点评判可能的后果

这就需要我们通过对知识的利用来将有限的计算性能尽量用在有价值的节点上。

逐渐扩展的方法就能较好地解决这个问题。逐渐扩展就是对于一个节点而言，如果它有很多子节点，我们并不是像之前那样把所有的节点都展开，然后选点进行接下来的计算；而是先对所有的可能成为子节点的选点进行一个静态评估，然后用评估结果对子节点进行排序，之后按照排序的顺序对子节点依次展开。

当评估结束之后，我们就已经得到了一个对所有可展开点的排序，我们首先激活分数最高的那个子节点，当这个节点被访问过一定次数之后，我们便可以开始考虑激活其他的子节点。对于访问的次数通常做如下规定，令t_n为展开第n个子节点时该节点所被访问的次数，由于第一个子节点是该节点被访问时立刻被创建的，故t₁＝0，对于后续节点展开所需满足的条件如下：

t_n＋1＝t_n＋40×1.4ⁿ　　　　　（10.1）

从式（10.1）中大家可以看到，排名越靠后的节点被展开所需要间隔的次数就越多，如表10.2所示中列出了每多展开一个子节点的话该节点就所需要被访问的次数。

表10.2　对节点评判可能的后果

当该节点被访问了56次后，第2个孩子节点就被激活，但是，当第4个子节点被激活之后，该节点又被访问了154次，它的第5个孩子才被激活。由此可知，排序越靠后的孩子节点被展开所需要的被访问次数也就越多，对于19×19的盘面而言，排序靠后的孩子节点就很难被访问到了，也就在一定程度上达到了剪枝的目的。

与直接的剪枝相比，通过逐渐扩展的方法来变相的实现剪枝具有如下两个主要优势。

①逐渐扩展的方法并没有直接拒绝掉静态评估不好的点，而是也给它们以机会，当搜索次数足够多的时候，就也会去对那些不那么好的点开始进行试探。

②对于静态评估较好的点，也不是平等对待，或者赋予不同的权重，而是都给予它们以试探的机会，较好的点多给一些机会；但是，如果静态评估较好的子节点在实际探索中表现得不是那么好的话，它们起初所具有的优势就不会持续存在了。