电脑围棋中的人工智能技术 Jay Burmeister 和 Janet Wiles澳大利亚昆士兰大学心理学与信息技术学院http://www.psy.uq.edu.au/~jay/翻译：Lookingfor摘要本文通过对几个顶尖电脑围棋程序的研究，从认知科学的角度介绍了电脑围棋，并特别针对电脑围棋编程人员（或有意投身于此的程序员）说明围棋作为一 个认知科学研究领域的日益增长的重要性。对于手谈、Go4 、Many Faces of Go、Go Intellect 和Explorer等几个目前最优秀的电脑围棋程序，我们概要介绍了这些程序所涉及的人工智能技术，不得不面对的关键性挑战和博弈树搜索所牵涉的问题，由 此揭示在围棋领域不能很好地移植计算机国际象棋技术的原因。

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.黑白领地由辐射值估计。黑白领地的差别作为一个给定走法的评估结果返回。

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