AI 版 (精华区)

发信人: yale (AI*PP*心如止水), 信区: AI
标  题: 电脑围棋中的人工智能技术
发信站: 哈工大紫丁香 (2003年12月13日09:44:54 星期六), 站内信件

发信人: yi127 (青松), 信区: AI
标  题: [转载]电脑围棋中的人工智能技术
发信站: 南京大学小百合站 (Sat Oct 25 09:24:01 2003)


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

Jay Burmeister 和 Janet Wiles
澳大利亚昆士兰大学心理学与信息技术学院
jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/

翻译：Lookingfor



摘要

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



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 & Wi
les，1995）。
注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如，直
接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。
实际的走子是个复杂的问题：参见3.4部分。

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

2.4 评估函数
在判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是
典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来获得的。有意思的是
，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争
中是可活的（即它必须赢得打劫来使自己活下来），就必须估算所有和对手相比用来决定
棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。

评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一
个绝对的死活回答可能超出了战术或死活搜索的范围。
从复杂的类型分析看，由一个绝对位置来确定赢家是NP空间难题（Lichtenstein & Sipse
r，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手，MF
G有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的距离次方分之一，MF
G是距离分之一。但过于依赖势函数的程序表现不佳（EX和Go4不再使用势函数，尽管Go4的
辐射函数很象一个势函数，EX采取另一些措施，象同色点或可联接点的距离）。
应用势的启发包括确定联接性和敌子（GI），以及确定领地（MFG）。MFG的块势初始值依
赖于块的强度等，强壮的块比弱块或将死的块辐射更大的影响。这也意味着死块辐射负影
响等，因为它对敌方有利。在MFG和GI中势都没有通过子辐射；MFG也没有通过  链辐射影
响。

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

电脑围棋的挑战性在于要扩展当前的围棋理论或发展新理论——特别是与评估有关的，针
对实时限制设计合适的数据结构和算法，解决知识瓶颈。目前还没有一个有力的程序使用
学习技术，尽管有过几次这样的尝试（如，Pell，1991；Schraudolph, Dayan & Sejnows
ki，1994；Donnelly, Corr & Crookes，1994）。回顾这些程序已经超出了本文的范围，
但我们推测这些程序也没有成功，因为它们的设计者的含蓄的围棋理论缺乏对围棋复杂性
的必要理解。怎样把学习能力赋予现有的程序（或者它们暗示的围棋理论）是个等待解决
的问题。


　

致谢

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

　

参考文献

Allis, V.Searching for solutions in games and artificial intelligence. PhD the
sis, University of Limburg, Maastricht, 1994.
Burmeister, J.&Wiles, J. The challenge of Go as a domain for AI research: a co
mparison between Go and chess. In proceedings of the Third Australian and New
Zealand Conference on Intelligent Information System, pages 181-186, Perth, No
vember 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 Olymp
iad, pages 195-210. Ellis Horwood, Chichester, 1989.
Chen, K. The move decision process of Go Intellect. In David Erbach, editor, C
omputer Go, 14: 9-17, 1990.
Chen, K. Attack and defence. In H. J. Van den Herik and L. V. Allis,(ed)s, Heu
ristic 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 o
n 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 combinatoria
l 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 Co
mputer Olympiad, volume 2. Ellis Horwood, 1991
Robson, J. The complexity of Go. In R. E. A. Mason, (ed), Proceedings of the I
FIP 9th World Computer Congress, pages 413-417, North Holland, 1983. IFIP, Els
evier Science Publishers.
Ryder, J. Heuristic analysis of large trees as generated in the game of Go. Ph
d thesis, Department of Computer Science, Standford University, 1971.
Saito, Y. & Yoshikawa, A. Go as a testbed for Cognitive Science studies. In IJ
CAI Workshop Proceedings Using Games as an Experimental Testbed for AI Researc
h, 1997.
Schraudolph, N., Dayan, P. and Sejnowski, T. Temporal difference learning of p
osition evaluation in the game of Go. In J. D. Cowan, G. Tesauro and J. Alspec
tor, (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 an
d the game of Go. PhD thesis, Graduate School of the University of Wisconsin,
1970.



--


--
As we know,there are known knowns.There are things we know we know.
We also know there are known unknowns. That is to say
We know there are somethings we do not know.
But there are also unknown unknowns, the ones we don't know we don't know
               -Rumsfeld

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.104]