电脑围棋中的人工智能技术

做为前些年热谈的人工智能典型研究如今似乎降温了不少，故转一篇学术性文章

电脑围棋中的人工智能技术
http://www.kuqin.com/artificial_intelligence/20080101/3292.html

摘要：本文通过研究几个最出色的电脑围棋程序，从认知科学的角度介绍了电脑围棋，并特别针对电脑围棋编程人员（或有意投身于此的程序员）揭示围棋作为一个认知科学研究领域的日益增长的重要性。对手谈，Go4++，Many Faces of Go，Go Intellect 和Explorer几个目前最优秀的电脑围棋程序，我们概括了它们用到的人工智能技术，必须面对的关键性挑战和博弈树搜索中牵涉的问题，以此揭示为什么计算机国际象棋技术不能被很好的移植到围棋领域。   

奇境小站 (WonderLand)1998.06 -- 2000.06  Webmaster: Kerry Jia
                           电脑围棋中的人工智能技术       作者:Jay Burmeister 和 Janet Wiles
澳大利亚昆士兰大学心理学与信息技术学院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/  翻译：Lookingfor

1． 挑战围棋的程序
    作为正规游戏之一的围棋领域，过去即便是应付一般的人类棋手计算机也难以有所作为。几个一年一度的电脑围棋赛事，如FOST杯赛为第一名提供2，000，000日元奖金，台湾的应氏基金为第一个能在分先七番棋中击败顶尖职业棋手的围棋程序许诺40万美元的奖金。
    最早以围棋为对象把电脑围棋纳入研究工作是在1962年，尽管第一次由程序下一盘完整的棋是发生在1968年（Zobrist，1970）。随着电脑围棋 赛事的举行和第一个商业程序的发放，电脑围棋作为一个领域于80年代被正式创立，并在90年代变得兴旺起来。目前活跃在电脑围棋竞赛中的顶尖程序有 Explorer，Go Intellect，Go4++，手谈和The Many Faces of Go，它们的水平大致在4-8级之间。

2． 围棋中的博弈树搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准博弈树搜索由四部分组成：
1．状态表示，2．候选走法产生，3．确定目标状态，以及4．一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如α-β）增强了程序的表现。
    博弈树这条途径很成功，如我们在国际象棋程序中所看到的，基于典型的完全广度α-β剪枝博弈树搜索的程序甚至击败了世界冠军。这一节我们从透视电脑围棋的角度检查博弈树搜索的四个构件。

2.1 状态表示
    从完全信息的角度看，围棋盘面有19X19的3次方格，每个交叉点要么空要么被黑子或白子占据。状态空间的大小（例如可能的位置数）是3的361次方（或 10的172次方），相比之下国际象棋大致为10的50次方而Othello棋为10的30次方（Allis，1994）。另外，博弈树的大小（例如可能 的博弈数）在10的575次方和10的620次方之间，对比国际象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。
    由于空间的组合尺寸，用19X19格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。接下来的层面的描述是把正交的邻接棋子组成串（或 链）。所有的程序把串搜集到更大的单元，然而没有通用的处理方法——即便是对专业棋手来说——把串组合到更大的单元中。依靠他们的围棋理论，程序员开发了 他们自己的启发式，当串有效的连接在一起时用做评估之用（叫做模糊组或块）。
    另外，恰当层次的表示能改变对运行时子任务的依赖，例如，战术分析，死活分析，或实地评估。

2.2 走子
    棋手在禁止自杀和同型反复（劫）的规则限制下轮流把棋子投放在空的交叉点（包括角和边）。象国际象棋一样，围棋在给定位置的上下文中只有所有合法走法中的 一部分是有效的。围棋的平均分枝因子是很大的，大约是国际象棋的六倍（200对35，Burmeister & Wiles，1995）。
    注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如，直接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。
    实际的走子是个复杂的问题：参见3.4部分。

2.3 目标状态
    围棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地：建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态，因为实地的获 得是靠慢慢积累起来的（不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上）。由于在接近终局前很难精确地计算实地，故启发式估计用的较多。 这样的启发方式通常要归并组件和指示领地安全潜力的（例如死活组和影响）次要目标（例如国际象棋里的材料优势）。
    当对局双方依次弃权时结束。棋手通常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上，要确定对局结束（即何时弃权）是相当困难的。 人们下棋，计算结果时如果遇到有关死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中，如果程序出现算法不能解决的得分争执，计分就由组织比赛的 人员来做。

2.4 评估函数
    在判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来 获得的。有意思的是，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争中是可活的（即它必须赢得打劫来使自己活下来），就 必须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。
    评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一个绝对的死活回答可能超出了战术或死活搜索的范围。
    从复杂的类型分析看，由一个绝对位置来确定赢家是P空间难题（Lichtenstein & Sipser，1980），决定一个棋手能否左右输赢需指数时间来完成（Robson，1983），由此也就不奇怪要用到启发式了。这些理论结果显示不存 在从一个绝对局势出发决定领地结果的多项式时间算法。

3． 参赛程序里的博弈树搜索和人工智能技术
    当前活跃在各电脑围棋赛事里的程序有Martin Muller（1995）的Explorer（EX），陈恳（陈，1989；1990；1992）的Go Intellect（GI），Michael Reiss 的Go4++（Go4），陈志行的HandTalk（HT）以及David Fotland 的Many Faces of Go（MFG）。针对第2节讨论的博弈树搜索和围棋专用的人工智能技术：战术搜索，死活搜索和势函数，我们报告这些程序的细节。

3.1 位置表示
    所有的程序都有子、串、块的表示，确认串属于某个组的典型方式是采用基于模式的启发来确定串与串之间的关联性。敌方（或块）表示也被用在EX和GI 中，启发式用来确定敌方的影响（GI）和领地区域（EX）。
    盘面（例如棋块、敌方）表示的对象属性包括它们的死活状态（也指安全性或生命力）、实地数、眼数和势。某些情况下这些属性值由战术搜索决定。
    MFG的表示方式中一些组件由评估函数控制（例如块、联接、眼、实地和势）。Go4的盘面只是简单的由评估函数（例如块、眼、安全性、实地）来表示。

3.2 候选走法
    通常，由模式或更常见的是由基于规则的专家系统产生候选走法。走子产生过程最后是通过（线性的或加权求和的）相加棋盘上所有点的参考值为合适的走法给出一个分值。全盘评估一般选最高得分点作为下一手的落子点。
    不同程序由全局水平变量估值得出的候选走法数也有所不同：GI（陈，1997）有12手，MFG有10手，而Go4至少有50手。程序变量保持的规则数： EX大约100，MFG大约200。GI含有约20个走子算法，它们或者基于模式库，或者基于面向目标的搜索，或者基于启发式规则（可能含有大量的规 则）。
    模式通常既包含低级信息也包含高级信息。低级信息与黑白子的位置有关，那些点必须是空着的，已经被子占据的点不在此列。高级信息则是关于气的数量、安全 性、眼位和领地的信息。模式匹配不仅与子的配置匹配，而且跟包含在子或串里的任何高级需求有关。大量的模式匹配计算是很耗时的，并且由于棋盘上的对称性而 变得更复杂。这已经导致了发展特殊算法来克服与模式匹配有关的问题（比如MFG的哈希函数，EX的串匹配）。
    知识以不同的方式组合到程序当中：一些程序几乎完全依据第一原则工作，另一些根据存储的模式匹配当前位置。不同的程序其模式数量相差很大：Go4约有15 个；MFG大约2000个；而EX则在3000个左右。有些程序也包含开放的走法模式数据库（定式）（例如，MFG含有约45，000个定式模式）。

3.3 目标  
    多数情况下，大量的实地比起少量的实地加相应的外势更合乎需要。尽管有时也存在着实地和外势间地转化（特别是在布局和中盘阶段）。然而，虽然实地的启发式 评估是可能的，实地依然不总是形势优劣最好的指示明灯。在对局的早期阶段，占有大量的实地可能表明一种过于集中的形势，从实地安全的角度看，这样的形对对 局的后面阶段或许是有害的。开局造就最大可能的势而不是实地通常导致局末对更多实地的追求。外势是可能用来确定形势优劣的子目标的一个例子。
    用来确定形势优劣的大量子目标的相对优先度在电脑围棋中看来没有一致性可言。典型的块和实地的死活状态（安全性）被包含在目标和子目标中。在手谈中，战术 手段是重点，而MFG集中在联接性、眼和块的生命力。Go4则好像完全贯注于联接性上，几乎任何东西都是从联接概率图上派生（直接或间接地）出来。

3.4 评估过程
    评估围棋的形势是个很慢的过程（例如，比起国际象棋程序的每秒10,000-100,000次评估，MFG是以低于每秒10次的速度完成对整局棋不超过 10,000种全盘形势的评估）。由于比赛时间的限制，程序执行的全局评估数通常是有限的（例如，MFG在选择下一步时全局的评估数不超过100）。
    Go4的50种候选走法中每一个都通过一个六步的过程来评估：1.启用一个联接概率图。对于盘面上的每一个黑子和白子，计算它与32个（实际的或假定的） 友好点的联接概率（要处理大量的数据）。确定联接性还要用到战术搜索；2.棋块由联接图和战术搜索来确定；3.眼位（利用模式）由联接性和棋块数据确定； 4.眼位的数量确定了棋块的安全性；5.每个子的安全性按联接概率图的比率辐射并在所有棋子上相加；6.黑白领地由辐射值估计。黑白领地的差别作为一个给 定走法的评估结果返回。
    MFG的评估是个多步过程，并且在很大程度上依赖于战术搜索。战术搜索检查所有少于四口和一部分有四口气的串以确定是不是死串。战术搜索也被用来鉴别联接 性和眼位。在这一环节，串组成了棋块。棋块的生命力由基于死活的考虑（例如，联接、眼位等）决定，并且用来确定黑白子在盘面每个点（在-50至+50的范 围之间）行使控制的总量统计。在总和每个点的值的基础上确定领地，给出最终的估计值。多达6轮的静态搜索可以被执行，有时用一个特殊的模式集找出能使形势 稳定下来的局部走法。
    GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法，它就被选为要走的下一步。如果候选走法中有些走法的得分大致相 等，靠评估带来方便的全局搜索决定选择走哪一步。评估时，敌子的安全性是为盘上每个点指定一个在-64到+64之间的黑白控度的基础，所有点的分值加起来 返回一个评估值。全局搜索检查的步数不多于6到7步，搜索的深度不超过6层。

3.5 战术搜索
    战术搜索是有选择的、面向目标的搜索，并且为一大堆目的而使用，包括确定串是死是活（Go4，MFG，EX，GI）、联接是安全的还是可被切断的 （Go4，MFG）、是否可以形成眼位（MFG）、产生候选走法（GI）和确定棋块的死活（EX）。就是在全局的水平，战术搜索也要用来做棋步产生和评 估。战术评估和全盘评估有区别，这跟搜索的目标（例如，一个串的气的数量）有关。由于时间上的制约，战术搜索通常在节点数、枝因子和层的深度上受到限制。 因此，尽管象死活这类的问题通常被认为是战术性的，棋子却可以在战略上就死去了，即使它们可能不能通过战术手段被抓获。由此，从围棋评估的方方面面看，战 术搜索只是一种启发式装备而已。
    MFG提供了一个战术搜索操作的很好的例证（通过“战术家”）：每个有三口或更少的气的串和许多有四口气的串被“战术家”检查过。每个串检查两次，一次白 先走一次黑先走。“战术家”决定一个串是否被抓（比如，即使它先走也不能活）、被威胁（比如，如果它先走则活，后走则死），或者是牢固的。“战术家”依靠 简单的启发式（例如，气数和联接性）。
    “战术家”有两个分离的走子器；一个执行攻击走法，一个执行防卫走法。走子器建议的走法按一些规则分类，这些规则包括二次气（气的气）、切点和简单的眼 形。一旦分类，根据依赖走法分类的质量的搜索的表现，一种α-β深度优先搜索被派上用场。走子和分类解释了多数时间依靠战术搜索的原因。
    战术搜索直接针对目标并被限制一个最大节点数。抓子时这个限制是大约100，然而当只有一步可走时就不考虑这个限制。采用这种方式，可以毫不费力地确定征 子的胜方。根据第一层走子产生赋予走法的分值，一次搜索的节点数分配到树枝中，因此不同的树枝可能在不同的深度结束。每一成功的层的枝因子被“战术家”逐 步强化；枝因子从第一层5降到第五层的1或2。
    对局过程中，MFG作大约100,000-150,000次战术搜索，以每秒2,000-2,500个节点的速度遍历1.5-2百万个节点。平均起来每次战术搜索访问约10-20个节点，尽管由于一些搜索因节点限制而终止，许多搜索访问过节点数要少于5个。

3.6 死活搜索
    不是所有的程序都做明确的死活分析，很多程序对此使用了战术搜索。MFG用与它的战术搜索过程类似的方式作死活分析，除了它是在块上作死活分析而不是分析串。
    一个静态死活评估器在多步过程中确定每个块的死活状态，而没有以从简单的结构中进一步产生复杂结构的方式向前搜索。静态死活评估器使用“战术家”并且为棋块中的每个合适的串至少调用两次。
    死活搜索是直接面向目标的（例如，拯救或杀死一个棋块）。如果在一个特定点没有获得搜索目标，合适走法由死活搜索引擎自身的走法器产生，并继续搜索。为了 在一次死活搜索期间确定目标是否已经达到，静态死活评估器在每个点被调用。死活搜索引擎使用深度优先α、β搜索，每一个特定的枝的搜索深度由启发式决定。 搜索树的大小是强制性的，通常可以达到7层的深度和20个节点的大小。死活搜索是很慢的，整棵树要装到缓存里以减少花在重复搜索上的开销。死活搜索的缓慢 也意味着它不会被用在全盘评估中。

3.7 势函数
    势是一种围棋概念，它表明了每一方棋子对空点的最大可能的控制潜力。通过确保开局时子力投放不过于集中，棋手在后面的对局中将取得最大限度获得领地的机会。
    势通过势函数建立可计算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盘上每个点的辐射影响值的和（黑白子 辐射正负相反的值）对周边的点施加辐射影响（MFG的黑白子的势是分离的）。子力辐射按距离函数递减：GI是2的距离次方分之一，MFG是距离分之一。但 过于依赖势函数的程序表现不佳（EX和Go4不再使用势函数，尽管Go4的辐射函数很象一个势函数，EX采取另一些措施，象同色点或可联接点的距离）。
    应用势的启发包括确定联接性和敌子（GI），以及确定领地（MFG）。MFG的块势初始值依赖于块的强度等，强壮的块比弱块或将死的块辐射更大的影响。这 也意味着死块辐射负影响等，因为它对敌方有利。在MFG和GI中势都没有通过子辐射；MFG也没有通过敌链辐射影响。

4． 讨论
    当前的围棋程序都使用了一定量的“知识”。由于建立在设计者下棋成功经验的启发之上，每个程序都可被看作一种（可能是含蓄的）围棋理论的一次以经验为依据 的实验。围棋理论成立的关键要靠数据结构的选择，因为它们决定了编码不同类型知识的难易和应用这些知识的计算开销。随着程序员同时在围棋和电脑围棋方面获 得技能，程序会有发展（例如，在过去的十五年中随着 Fotland 的棋力从15级发展到2段，MFG也增长了棋力并且代码长度增加到目前的4万行）。程序的性能由它最弱的部件决定，而向程序增加新知识的难易是提高程序性 能的重要部分。
    由此可见，电脑围棋领域在关于怎样构筑一个围棋程序或者指配不同围棋知识的优先性（例如，Go4注重联接性而MFG注重死活）方面还没有一致性可言。必须 提到的一点是：关于人类是怎样下围棋的至今也没个一致的说法，这是目前认知科学研究的一个课题（见Saito & Yoshikawa，1977，作为回顾）。这个领域的任何进展都会对围棋理论有个直接的促进，并可能导致电脑围棋程序算法的改进。
    本文对目前比较成功的几个程序作了比较。通过这项工作，我们在博弈树搜索的框架内分析了围棋，并通过对示例电脑围棋编程的观察把有关的问题暴露出来。这种 困难在电脑围棋领域是常识，但在更为广泛的人工智能范畴却很少被人们认识和接受。围棋全盘评估需要确定棋块的死活状态，不管是通过死活搜索还是战术搜索， 评估是非常消耗计算资源的。缺乏快速有效的评估函数是电脑围棋遭遇的一个基本问题，并且和巨大的树枝因素、用户和电脑比赛的实时需求（一般来说，相对于国 际象棋的每秒180步围棋每秒只有24步）等搅和在一起。因此，计算机国际象棋通常要用到的完全广度博弈树搜索在电脑围棋里是行不通的。
    除了所列出的围棋领域固有的问题外，本文还探讨当前的程序怎样地处理这些问题，由此为未来的围棋程序员提供一个跳板。请注意电脑围棋是个商业的领域，程序 本身（不是学术论文）就是它的主要产品。跟其它的参考不同的是，这里报告的细节都已经通过个人交流征询了（慷慨贡献自己的知识的）程序作者本人的意见，并 且有相关的电脑围棋邮件列表和FTP站点的信息为依据。
    电脑围棋的挑战性在于要扩展当前的围棋理论或发展新理论——特别是与评估有关的，针对实时限制设计合适的数据结构和算法，解决知识瓶颈。目前还没有一个有 力的程序使用学习技术，尽管有过几次这样的尝试（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）。回顾这些程序已经超出了本文的范围，但我们推测这些程序也没有成功，因为它们的设计者的含蓄的围棋理论缺乏对围棋复杂性的必 要理解。怎样把学习能力赋予现有的程序（或者它们暗示的围棋理论）是个等待解决的问题。

致谢
    感谢Ken Chen、陈志行、David Fotland、Martin Muller 和Mick Reiss，他们向我们提供了有关程序的细节和对本文不无裨益的反馈。  

参考文献  
Allis, V.Searching for solutions in games and artificial intelligence. PhD thesis, University of Limburg, Maastricht, 1994.
Burmeister, J.&Wiles, J. The challenge of Go as a domain for AI research: a comparison between Go and chess. In proceedings of the Third Australian and New Zealand Conference on Intelligent Information System, pages 181-186, Perth, November 1995. IEEE Western Australia Section.
Chen, K. Group Identification in Computer Go. In D.N.L.Levy and B.F.Beal, (eds), Heuristic Programming in Aritificial Intelligence: the First Computer Olympiad, pages 195-210. Ellis Horwood, Chichester, 1989.
Chen, K. The move decision process of Go Intellect. In David Erbach, editor, Computer Go, 14: 9-17, 1990.
Chen, K. Attack and defence. In H. J. Van den Herik and L. V. Allis,(ed)s, Heuristic Programming in Artificial Intelligence 3 - The Third Computer Olympiad, pages 146-156. Ellis Horwood, Chichester, 1992.
Donnelly, P., Corr, P., and Crookes, D. Evolving Go playing strategy in neurl networks, 1994. Available on the Internet at ftp://igs.nuri.net/Go/comp/egpsnn.ps.z.
Fotland, D. Knowledge representation in The Many Faces of Go,1993. Available on the Internet at ftp://igs.nuri.net/Go/comp/mfg.z.
Lishtenstein, D. & Sipser, M. Go is polynomial-space hard. Journal of the ACM, 27(2):393-401, 1980.
Muller, M. Computer Go as a sum of local games: an application of combinatorial game theory. PhD thesis, Swiss Federal Institute of Technology Zurich, 1995.
Pell, B. Exploratory learning in the game of Go. In D. N. L. Levy and D.F. F. Beal,(eds), Heuristic Programming in Artificial Intelligence 2 - The Second Computer Olympiad, volume 2. Ellis Horwood, 1991
Robson, J. The complexity of Go. In R. E. A. Mason, (ed), Proceedings of the IFIP 9th World Computer Congress, pages 413-417, North Holland, 1983. IFIP, Elsevier Science Publishers.
Ryder, J. Heuristic analysis of large trees as generated in the game of Go. Phd thesis, Department of Computer Science, Standford University, 1971.
Saito, Y. & Yoshikawa, A. Go as a testbed for Cognitive Science studies. In IJCAI Workshop Proceedings Using Games as an Experimental Testbed for AI Research, 1997.
Schraudolph, N., Dayan, P. and Sejnowski, T. Temporal difference learning of position evaluation in the game of Go. In J. D. Cowan, G. Tesauro and J. Alspector, (eds), Advances in Neural Information Processing 6, pages 817-824. Morgan Kaufmann, San Francisco, 1994.
Zorbrist, A. Amodel of visual organization for game Go. In Proceedings of the Spring Joint Computer Conference, 34: 103-112, 1969.
Zorbrist, A. Feature extractions and representation for pattern recognition and the game of Go. PhD thesis, Graduate School of the University of Wisconsin, 1970. 做为前些年热谈的人工智能典型研究如今似乎降温了不少，故转一篇学术性文章

电脑围棋中的人工智能技术
http://www.kuqin.com/artificial_intelligence/20080101/3292.html

摘要：本文通过研究几个最出色的电脑围棋程序，从认知科学的角度介绍了电脑围棋，并特别针对电脑围棋编程人员（或有意投身于此的程序员）揭示围棋作为一个认知科学研究领域的日益增长的重要性。对手谈，Go4++，Many Faces of Go，Go Intellect 和Explorer几个目前最优秀的电脑围棋程序，我们概括了它们用到的人工智能技术，必须面对的关键性挑战和博弈树搜索中牵涉的问题，以此揭示为什么计算机国际象棋技术不能被很好的移植到围棋领域。   

奇境小站 (WonderLand)1998.06 -- 2000.06  Webmaster: Kerry Jia
                           电脑围棋中的人工智能技术       作者:Jay Burmeister 和 Janet Wiles
澳大利亚昆士兰大学心理学与信息技术学院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/  翻译：Lookingfor

1． 挑战围棋的程序
    作为正规游戏之一的围棋领域，过去即便是应付一般的人类棋手计算机也难以有所作为。几个一年一度的电脑围棋赛事，如FOST杯赛为第一名提供2，000，000日元奖金，台湾的应氏基金为第一个能在分先七番棋中击败顶尖职业棋手的围棋程序许诺40万美元的奖金。
    最早以围棋为对象把电脑围棋纳入研究工作是在1962年，尽管第一次由程序下一盘完整的棋是发生在1968年（Zobrist，1970）。随着电脑围棋 赛事的举行和第一个商业程序的发放，电脑围棋作为一个领域于80年代被正式创立，并在90年代变得兴旺起来。目前活跃在电脑围棋竞赛中的顶尖程序有 Explorer，Go Intellect，Go4++，手谈和The Many Faces of Go，它们的水平大致在4-8级之间。

2． 围棋中的博弈树搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准博弈树搜索由四部分组成：
1．状态表示，2．候选走法产生，3．确定目标状态，以及4．一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如α-β）增强了程序的表现。
    博弈树这条途径很成功，如我们在国际象棋程序中所看到的，基于典型的完全广度α-β剪枝博弈树搜索的程序甚至击败了世界冠军。这一节我们从透视电脑围棋的角度检查博弈树搜索的四个构件。

2.1 状态表示
    从完全信息的角度看，围棋盘面有19X19的3次方格，每个交叉点要么空要么被黑子或白子占据。状态空间的大小（例如可能的位置数）是3的361次方（或 10的172次方），相比之下国际象棋大致为10的50次方而Othello棋为10的30次方（Allis，1994）。另外，博弈树的大小（例如可能 的博弈数）在10的575次方和10的620次方之间，对比国际象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。
    由于空间的组合尺寸，用19X19格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。接下来的层面的描述是把正交的邻接棋子组成串（或 链）。所有的程序把串搜集到更大的单元，然而没有通用的处理方法——即便是对专业棋手来说——把串组合到更大的单元中。依靠他们的围棋理论，程序员开发了 他们自己的启发式，当串有效的连接在一起时用做评估之用（叫做模糊组或块）。
    另外，恰当层次的表示能改变对运行时子任务的依赖，例如，战术分析，死活分析，或实地评估。

2.2 走子
    棋手在禁止自杀和同型反复（劫）的规则限制下轮流把棋子投放在空的交叉点（包括角和边）。象国际象棋一样，围棋在给定位置的上下文中只有所有合法走法中的 一部分是有效的。围棋的平均分枝因子是很大的，大约是国际象棋的六倍（200对35，Burmeister & Wiles，1995）。
    注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如，直接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。
    实际的走子是个复杂的问题：参见3.4部分。

2.3 目标状态
    围棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地：建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态，因为实地的获 得是靠慢慢积累起来的（不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上）。由于在接近终局前很难精确地计算实地，故启发式估计用的较多。 这样的启发方式通常要归并组件和指示领地安全潜力的（例如死活组和影响）次要目标（例如国际象棋里的材料优势）。
    当对局双方依次弃权时结束。棋手通常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上，要确定对局结束（即何时弃权）是相当困难的。 人们下棋，计算结果时如果遇到有关死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中，如果程序出现算法不能解决的得分争执，计分就由组织比赛的 人员来做。

2.4 评估函数
    在判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来 获得的。有意思的是，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争中是可活的（即它必须赢得打劫来使自己活下来），就 必须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。
    评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一个绝对的死活回答可能超出了战术或死活搜索的范围。
    从复杂的类型分析看，由一个绝对位置来确定赢家是P空间难题（Lichtenstein & Sipser，1980），决定一个棋手能否左右输赢需指数时间来完成（Robson，1983），由此也就不奇怪要用到启发式了。这些理论结果显示不存 在从一个绝对局势出发决定领地结果的多项式时间算法。

3． 参赛程序里的博弈树搜索和人工智能技术
    当前活跃在各电脑围棋赛事里的程序有Martin Muller（1995）的Explorer（EX），陈恳（陈，1989；1990；1992）的Go Intellect（GI），Michael Reiss 的Go4++（Go4），陈志行的HandTalk（HT）以及David Fotland 的Many Faces of Go（MFG）。针对第2节讨论的博弈树搜索和围棋专用的人工智能技术：战术搜索，死活搜索和势函数，我们报告这些程序的细节。

3.1 位置表示
    所有的程序都有子、串、块的表示，确认串属于某个组的典型方式是采用基于模式的启发来确定串与串之间的关联性。敌方（或块）表示也被用在EX和GI 中，启发式用来确定敌方的影响（GI）和领地区域（EX）。
    盘面（例如棋块、敌方）表示的对象属性包括它们的死活状态（也指安全性或生命力）、实地数、眼数和势。某些情况下这些属性值由战术搜索决定。
    MFG的表示方式中一些组件由评估函数控制（例如块、联接、眼、实地和势）。Go4的盘面只是简单的由评估函数（例如块、眼、安全性、实地）来表示。

3.2 候选走法
    通常，由模式或更常见的是由基于规则的专家系统产生候选走法。走子产生过程最后是通过（线性的或加权求和的）相加棋盘上所有点的参考值为合适的走法给出一个分值。全盘评估一般选最高得分点作为下一手的落子点。
    不同程序由全局水平变量估值得出的候选走法数也有所不同：GI（陈，1997）有12手，MFG有10手，而Go4至少有50手。程序变量保持的规则数： EX大约100，MFG大约200。GI含有约20个走子算法，它们或者基于模式库，或者基于面向目标的搜索，或者基于启发式规则（可能含有大量的规 则）。
    模式通常既包含低级信息也包含高级信息。低级信息与黑白子的位置有关，那些点必须是空着的，已经被子占据的点不在此列。高级信息则是关于气的数量、安全 性、眼位和领地的信息。模式匹配不仅与子的配置匹配，而且跟包含在子或串里的任何高级需求有关。大量的模式匹配计算是很耗时的，并且由于棋盘上的对称性而 变得更复杂。这已经导致了发展特殊算法来克服与模式匹配有关的问题（比如MFG的哈希函数，EX的串匹配）。
    知识以不同的方式组合到程序当中：一些程序几乎完全依据第一原则工作，另一些根据存储的模式匹配当前位置。不同的程序其模式数量相差很大：Go4约有15 个；MFG大约2000个；而EX则在3000个左右。有些程序也包含开放的走法模式数据库（定式）（例如，MFG含有约45，000个定式模式）。

3.3 目标  
    多数情况下，大量的实地比起少量的实地加相应的外势更合乎需要。尽管有时也存在着实地和外势间地转化（特别是在布局和中盘阶段）。然而，虽然实地的启发式 评估是可能的，实地依然不总是形势优劣最好的指示明灯。在对局的早期阶段，占有大量的实地可能表明一种过于集中的形势，从实地安全的角度看，这样的形对对 局的后面阶段或许是有害的。开局造就最大可能的势而不是实地通常导致局末对更多实地的追求。外势是可能用来确定形势优劣的子目标的一个例子。
    用来确定形势优劣的大量子目标的相对优先度在电脑围棋中看来没有一致性可言。典型的块和实地的死活状态（安全性）被包含在目标和子目标中。在手谈中，战术 手段是重点，而MFG集中在联接性、眼和块的生命力。Go4则好像完全贯注于联接性上，几乎任何东西都是从联接概率图上派生（直接或间接地）出来。

3.4 评估过程
    评估围棋的形势是个很慢的过程（例如，比起国际象棋程序的每秒10,000-100,000次评估，MFG是以低于每秒10次的速度完成对整局棋不超过 10,000种全盘形势的评估）。由于比赛时间的限制，程序执行的全局评估数通常是有限的（例如，MFG在选择下一步时全局的评估数不超过100）。
    Go4的50种候选走法中每一个都通过一个六步的过程来评估：1.启用一个联接概率图。对于盘面上的每一个黑子和白子，计算它与32个（实际的或假定的） 友好点的联接概率（要处理大量的数据）。确定联接性还要用到战术搜索；2.棋块由联接图和战术搜索来确定；3.眼位（利用模式）由联接性和棋块数据确定； 4.眼位的数量确定了棋块的安全性；5.每个子的安全性按联接概率图的比率辐射并在所有棋子上相加；6.黑白领地由辐射值估计。黑白领地的差别作为一个给 定走法的评估结果返回。
    MFG的评估是个多步过程，并且在很大程度上依赖于战术搜索。战术搜索检查所有少于四口和一部分有四口气的串以确定是不是死串。战术搜索也被用来鉴别联接 性和眼位。在这一环节，串组成了棋块。棋块的生命力由基于死活的考虑（例如，联接、眼位等）决定，并且用来确定黑白子在盘面每个点（在-50至+50的范 围之间）行使控制的总量统计。在总和每个点的值的基础上确定领地，给出最终的估计值。多达6轮的静态搜索可以被执行，有时用一个特殊的模式集找出能使形势 稳定下来的局部走法。
    GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法，它就被选为要走的下一步。如果候选走法中有些走法的得分大致相 等，靠评估带来方便的全局搜索决定选择走哪一步。评估时，敌子的安全性是为盘上每个点指定一个在-64到+64之间的黑白控度的基础，所有点的分值加起来 返回一个评估值。全局搜索检查的步数不多于6到7步，搜索的深度不超过6层。

3.5 战术搜索
    战术搜索是有选择的、面向目标的搜索，并且为一大堆目的而使用，包括确定串是死是活（Go4，MFG，EX，GI）、联接是安全的还是可被切断的 （Go4，MFG）、是否可以形成眼位（MFG）、产生候选走法（GI）和确定棋块的死活（EX）。就是在全局的水平，战术搜索也要用来做棋步产生和评 估。战术评估和全盘评估有区别，这跟搜索的目标（例如，一个串的气的数量）有关。由于时间上的制约，战术搜索通常在节点数、枝因子和层的深度上受到限制。 因此，尽管象死活这类的问题通常被认为是战术性的，棋子却可以在战略上就死去了，即使它们可能不能通过战术手段被抓获。由此，从围棋评估的方方面面看，战 术搜索只是一种启发式装备而已。
    MFG提供了一个战术搜索操作的很好的例证（通过“战术家”）：每个有三口或更少的气的串和许多有四口气的串被“战术家”检查过。每个串检查两次，一次白 先走一次黑先走。“战术家”决定一个串是否被抓（比如，即使它先走也不能活）、被威胁（比如，如果它先走则活，后走则死），或者是牢固的。“战术家”依靠 简单的启发式（例如，气数和联接性）。
    “战术家”有两个分离的走子器；一个执行攻击走法，一个执行防卫走法。走子器建议的走法按一些规则分类，这些规则包括二次气（气的气）、切点和简单的眼 形。一旦分类，根据依赖走法分类的质量的搜索的表现，一种α-β深度优先搜索被派上用场。走子和分类解释了多数时间依靠战术搜索的原因。
    战术搜索直接针对目标并被限制一个最大节点数。抓子时这个限制是大约100，然而当只有一步可走时就不考虑这个限制。采用这种方式，可以毫不费力地确定征 子的胜方。根据第一层走子产生赋予走法的分值，一次搜索的节点数分配到树枝中，因此不同的树枝可能在不同的深度结束。每一成功的层的枝因子被“战术家”逐 步强化；枝因子从第一层5降到第五层的1或2。
    对局过程中，MFG作大约100,000-150,000次战术搜索，以每秒2,000-2,500个节点的速度遍历1.5-2百万个节点。平均起来每次战术搜索访问约10-20个节点，尽管由于一些搜索因节点限制而终止，许多搜索访问过节点数要少于5个。

3.6 死活搜索
    不是所有的程序都做明确的死活分析，很多程序对此使用了战术搜索。MFG用与它的战术搜索过程类似的方式作死活分析，除了它是在块上作死活分析而不是分析串。
    一个静态死活评估器在多步过程中确定每个块的死活状态，而没有以从简单的结构中进一步产生复杂结构的方式向前搜索。静态死活评估器使用“战术家”并且为棋块中的每个合适的串至少调用两次。
    死活搜索是直接面向目标的（例如，拯救或杀死一个棋块）。如果在一个特定点没有获得搜索目标，合适走法由死活搜索引擎自身的走法器产生，并继续搜索。为了 在一次死活搜索期间确定目标是否已经达到，静态死活评估器在每个点被调用。死活搜索引擎使用深度优先α、β搜索，每一个特定的枝的搜索深度由启发式决定。 搜索树的大小是强制性的，通常可以达到7层的深度和20个节点的大小。死活搜索是很慢的，整棵树要装到缓存里以减少花在重复搜索上的开销。死活搜索的缓慢 也意味着它不会被用在全盘评估中。

3.7 势函数
    势是一种围棋概念，它表明了每一方棋子对空点的最大可能的控制潜力。通过确保开局时子力投放不过于集中，棋手在后面的对局中将取得最大限度获得领地的机会。
    势通过势函数建立可计算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盘上每个点的辐射影响值的和（黑白子 辐射正负相反的值）对周边的点施加辐射影响（MFG的黑白子的势是分离的）。子力辐射按距离函数递减：GI是2的距离次方分之一，MFG是距离分之一。但 过于依赖势函数的程序表现不佳（EX和Go4不再使用势函数，尽管Go4的辐射函数很象一个势函数，EX采取另一些措施，象同色点或可联接点的距离）。
    应用势的启发包括确定联接性和敌子（GI），以及确定领地（MFG）。MFG的块势初始值依赖于块的强度等，强壮的块比弱块或将死的块辐射更大的影响。这 也意味着死块辐射负影响等，因为它对敌方有利。在MFG和GI中势都没有通过子辐射；MFG也没有通过敌链辐射影响。

4． 讨论
    当前的围棋程序都使用了一定量的“知识”。由于建立在设计者下棋成功经验的启发之上，每个程序都可被看作一种（可能是含蓄的）围棋理论的一次以经验为依据 的实验。围棋理论成立的关键要靠数据结构的选择，因为它们决定了编码不同类型知识的难易和应用这些知识的计算开销。随着程序员同时在围棋和电脑围棋方面获 得技能，程序会有发展（例如，在过去的十五年中随着 Fotland 的棋力从15级发展到2段，MFG也增长了棋力并且代码长度增加到目前的4万行）。程序的性能由它最弱的部件决定，而向程序增加新知识的难易是提高程序性 能的重要部分。
    由此可见，电脑围棋领域在关于怎样构筑一个围棋程序或者指配不同围棋知识的优先性（例如，Go4注重联接性而MFG注重死活）方面还没有一致性可言。必须 提到的一点是：关于人类是怎样下围棋的至今也没个一致的说法，这是目前认知科学研究的一个课题（见Saito & Yoshikawa，1977，作为回顾）。这个领域的任何进展都会对围棋理论有个直接的促进，并可能导致电脑围棋程序算法的改进。
    本文对目前比较成功的几个程序作了比较。通过这项工作，我们在博弈树搜索的框架内分析了围棋，并通过对示例电脑围棋编程的观察把有关的问题暴露出来。这种 困难在电脑围棋领域是常识，但在更为广泛的人工智能范畴却很少被人们认识和接受。围棋全盘评估需要确定棋块的死活状态，不管是通过死活搜索还是战术搜索， 评估是非常消耗计算资源的。缺乏快速有效的评估函数是电脑围棋遭遇的一个基本问题，并且和巨大的树枝因素、用户和电脑比赛的实时需求（一般来说，相对于国 际象棋的每秒180步围棋每秒只有24步）等搅和在一起。因此，计算机国际象棋通常要用到的完全广度博弈树搜索在电脑围棋里是行不通的。
    除了所列出的围棋领域固有的问题外，本文还探讨当前的程序怎样地处理这些问题，由此为未来的围棋程序员提供一个跳板。请注意电脑围棋是个商业的领域，程序 本身（不是学术论文）就是它的主要产品。跟其它的参考不同的是，这里报告的细节都已经通过个人交流征询了（慷慨贡献自己的知识的）程序作者本人的意见，并 且有相关的电脑围棋邮件列表和FTP站点的信息为依据。
    电脑围棋的挑战性在于要扩展当前的围棋理论或发展新理论——特别是与评估有关的，针对实时限制设计合适的数据结构和算法，解决知识瓶颈。目前还没有一个有 力的程序使用学习技术，尽管有过几次这样的尝试（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）。回顾这些程序已经超出了本文的范围，但我们推测这些程序也没有成功，因为它们的设计者的含蓄的围棋理论缺乏对围棋复杂性的必 要理解。怎样把学习能力赋予现有的程序（或者它们暗示的围棋理论）是个等待解决的问题。

致谢
    感谢Ken Chen、陈志行、David Fotland、Martin Muller 和Mick Reiss，他们向我们提供了有关程序的细节和对本文不无裨益的反馈。  

参考文献  
Allis, V.Searching for solutions in games and artificial intelligence. PhD thesis, University of Limburg, Maastricht, 1994.
Burmeister, J.&Wiles, J. The challenge of Go as a domain for AI research: a comparison between Go and chess. In proceedings of the Third Australian and New Zealand Conference on Intelligent Information System, pages 181-186, Perth, November 1995. IEEE Western Australia Section.
Chen, K. Group Identification in Computer Go. In D.N.L.Levy and B.F.Beal, (eds), Heuristic Programming in Aritificial Intelligence: the First Computer Olympiad, pages 195-210. Ellis Horwood, Chichester, 1989.
Chen, K. The move decision process of Go Intellect. In David Erbach, editor, Computer Go, 14: 9-17, 1990.
Chen, K. Attack and defence. In H. J. Van den Herik and L. V. Allis,(ed)s, Heuristic Programming in Artificial Intelligence 3 - The Third Computer Olympiad, pages 146-156. Ellis Horwood, Chichester, 1992.
Donnelly, P., Corr, P., and Crookes, D. Evolving Go playing strategy in neurl networks, 1994. Available on the Internet at ftp://igs.nuri.net/Go/comp/egpsnn.ps.z.
Fotland, D. Knowledge representation in The Many Faces of Go,1993. Available on the Internet at ftp://igs.nuri.net/Go/comp/mfg.z.
Lishtenstein, D. & Sipser, M. Go is polynomial-space hard. Journal of the ACM, 27(2):393-401, 1980.
Muller, M. Computer Go as a sum of local games: an application of combinatorial game theory. PhD thesis, Swiss Federal Institute of Technology Zurich, 1995.
Pell, B. Exploratory learning in the game of Go. In D. N. L. Levy and D.F. F. Beal,(eds), Heuristic Programming in Artificial Intelligence 2 - The Second Computer Olympiad, volume 2. Ellis Horwood, 1991
Robson, J. The complexity of Go. In R. E. A. Mason, (ed), Proceedings of the IFIP 9th World Computer Congress, pages 413-417, North Holland, 1983. IFIP, Elsevier Science Publishers.
Ryder, J. Heuristic analysis of large trees as generated in the game of Go. Phd thesis, Department of Computer Science, Standford University, 1971.
Saito, Y. & Yoshikawa, A. Go as a testbed for Cognitive Science studies. In IJCAI Workshop Proceedings Using Games as an Experimental Testbed for AI Research, 1997.
Schraudolph, N., Dayan, P. and Sejnowski, T. Temporal difference learning of position evaluation in the game of Go. In J. D. Cowan, G. Tesauro and J. Alspector, (eds), Advances in Neural Information Processing 6, pages 817-824. Morgan Kaufmann, San Francisco, 1994.
Zorbrist, A. Amodel of visual organization for game Go. In Proceedings of the Spring Joint Computer Conference, 34: 103-112, 1969.
Zorbrist, A. Feature extractions and representation for pattern recognition and the game of Go. PhD thesis, Graduate School of the University of Wisconsin, 1970.