地域剪枝条件

10.3.3　地域剪枝条件

上面两种剪枝方式都是与领域知识无关的。而现在我们要介绍一种与围棋领域知识有关的剪枝方法。该剪枝方法在蒙特卡罗规划的过程中用到了围棋的地域信息。由于围棋比赛的过程就是双方选手争夺地域的过程，并且最终的胜者正是那个获得最大地域的人。所以，这种剪枝方法是相当重要的。

地域信息的获得是基于围棋知识的。一般说来，在行棋过程中双方选手所占地域不会发生剧烈的变化。但是，如果出现了使得地域信息发生严重变化的节点，我们则认为这样的节点十分重要，我们称这种在行棋过程中使得双方地域信息发生严重变化的节点为“热点”。如图10.1所示中那些标记为“△”的点即为热点。

图10.1　热点

下面我们给出一些关于热点计算的定义。用B表示某一给定节点所表示的盘面，P（B）定义其父亲节点所表示的盘面，S（B）表示由该父亲产生的所有兄弟节点所表示的盘面的集合，p表示给定盘面B上的某一点表示p点所占领的地域值，T^B表示盘面B的总体地域值，自然就有

如果用ΔB定义盘面B与盘面P（B）之间地域值的变化，则

ΔB＝T^P（B）-T^B　　　　　（10.11）

如果对这种变化取平均，我们可以得到盘面B相对于盘面P（B）而言每一点地域的平均变化：

我们也可以用方差来衡量这种变化的剧烈程度

D（ΔB）＝E（Δ² B）-E（ΔB）²　　　　　（10.13）

这里，我们用Φ（B）来表示盘面B在考虑其父亲盘面特性后得到的相对变化

其中，Φ（B）∈［0，1］，我们用它来衡量盘面的稳定度。

地域剪枝条件：如果存在盘面B_j∈S（B），B_i≠B_j使得Φ（B_j）∈［M，N］且Φ（B_i）∈［M，N］，则盘面B_i可以被剪枝，这里M和N为两给定的常量（通常可以根据实验经验得到）。

显然地，上面的定义假设我们可以完全准确的给出盘面上每个点的地域信息值。但是，地域的计算是非常复杂的，我们往往是采用蒙特卡罗规划的方法得到这一值。换句话说，我们可以在原始蒙特卡罗规划过程中加入返回地域信息的过程。通过大量的模拟，我们可以较准确的评估盘面的地域信息。

更确切地说，在UCT算法中我们用蒙特卡罗模拟的方法作为评估方法：每一次蒙特卡罗模拟都将得到一个完整比赛的全盘地域信息。在一定数量的模拟后，我们可以计算每一个点的平均占有率。我们令n表示从当前盘面开始模拟的总次数。用b_p（n）定义在这么多次模拟中该点被黑棋占领的次数，用w_p（n）定义在这么多次模拟中该点被白棋占领的次数，而用e_p（n）定义在这么多次模拟中该点没有被任何颜色的棋占领的次数。显然，n＝b_p（n）＋w_p（n）＋e_p（n）。根据以上定义，p点的地域值为：

我们可以通过以这种方式得到地域信息。如图10.2（a）和图10.2（b）所示分别显示了一盘棋初始时和终盘时的地域状态。通过规范化处理，我们使其相应的地域值的范围保持在［0，10］之间，上述两个局面的地域信息值分别如图10.3（a）和图10.3（b）所示。当地域值接近10时，代表该点有较大的可能性属于黑棋；当地域值接近0时，代表该点有较大的可能性属于白棋。

图10.2　地域信息值Ⅰ

图10.3　地域信息值Ⅱ