六子棋计算机博弈关键技术研究
|
摘要
人工智能是计算机科学的一个重要分支,与能源技术、生物工程、空间技术等并称为当今世界的尖端科技。计算机博弈是人工智能研究的一个重要方面,人类对计算机博弈的研究衍生了大量的研究成果,这些成果对更广泛的领域产生了重要影响。随着计算机博弈在Othello、Checker和国际象棋等棋类上的成功,全世界的学者又把目光投到了中国象棋、日本将棋、围棋等更为复杂的棋类上面。六子棋(Connect6)作为一种二人零和完备信息博弈,与围棋有着相近的复杂度,成为学者们研究的焦点之一。
六子棋计算机博弈的关键技术包括状态表示、走法生成、状态评估、搜索引擎、开局库建立、参数优化等,本文的主要工作是围绕走法生成、状态评估、搜索引擎、开局库建立等进行研究和改进,具体的工作内容和成果如下:
1.比较研究常用的棋盘状态表示法的优缺点后,借鉴比特棋盘的思想,提出了一种适用于六子棋的改进后的比特棋盘。使用该数据结构,可通过位运算快速判断各种棋型。
2.深入地研究了各种Alpha-Beta搜索及改进技术后,通过编程实现了这些算法,并比较了六子棋博弈程序中这些算法间的性能差异,发现其中MTD(f)算法的性能最好。
3.通过分析搜索算法的工作过程,并结合六子棋走法生成的特殊性,提出了将走法生成模块中的预置表与搜索引擎中的置换表融合在一起的改进措施,极大地避免了在搜索过程中频繁地生成走法。同时还比较了改进前后的MTD(f)算法的性能差异,证明了改进措施的有效性。
4.认真研究六子棋的特点后,提出了对六子棋棋型的新定义。使用该定义可极大地降低棋形的分类难度,从而提高估值函数的运行速度。
5.针对新的棋型定义,设计了一种简单可行的棋型识别方法。同时还结合改进后的比特棋盘技术实现了基于该方法的快速而有效的估值算法。
6.利用哈希技术设计了一个简单的开局库,搜集并录入了31种常见开局及其对称形式,同时还录入了4个开局的关键走法及其变化。
本文的创新之处有以下几点:
1.在状态表示中,改进比特棋盘,使之适用于六子棋博弈程序。
2.在搜索引擎中,融合预置表与置换表,降低生成走法的时间耗费,提高了搜索算法的效率。
3.在六子棋理论方面,提出了新的六子棋棋型定义,简化了棋型分类。
4.在棋局评估中,提出了6-8窗口法,该方法可快速有效的判断各种棋型。该方法同时也利用在走法生成中,评估各空点的价值。
Artificial Intelligence is an important branch of computer science, with energy technology, biotechnology, space technology, known as the world's most advanced technology. Computer games are an important aspect of artificial intelligence research, a large number of research results have been made because of studies about computer game, these results had an important impact in wider areas. After the computer game has successed in Othello, Checker , chess and so on, scholars around the world again eyeing on the Chinese chess, Shogi, Go and other more complex chess. Connect6 as a two-person zero-sum perfect information game, has the similar complexity with Go, and become to the focus of research.
The key technologies of Connect6 computer game include data structure, generating moves, evaluating state, search engine, opening bank and optimization of parameters, this paper’s main task is to research and improve generating moves, evaluating state, search engine, opening bank, the specific content of the work and results are as follows:
1. Having a comparison of advantages and disadvantages of the current board state representations, and studying bit board's thinking, a new improved bit board has been submitted and applied to the Connect6. Various chess-types can be quickly distinguished using‘and’operation provided by the new bit board.
2. After having in-depth study of some varieties of Alpha-Beta Search and technology used to improve it, I programed these algorithms, and compared the difference of performance between these algorithms while be used in the Connect6 game program, and founded that MTD(f) algorithm has the best performance.
3. By analyzing the work process of the MTD(f) search, and the special moves generation in the Connect6, I proposed to make the preset table in the moves generation module and the transposition table in the search engines together as a improvement, this improvement can reduce the frequent of generating moves in the search process. And by comparing the performance of different MTD(f) algorithms before and after improved, proved the effectiveness of the improvement measures.
4. Through seriously studying the characteristics of Connect6, raised some new definitions of Connect6 chess-type. Using the definitions can greatly reduce the difficulty of chess-type classification, and improve the operating speed of the evaluation function.
5. Basing on the new chess-type definitions, designed a simple and feasible method of chess-type identification, and proved the correctness of the method. Also realized a rapid and efficient evaluation algorithm basing on the method and the improved bit board.
6. A simple opening bank has been designed and realized using hashing table technology, including 31 kinds of openings and their symmetrical forms, and also including the key moves to four bad openings among them and some diversifications following the key moves.
The innovations of this paper are as follow:
1. In the state representation aspect, A new bit board which was improved from the chess bit board was raised to apply to the Connect6 game program.
2. In the search engine aspect, by using the preset table and the transposition table together, reduced the time spent to generate moves, and improved the efficiency of the search algorithm.
3. In the Connect6 theory aspect, put forward some new definitions of Connect6 chess-type, and simplified the chess-type classification.
4. In the Connect6 game situation evaluation aspect, proposed a 6-8 window method, this method can be used to quickly and effectively identify the chess-type. This method is also used in the generating moves and the evaluation of the value of the empty spots.
六子棋计算机博弈的关键技术包括状态表示、走法生成、状态评估、搜索引擎、开局库建立、参数优化等,本文的主要工作是围绕走法生成、状态评估、搜索引擎、开局库建立等进行研究和改进,具体的工作内容和成果如下:
1.比较研究常用的棋盘状态表示法的优缺点后,借鉴比特棋盘的思想,提出了一种适用于六子棋的改进后的比特棋盘。使用该数据结构,可通过位运算快速判断各种棋型。
2.深入地研究了各种Alpha-Beta搜索及改进技术后,通过编程实现了这些算法,并比较了六子棋博弈程序中这些算法间的性能差异,发现其中MTD(f)算法的性能最好。
3.通过分析搜索算法的工作过程,并结合六子棋走法生成的特殊性,提出了将走法生成模块中的预置表与搜索引擎中的置换表融合在一起的改进措施,极大地避免了在搜索过程中频繁地生成走法。同时还比较了改进前后的MTD(f)算法的性能差异,证明了改进措施的有效性。
4.认真研究六子棋的特点后,提出了对六子棋棋型的新定义。使用该定义可极大地降低棋形的分类难度,从而提高估值函数的运行速度。
5.针对新的棋型定义,设计了一种简单可行的棋型识别方法。同时还结合改进后的比特棋盘技术实现了基于该方法的快速而有效的估值算法。
6.利用哈希技术设计了一个简单的开局库,搜集并录入了31种常见开局及其对称形式,同时还录入了4个开局的关键走法及其变化。
本文的创新之处有以下几点:
1.在状态表示中,改进比特棋盘,使之适用于六子棋博弈程序。
2.在搜索引擎中,融合预置表与置换表,降低生成走法的时间耗费,提高了搜索算法的效率。
3.在六子棋理论方面,提出了新的六子棋棋型定义,简化了棋型分类。
4.在棋局评估中,提出了6-8窗口法,该方法可快速有效的判断各种棋型。该方法同时也利用在走法生成中,评估各空点的价值。
Artificial Intelligence is an important branch of computer science, with energy technology, biotechnology, space technology, known as the world's most advanced technology. Computer games are an important aspect of artificial intelligence research, a large number of research results have been made because of studies about computer game, these results had an important impact in wider areas. After the computer game has successed in Othello, Checker , chess and so on, scholars around the world again eyeing on the Chinese chess, Shogi, Go and other more complex chess. Connect6 as a two-person zero-sum perfect information game, has the similar complexity with Go, and become to the focus of research.
The key technologies of Connect6 computer game include data structure, generating moves, evaluating state, search engine, opening bank and optimization of parameters, this paper’s main task is to research and improve generating moves, evaluating state, search engine, opening bank, the specific content of the work and results are as follows:
1. Having a comparison of advantages and disadvantages of the current board state representations, and studying bit board's thinking, a new improved bit board has been submitted and applied to the Connect6. Various chess-types can be quickly distinguished using‘and’operation provided by the new bit board.
2. After having in-depth study of some varieties of Alpha-Beta Search and technology used to improve it, I programed these algorithms, and compared the difference of performance between these algorithms while be used in the Connect6 game program, and founded that MTD(f) algorithm has the best performance.
3. By analyzing the work process of the MTD(f) search, and the special moves generation in the Connect6, I proposed to make the preset table in the moves generation module and the transposition table in the search engines together as a improvement, this improvement can reduce the frequent of generating moves in the search process. And by comparing the performance of different MTD(f) algorithms before and after improved, proved the effectiveness of the improvement measures.
4. Through seriously studying the characteristics of Connect6, raised some new definitions of Connect6 chess-type. Using the definitions can greatly reduce the difficulty of chess-type classification, and improve the operating speed of the evaluation function.
5. Basing on the new chess-type definitions, designed a simple and feasible method of chess-type identification, and proved the correctness of the method. Also realized a rapid and efficient evaluation algorithm basing on the method and the improved bit board.
6. A simple opening bank has been designed and realized using hashing table technology, including 31 kinds of openings and their symmetrical forms, and also including the key moves to four bad openings among them and some diversifications following the key moves.
The innovations of this paper are as follow:
1. In the state representation aspect, A new bit board which was improved from the chess bit board was raised to apply to the Connect6 game program.
2. In the search engine aspect, by using the preset table and the transposition table together, reduced the time spent to generate moves, and improved the efficiency of the search algorithm.
3. In the Connect6 theory aspect, put forward some new definitions of Connect6 chess-type, and simplified the chess-type classification.
4. In the Connect6 game situation evaluation aspect, proposed a 6-8 window method, this method can be used to quickly and effectively identify the chess-type. This method is also used in the generating moves and the evaluation of the value of the empty spots.
引文
[1]张维迎.博弈论与信息经济学陈玉东[M].上海:上海人民出版社,1996.08
[2]范如国.韩民春.博弈论[M].武汉:武汉大学出版社,2006.
[3]David N.L.Levy,eds.Computer Games[M].New York:Springer New York Inc,1988.335-365
[4]许舜钦.电脑西洋棋和电脑象棋的回顾与前瞻[J].电脑学刊台湾1990 3 2:1-8
[5]张玉志.计算机围棋博弈系统[D].北京:中国科学院计算技术研究所,1991
[6]Kierulf,Anders.Smart Game Board:A Workbench for Game-Playing Programs,with Go and Othello as Case Studies:[Ph.D.Thesis No.9135].Switzerland:Swiss Federal Institute of Technology(ETH)Z"urich,1990
[7]李果.六子棋计算机博弈及其系统的研究与实现[D]( Research and Realization of the Computer Game and System of Connect6).重庆大学硕士学位论文.2007
[8]谷蓉.计算机围棋博弈系统的若干问题研究[D]( Study on Several Problems for Computer Go System).清华大学硕士学位论文.2003
[9]万翼.计算机国际象棋博弈系统的研究与实现[D](Research and Implementation of Computer Chess-Playing System).西南交通大学硕士学位论文.2006
[10]王骐.博弈树搜索算法的研究及改进[D](The Study of Algorithms in Computer Go).浙江大学硕士学位论文.2006
[11]董红安.计算机五子棋博奕系统的研究与实现[D](The Study and Practice of Computer Five-Piece Game-playing System).山东师范大学硕士学位论文.2005
[12]莫建文.机器自学习博弈策略研究与实现[D](Study and Practice on Machine Self Learning of Game-playing).广西师范大学硕士学位论文.2002
[13]岳鹏.计算机围棋中的算法研究[D](The Study of Algorithms in Computer Go).西南大学博士士学位论文.2007
[14]谢艳茹.中国象棋计算机博弈数据结构与评估函数的研究和实现[D]( Research and Implementation of Data Structure and Evaluation in Computer Chinese Chess).西安理工大学硕士学位论文.2008
[15]王一非.具有自学习功能的计算机象棋博弈系统的研究与实现[D]( Research and Implementation of a Chinese Chess Computer Game System with Self Learning).哈尔滨工程大学硕士学位论文.2007
[16]谢国.中国象棋机器博弈数据结构设计与搜索算法研究[D] (Data Structure Design and Game-Tree Search Algorithm Research for Chinese Chess Computer Game).西安理工大学硕士学位论文.2008
[17]高强.一种混合博弈树算法在中国象棋人机博弈中的应用研究[D]( A Hybrid Game Tree Algorithm and Its Application Research in Chinese Chess Man-machine Game).大连交通大学硕士学位论文.2007
[18]张赜.计算机中国象棋博弈中的二次估值方法及其优化的研究[D](The Study of Algorithms in Computer Go).东北大学硕士学位论文.2006
[19]张颖.六子棋计算机博弈及其系统的研究与优化[D](Research and Optimization of the Computer-game system of Connect6).重庆大学硕士学位论文.2008
[20]张明亮.一种新的博弈树搜索算法及其应用研究[D]( A New Game-tree Search Algorithm and Its Application Research).苏州大学.2007
[21]I-Chen Wu,Dei-Yen Huang,and Hsiu-Chen Chang.CONNECT6[J].Hsinchu,Taiwan. 2005.12.
[22]I-Chen Wu and Dei-Yen Huang.A New Family of k-in-a-row Games[J].Hsinchu,Taiwan. 2005
[23]六子棋主页[Z].http://www.connect6.org/.
[24]Allis,L.V.,Searching for solutions in games and artificial intelligence.Ph.D. Thesis,University of Limburg,Maastricht(1994)
[25]Allis,L.V.,Herik,H.J.van den,and Huntjens,M.P.H. Go-Moku Solved by New Search Techniques.Computational Intelligence,Vol.12(1996)7–23
[26]Renju International Federation:The International Rules of Renju. http://www.renju.nu /rifrules.htm .1998
[27]Sakata,G.and Ikawa,W.Five-In-A-Row.Renju.The Ishi Press,Inc.,Tokyo,Japan.1981
[28]Herik,H.J.van den,Uiterwijk,J.W.H.M.,Rijswijck,J.V. Games solved:Now and in the future.Artificial Intelligence,Vol.134(2002)277–311
[29]王小春.PC游戏编程[M].重庆重庆大学出版社.2002.
[30]徐心和,王骄.中国象棋计算机博弈关键技术分析[J].小型微型计算机系统,2006,27(6):961-969(Xu Xinghe,Wang Jiao.Key technologies analysis of Chinese chess computer game[J].Journal of Chinese Computer Systems,2006,27(6):961-969.)
[31]Heinz,E.A.,How dark thought plays chess[J].ICCA Journal,1997,20(3):167-176.
[32]Pablo,S.S.,Ramón G.,Fernando M.,et al.Efficient search using bitboard models[C] International Conference on Tools with Artificial Intelligence.Washington D C:IEEE,2006:132-138.
[33]Yu H M,Chun T S., On the fairness and complexity of generalized k-in-a-row games[J].Theoretical Computer Science,2007,385:88-100.
[34]徐长明,马宗民,徐心和.一种新的连珠棋局面表示法及其在六子棋中的应用[J].东北大学学报(自然科学版)2009.30:514-517
[35]Claude E. Shannon. Programming a computer for playing chess[J], Philosophical Magazine, 1950.Vol.41:256-275.
[36]T.A.Marsland.COMPUTER CHESS AND SEARCH[R],Computing Science Department, University of Alberta,1992
[37]Shi-Jim Yen,Jr-Chang Ghen,Tai-Ning Yang.COMPUTER CHINESE CHESS[J],ICCA, 2004.3.
[38]Aske Plaat. Research Re: Search&Re-search[D]. Ph.D. thesis, Erasmus University, Rotterdam, The Netherlands, 1996
[39]R.L.Rivest. Game Tree Searching by MinMax Approximation[J].Artificial Intelligence, 1997 Vo1.34, No.1.:77-96
[40]D.Knuth and R.Moore,An Analysis of Alpha-Beta Pruning[J],Artificial Intelligence, 1975 Vol.6, No.4:293--326.
[41]A.L.Brudno.Bounds and valuations for shortening the search of estimates[J]. Problems of Cybernetics. 1963.Vol.10:225-241.
[42]Qian L. The Evolution Of Mulan: Some Studies In Game-Tree Pruning And Evaluation Function In The Game Amazons [D]. Master of Science Thesis, University of New Mexico Albuquerque, New Mexico, December 2003.
[43]M.M.Newborn, The Efficiency of the Alpha-Beta search on trees with branch- dependent terminal node scores, Artificial Intelligence, 1977.Vol.8:137-153.
[44]G.C.Stockman,A Minimax Algorithm Better than Alpha-beta?[J].Aritificial Intelligence,Vol.12,No.2,1979
[45]John P. Fishburn. Another optimization of alpha-beta search, SIGART Bulletin, Issue 84. 1983
[46]Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Pattern Analysis and Machine Intelligence,November 1989,PAMI-11(1):1203-1212
[47]Reinefeld, A.Spielbaum Suchverfahren. Volume Informatik- Fachberichte 200. Springer-Verlag, Berlin, Germany.1989.
[48]Reinefeld, A. An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, 1983 Vol.6,No.4: 4-14
[49]Aske Plaat. MTD(f):A Minimax Algorithm faster than NegaScout[OL]. http:// people.csail.mit.edu /plaat/mtdf.html
[50]Plaat, A., Schaeffer, J., Pijls, W., and Bruin, A. de (1996). An Algorithm Faster than NegaScout and SSS* in Practice[OL]. http://citeseerx.ist.psu.edu/viewdoc/ summary?doi=10.1.1.50.8641
[51]Nelson, H.L.Hash Tables in Cray Blitz[J].ICCA Journal,1985. Vol.8, No.1.
[52]Hyatt, R. M. and Cozzie, A.. The Effect of Hash Signature Collisions in a Chess Program[J]. ICGA Journal.2005, Vol. 28., No. 3.
[53]Hyatt, R. M. and Mann, T.. A lock-less transposition table implementation for parallel search chess engines[J]. ICGA Journal.2002, Vol. 25, No. 1.
[54]Breuker, D. M., Uiterwijk, J.W.H.M., and Herik, H.J. van den. Information in Transposition Tables. Advances in Computer Chess 8. 1997
[55]A.Zobrist.A New Hashing Method with Application for Game Playing[OL].Technical Report 88#.Science Department,University of Wisconsin,Madison. 1970. https://www.cs. wisc.edu/techreports/1970/TR88.pdf
[56]A.Zobrist. Feature Extraction and Representation for Pattern Recognition and the Game of Go[OL], Ph.D. Thesis, University of Wisconsin. 1970. http://www.cs.wisc.edu/ techreports/1970/TR85.pdf
[57]Breuker,D.M.,Uiterwijk J.W.H.M,Herik H.J.vanden.Replacement Sehemes for Transposition Tables[J].ICCAJoumal,1994,17(4):183-193
[58]Warnock, T. and Wendroff, B. Search Tables in Computer Chess[J]. ICCA Journal, 1988.Vol.11, No.1:10-13
[59]Schaeffer,J..The History Heuristic. ICCA Journal[J], 1983.Vol.6,No.3:16-19
[60]Berliner, H. and Goetsch, G.. A quantitative study of search methods and the effect of constraint satisfaction, Tech. Rept. CMU-CS-84-147, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 1984.
[61]Berliner, H.. Search, Artificial Intelligence Syllabus, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 1983.
[62]Winston, P.H.,Artificial Intelligence. Addison-Wesley, Reading, MA. 1984.
[63]岳金朋,冯速.博弈树搜索算法概述计算机系统应用[J],2009,18(9):203—207
[64]Omid David. Netanyahu, N.. Verified null-move pruning[J]. ICGA Journal, 2002. Vol.25 No.3:153-161, http://www.omiddavid.com/pubs/vrfd_null.html
[65]E.A.Heinz.Adaptive null-move pruning[J].ICCA Journal,1999.Vol.22,No.3:123-132, http://people.csail.mit.edu/heinz/ps/adpt_null.ps.gz
[66]Plenkner, S. A Null-Move Technique Impervious to Zugzwang[J]. ICCA Journal, Vol. 18, No. 2:82-84.
[67]Kaindl, H.Quiescence Search in Computer Chess. SIGART Newsletter, 80, 1982. pp.124-131. Reprinted (1983) in Computer-Game-Playing: Theory and Practice, pp. 39-52. Ellis Horwood Ltd., Chichester.
[68]Kaindl, H.Dynamic Control of the Quiescence Search in Computer Chess. Cybernetics and Systems Research (ed. R. Trappl), 1982. pp. 973-977. North-Holland, Amsterdam.
[69]Schrüfer.G,A Strategic Quiescence Search[J].ICCA Journal,1989.Vol.12,No.1:3-9.
[70]Goetsch, G. and Campbell, M.S. Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, 1988. pp. 14-18.
[71]Plaat,A.,Schaeffer,J.,Pijls, W., and Bruin, A. de ( 1996 ) . Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, pp. 255-293. ISSN 0004-3702. http://www.ldc.usb.ve/~bonet/courses/ci5437/papers/ mtd.pdf
[72]Aske Plaat,Jonathan Schaeffer,Wim Pijls and Arie de Bruin. SSS* = Alpha-Beta + TT Technical Report EUR-CS-95-02,1995. http://publishing.eur.nl/ir/repub/asset/ 1441/eur-few-cs-95-02.pdf
[73]Stockman, George C. and Kanal, Laveen N. Problem Reduction Representation for the Linguistic Analysis of Waveforms. Pattern Analysis and Machine Intelligence, 1983.IEEE Transactions Volume: PAMI-5, Issue 3
[74]Jaap van den Herik et al. Intelligent Search Techniques Proof-Number Search. MICC/IKAT Universiteit Maastricht. 2006.
[75]Winands,M.H.M.,Uiterwijk,J.W.H.M.,van den Herik, H.J. PDS-PN: A new proofnumber search algorithm: Application to Lines of Action. In Proceedings of CG 2002.2002.
[76]Andreas Junghanns,J.Schaeffer,Search Vesus Knowledge in Game-Playing Program Revisited.Techical Report,Dept. of Computer Science,university of Alhama,1998
[2]范如国.韩民春.博弈论[M].武汉:武汉大学出版社,2006.
[3]David N.L.Levy,eds.Computer Games[M].New York:Springer New York Inc,1988.335-365
[4]许舜钦.电脑西洋棋和电脑象棋的回顾与前瞻[J].电脑学刊台湾1990 3 2:1-8
[5]张玉志.计算机围棋博弈系统[D].北京:中国科学院计算技术研究所,1991
[6]Kierulf,Anders.Smart Game Board:A Workbench for Game-Playing Programs,with Go and Othello as Case Studies:[Ph.D.Thesis No.9135].Switzerland:Swiss Federal Institute of Technology(ETH)Z"urich,1990
[7]李果.六子棋计算机博弈及其系统的研究与实现[D]( Research and Realization of the Computer Game and System of Connect6).重庆大学硕士学位论文.2007
[8]谷蓉.计算机围棋博弈系统的若干问题研究[D]( Study on Several Problems for Computer Go System).清华大学硕士学位论文.2003
[9]万翼.计算机国际象棋博弈系统的研究与实现[D](Research and Implementation of Computer Chess-Playing System).西南交通大学硕士学位论文.2006
[10]王骐.博弈树搜索算法的研究及改进[D](The Study of Algorithms in Computer Go).浙江大学硕士学位论文.2006
[11]董红安.计算机五子棋博奕系统的研究与实现[D](The Study and Practice of Computer Five-Piece Game-playing System).山东师范大学硕士学位论文.2005
[12]莫建文.机器自学习博弈策略研究与实现[D](Study and Practice on Machine Self Learning of Game-playing).广西师范大学硕士学位论文.2002
[13]岳鹏.计算机围棋中的算法研究[D](The Study of Algorithms in Computer Go).西南大学博士士学位论文.2007
[14]谢艳茹.中国象棋计算机博弈数据结构与评估函数的研究和实现[D]( Research and Implementation of Data Structure and Evaluation in Computer Chinese Chess).西安理工大学硕士学位论文.2008
[15]王一非.具有自学习功能的计算机象棋博弈系统的研究与实现[D]( Research and Implementation of a Chinese Chess Computer Game System with Self Learning).哈尔滨工程大学硕士学位论文.2007
[16]谢国.中国象棋机器博弈数据结构设计与搜索算法研究[D] (Data Structure Design and Game-Tree Search Algorithm Research for Chinese Chess Computer Game).西安理工大学硕士学位论文.2008
[17]高强.一种混合博弈树算法在中国象棋人机博弈中的应用研究[D]( A Hybrid Game Tree Algorithm and Its Application Research in Chinese Chess Man-machine Game).大连交通大学硕士学位论文.2007
[18]张赜.计算机中国象棋博弈中的二次估值方法及其优化的研究[D](The Study of Algorithms in Computer Go).东北大学硕士学位论文.2006
[19]张颖.六子棋计算机博弈及其系统的研究与优化[D](Research and Optimization of the Computer-game system of Connect6).重庆大学硕士学位论文.2008
[20]张明亮.一种新的博弈树搜索算法及其应用研究[D]( A New Game-tree Search Algorithm and Its Application Research).苏州大学.2007
[21]I-Chen Wu,Dei-Yen Huang,and Hsiu-Chen Chang.CONNECT6[J].Hsinchu,Taiwan. 2005.12.
[22]I-Chen Wu and Dei-Yen Huang.A New Family of k-in-a-row Games[J].Hsinchu,Taiwan. 2005
[23]六子棋主页[Z].http://www.connect6.org/.
[24]Allis,L.V.,Searching for solutions in games and artificial intelligence.Ph.D. Thesis,University of Limburg,Maastricht(1994)
[25]Allis,L.V.,Herik,H.J.van den,and Huntjens,M.P.H. Go-Moku Solved by New Search Techniques.Computational Intelligence,Vol.12(1996)7–23
[26]Renju International Federation:The International Rules of Renju. http://www.renju.nu /rifrules.htm .1998
[27]Sakata,G.and Ikawa,W.Five-In-A-Row.Renju.The Ishi Press,Inc.,Tokyo,Japan.1981
[28]Herik,H.J.van den,Uiterwijk,J.W.H.M.,Rijswijck,J.V. Games solved:Now and in the future.Artificial Intelligence,Vol.134(2002)277–311
[29]王小春.PC游戏编程[M].重庆重庆大学出版社.2002.
[30]徐心和,王骄.中国象棋计算机博弈关键技术分析[J].小型微型计算机系统,2006,27(6):961-969(Xu Xinghe,Wang Jiao.Key technologies analysis of Chinese chess computer game[J].Journal of Chinese Computer Systems,2006,27(6):961-969.)
[31]Heinz,E.A.,How dark thought plays chess[J].ICCA Journal,1997,20(3):167-176.
[32]Pablo,S.S.,Ramón G.,Fernando M.,et al.Efficient search using bitboard models[C] International Conference on Tools with Artificial Intelligence.Washington D C:IEEE,2006:132-138.
[33]Yu H M,Chun T S., On the fairness and complexity of generalized k-in-a-row games[J].Theoretical Computer Science,2007,385:88-100.
[34]徐长明,马宗民,徐心和.一种新的连珠棋局面表示法及其在六子棋中的应用[J].东北大学学报(自然科学版)2009.30:514-517
[35]Claude E. Shannon. Programming a computer for playing chess[J], Philosophical Magazine, 1950.Vol.41:256-275.
[36]T.A.Marsland.COMPUTER CHESS AND SEARCH[R],Computing Science Department, University of Alberta,1992
[37]Shi-Jim Yen,Jr-Chang Ghen,Tai-Ning Yang.COMPUTER CHINESE CHESS[J],ICCA, 2004.3.
[38]Aske Plaat. Research Re: Search&Re-search[D]. Ph.D. thesis, Erasmus University, Rotterdam, The Netherlands, 1996
[39]R.L.Rivest. Game Tree Searching by MinMax Approximation[J].Artificial Intelligence, 1997 Vo1.34, No.1.:77-96
[40]D.Knuth and R.Moore,An Analysis of Alpha-Beta Pruning[J],Artificial Intelligence, 1975 Vol.6, No.4:293--326.
[41]A.L.Brudno.Bounds and valuations for shortening the search of estimates[J]. Problems of Cybernetics. 1963.Vol.10:225-241.
[42]Qian L. The Evolution Of Mulan: Some Studies In Game-Tree Pruning And Evaluation Function In The Game Amazons [D]. Master of Science Thesis, University of New Mexico Albuquerque, New Mexico, December 2003.
[43]M.M.Newborn, The Efficiency of the Alpha-Beta search on trees with branch- dependent terminal node scores, Artificial Intelligence, 1977.Vol.8:137-153.
[44]G.C.Stockman,A Minimax Algorithm Better than Alpha-beta?[J].Aritificial Intelligence,Vol.12,No.2,1979
[45]John P. Fishburn. Another optimization of alpha-beta search, SIGART Bulletin, Issue 84. 1983
[46]Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Pattern Analysis and Machine Intelligence,November 1989,PAMI-11(1):1203-1212
[47]Reinefeld, A.Spielbaum Suchverfahren. Volume Informatik- Fachberichte 200. Springer-Verlag, Berlin, Germany.1989.
[48]Reinefeld, A. An Improvement to the Scout Tree-Search Algorithm. ICCA Journal, 1983 Vol.6,No.4: 4-14
[49]Aske Plaat. MTD(f):A Minimax Algorithm faster than NegaScout[OL]. http:// people.csail.mit.edu /plaat/mtdf.html
[50]Plaat, A., Schaeffer, J., Pijls, W., and Bruin, A. de (1996). An Algorithm Faster than NegaScout and SSS* in Practice[OL]. http://citeseerx.ist.psu.edu/viewdoc/ summary?doi=10.1.1.50.8641
[51]Nelson, H.L.Hash Tables in Cray Blitz[J].ICCA Journal,1985. Vol.8, No.1.
[52]Hyatt, R. M. and Cozzie, A.. The Effect of Hash Signature Collisions in a Chess Program[J]. ICGA Journal.2005, Vol. 28., No. 3.
[53]Hyatt, R. M. and Mann, T.. A lock-less transposition table implementation for parallel search chess engines[J]. ICGA Journal.2002, Vol. 25, No. 1.
[54]Breuker, D. M., Uiterwijk, J.W.H.M., and Herik, H.J. van den. Information in Transposition Tables. Advances in Computer Chess 8. 1997
[55]A.Zobrist.A New Hashing Method with Application for Game Playing[OL].Technical Report 88#.Science Department,University of Wisconsin,Madison. 1970. https://www.cs. wisc.edu/techreports/1970/TR88.pdf
[56]A.Zobrist. Feature Extraction and Representation for Pattern Recognition and the Game of Go[OL], Ph.D. Thesis, University of Wisconsin. 1970. http://www.cs.wisc.edu/ techreports/1970/TR85.pdf
[57]Breuker,D.M.,Uiterwijk J.W.H.M,Herik H.J.vanden.Replacement Sehemes for Transposition Tables[J].ICCAJoumal,1994,17(4):183-193
[58]Warnock, T. and Wendroff, B. Search Tables in Computer Chess[J]. ICCA Journal, 1988.Vol.11, No.1:10-13
[59]Schaeffer,J..The History Heuristic. ICCA Journal[J], 1983.Vol.6,No.3:16-19
[60]Berliner, H. and Goetsch, G.. A quantitative study of search methods and the effect of constraint satisfaction, Tech. Rept. CMU-CS-84-147, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 1984.
[61]Berliner, H.. Search, Artificial Intelligence Syllabus, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 1983.
[62]Winston, P.H.,Artificial Intelligence. Addison-Wesley, Reading, MA. 1984.
[63]岳金朋,冯速.博弈树搜索算法概述计算机系统应用[J],2009,18(9):203—207
[64]Omid David. Netanyahu, N.. Verified null-move pruning[J]. ICGA Journal, 2002. Vol.25 No.3:153-161, http://www.omiddavid.com/pubs/vrfd_null.html
[65]E.A.Heinz.Adaptive null-move pruning[J].ICCA Journal,1999.Vol.22,No.3:123-132, http://people.csail.mit.edu/heinz/ps/adpt_null.ps.gz
[66]Plenkner, S. A Null-Move Technique Impervious to Zugzwang[J]. ICCA Journal, Vol. 18, No. 2:82-84.
[67]Kaindl, H.Quiescence Search in Computer Chess. SIGART Newsletter, 80, 1982. pp.124-131. Reprinted (1983) in Computer-Game-Playing: Theory and Practice, pp. 39-52. Ellis Horwood Ltd., Chichester.
[68]Kaindl, H.Dynamic Control of the Quiescence Search in Computer Chess. Cybernetics and Systems Research (ed. R. Trappl), 1982. pp. 973-977. North-Holland, Amsterdam.
[69]Schrüfer.G,A Strategic Quiescence Search[J].ICCA Journal,1989.Vol.12,No.1:3-9.
[70]Goetsch, G. and Campbell, M.S. Experimenting with the Null Move Heuristic in Chess. AAAI Spring Symposium Proceedings, 1988. pp. 14-18.
[71]Plaat,A.,Schaeffer,J.,Pijls, W., and Bruin, A. de ( 1996 ) . Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, pp. 255-293. ISSN 0004-3702. http://www.ldc.usb.ve/~bonet/courses/ci5437/papers/ mtd.pdf
[72]Aske Plaat,Jonathan Schaeffer,Wim Pijls and Arie de Bruin. SSS* = Alpha-Beta + TT Technical Report EUR-CS-95-02,1995. http://publishing.eur.nl/ir/repub/asset/ 1441/eur-few-cs-95-02.pdf
[73]Stockman, George C. and Kanal, Laveen N. Problem Reduction Representation for the Linguistic Analysis of Waveforms. Pattern Analysis and Machine Intelligence, 1983.IEEE Transactions Volume: PAMI-5, Issue 3
[74]Jaap van den Herik et al. Intelligent Search Techniques Proof-Number Search. MICC/IKAT Universiteit Maastricht. 2006.
[75]Winands,M.H.M.,Uiterwijk,J.W.H.M.,van den Herik, H.J. PDS-PN: A new proofnumber search algorithm: Application to Lines of Action. In Proceedings of CG 2002.2002.
[76]Andreas Junghanns,J.Schaeffer,Search Vesus Knowledge in Game-Playing Program Revisited.Techical Report,Dept. of Computer Science,university of Alhama,1998