计算机中国象棋界面和搜索引擎的设计与实现
|
摘要
计算机博弈是人工智能的一个传统研究领域。计算机博弈为人工智能提供一个实验平台,将人工智能的一些理论与方法应用于计算机博弈,可通过博弈水平的高低来检验这些理论与方法的有效性,研究计算机博弈所得到的成果也可推广至人工智能的其他领域。因此,二者相辅相成,相互促进。在国际象棋计算机博弈高度发展的今天,基于两个原因,中国象棋则具有得天独厚的发展优势。首先,它是世界上最流行最古老的棋类游戏之一,且现在已经存在较高棋力的中国象棋程序；其次,它的复杂度介于国际象棋与围棋之间。可以相信自1997年“深蓝”击败卡斯帕罗夫之后,中国象棋必将成为下一个拥有可以击败人类高手的软件程序的棋类游戏。
本文在阅读了大量国内外相关文献的基础之上,结合现有的国际象棋以及中国象棋软件设计实例,介绍如何实现一款具有一定棋力且交互友好的中国象棋博弈软件程序,文中的主要工作如下：
1.分析并总结了中国象棋计算机博弈的关键技术,包括：数据结构、搜索算法、评估函数以及博弈界面等；
2.研究并设计了中国象棋博弈程序的数据结构,包括棋盘、棋子在计算机中的表示等,同时引入了位行位列技术、模板匹配法与预置表法等辅助数据结构以提高着法生成的效率,且对其进行了测试总结；
3.研究并实现了建立在博弈树的极大极小搜索技术基础之上的各种优化方法,文中主要讨论了基于窗口探测、内存增强、节点顺序调整以及时间控制四个方面的优化方法；之后经过比较分析,文中选择并实现了辅以迭代深化、置换表、历史启发的MTD(f)搜索算法,极大地提高了计算机的“思考”效率,并进行测试总结；另外提出并实现了克制水平线效应的静态搜索、将军延伸以及兑子延伸使得计算机的“思考”更加稳定,进而采用Zobrist哈希技术解决了单方长将以及双方循环走棋的问题；
4.应用VB设计并实现了中国象棋博弈软件的界面及辅助功能,包括悔棋、计时、着法显示等；
5.系统的实现。
Computer game is a traditional researching field of artificial intelligence (AI). It shows a test-platform for AI. Applying some theories and methods of AI in computer game, we can prove the validity of those by means of testing the level of game system. In turn, the fruits obtained through researching the computer game are used in the other realms of AI. So, they supplement and promote each other. Nowadays, Chess computer game has a long history, and come through tough research. For two reasons, Chinese chess is with intrinsic advantages in development. First, Chinese chess is one of the most popular and oldest board games worldwide, currently the strength of a Chinese chess program can be compared to that of human players. Second, the complexity of Chinese chess is between that of Chess and Go. We assume that after DEEP BLUE's victory over Kasparov in 1997, Chinese chess will be the next chess-like board game at which will defeat a human top player.
On the basis of lots of related references at home and abroad, and the existing examples of Chess and Chinese chess software, this paper presents how to realize a Chinese chess game software program with considerable strength and good human-computer interface, including the following works:
1. Analyze and summarize the key techniques of computer game for Chinese chess, such as data structure, search algorithms, evaluation functions, and user interface etc.
2. Study and design the data structures of Chinese-chess program, including the representation of chessboard and chessman in computer etc. At the same time, some assisting data structures, such as the BitFile and BitRank technique, the template matching method and prefabricated table method, are introduced and used to enhance the efficiency of moves' generation. Furthermore, a series of tests and results are presents.
3. Research deeply and realize several optimization algorithms based on Minimax search for game tree. In the article, four kinds of methods are summarized, including based window detection, memory-enhanced, nodes-sorting and time-control. Furthermore, as a result of comparison and analysis, the MTD(f) algorithm is selected and implemented with Iterative Deepening, Transposition Table and History Heuristic, which improves the efficiency of computer thinking markedly, and a series of tests and results are presents. In addition, Quiescence Search, Check Extension and Recapturing Extension reducing effects of the Horizon Effect are brought forward and implemented, which make computer's thinking more stable. Finally, the unceasing checking for one-player and the repetition of moves for two-players are settled successfully by means of Zobrist hash technique.
4. Design and realize the user interface and assisting functions such as tack-back, timing, displaying moves etc with VB.
5. Implementation of system.
本文在阅读了大量国内外相关文献的基础之上,结合现有的国际象棋以及中国象棋软件设计实例,介绍如何实现一款具有一定棋力且交互友好的中国象棋博弈软件程序,文中的主要工作如下：
1.分析并总结了中国象棋计算机博弈的关键技术,包括：数据结构、搜索算法、评估函数以及博弈界面等；
2.研究并设计了中国象棋博弈程序的数据结构,包括棋盘、棋子在计算机中的表示等,同时引入了位行位列技术、模板匹配法与预置表法等辅助数据结构以提高着法生成的效率,且对其进行了测试总结；
3.研究并实现了建立在博弈树的极大极小搜索技术基础之上的各种优化方法,文中主要讨论了基于窗口探测、内存增强、节点顺序调整以及时间控制四个方面的优化方法；之后经过比较分析,文中选择并实现了辅以迭代深化、置换表、历史启发的MTD(f)搜索算法,极大地提高了计算机的“思考”效率,并进行测试总结；另外提出并实现了克制水平线效应的静态搜索、将军延伸以及兑子延伸使得计算机的“思考”更加稳定,进而采用Zobrist哈希技术解决了单方长将以及双方循环走棋的问题；
4.应用VB设计并实现了中国象棋博弈软件的界面及辅助功能,包括悔棋、计时、着法显示等；
5.系统的实现。
Computer game is a traditional researching field of artificial intelligence (AI). It shows a test-platform for AI. Applying some theories and methods of AI in computer game, we can prove the validity of those by means of testing the level of game system. In turn, the fruits obtained through researching the computer game are used in the other realms of AI. So, they supplement and promote each other. Nowadays, Chess computer game has a long history, and come through tough research. For two reasons, Chinese chess is with intrinsic advantages in development. First, Chinese chess is one of the most popular and oldest board games worldwide, currently the strength of a Chinese chess program can be compared to that of human players. Second, the complexity of Chinese chess is between that of Chess and Go. We assume that after DEEP BLUE's victory over Kasparov in 1997, Chinese chess will be the next chess-like board game at which will defeat a human top player.
On the basis of lots of related references at home and abroad, and the existing examples of Chess and Chinese chess software, this paper presents how to realize a Chinese chess game software program with considerable strength and good human-computer interface, including the following works:
1. Analyze and summarize the key techniques of computer game for Chinese chess, such as data structure, search algorithms, evaluation functions, and user interface etc.
2. Study and design the data structures of Chinese-chess program, including the representation of chessboard and chessman in computer etc. At the same time, some assisting data structures, such as the BitFile and BitRank technique, the template matching method and prefabricated table method, are introduced and used to enhance the efficiency of moves' generation. Furthermore, a series of tests and results are presents.
3. Research deeply and realize several optimization algorithms based on Minimax search for game tree. In the article, four kinds of methods are summarized, including based window detection, memory-enhanced, nodes-sorting and time-control. Furthermore, as a result of comparison and analysis, the MTD(f) algorithm is selected and implemented with Iterative Deepening, Transposition Table and History Heuristic, which improves the efficiency of computer thinking markedly, and a series of tests and results are presents. In addition, Quiescence Search, Check Extension and Recapturing Extension reducing effects of the Horizon Effect are brought forward and implemented, which make computer's thinking more stable. Finally, the unceasing checking for one-player and the repetition of moves for two-players are settled successfully by means of Zobrist hash technique.
4. Design and realize the user interface and assisting functions such as tack-back, timing, displaying moves etc with VB.
5. Implementation of system.
引文
[1][美]Nils. J Nilsson.人工智能[M].北京：机械工业出版社,2000.
[2]廉师友.人工智能技术导论[M].西安：西安电子科技大学出版社,2000.
[3]T. Anthony Marsland and Jonathan Schaeffer, Computers, Chess and Cognition[M], New York: Springer-Verlag,1990.
[4]国际象棋译文苑.http://www.chessit.net/.
[5]Computer Chess Programming. http://www.xs4all.nl/-verhelst/chess/programming.html.
[6]Francis Dominic Larame. http://www.gamedev.net/.
[7]象棋百科全书.http://www.elephantbase.net/.
[8]黄晨.解剖大象的眼睛——象棋程序设计探索[EB/OL]. http://www.xqsj.org/news/show.aspx?page =1&id=824&cid=9.
[9]Claude E. Shannon. Programming a Computer for Playing Chess[J]. Philosophical Magazine,1950, Vol.41:256-275.
[10]电脑国际象棋简史.http://www.chessit.net/file_topic/computerchess/c_briefhistory.htm.
[11]Plaat. Reach Re, Search & Re-Search. PhD thesis[D]. Erasmus University, Dept. of Computer Science, Rotterdam, the Netherlands,1996.
[12]柳玉栋.中国象棋教科书[M].北京：华夏出版社,1989.
[13]黄振根.中国象棋入门与提高问答[M].福州：福建科学技术出版社,2001.
[14]Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, Shun-Chin Hsu. COMPUTER CHINESE CHESS [J]. ICGA Journal, March 2004:3-18.
[15]徐心和,王骄.中国象棋计算机博弈关键技术分析[J].小型微型计算机系统,2006,27(6)：961-969.
[16]棋天大圣网站.http://www.neuchess.com.
[17]涂志坚.电脑象棋的设计与实现[D].广州：中山大学硕士学位论文,2004.
[18]M.Newbom. Recent Progress in Computer Chess[J]. Advances in Computer,1978,18:59-117.
[19]肖其英,王正志.博弈树搜索与静态估值函数[J].计算机应用研究.1997,4：74-76.
[20]王骄,王涛,罗艳红,徐心和.中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J].东北大学学报(自然科学版),2005,26(5)：949-952
[21]王小春.PC游戏编程[M].重庆：重庆大学出版社,2002.
[22]Chen J R. Chinese Chess Open-game Database Design[D]. M.Sc. Thesis, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan,1997.
[23]魏钦刚,王骄,徐心和,南晓斐.中国象棋计算机博弈开局库研究与设计[J].智能系统学报.2007.2,2(1)：85-89.
[24]Fang H R. Chinese Chess Endgame Database and Related Applications[D]. M.Sc. Thesis, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, 1996.
[25]Thong B. Trinh, Anwer S. Bashi, Nikhil Deshpande. Temporal Difference Learning In Chinese Chess[J], Lecture Notes In Computer Science,1998,1416:612-618.
[26]莫建文,林士敏,张顺岚.基于TD强化学习智能博弈程序的设计与实现[J].计算机应用,2004,24(6)：287-288.
[27]电脑象棋循序渐进. http://www.elephantbase.net/computer/stepbystepl.htm.
[28]S Cracraft. Bitmap Move Generation in Chess [J]. ICCA Journal,1984,7 (3):146-153.
[29]Marsland T A. Computer Chess and Search [J]. Encyclopedia of Artificial Intelligence, S. Shapiro (editor), J. Wiley & Sons,2nd edition,1992:224-241.
[30]Don F Beal. A Generalized Quiescence Search Algorithm[J]. Artificial Intelligence.1990,43(1): 85-98.
[31]Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin. Best-first Fixed-depth Minimax Algorithms[J], Artificial Intelligence,1996,87(1):255-293.
[32]Ye, C. and Marsland T A. Experiments in Forward Pruning with Limited Extensions[J]. ICCA Journal,1992,15(2):55-66.
[33]Ye, C. and Marsland, T.A. Selective Extensions in Game-Tree Search[J]. Heuristic Programming in Artificial Intelligence 3(eds. H.J. van den Herik and L.V. Allis),1992:112-122.
[34]徐心和,王骄等.中国象棋计算机博弈问题研究[R].沈阳：东北大学人工智能与机器人研究所,2005.
[35]Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin. Nearly Optimal Minimax Tree Search? [R] Technical Report, University of Alberta,1994.
[36]Strategy Game Programming. http://www.fierz.ch/strategyl.htm.
[37]Game Tree Searching and pruning:http://www.cs.unm.edu/-aaron/downloads/qian_search.pdf.
[38]Jonathan Schaeffer. The History Heuristic and Alpha-Beta Search Enhancements in Practice[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1989,11(11):1203-1212.
[39]Zobrist A. A new Hashing Method with Application for Game Playing[R]. Computer Science Department, The University of Wisconsin, Madison,1970.
[40]D.M. Breuker, J.W.H.M. Uiterwijk, H.J. van den Herik. Replacement Schemes for Transposition Tables[J]. ICCA Journal, December 1994,17(4):183-193.
[41]Dennis M. Breuker, Jos W. H. M. Uiterwijk. Transposition Tables in Computer Chess[J]. International Institute for Asian Studies(IIAS),1995:135-143.
[42]Sashi Lazar. Analysis of Transposition Tables and Replacement Schemes[R]. Technical report, University of Maryland,1995.
[43]Akihlro Kishimoto. Transposition Table Driven Scheduling for Two-Player Games[D]. M.Sc. Thesis, University of Alberta.2002.
[44]A. Reinefeld, T. A. Marsland. Enhanced Iterative-Deepening Search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI),1994,16(7):701-710.
[45]Korf R. Depth-first Iterative Deepening:an Optimal Admissible Tree Search[J]. Artificial Intelligence,1985,27(1):97-109.
[46]Andreas Junghanns, Jonathan Schaeffer. Search Versus Knowledge in Game-Playing Programs Revisited[C]. Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97),1997,1:692-697.
[47]Knuth D E, Moore R W. An Analysis of Alpha-beta Pruning[J]. Artificial Intelligence,1975,6 (4): 293-326.
[48]MTD(f)-A Minimax Algorithm faster than NegaScout. http://theory.lcs.mit.edu/-plaat/mtdf.html, 1997.
[49]黄晨.棋类游戏中的先行权[J].智能系统学报.2007.6,2(3)：91-94.
[50]Heinz E A. Adaptive null-move pruning[J]. ICCA Journal,1999,22(3):123-132.
[51]Omid David Tabibi and Nathan S. Netanyahu. Verified Null-Move Pruning[J]. ICGA Journal,2002, 25(3):153-161.
[52]Heinz E A. Extended Futility Pruning[J]. ICCA Journal,1998,21(2):75-83.
[53]付强.基于激励学习的中国象棋研究[D].长沙：长沙理工大学硕士学位论文.2006.
[54]王一非.具有自学习功能的计算机象棋博弈系统的研究与实现[D].哈尔滨：哈尔滨工程大学硕士学位论文.2007.
[55]王骄,王涛,罗艳红,徐心和.中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J].东北大学学报(自然科学版),2005,26(5)：949-952.
[56]周玮,张赜,周静怡.基于对弈局势的二次估值方法[J].系统仿真学报,2006.9,18(9)：2665-2668.
[57]王骐,孙建伶.基于优化迭代的博弈树算法[J].计算机应用与软件,2008.2,25(2)：228-230.
[58]机器博弈机器搜索算法研究.http://hi.baidu.com/laona/blog/item/bfe77bcbe9cbf01fbe09e6df.html.
[59]龚尚福.C/C++语言程序设计[M].徐州：中国矿业大学出版社,2007.
[60]林锐.高质量C++编程指南[M].北京：电子工业出版社,2001.
[61]胡达.C++ Builder程序设计范例——中国象棋[M].北京：清华大学出版社,2002.
[62]严蔚敏,吴伟民.数据结构[M].北京：清华大学出版社,1997.
[63]黄少龙.象棋对策论[M].成都：蜀蓉棋艺出版社,1986.
[2]廉师友.人工智能技术导论[M].西安：西安电子科技大学出版社,2000.
[3]T. Anthony Marsland and Jonathan Schaeffer, Computers, Chess and Cognition[M], New York: Springer-Verlag,1990.
[4]国际象棋译文苑.http://www.chessit.net/.
[5]Computer Chess Programming. http://www.xs4all.nl/-verhelst/chess/programming.html.
[6]Francis Dominic Larame. http://www.gamedev.net/.
[7]象棋百科全书.http://www.elephantbase.net/.
[8]黄晨.解剖大象的眼睛——象棋程序设计探索[EB/OL]. http://www.xqsj.org/news/show.aspx?page =1&id=824&cid=9.
[9]Claude E. Shannon. Programming a Computer for Playing Chess[J]. Philosophical Magazine,1950, Vol.41:256-275.
[10]电脑国际象棋简史.http://www.chessit.net/file_topic/computerchess/c_briefhistory.htm.
[11]Plaat. Reach Re, Search & Re-Search. PhD thesis[D]. Erasmus University, Dept. of Computer Science, Rotterdam, the Netherlands,1996.
[12]柳玉栋.中国象棋教科书[M].北京：华夏出版社,1989.
[13]黄振根.中国象棋入门与提高问答[M].福州：福建科学技术出版社,2001.
[14]Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, Shun-Chin Hsu. COMPUTER CHINESE CHESS [J]. ICGA Journal, March 2004:3-18.
[15]徐心和,王骄.中国象棋计算机博弈关键技术分析[J].小型微型计算机系统,2006,27(6)：961-969.
[16]棋天大圣网站.http://www.neuchess.com.
[17]涂志坚.电脑象棋的设计与实现[D].广州：中山大学硕士学位论文,2004.
[18]M.Newbom. Recent Progress in Computer Chess[J]. Advances in Computer,1978,18:59-117.
[19]肖其英,王正志.博弈树搜索与静态估值函数[J].计算机应用研究.1997,4：74-76.
[20]王骄,王涛,罗艳红,徐心和.中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J].东北大学学报(自然科学版),2005,26(5)：949-952
[21]王小春.PC游戏编程[M].重庆：重庆大学出版社,2002.
[22]Chen J R. Chinese Chess Open-game Database Design[D]. M.Sc. Thesis, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan,1997.
[23]魏钦刚,王骄,徐心和,南晓斐.中国象棋计算机博弈开局库研究与设计[J].智能系统学报.2007.2,2(1)：85-89.
[24]Fang H R. Chinese Chess Endgame Database and Related Applications[D]. M.Sc. Thesis, Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, 1996.
[25]Thong B. Trinh, Anwer S. Bashi, Nikhil Deshpande. Temporal Difference Learning In Chinese Chess[J], Lecture Notes In Computer Science,1998,1416:612-618.
[26]莫建文,林士敏,张顺岚.基于TD强化学习智能博弈程序的设计与实现[J].计算机应用,2004,24(6)：287-288.
[27]电脑象棋循序渐进. http://www.elephantbase.net/computer/stepbystepl.htm.
[28]S Cracraft. Bitmap Move Generation in Chess [J]. ICCA Journal,1984,7 (3):146-153.
[29]Marsland T A. Computer Chess and Search [J]. Encyclopedia of Artificial Intelligence, S. Shapiro (editor), J. Wiley & Sons,2nd edition,1992:224-241.
[30]Don F Beal. A Generalized Quiescence Search Algorithm[J]. Artificial Intelligence.1990,43(1): 85-98.
[31]Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin. Best-first Fixed-depth Minimax Algorithms[J], Artificial Intelligence,1996,87(1):255-293.
[32]Ye, C. and Marsland T A. Experiments in Forward Pruning with Limited Extensions[J]. ICCA Journal,1992,15(2):55-66.
[33]Ye, C. and Marsland, T.A. Selective Extensions in Game-Tree Search[J]. Heuristic Programming in Artificial Intelligence 3(eds. H.J. van den Herik and L.V. Allis),1992:112-122.
[34]徐心和,王骄等.中国象棋计算机博弈问题研究[R].沈阳：东北大学人工智能与机器人研究所,2005.
[35]Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin. Nearly Optimal Minimax Tree Search? [R] Technical Report, University of Alberta,1994.
[36]Strategy Game Programming. http://www.fierz.ch/strategyl.htm.
[37]Game Tree Searching and pruning:http://www.cs.unm.edu/-aaron/downloads/qian_search.pdf.
[38]Jonathan Schaeffer. The History Heuristic and Alpha-Beta Search Enhancements in Practice[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1989,11(11):1203-1212.
[39]Zobrist A. A new Hashing Method with Application for Game Playing[R]. Computer Science Department, The University of Wisconsin, Madison,1970.
[40]D.M. Breuker, J.W.H.M. Uiterwijk, H.J. van den Herik. Replacement Schemes for Transposition Tables[J]. ICCA Journal, December 1994,17(4):183-193.
[41]Dennis M. Breuker, Jos W. H. M. Uiterwijk. Transposition Tables in Computer Chess[J]. International Institute for Asian Studies(IIAS),1995:135-143.
[42]Sashi Lazar. Analysis of Transposition Tables and Replacement Schemes[R]. Technical report, University of Maryland,1995.
[43]Akihlro Kishimoto. Transposition Table Driven Scheduling for Two-Player Games[D]. M.Sc. Thesis, University of Alberta.2002.
[44]A. Reinefeld, T. A. Marsland. Enhanced Iterative-Deepening Search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI),1994,16(7):701-710.
[45]Korf R. Depth-first Iterative Deepening:an Optimal Admissible Tree Search[J]. Artificial Intelligence,1985,27(1):97-109.
[46]Andreas Junghanns, Jonathan Schaeffer. Search Versus Knowledge in Game-Playing Programs Revisited[C]. Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97),1997,1:692-697.
[47]Knuth D E, Moore R W. An Analysis of Alpha-beta Pruning[J]. Artificial Intelligence,1975,6 (4): 293-326.
[48]MTD(f)-A Minimax Algorithm faster than NegaScout. http://theory.lcs.mit.edu/-plaat/mtdf.html, 1997.
[49]黄晨.棋类游戏中的先行权[J].智能系统学报.2007.6,2(3)：91-94.
[50]Heinz E A. Adaptive null-move pruning[J]. ICCA Journal,1999,22(3):123-132.
[51]Omid David Tabibi and Nathan S. Netanyahu. Verified Null-Move Pruning[J]. ICGA Journal,2002, 25(3):153-161.
[52]Heinz E A. Extended Futility Pruning[J]. ICCA Journal,1998,21(2):75-83.
[53]付强.基于激励学习的中国象棋研究[D].长沙：长沙理工大学硕士学位论文.2006.
[54]王一非.具有自学习功能的计算机象棋博弈系统的研究与实现[D].哈尔滨：哈尔滨工程大学硕士学位论文.2007.
[55]王骄,王涛,罗艳红,徐心和.中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J].东北大学学报(自然科学版),2005,26(5)：949-952.
[56]周玮,张赜,周静怡.基于对弈局势的二次估值方法[J].系统仿真学报,2006.9,18(9)：2665-2668.
[57]王骐,孙建伶.基于优化迭代的博弈树算法[J].计算机应用与软件,2008.2,25(2)：228-230.
[58]机器博弈机器搜索算法研究.http://hi.baidu.com/laona/blog/item/bfe77bcbe9cbf01fbe09e6df.html.
[59]龚尚福.C/C++语言程序设计[M].徐州：中国矿业大学出版社,2007.
[60]林锐.高质量C++编程指南[M].北京：电子工业出版社,2001.
[61]胡达.C++ Builder程序设计范例——中国象棋[M].北京：清华大学出版社,2002.
[62]严蔚敏,吴伟民.数据结构[M].北京：清华大学出版社,1997.
[63]黄少龙.象棋对策论[M].成都：蜀蓉棋艺出版社,1986.