影响函数的算法

6.3.1　影响函数的算法

一个点的影响力的辐射过程可以被看作是一个从临近点不断向远方扩展的广度优先搜索过程。在GNU Go中，一个单独的影响源的影响如图6.1所示，影响源标为“X”，其强度为100，衰减系数为3；需要注意的是，GNU Go中的影响强度采用实数表示，图6.1中取的是距离该实数最近的整数，图中显示为0的地方并不是其影响强度真的消失了。

图6.1　棋子的影响力

在计算图6.1中例子的影响强度时，其传播的顺序是从里层向外层传播的。这样既可以保证每个节点被访问且仅被访问一次，又可以保证这个过程会结束。如图6.2所示中的数字顺序就是图6.1中节点的计算顺序，当然，其影响力在“＋”之外的区域也会按照这个方式不断传播下去。

对于处在一个复杂的环境中的影响源，会存在其他的棋子和一些紧密的连接关系阻止其影响力传播到某个区域中去的现象。这将会扰乱图6.2中的传播顺序，但是它的传播仍会继续下去。

GNU Go中关于影响函数的实现策略如下，（m，n）是影响点的源坐标，（i，j）在传播过程中访问的点，它的影响会传播到周边的8个点（4个相邻点和4个对角点），对应于8个方向（d_i，d_j）。

①计算d_i＊（i-m）＋d_j＊（j-n）；

②如果（i，j）！＝（m，n），且结果为负数或零，则方向在外部，继续另一个方向，回到过程1。如果（j，j）＝＝（m，n）或（i，j）！＝（m，n），但结果为正，则继续下一步；

③如果（i＋d_i，j＋d_j）在棋盘外部或已占用，则回到过程1；

④S为（i，j）的影响强度，影响力从该点传播到（i＋d_i，j＋d_j）为P＊（1/A）＊D＊S，其中有3类阻尼：

·渗透度P，为棋盘属性，在没有遇到有效阻拦的时候为1，但是当其遇到有效阻拦时，则需在模式匹配时将该点的渗透度设为0；在如图6.3所示中，角上是白子的实地，黑子对角的影响可以忽略，为防止黑子的影响渗透到角上，可以通过模式匹配来将a点的渗透度设为0；

·衰减度A，是影响源属性，在不同的方向上有所不同，默认值为3，对角线上为双倍，修改衰减度可以调整影响源的影响范围的大小；

·方向阻尼D，是（d_i，d_j）和（i，j）-（m，n）夹角余弦的平方，作用在于阻止影响绕过干扰棋子并在该方向继续作用，对于影响源，该数值设为1。

图6.3中，角上对白来说是安全的，黑子对其内部影响可以忽略。为阻止黑子影响泄漏到角部，GNU Go中使用表示障碍的模式将黑子在此点的渗透度修改为零，而白子在此位置则仍可继续。

图6.2　计算棋子影响力的传播顺序

图6.3　棋子影响力的渗透

在如图6.4所示中，对于白走B点的价值，由影响函数计算如下：先计算黑先走在这个局部的任何一处的价值，再计算白走B后在这个局部落子的价值，这两个值的差即该着手的价值。在该例中，如果黑先手，白影响在B停止，黑实地四点，而如果白先手是着手方，则可以假定左面的后续着手为B的影响源，在A停止，实地三点。白在B价值返回1，当然前提是着手值得使用，并取得价值为2。当然，某些地方也需要考虑其后续着手价值。

图6.4　影响函数的计算