[1]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.
Copy

Using Different Search Algorithms to Solve Computer Go Capturing Problems

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 2 Number of periods: 2007 3 Page number: 84-90 Column: 学术论文—人工智能基础 Public date: 2007-06-25
Title:
Using Different Search Algorithms to Solve Computer Go Capturing Problems
Author(s):
ZHANG;  Pei-gang ; CHEN Keh-hsun
Department of Computer Science, University of North Carolina a t Charlotte, Charlotte, NC 28223, USA
Keywords:
Computer Go;  Game Tree Search;  Heuristic Search;  AlphaBeta;  Proofnu mber Search;  Block Capturing.
CLC:
TP18
DOI:
-
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
Similar References:

Memo

-

Last Update: 2009-05-07

Copyright © CAAI Transactions on Intelligent Systems