<-上一篇/Previous Article 下一篇/Next Article->

[1]张培刚,陈克训.使用不同的博弈树搜索算法解决计算机围棋的吃子问题[J].智能系统学报,2007,2(3):84-90.
　ZHANG,Pei-gang,CHEN Keh-hsun.Using Different Search Algorithms to Solve Computer Go Capturing Problems[J].CAAI Transactions on Intelligent Systems,2007,2(3):84-90.

点击复制

使用不同的博弈树搜索算法解决计算机围棋的吃子问题

PDF下载 HTML

《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷: 2 期数: 2007年第3期页码: 84-90 栏目: 学术论文—人工智能基础出版日期: 2007-06-25

Title:: Using Different Search Algorithms to Solve Computer Go Capturing Problems

文章编号:: 1673-4785(2007)03-0067-07

作者:: 张培刚，陈克训; 北卡莱罗纳大学夏洛特分校计算机系，Charlotte, NC 28223美国

Author(s):: ZHANG, Pei-gang ，CHEN Keh-hsun; Department of Computer Science, University of North Carolina a t Charlotte, Charlotte, NC 28223, USA

关键词:: 计算机围棋; 博弈树搜索; 启发式搜索; AlphaBeta搜索; proofnumber搜索; 吃子问题

Keywords:: Computer Go; Game Tree Search; Heuristic Search; AlphaBeta; Proofnu mber Search; Block Capturing.

分类号:: TP18

文献标志码:: A

摘要:: 使用AlphaBeta搜索和proofnumber (pn) 搜索解决计算机围棋的吃子问题.对吃子问题形式化并给出了简单有效的评估函数.AlphaBeta搜索使用了包括置换表在内的各种扩展技术.Pn搜索使用了包括dfpn在内的4种变体.研究结果显示，对于解决吃子问题pn搜索优于AlphaBeta搜索.并且搜索过程中所产生的数据的一些模式可以帮助在结果未知的情况下对结果进行预测.所设计的算法可以用于解决单独的吃子问题或者计算机围棋比赛中的吃子计算.

Abstract:: Capturing problem is an important tactical subprobl e m in computer Go. We used AlphaBeta (pn) search and proofnumber (pn) search t o solve computer Go capturing problems with same evalutaion function. The perfor mance 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 computer Go tournament matches. Our results show that pnsearc h is superior than (pn)search on solving capturing problems. And we can find som e patterns in the searching process that could help us to predict the search out come when the outcome is still unknown. Our work also provides the framwork that could be used to solve other computer Go subproblems and other games.

参考文献/References:: ［1］KISHIMOTO A. Correct and efficient search algorithms in the presenc e of repetitions［D］.城市： University of Alberta, 2005.
［2］WOLF T. Forward pruning and other heuristic search techniques in tsume go ［J］.Information Sciences, 2000,122 (1) :59-76.
［3］CHEN K., ZHANG P. A heuristic search algorithm for capturing problems in g o［J］. ICGA Journal. 2006, 29 (4): 183-190.
［4］CHEN K. Soft and hard connectivity in go［A］. Proceedings of the 8th International Conference on Computer Science and Informatics［C］.城市，国家， 2005.
［5］BOUZY B, CAZENAVE T. Computer go: an AI oriented survey［J］. Artificial I ntelligence, 2001,132(1):39-103. 
［6］MULLER M. Computer go［J］. Artificial Intelligence, 2002, 134(1-2):145-17 9. 
［7］CHEN K. Computer go: knowledge, search, and move decision［J］.ICGA Journa l, 2001,24(4):203-215.
［8］CAZENAVE T. Abstract proof search, computers and games 2000［A］. LNCS 206 3［C］. Hamamatsu, Japan, 2000.
［9］THOMSEN T. LambdaSearch in game treeswith application to go［J］. ICG A Journal, 2000,23(4):203-217 .
［10］CAMPBELL M, HOANE A J, HSU F. Deep blue［J］ .Artificial Intelligence, 20 02, 134(1-2): 57-83. 
［11］JUNGHANNS A. Are there practical alternatives to alphabeta［J］ .I CCA J ournal,1998,21(1):14-32.
［12］ALLIS L V, MEULEN M, HERIK H J. Proofnumber search［J］. Artificial Inte lligence,66 (1994) (1): 91-124.
［13］SEO M, IIDA H, UITERWIJK J W H M. The PN*search algorithm: application t o TsumeShogi［J］. Artificial Intelligence, 2001, 129(1-2):253-277. 
［14］NAGAI A. Dfpn algorithm for searching and/or trees and its applications ［D］. Tokyo: University of Tokyo, 2002.
［15］KNUTH D, MOORE R. analysis of alpha-beta pruning［J］. Artificial Intelli gence,1975,6(4):293-326.
［16］ZOBRIST A L. A new hashing method with application for game playing［R］. Techn. Rep. #88, Univ. of Wisconsin, Madison, WI 53706 ,1970.
［17］CAMPBELL M., MARSLAND T. A comparison of minimax treesearch algorithms［ J］.Artificial Intelligence, 1983,20 (4): 347-367

相似文献/References:: [1]岳? 鹏,李太华,邱玉辉.对称无关的模式编码方法在定式学习中的应用[J].智能系统学报,2007,2(4):92.
　YUE Peng,LI Tai hua,QIU Yu hui.A pattern encoding method independent of symmetry applied in joseki learnin g[J].CAAI Transactions on Intelligent Systems,2007,2():92.

备注/Memo

收稿日期：2006-08-21.
作者简介：
张培刚，男，1973年生，博士研究生，主要研究方向为计算机围棋、人工智能、启发式搜索和机器学习等领域. E-mail：pzhang1@uncc.edu.
陈克训，男，1945年生，教授，博士.主要研究方向为启发式搜索、人工智能和计算理论等 .所研发的电脑围棋程序“棋慧”曾两获电脑围棋世界冠军和七次夺得计算机奥林匹亚竞赛金牌.发表在专业书籍和期刊上的著作四十余篇. E-mail：chen@uncc.edu.

更新日期/Last Update: 2009-05-07

使用不同的博弈树搜索算法解决计算机围棋的吃子问题 PDF下载HTML

备注/Memo

使用不同的博弈树搜索算法解决计算机围棋的吃子问题

PDF下载 HTML