《电脑围棋中的人工智能技术.doc》由会员分享，可在线阅读，更多相关《电脑围棋中的人工智能技术.doc（8页珍藏版）》请在金锄头文库上搜索。
1、本文研究了几个最出色的电脑围棋程序，从认知科学的角度介绍了电脑围棋程序和相关人工智能技术。Jay Burmeister 和 Janet Wiles澳大利亚昆士兰大学心理学与信息技术学院jayit.uq.edu.au http:/www.psy.uq.edu.au/jay/翻译：Lookingfor摘要：本文通过研究几个最出色的电脑围棋程序，从认知科学的角度介绍了电脑围棋，并特别针对电脑围棋编程人员（或有意投身于此的程序员）揭示围棋作为一个认知科学研究领域的日益增长的重要性。对手谈，Go4+，Many Faces of Go，Go Intellect 和Explorer几个目前最优秀的电脑围棋程
2、序，我们概括了它们用到的人工智能技术，必须面对的关键性挑战和博弈树搜索中牵涉的问题，以此揭示为什么计算机国际象棋技术不能被很好的移植到围棋领域。1挑战围棋的程序作为正规游戏之一的围棋领域，过去即便是应付一般的人类棋手计算机也难以有所作为。几个一年一度的电脑围棋赛事，如FOST杯赛为第一名提供2，000，000日元奖金，台湾的应氏基金为第一个能在分先七番棋中击败顶尖职业棋手的围棋程序许诺40万美元的奖金。最早以围棋为对象把电脑围棋纳入研究工作是在1962年，尽管第一次由程序下一盘完整的棋是发生在1968年（Zobrist，1970）。随着电脑围棋赛事的举行和第一个商业程序的发放，电脑围棋作为一个
3、领域于80年代被正式创立，并在90年代变得兴旺起来。目前活跃在电脑围棋竞赛中的顶尖程序有Explorer，Go Intellect，Go4+，手谈和The Many Faces of Go，它们的水平大致在4-8级之间。2围棋中的博弈树搜索二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准博弈树搜索由四部分组成：1状态表示，2候选走法产生，3确定目标状态，以及4一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如-）增强了程序的表现。博弈树这条途径很成功，如我们在国际象棋程序中所看到的，基于典型的完全广度-剪枝博弈树搜索的程序甚至击败了世界冠军。这一节我们从透视电脑
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格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。接下来的层面的描述是把
5、正交的邻接棋子组成串（或链）。所有的程序把串搜集到更大的单元，然而没有通用的处理方法即便是对专业棋手来说把串组合到更大的单元中。依靠他们的围棋理论，程序员开发了他们自己的启发式，当串有效的连接在一起时用做评估之用（叫做模糊组或块）。另外，恰当层次的表示能改变对运行时子任务的依赖，例如，战术分析，死活分析，或实地评估。2.2 走子棋手在禁止自杀和同型反复（劫）的规则限制下轮流把棋子投放在空的交叉点（包括角和边）。象国际象棋一样，围棋在给定位置的上下文中只有所有合法走法中的一部分是有效的。围棋的平均分枝因子是很大的，大约是国际象棋的六倍（200对35，Burmeister & Wiles，1995
6、）。注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如，直接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。实际的走子是个复杂的问题：参见3.4部分。2.3 目标状态围棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地：建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态，因为实地的获得是靠慢慢积累起来的（不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上）。由于在接近终局前很难精确地计算实地，故启发式估计用的较多。这样的启发方式通常要归并组件和指示领地安全潜力的（例如死活组和影响）次要目标（例如国际象棋里的材料优势
7、）。当对局双方依次弃权时结束。棋手通常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上，要确定对局结束（即何时弃权）是相当困难的。人们下棋，计算结果时如果遇到有关死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中，如果程序出现算法不能解决的得分争执，计分就由组织比赛的人员来做。2.4 评估函数在判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来获得的。有意思的是，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争中是可活的（即它必须赢得打劫来使自己活下来
8、），就必须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一个绝对的死活回答可能超出了战术或死活搜索的范围。从复杂的类型分析看，由一个绝对位置来确定赢家是P空间难题（Lichtenstein & Sipser，1980），决定一个棋手能否左右输赢需指数时间来完成（Robson，1983），由此也就不奇怪要用到启发式了。这些理论结果显示不存在从一个绝对局势出发决定领地结果的多项式时间算法。3参赛程序里的博弈树搜索和人工智能技术当前活跃在各电脑围棋赛事里的程序有Mar
9、tin 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）和领地区
10、域（EX）。盘面（例如棋块、敌方）表示的对象属性包括它们的死活状态（也指安全性或生命力）、实地数、眼数和势。某些情况下这些属性值由战术搜索决定。MFG的表示方式中一些组件由评估函数控制（例如块、联接、眼、实地和势）。Go4的盘面只是简单的由评估函数（例如块、眼、安全性、实地）来表示。3.2 候选走法通常，由模式或更常见的是由基于规则的专家系统产生候选走法。走子产生过程最后是通过（线性的或加权求和的）相加棋盘上所有点的参考值为合适的走法给出一个分值。全盘评估一般选最高得分点作为下一手的落子点。不同程序由全局水平变量估值得出的候选走法数也有所不同：GI（陈，1997）有12手，MFG有10手，而G
11、o4至少有50手。程序变量保持的规则数：EX大约100，MFG大约200。GI含有约20个走子算法，它们或者基于模式库，或者基于面向目标的搜索，或者基于启发式规则（可能含有大量的规则）。模式通常既包含低级信息也包含高级信息。低级信息与黑白子的位置有关，那些点必须是空着的，已经被子占据的点不在此列。高级信息则是关于气的数量、安全性、眼位和领地的信息。模式匹配不仅与子的配置匹配，而且跟包含在子或串里的任何高级需求有关。大量的模式匹配计算是很耗时的，并且由于棋盘上的对称性而变得更复杂。这已经导致了发展特殊算法来克服与模式匹配有关的问题（比如MFG的哈希函数，EX的串匹配）。知识以不同的方式组合到程序
12、当中：一些程序几乎完全依据第一原则工作，另一些根据存储的模式匹配当前位置。不同的程序其模式数量相差很大：Go4约有15个；MFG大约2000个；而EX则在3000个左右。有些程序也包含开放的走法模式数据库（定式）（例如，MFG含有约45，000个定式模式）。3.3 目标多数情况下，大量的实地比起少量的实地加相应的外势更合乎需要。尽管有时也存在着实地和外势间地转化（特别是在布局和中盘阶段）。然而，虽然实地的启发式评估是可能的，实地依然不总是形势优劣最好的指示明灯。在对局的早期阶段，占有大量的实地可能表明一种过于集中的形势，从实地安全的角度看，这样的形对对局的后面阶段或许是有害的。开局造就最大可能
13、的势而不是实地通常导致局末对更多实地的追求。外势是可能用来确定形势优劣的子目标的一个例子。用来确定形势优劣的大量子目标的相对优先度在电脑围棋中看来没有一致性可言。典型的块和实地的死活状态（安全性）被包含在目标和子目标中。在手谈中，战术手段是重点，而MFG集中在联接性、眼和块的生命力。Go4则好像完全贯注于联接性上，几乎任何东西都是从联接概率图上派生（直接或间接地）出来。3.4 评估过程评估围棋的形势是个很慢的过程（例如，比起国际象棋程序的每秒10,000-100,000次评估，MFG是以低于每秒10次的速度完成对整局棋不超过10,000种全盘形势的评估）。由于比赛时间的限制，程序执行的全局评估
14、数通常是有限的（例如，MFG在选择下一步时全局的评估数不超过100）。Go4的50种候选走法中每一个都通过一个六步的过程来评估：1.启用一个联接概率图。对于盘面上的每一个黑子和白子，计算它与32个（实际的或假定的）友好点的联接概率（要处理大量的数据）。确定联接性还要用到战术搜索；2.棋块由联接图和战术搜索来确定；3.眼位（利用模式）由联接性和棋块数据确定；4.眼位的数量确定了棋块的安全性；5.每个子的安全性按联接概率图的比率辐射并在所有棋子上相加；6.黑白领地由辐射值估计。黑白领地的差别作为一个给定走法的评估结果返回。MFG的评估是个多步过程，并且在很大程度上依赖于战术搜索。战术搜索检查所有少
15、于四口和一部分有四口气的串以确定是不是死串。战术搜索也被用来鉴别联接性和眼位。在这一环节，串组成了棋块。棋块的生命力由基于死活的考虑（例如，联接、眼位等）决定，并且用来确定黑白子在盘面每个点（在-50至+50的范围之间）行使控制的总量统计。在总和每个点的值的基础上确定领地，给出最终的估计值。多达6轮的静态搜索可以被执行，有时用一个特殊的模式集找出能使形势稳定下来的局部走法。GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法，它就被选为要走的下一步。如果候选走法中有些走法的得分大致相等，靠评估带来方便的全局搜索决定选择走哪一步。评估时，敌子的安全性是为盘上每个点指
16、定一个在-64到+64之间的黑白控度的基础，所有点的分值加起来返回一个评估值。全局搜索检查的步数不多于6到7步，搜索的深度不超过6层。3.5 战术搜索战术搜索是有选择的、面向目标的搜索，并且为一大堆目的而使用，包括确定串是死是活（Go4，MFG，EX，GI）、联接是安全的还是可被切断的（Go4，MFG）、是否可以形成眼位（MFG）、产生候选走法（GI）和确定棋块的死活（EX）。就是在全局的水平，战术搜索也要用来做棋步产生和评估。战术评估和全盘评估有区别，这跟搜索的目标（例如，一个串的气的数量）有关。由于时间上的制约，战术搜索通常在节点数、枝因子和层的深度上受到限制。因此，尽管象死活这类的问题通常被认为是战术性的，棋子却可以在战略上就死去了，即使它们可能不能通过战术手段被抓获。由此，从围棋评估的方方面面看，战术搜索只是一种启发式装备而已。MFG提供
