Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: 陈克训及其棋子分块法（转贴）(转载)
发信站: 哈工大紫丁香 (2000年09月07日15:56:34 星期四), 站内信件

【 以下文字转载自 Programming 讨论区 】
【 原文由 Nabla 所发表 】


“棋慧”是美籍华人陈克训所设计的电脑围棋程序，在电脑围棋赛上屡获佳绩。
其特点之一是战斗力较强。这种较强的战斗力在很大程度上应归功于陈克训对
棋子分块的深入研究。这种研究成果已用于他早期的程序“探索者”。下面的
介绍中提到的具体数字都是在“探索者中用到的。

“块”大体是一组有关连的同色棋子，它构成了围棋对局中的战术单元。若把
整个棋局看成一个战争，则块可看成一支部队，它可以独立地活动，在局部与
邻块的攻防就构成一个战役。

围棋的人工智能的一个基本任务是分块。优良的分块法能使电脑对当前的局面
有较好的了解。它可用于估计局部棋子的安危、确定战术搜索的范围、产生弱
块的攻防着点，且在终局阶段在块边缘及其外侧选取收官着点。

陈克训的分块法以“影响”和“链”这两个基本概念为基础。

首先讨论“影响”。

围棋中有一个概念叫做“外势”，它表征着棋子对外的影响。例如，下图的黑子
把白角包围起来。白角形成了近10目的实空，而黑棋则对外方有着强大的影响，
也就是有强大的外势。在围棋程序中，影响这个概念是泛指，不仅包括外势。图
中的白子虽因不能对中腹和两边发出影响而无外势，但这些白子仍有对角上空位
的影响，其结果是把这些空位控制在白方而形成实空。

 ┏┳┳┳┳┳┳┳┳┳
 ┣╋╋╋○○╋╋╋╋
   ○○○●●●╋╋╋ 图一
 ┣○●●╋╋╋╋╋╋
 ┣●╋╋╋╋╋╋╋╋
 ┣╋●╋╋╋╋╋╋╋
 ┣╋╋╋╋╋╋╋╋╋

棋盘上的每个棋子都要对盘面发出影响。这影响在棋子的紧邻（距离为1）为最大值
ｍ，并随距离增加而按比例衰减，衰减因子为ｆ。“探索者”选用ｍ=64、ｆ=1/2。
衰减因子为1/2就是距离每增加１时影响值减半。于是，一个棋子对邻位的影响值为
64，尖位和关位为32,小飞和大关位（拆二位）为16,等等。ｍ值取为2的幂，而ｆ取
为1/2，就使各影响值均为整数，避免了小数运算。围棋程序因要计算很多问题，宜
尽量节省计算量，因此通常都避免小数运算而只用整数运算。

这里所说的距离，严格些说应该是有效距离。问题在于棋子前面若有别的棋子挡住，
则不易影响到它的后面。陈克训的做法是定义两点间的有效距离为从其中一点到另一
点通过空位的最短途径。例如，下列棋盘上从棋子１到ａ位距离为２、到ｂ位距离为
３。棋子１到ｃ位的距离，若黑子不存在，则距离还是３。现在有了黑子挡路，要绕
弯路才能到达Ｃ位，距离为５。这么一来，棋子１对ｂ、ｃ两处的影响就不一样：对
ｂ的影响是16，而对ｃ的影响则只有4。

 ╋╋╋╋╋╋╋╋╋╋
 ╋╋①╋●ｃ╋╋╋╋  图二
 ╋╋╋ａ╋╋╋╋╋╋
 ╋╋╋╋╋╋╋╋╋╋
 ╋╋ｂ╋②╋╋╋╋╋
 ╋╋╋╋╋╋╋╋╋╋

若干个棋子对一个空位的这些影响可以取代数和。陈克训取黑子的影响为正、白子的
为负。上图ａ位受上方黑白各一子的影响互相抵销，只剩白子２的影响，为-16；ｂ位
受黑子影响为４、受白１影响为-16，受白２影响为-32，净影响为4-16-32 = -44。
ｃ位受黑子影响为64，受白１影响为４，受白２影响为８，净影响为64-4-8 = 52。

由于边角更易接受棋子的影响，在一至三线的空位的影响值被乘以某因子使其变大。
这称为边角调整。边角调整后更把净影响值按比例换算为-ｎ与ｎ间的数。“探索者”
取ｎ=64。这就是说，把净影响值等于或大于198者换算为64，-198或更小者换算为-64，
而中间的值则变换到（-64,64)之间。这种换算称为规格化。具规格化影响值ｎ(-ｎ)
的空位意为该点受黑（白）全控制，大体就是该方的实空了。规格化影响值０是不属
任何一方控制的点。容易理解，规格化影响值可以用来计算地域。把特别大的净影响
值通过规格化变为ｎ(-ｎ)，是因为某点的净影响值不论多大也不过是某方的一目地域。

规格化影响值可用于分块并对棋子的安危进行估算。相连的同色子，即属于同一串的棋
子，当然属于同一块。取定一个界限值ａ。规格化影响值不小于ａ的空位作为黑方所控
制的空位，而对白方则为不大于-ａ者。经验表明 a=n/4 是合适的界限。这ｎ就是上述
规格化影响中的最大值。某方的若干棋子若与己方所控制的空位或敌死子相连，就可以
认为这些棋子属于同一块。这里的所谓相连，是指通过相邻位置不间断地相连，就像串
的定义中的一样。

这种分块法符合块的意义，即块是可以独立地作战的同色棋子的一个集体。若同色子连
同所控制的位置（空位和敌死子）连在一起，就可看成难以分割的整体，即成为一块。

然而只用影响值来确定块是不全面的。常有这样的情况，同色的两串实际上不可分割，
却并非通过具足够大的影响值的空位相连。为了使分块方案更为完善，须补充以“链”
的概念。

原则上，链是不可分割的同色串的整体。然而如何确定不可分割性却不简单。陈克训提出
了实际上采用的直观推断准则。

若两串有两个以上的公气，或只有一个公气但该处能防止敌进子（例如该处是虎口），
就把这两串看成属于同一链。

 ┣╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋
 ┣○○╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋ 图三
 ａｂｂａ╋╋╋╋╋○╋╋╋╋○╋○╋╋╋
 ┣○○╋╋╋╋╋○╋╋╋╋╋●○╋╋╋╋ 链的例子
 ┣╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋╋
   双关          尖            虎

对于前一情况，若敌在两公气之一走棋，则我方可走在另一公气处使两串合而为一。
对于后一情况，若敌着子于公气处，我方可立即吃掉它。

双关和尖连均属前一情况。图中的两ａ位若均有黑子，则两ｂ位的影响值黑白相消而
不为任何一方所控制。但不论黑走在两ｂ位中哪一点，白均可占另一点而将两串连起
来，故不能分割。

显然这种只管判断不能识别复杂的不可断的连接。相反，这里有一个有意思的缺点。
考虑如下图的三个白子：

 ╋╋╋╋╋╋╋╋╋
 ╋╋╋╋╋╋╋╋╋
 ╋╋╋ａ○╋╋╋╋   图四
 ╋╋╋○ｂ●●╋╋
 ╋╋╋ｃ○╋╋╋╋
 ╋╋╋╋╋╋╋╋╋

上、中两白子有两公气ａ和ｂ，故属同一链。同样中、下两白子有两公气ｂ和ｃ，
亦属同一链。但三者不能属于同一链，因若黑走在ｂ处，白智能连接在ａ、ｃ两点
之一而不能都走到。为了回避这一问题，当我们发现正好有两个公气且无一是能防
敌进子的，我们把两者合并成链，并标出这两点使其不再用于将来的合并。

同一链中的棋子均应属于同一块。例如，下图中的白子若仅考虑影响值则成为两块，
每块只有一个眼。有了链的概念，因两串通过尖连而成为一链，就构成有两眼的一块。

 ┏┳┳●○┳○●┳┳
 ┣╋╋●○○○●╋╋
 ┣╋●●○●●●╋╋  图五
 ●●●╋○●╋╋╋╋
 ●╋○○╋●╋╋╋╋
 ●○╋○●●╋╋╋╋
 ●○○○●╋╋╋╋╋
 ●●●●●╋╋╋╋╋
 ┣╋╋╋╋╋╋╋╋╋

通过影响和链来作出分块，与人类棋手的直觉是颇为一致的。一旦分了块，其安全
性即可用其影响值及其自由度来估计。块的自由度意为它周围的敞开程度，它和逃
出及利用周围敞开处做眼的难易程度有关。块中的影响值及自由度足够大则安全。
不够大的可检查它能否做两眼，从两眼及逃出的难易程度来对安全程度作估计，并
加以定量化而用数字0至64来表示：64为安全，较少的则不尽安全。安全性为0的即
完全无望，也就是死块，其中的棋子和邻近的空位均可判为对方的地域。

若我方某块不安全而非无望，即安全性小于64但大于某界限，就会有适当的防守着
点使其加强。若某敌块不安全而非无望，就会有攻击点以图攻杀或欺凌该块而取利。
这就是说，分块能用来产生攻防着点。


--
迷失在都市的旷野
享受孤独的梦想
体会寂寞的光荣


--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.148]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: malacs.hit.edu.cn]