第2卷第3期 智能系统学报 Vol.2 Ne 3 2007年6月 CAAI Transactions on Intelligent Systems Jun.2007 使用不同的博弈树搜索算法解决 计算机围棋的吃子问题 张培刚，陈克训 (Department of Computer Science,University of North Carolina at Charlotte,Charlotte NC 28223,USA) 摘要：使用AlpharBeta搜索和proof-number(pn)搜索解决计算机围棋的吃子问题.对吃子问题形式化并给出了 简单有效的评估函数.Alpha-Beta搜索使用了包括置换表在内的各种扩展技术.pn搜索使用了包括dfpn在内的4 种变体.研究结果显示，对于解决吃子问题pn搜索优于Alpha-Beta搜索.并且搜索过程中所产生的数据的一些模式 可以帮助在结果未知的情况下对结果进行预测，所设计的算法可以用于解决单独的吃子问题或者计算机围棋比赛 中的吃子计算 关键词：计算机围棋；博弈树搜索；启发式搜索；AlphaBeta搜索proof-number搜索；吃子问题 中图分类号：TP18文献标识码：A文章编号：16734785(2007)03008407 Using different search algorithms to solve computer Go ca pturing problems ZHAN G Pei-gang ,CHEN Kehhsun (Department of Computer Science,University of North Carolina at Charlotte,Charlotte NC 28223,USA) Abstract:The capturing problem is an important tactical sub-problem in computer Go.Alpha-Beta() search and proof-number (pn)searches are used to solve computer Go capturing problems with the same e- valuation function.The performance of the capturing algorithm is favorable and practical.The algorithm could be used to solve post game capturing problems or to perform real time capturing calculations in com- puter Go tournament matches.Our results show that pmsearch is superior to-search at solving capturing problems.Some patterns can be found in the searching process that could help predict the search outcome when it is still unknown.Our work also provides a framework that could be used to solve other computer Go subproblems and other games. Keywords:computer Go:game tree search:Heuristic search:Alpha-Beta search:proof-number search; block capturing 博弈树搜索算法是博弈程序的核心组成部分」 好地解决这些战术问题 Alpha-Beta搜索是最广泛使用的博弈树搜索算法， 文中尝试使用不同的树搜索算法解决围棋的吃 pn搜索对于解决非对称博弈树问题也非常有效 子问题.首先设计和实现了Alpha-Beta搜索及其扩 面对博弈程序设计人员的一些问题包括： 展和pn搜索及其变体去解决吃子问题.进一步对 1)每种搜索算法的特性是什么？2)对于解决一 这些算法的结果进行比较并总结不同算法的特征： 类特定问题哪种搜索算法比较好？3)如何将搜索算 最后对搜索过程中产生的数据进行分析并发现一些 法嵌入博弈程序用于实时地解决问题？计算机围棋 模式可以用于对搜索结果进行预测.这个吃子算法 是当前人工智能领域的一大难题.计算机围棋包括 的表现是出色和实用的.这个算法可以用于解决单 很多战术问题例如死活问题·】、吃子问题到和连 独的吃子问题或者计算机围棋比赛中的吃子计算 接问题.构建一个强大的计算机围棋程序需要很 结果显示，对于解决吃子问题pn搜索优于Alpha Beta搜索.并且发现搜索过程中的一些模式可以帮 收稿日期：20060821. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 2 卷第 3 期 智 能 系 统 学 报 Vol. 2 №. 3 2007 年 6 月 CAA I Transactions on Intelligent Systems J un. 2007 使用不同的博弈树搜索算法解决 计算机围棋的吃子问题 张培刚 ,陈克训 (Department of Computer Science , University of North Carolina at Charlotte , Charlotte NC 28223 , USA) 摘 要 :使用 Alpha2Beta 搜索和 proof2number (pn) 搜索解决计算机围棋的吃子问题. 对吃子问题形式化并给出了 简单有效的评估函数. Alpha2Beta 搜索使用了包括置换表在内的各种扩展技术. pn 搜索使用了包括 df2pn 在内的 4 种变体. 研究结果显示 ,对于解决吃子问题 pn 搜索优于 Alpha2Beta 搜索. 并且搜索过程中所产生的数据的一些模式 可以帮助在结果未知的情况下对结果进行预测. 所设计的算法可以用于解决单独的吃子问题或者计算机围棋比赛 中的吃子计算. 关键词 :计算机围棋 ;博弈树搜索 ;启发式搜索 ;Alpha2Beta 搜索 ;proof2number 搜索 ;吃子问题 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0320084207 Using different search algorithms to solve computer Go capturing problems ZHAN G Pei2gang ,CH EN Keh2hsun (Department of Computer Science , University of North Carolina at Charlotte , Charlotte NC 28223 , USA) Abstract :The capturing problem is an important tactical sub2problem in comp uter Go. Alp ha2Beta ( ) search and proof2number (p n) searches are used to solve comp uter Go capt uring problems wit h t he same e2 valuation f unction. The performance of t he capt uring algorithm is favorable and practical. The algorit hm could be used to solve post game capt uring problems or to perform real time capt uring calculations in com2 p uter Go tournament matches. Our results show that p n2search is superior to2search at solving capt uring problems. Some patterns can be found in the searching process t hat could help predict t he search outcome when it is still unknown. Our work also provides a framework that could be used to solve ot her comp uter Go sub2problems and ot her games. Keywords : comp uter Go ; game tree search ; Heuristic search ; Alp ha2Beta search ; proof - number search ; block capt uring 收稿日期 :2006208221. 博弈树搜索算法是博弈程序的核心组成部分. Alp ha2Beta 搜索是最广泛使用的博弈树搜索算法. p n 搜索对于解决非对称博弈树问题也非常有效. 面对博弈程序设计人员的一些问题包括 : 1) 每种搜索算法的特性是什么 ? 2) 对于解决一 类特定问题哪种搜索算法比较好 ? 3) 如何将搜索算 法嵌入博弈程序用于实时地解决问题 ? 计算机围棋 是当前人工智能领域的一大难题. 计算机围棋包括 很多战术问题例如死活问题[ 1 - 2 ] 、吃子问题[3 ] 和连 接问题[4 ] . 构建一个强大的计算机围棋程序需要很 好地解决这些战术问题. 文中尝试使用不同的树搜索算法解决围棋的吃 子问题. 首先设计和实现了 Alp ha2Beta 搜索及其扩 展和 p n 搜索及其变体去解决吃子问题. 进一步对 这些算法的结果进行比较并总结不同算法的特征. 最后对搜索过程中产生的数据进行分析并发现一些 模式可以用于对搜索结果进行预测. 这个吃子算法 的表现是出色和实用的. 这个算法可以用于解决单 独的吃子问题或者计算机围棋比赛中的吃子计算. 结果显示 ,对于解决吃子问题 ,p n 搜索优于 Alp ha2 Beta 搜索. 并且发现搜索过程中的一些模式可以帮