[转载]原文来自：道客巴巴网站的论文。下面的论文摘要是我自己阅读时所做。该论文在围棋形势判断编程方面给了我很大的启发和帮助！在此特别感谢论文作者和论文的提供者：道客巴巴网站。

                      第四章    局面分析功能的设计与实现

围棋的最终目的是围空，占领地盘，但是棋子的作用显然不仅仅是围空，每一颗棋子都有它的本身价值，这个价值由对局形势所决定。如何标识和衡量棋子在棋局中发挥的作用，对局面进行分析，这是围棋对弈系统设计的一
个重要内容，即计算机围棋的形势判断。

           4.1   围棋局面分析的影响模型

计算机围棋的形势判断，通常采用影响模型，将棋子向棋盘其他部分的辐射影响量化。
围棋中的“势”通过影响函数（又称势函数）建立可计算模型。通常，黑白子辐射值正负相反，子力辐射按距离的增加而单调递减。
棋子的影响模型是战术决策和战略决策的基础。局面的静态评估，棋子的安全性判断与分块，领地的计算与划分等，通常都基于影响模型的计算结果。在影响模型中，多个棋子的作用被看作是单个棋子作用的叠加，而单个棋
子的作用根据相对位置不同作一定的修正，黑白棋子会产生正负相反的影响。
围棋编程的一个基本任务是分块。“块”是一组有关联的同色棋子。优良的分块法能使计算机对当前的局面有较好的了解。它可用于估计局部棋子的安危，确定战术搜索的范围，产生弱块的攻防点，而且可以在块边缘选取收
官点。分块法与棋子的影响模型是分不开的。
对某点的影响估计过高或过低都将给判断带来问题。估计过高会将弱块看作强块，将原本联系不紧密的棋子视为同一棋块。估计过低会忽略可以利用依靠的棋块，在强块部分浪费手数补棋。总之，影响模型的优劣对战术、战
略决策有极其显著的影响。

            4.1.2    典型的影响模型举例
影响模型的使用，贯穿了计算机围棋的发展历史，各种计算机围棋程序，都将影响模型作为战术和战略决策的基础。
1.    Zobrist的影响模型
Zobrist首次引入了影响函数将棋盘分为黑方和白方地域。他的影响函数计算棋盘上每一个交叉点的数值，黑子取+50，白子取-50,空点为0；正负数的点给临近点+1或-1，以这样的算法递归4次，可以把棋盘数值化。
                                      1
                                 2    2  2
                               2   4  6   4   2
                           2   4   8  10  8   4   2
                       1   2   6  10  62  10  6   2   1
                           2   4   8  10  8   4   2
                               2   4  6   4   2
                                   2  2   2
                                      1

                            图 4-2  Zobrist的黑子影响模型

2．Ryder的影响模型
Ryder使用的影响函数同样黑取正数，白取负数，某点影响的取值由其邻点的影响传播累加形成，传播系数固定。

3.    陈克训的影响模型
陈克训的影响模型中，棋子的紧邻（距离为1）为最大值m，并随着距离增加而按比例衰减，衰减因子为f。他早期的程序“探索者”选用m=64、f=1/2。衰减因1/2子为就是距离每增加1时影响值减半。于是，一个棋子对直线紧

邻的影响值为64，尖位关位为32，小飞和大关位（拆二位）为16，等等。m值取为2的幂，而f取为1/2，就使各级影响值均为整数，避免了小数运算，可以节省计算量。
                  
                                      1
                               1   2  5   2    1
                               1   6  13  6    1
                           1   5  13  60  13  5   1
                               1   6  13  6    1
                               1   2  5   2    1
                                      1
                     图4-3 Ryder的黑子辐射模型
棋子之间有别的棋子挡住，就不易影响到它的后面。陈克训定义两点间的有效距离为，从其中一点到另一点通过空位的最短途径。例如，图4-4中从黑1到a位距离为2，到b距离为3，到c距离为5（因为有白2阻挡，只能绕路）.
黑1对b的影响为16，对c的影响为4.
  http://s11/mw690/a1204ac8tdf69f2797dba&690


                 图4-4 有效距离
若干个棋子对一个空位的影响可以取代数和。陈克训去黑子的影响为正、白子的为负。
1~3线的空位影响值被乘以某因子使其边大，这成为边角调整。边角调整后把净影响值按比例换算为-n与n之间的数。“探索者”取n=64.这就是说，把净影响值等于或大于198者换算为64，-198或更小者换算为-64,而中间的值
则变换到（-64,64）之间。这种换算称为规格化。距规格化影响值n（-n）的空位即为该点受黑（白）全控制，大体就是该方的实空了。规格化影响值0是不属于任何一方控制的点。把特别大的净影响值通过规格化变为n（-n），是因为某点的净影响值不论多大也不过是某方的1目空。
规格化影响值可用于分块并对棋子的安危进行估算。同色串属于同一块。
取定一个界限值a，规格化影响值不小于a的空位作为黑方所控制的空位，白方则为不大于-a者。经验表明a=n/4是合适的界限。n是规格化影响值的最大值。将相连的己方棋子和己方控制点合在一起，形成一棋块。只用影响值类确定块是不全面的。常有这样的情况，同色的两串实际上不可分割，却并非通过有足够大的影响值的空位相连。为了使分块方案更为完善，还补充了“链”的概念。链是不可分割的同色串的整体。如何确定不可分割？陈克训提出了直观推断准则。
通过影响和链来做出分块，与人类棋手的直觉是颇为一致的。当然，这也需要设计者凭自己的经验进行调整。一旦分了块，其安全性即可用其影响值及其自由度来估计。
块的自由度为该棋块周围的敞开程度，自由度和逃出以及利用周围敞开处做眼的难易程度有关。块的影响值及自由度足够大则安全。不够大的可检查该块能否做两眼，从做出两眼以及逃出的难易程度来对安全度进行评估，并
加以量化，用数字0~64来表示；64为安全，越接近0越不安全。安全性为0的，就是死块，其中的棋子和临近的空位均可判为对方的地域。若我方某块不安全而非无望，即安全性小于64但大于某界限，就会有适当的防守点使其
加强。若对方某块不安全而非无望，就会有攻击点以图攻杀或欺凌该块而取利。这就是说，分块能用来产生攻防着点。
基于不同的影响模型，棋子分块、自由度计算、势力划分等部分的处理也完全不同。影响模型在一定程度上可以将棋子在棋局中发挥的作用量化，从而判定棋子关系、评估盘面局势，是计算机博弈程序的基础。

               4.2    围棋局面分析的常用算法
目前，世界上流行的围棋软件主要由以下三种算法组成：
1．    使每个棋子周围产生某种影响，这种影响随着距离的增加而减少，用一定的公式计算叠加这种影响，以判断形势和估计着点的价值。这与围棋的棋理相通，即对于每个棋子可估算棋“势力”。此中有著名的“气位”
理论。
2．    建立模式库，贮存了大量模式（定式、棋形等），以供匹配。这其实涉及到围棋的许多格言和棋理。如“二子头必扳”、“镇以飞应”、“断从一边长”、三子正中、点方等。这些都是根据围棋的具体情况而设计的
。
3．    对目标明确的局部，用人工智能中的搜索法探求其结果。
一般来说，现在还没有找到突破性的算法，只有在以上三种算法中细细加工。

                  4.3    围棋局面分析功能的实现

Stone{int value，int distanc}，记录每一点与棋盘上已落棋子的距离和受到的影响值。
Map（1 to 19,1 to 19）as Stone，记录最后的累加影响。Map（i，j）距离和影响值的关系为：value=2的（6-distanc）次方。每一点Map（i，j）的最终影响要通过计算一下模型，递减定律以及反射定律，经过度量公式来
计算，大于定值a的点显示为黑棋地域，小于-a的点显示为白棋地域。
在设计系统局面分析时，采用了如下模型。

                   4.3.1    影响模型

设定影响在棋子的距离1处为最大值32，随着距离增加而按比例衰减，衰减因子为1/2，即距离每增加1则影响值减半。例如，一个棋子紧邻的长影响值为32，小尖和跳影响值为16，小飞和拆二为8，等等。各级影响值均为整数，避免了小数运算。黑影响值为正数，白为负数。黑子的影响如图4-5。
影响模型的实现，采用循环嵌套，对落子（i，j）计算其对周边的影响，定义变量row，colum，对于满足i-6<=row<=i+6,i-6<=column<=i+6的点，（row,column）的距离distance为|row-i|+|column-j|，并记录到棋谱Map（19,19）中。

                  4.3.2    力学模型

棋盘上的每一个棋子，都向周围四个方向发出影响，通过这种影响实现对空点的占领和棋子之间的相互作用，这种影响可以被视为一种控制力，沿着四个方向大小相等，而黑白棋子产生的控制力正负相反。
棋子控制力的传播规律如下：
1.    递减律
控制力遇到一个空点，乘以传播率1/2，遇到有子点，则同方向的距离distanc+2，即受到的影响值减1/4倍。
2.    反射律
“金角银边”的体现，控制力会被棋盘的边界反射回来，该反射力与原控制力方向相反，封号相同，大小为原控制力的一个常数倍，该常数被称为反射律。实现时，棋子（i，j）在传播过程中，利用row，column双重循环，如遇到row=1或19，则同方向的距离distanc-|row-i|;如遇到column=1或19，则同方向的距离distance-|column-j|。
每一个点都受到四个方向的控制力的作用，遵循力的合成法则，任一方向的控制力是该方向上各种控制力的代数和。
                                   1
                             1     2     1
                       1     2     4     2      1
                  1    2     4     8     4      2      1
             1    2    4     8     16    8      4      2     1
         1   2    4    8     16    32    16     8      4     2     1
    1    2   4    8    16    32    64    32     16     8     4     2      1
         1   2    4    8     16    32    16     8      4     2     1
             1    2    4     8     16    8      4      2     1
                  1    2     4     8     4      2      1
                       1     2     4     2      1
                             1     2     1
                                   1
                     图4-5   本系统使用的影响模型
实际计算控制力时，
1,任意棋子的初始控制力为64，64为2的幂，可以避免小数运算。
2，黑子的影响为正，白子的影响为负；
3，传播率为1/2；
4，反射率为1；

                4.3.3  棋盘分块设计

由于棋盘上棋子的影响会因为同色相连的棋子而加倍，故一盘棋的局面分析还需对棋盘上的块棋加以分析。块棋的气势组成它的所有棋子的气总和。以worm数据结构来描述块棋：
Worm{int color,int size,int originX,int originY,int Liberities,bool cheched}。
其中，color为棋块的颜色，黑为1，白为-1，空位0；
size为同色棋子的个数；
originX,originY记录块的原点，以区分不同的块；
liberities记录块的气；
cheched标记是否属于该块，且已经搜索过。
定义分块的棋谱：worm_map(1 to 19,1 to 19) as worm
Worm结构是棋盘上横向或竖向连着的最大限度的一组相同颜色的点，颜色可以是黑，白，空。非空为串string，空块为cavity。
同色串的集合为龙dragon。龙通常一起死或者一起活。Dragon越小，越容易受到对方的攻击。
直线上的同色块称为串，横竖等几个连在一起的串组成龙。棋块可以从一个原点沿着直线搜索得到。

4.3.3    度量公式

在得到任一棋盘状态下空点影响的分布图后，可以由这些影响值计算出棋盘状态的深层信息，一些常用的度量公式如下：
一点受到四个方向的控制力，F为四个力的代数和，F大于0，受黑棋影响大；F小于0，受白棋影响强。F=0,双方的影响基本平衡。

4.3.4    判定双方的势力范围

棋盘上每一点受到的控制力的代数和F的绝对值大于某一数值n是，将该点显示为地域。取n=20。加入显示黑棋地域和显示白棋地域2个函数。
用数字Map（19,19）记录每一点势力的情况。

                      结论与展望

    围棋对弈系统的研究与实现为进一步进行计算机博弈打下了基础。但是该系统存在一些亟待解决的问题，例如，对死活库的建立，可以为将来系统进一步判断死活打下基础，达到真正智能化，并进一步实现“人-机”对弈。毋庸置疑，死活是一个很有研究价值的领域。
陈志行教授在《电脑围棋门径》中提到了设计计算机围棋的方法：第一，显示棋盘棋子和其他辅助功能。第二，设置计算和记录棋子串气数的功能，赋予提子和禁着点的功能。第三，设计一种函数，表征每个棋子对周围的影
响，用以划分势力范围，作为静态形势判断的基础。第四，要对棋盘上各点分别试下黑棋或白棋，比较落子前后的静态形势，以估算该点的落子价值，成为着点选择的基本依据。还要设置棋谱记录、计时、发声、显示显示形
势对比、计算胜负等功能。“首先必须完成前两个部分，其次解决后两个部分，这样程序就算是基本会下棋了”。

                  继续以前的对局

多日围棋赛制，一盘棋可以下好几天，甚至几个月。因此围棋软件需要“继续以前的对局”这一功能。设计成通用文件格式的继续对局处理，无需在存盘棋谱文件里设置特殊的标记，从一般的sgf棋谱里就可以继续对局。

文献：

1,T.Cazenave.”Generation of Patterns with External Conditions for the Game of Go’第二页。
2,Albert L.Zobrrist.”A new hashing method with application for Game Playing”,technical rport88,university of Wisconsin,april 1970 reprinted in ICCA Journal.，第69-73页,1970年第13期。
3，K.Chen.”Group identification in computer Go”,in:D.levy,D.Beal,eds,Heuuristic programming in artificial intelligence, the first computer Olympiad,Chichester:Ellis Horwood,第195-210页，1989年。
4，A.Zorbrist.”a model of visual organization for game Go”,in proceeding of the spring joint computer conference.
5,Jon Reder-Heuristic.”analysis of large trees as generated int the game of Go”[PhDthesis]Department of Computer Science,Standford university 1971.
6,K.Chen.”some practical techniques for global search in Go”,ICGA Journal,第67-74页，2000年第23期。
7，王斌君，郑建息，郝克刚。“计算机辅助围棋系统”《西北大学学报（自然科学版）》第481页，1994年12月第26期。
8陈志行。“电脑围棋门径”http://www.usgo.org/computer

附录

常用围棋术语中英文对照

眼eye，气liberty，先手sente，后手gote，好手tesuji，双活seki（impasse），围contain，拆extend，立sagari，叫吃atari（cheok），长nobi，空chi，territoty，提通ponnuki，脱先kenuki，断cut，切断cut-in，断点cutting point，跳jump，一间跳ikken bsasme，贴目 komi，交换 furikawari（exchange），布局fuseki，收官endgame move，尖diagonal move，枷geta，征子ladder，级kyu，段位dan grading，轻karui（light），打atari，欺着hamete（trick play），厚thickness，失着slip，本手honte（proper move），手筋tesuji，先手得利kikashi，见合miai，打入uehikomi，腾挪sabaki，挤去眼sashikomi，挡osae，劫ko，对杀semeai，压kake（pressing move），靠tsuke，模样moyo，夹diagonal move，一间夹 ikken basame，定式formalized series of moves，挂角kakari，托角touke（corner），逼tsume（checking extension）