围棋中电脑人智能技术

电脑围棋中人工智能技术
摘要:本文通过研究几个最出色电脑围棋从认知科学角度介绍了电脑围棋并特别针对电脑围棋编程人员(或有意投身于此员)揭示围棋作为个认知科学研究领域日益增长重要性对手谈Go4ManyFacesofGoGoIntellect和Explorer几个目前最优秀电脑围棋我们概括了它们用到人工智能技术必须面对关键性挑战和博弈树搜索中牵涉问题以此揭示为什么计算机国际象棋技术不能被很好移植到围棋领域
奇境小站(WonderLand)1998.06--2000.06Webmaster:KerryJia
电脑围棋中人工智能技术作者:JayBurmeister和JanetWiles
澳大利亚昆士兰大学心理学和信息技术学院[email protected]://www.psy.uq.edu.au/~jay/翻译:Lookingfor

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

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

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

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

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

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


评估结果有时不确定明确死活定义在受限战术搜索里也许是不可能即个绝对死活回答可能超出了战术或死活搜索范围 [Page]
从复杂类型分析看由个绝对位置来确定赢家是P空间难题(Lichtenstein&Sipser1980)决定个棋手能否左右输赢需指数时间来完成(Robson1983)由此也就不奇怪要用到启发式了这些理论结果显示不存在从个绝对局势出发决定领地结果多项式时间算法

3．参赛里博弈树搜索和人工智能技术
当前活跃在各电脑围棋赛事里有MartinMuller(1995)Explorer(EX)陈恳(陈1989；1990；1992)GoIntellect(GI)MichaelReissGo4(Go4)陈志行HandTalk(HT)以及DavidFotlandManyFacesofGo(MFG)针对第2节讨论博弈树搜索和围棋专用人工智能技术:战术搜索死活搜索和势我们报告这些细节

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

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

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

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



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

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

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

4．讨论
当前围棋都使用了定量“知识”由于建立在设计者下棋成功经验启发的上每个都可被看作种(可能是含蓄)围棋理论次以经验为依据实验围棋理论成立关键要靠数据结构选择它们决定了编码区别类型知识难易和应用这些知识计算开销随着员同时在围棋和电脑围棋方面获得技能会有发展(例如在过去十 5年中随着Fotland棋力从15级发展到2段MFG也增长了棋力并且代码长度增加到目前4万行)性能由它最弱部件决定而向增加新知识难易是提高性能重要部分
由此可见电脑围棋领域在有关怎样构筑个围棋或者指配区别围棋知识优先性(例如Go4注重联接性而MFG注重死活)方面还没有致性可言必须提到点是:有关人类是怎样下围棋至今也没个致说法这是目前认知科学研究个课题(见Saito&Yoshikawa1977作为回顾)这个领域任何进展都会对围棋理论有个直接促进并可能导致电脑围棋算法改进
本文对目前比较成功几个作了比较通过这项工作我们在博弈树搜索框架内分析了围棋并通过对举例电脑围棋编程观察把有关问题暴露出来这种困难在电脑围棋领域是常识但在更为广泛人工智能范畴却很少被人们认识和接受围棋全盘评估需要确定棋块死活状态不管是通过死活搜索还是战术搜索评估是非常消耗计算资源缺乏快速有效评估是电脑围棋遭遇个基本问题并且和巨大树枝原因、用户和电脑比赛实时需求(般来说相对于国际象棋每秒180步围棋每秒只有24步)等搅和在起因此计算机国际象棋通常要用到完全广度博弈树搜索在电脑围棋里是行不通


除了所列出围棋领域固有问题外本文还探讨当前怎样地处理这些问题由此为未来围棋员提供个跳板请注意电脑围棋是个商业领域本身(不是学术论文)就是它主要产品跟其它参考区别是这里报告细节都已经通过个人交流征询了(慷慨贡献自己知识)作者本人意见并且有相关电脑围棋邮件列表和FTP站点信息为依据 [Page]
电脑围棋挑战性在于要扩展当前围棋理论或发展新理论——特别是和评估有关针对实时限制设计合适数据结构和算法解决知识瓶颈目前还没有个有力使用学习技术尽管有过几次这样尝试(如Pell1991；Schraudolph,Dayan&Sejnowski1994；Donnelly,Corr&Crookes1994)回顾这些已经超出了本文范围但我们推测这些也没有成功它们设计者含蓄围棋理论缺乏对围棋复杂性必要理解怎样把学习能力赋予现有(或者它们暗示围棋理论)是个等待解决问题

致谢
感谢KenChen、陈志行、DavidFotland、MartinMuller和MickReiss他们向我们提供了有关细节和对本文不无裨益反馈

参考文献
Allis,V.Searchingforsolutionsingamesandarticialelligence.PhDthesis,UniversityofLimburg,Maastricht,1994.
Burmeister,J.&Wiles,J.ThechallengeofGoasadoforAIresearch:acomparisonbetweenGoandchess.InproceedingsoftheThirdAustralianandNewZealandConferenceonIntelligentInformation,pages181-186,Perth,November1995.IEEEWesternAustraliaSection.
Chen,K.GroupIdenticationinComputerGo.InD.N.L.LevyandB.F.Beal,(eds),HeuristicProgramminginAriticialIntelligence:theFirstComputerOlympiad,pages195-210.EllisHorwood,Chichester,1989.
Chen,K.ThemovedecisionprocessofGoIntellect.InDavidErbach,editor,ComputerGo,14:9-17,1990.
Chen,K.Attackanddefence.InH.J.VandenHerikandL.V.Allis,(ed)s,HeuristicProgramminginArticialIntelligence3-TheThirdComputerOlympiad,pages146-156.EllisHorwood,Chichester,1992.
Donnelly,P.,Corr,P.,andCrookes,D.EvolvingGoplayingstrategyinneurlnetworks,1994.AvailableontheInternetatftp://igs.nuri.net/Go/comp/egpsnn.ps.z. [Page]
Fotland,D.KnowledgerepresentationinTheManyFacesofGo,1993.AvailableontheInternetatftp://igs.nuri.net/Go/comp/mfg.z.
Lishtenstein,D.&Sipser,M.Goispolynomial-spacehard.JournaloftheACM,27(2):393-401,1980.
Muller,M.ComputerGoasasumoflocalgames:anapplicationofcombinatorialgametheory.PhDthesis,SwissFederalInstituteofTechnologyZurich,1995.
Pell,B.ExploratorylearninghegameofGo.InD.N.L.LevyandD.F.F.Beal,(eds),HeuristicProgramminginArticialIntelligence2-TheSecondComputerOlympiad,volume2.EllisHorwood,1991
Robson,J.ThecomplexityofGo.InR.E.A.Mason,(ed),ProceedingsoftheIFIP9thWorldComputerCongress,pages413-417,NorthHolland,1983.IFIP,ElsevierSciencePublishers.
Ryder,J.HeuristicanalysisoflargetreesasgeneratedhegameofGo.Phdthesis,DepartmentofComputerScience,StandfordUniversity,1971.
Saito,Y.&Yoshikawa,A.GoasatestbedforCognitiveSciencestudies.InIJCAIWorkshopProceedingsUsingGamesasanExperimentalTestbedforAIResearch,1997.
Schraudolph,N.,Dayan,P.andSejnowski,T.TemporaldferencelearningofpositionevaluationhegameofGo.InJ.D.Cowan,G.TesauroandJ.Alspector,(eds),AdvancesinNeuralInformationProcessing6,pages817-824.MorganKaufmann,SanFrancisco,1994.


Zorbrist,A.AmodelofvisualorganizationforgameGo.InProceedingsoftheSpringJoComputerConference,34:103-112,1969. [Page]
Zorbrist,A.FeatureextractionsandrepresentationforpatternrecognitionandthegameofGo.PhDthesis,GraduateSchooloftheUniversityofWisconsin,1970.

延伸阅读