一种混合博弈树算法在中国象棋人机博弈中的应用研究
|
摘要
人机博弈问题是近年来比较热点的问题，机器博弈被专家们描述为人工智能的果蝇，就是说人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。象棋是一种完全知识博弈，意思是指参与双方在任何时候都完全清楚每一个棋子是否存在，位于何处。只要看看棋盘，就一清二楚了。跳棋、围棋、象棋等都属于完全知识博弈。国外的研究人员经过五十多年的对国际象棋博弈系统的探索，IBM公司在1997年开发出了超级计算机“深蓝”，并且战胜了世界国际象棋大师卡斯帕罗夫；而中国象棋的历史更为悠久，中国象棋计算机博弈的难度绝不亚于国际象棋，不仅涉足学者太少，而且参考资料不多。中国象棋计算机博弈的难点主要表现在盘面规模更大、着法更为特殊、变化也更加复杂。中国象棋人机博弈系统一般被分为：数据表示、走法生成、搜索引擎、估值核心、开局库、残局库。
本文通过对自行研制的象棋程序“棋之梦”的数据表示、走法生成、搜索引擎、估值核心、开局库模块的描述与分析，阐述了此象棋程序的设计与实现的原理，并且着重提出了一种改进的置换表与目前流行的一些搜索算法(包括：null-move pruning、历史启发、迭代深化、静寂搜索、负极大值搜索、杀手启发)相结合的混合算法并将其应用在象棋程序中，实验表明新算法明显地提高了程序的运算效率。“棋之梦”在06年8月份于北京举行的“全国首届中国象棋计算机锦标赛”中获得新秀奖。
The problem of man-machine game is very popular precently. Match is described as a fruit fly of the artificial intelligence by experts. That's to say human's research to the machine has achieved massive research results. These achievements have played an important influence on a more widespread domain. Chess is a kind of Games of Perfect Information,which means that both sides know clearly if every chessman is existed or not and where they are at any time completely.It will be clear as long as you take a look at the chessboard. Chesses such as jump chess,I-go and chess all belong to Games of Perfect Information. Through overseas researchers' exploration of chess gambling system for more than 50 years, IBM Corporation developed supercomputer "Dark Blue" in 1997, and has defeated world chess master Ksparov;while the Chinese chess history is more glorious, the level of the Chinese chess computer game is not easier than chess.Not only the number of scholar who joines in the computer Chinese chess game is little,but also information which is worth of reference is few. The difficulty of Chinese chess computer game mostly lies in the greater model of chessboard, the more different move generation, the more complex change. The Chinese chess man-machine gambling system is generally divided into: the data expression, move generation, the search engine, evaluation function, the database of starting game and the database of aftermatch.
By describing and analyzing the module of chess program "QZM" such as its data expression,move generation,search engine,evaluation function and database of starting game,this article expounds the Chinese chess program's principle of design and realization,furthermore,it puts forward a hybrid search algorithm which combined by the improved transposition table and some popular search algorithm(null-move pruning,history heuristic,interative deepening and so on) ,and it improve calculation efficency of the program obviously after being applied to the chess program. "QZM" won the new personality award in The First China Chess computer match on Aug.6th 2006.
本文通过对自行研制的象棋程序“棋之梦”的数据表示、走法生成、搜索引擎、估值核心、开局库模块的描述与分析，阐述了此象棋程序的设计与实现的原理，并且着重提出了一种改进的置换表与目前流行的一些搜索算法(包括：null-move pruning、历史启发、迭代深化、静寂搜索、负极大值搜索、杀手启发)相结合的混合算法并将其应用在象棋程序中，实验表明新算法明显地提高了程序的运算效率。“棋之梦”在06年8月份于北京举行的“全国首届中国象棋计算机锦标赛”中获得新秀奖。
The problem of man-machine game is very popular precently. Match is described as a fruit fly of the artificial intelligence by experts. That's to say human's research to the machine has achieved massive research results. These achievements have played an important influence on a more widespread domain. Chess is a kind of Games of Perfect Information,which means that both sides know clearly if every chessman is existed or not and where they are at any time completely.It will be clear as long as you take a look at the chessboard. Chesses such as jump chess,I-go and chess all belong to Games of Perfect Information. Through overseas researchers' exploration of chess gambling system for more than 50 years, IBM Corporation developed supercomputer "Dark Blue" in 1997, and has defeated world chess master Ksparov;while the Chinese chess history is more glorious, the level of the Chinese chess computer game is not easier than chess.Not only the number of scholar who joines in the computer Chinese chess game is little,but also information which is worth of reference is few. The difficulty of Chinese chess computer game mostly lies in the greater model of chessboard, the more different move generation, the more complex change. The Chinese chess man-machine gambling system is generally divided into: the data expression, move generation, the search engine, evaluation function, the database of starting game and the database of aftermatch.
By describing and analyzing the module of chess program "QZM" such as its data expression,move generation,search engine,evaluation function and database of starting game,this article expounds the Chinese chess program's principle of design and realization,furthermore,it puts forward a hybrid search algorithm which combined by the improved transposition table and some popular search algorithm(null-move pruning,history heuristic,interative deepening and so on) ,and it improve calculation efficency of the program obviously after being applied to the chess program. "QZM" won the new personality award in The First China Chess computer match on Aug.6th 2006.
引文
[1] 国际象棋人机博弈简史 http://www.chessit.net/file_topic/computerches/c_briefhistory.html
[2] 徐心和，王骄，徐峥等．中国象棋计算机博弈问题研究(一)中国象棋计算机博弈的难点分析
[3] 黄文奇，宋恩民，关于象棋的不败算法，华中科技大学学报，Vol．23 No.5 May 1995
[4] 王小春，游戏编程(人机博弈)[M]，重庆：重庆大学出版社 2002
[5] T. A. Marsland, COMPUTER CHESS AND SEARCH[D], Computing Science Department, University of Alberta
[6] 戴锦锟，计算机象棋，微计算机应用 Vol．15 No.3 May，1994
[7] Knuth D. E. , Moore R. W. An analysis of alpha-beta pruning[J]. Artificial Intelligence, 1975, 6(4): 293-326
[8] Marsland T A. Computer Chess and Search[M]. Encyclopedia of Artificial Intelligence, S. Shapiro, J. Wiley & Sons, 2nd edition, 1992: 224-241
[9] 王骄，李思仲，徐长明等．中国象棋计算机博弈问题研究(三)基本博弈搜索引擎
[10] Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice.IEEE Transactionson Pattern Analysis and Machine Intelligence, November1989, PAMI-11 (1): 1203～1212
[11] Lu P. Parallel Search of Narrow Game Trees. Master of Science, 1993, University of Alberta
[12] Donninger, C. Null move and deep search: Selective search heuristics for obtuse chess programs[J]. ICCA Journal, 1993, 16(3): 137-143
[13] Heinz E A. Adaptive null-move pruning[J]. ICCA Journal,1999,22(3):123-132.
[14] Sakuta M, Hashimoto T, Nagashima J, et al. Application of the killer-tree heuristic and the lambda-search method to lines of action, Information Science, 2003, 154(3-4): 141-155.
[15] 王骄，徐长明，李维宏等．中国象棋计算机博弈问题研究(二)数据结构与着法生成研
[16] Breuker D M, Uiterwijk J. W. H. M, Herik H.J. van den (1997). Information in transposition tables[C]. Advances in Computer Chess 8 (editors H. J. van den Herik and J.W.H.M. Uiterwijk), pp. 199-212. University of Limburg, Maastricht, The Netherlands. ISBN 9062162347
[17] A.Zobrist.'A New Hashing Method with Application for Game Playing'.Technical Report 88, Computer Science Department, University of Wisconsin, Madison. 1970
[18] 王骄，洪波，叶柠等．中国象棋计算机博弈问题研究(四)高级博弈搜索引擎
[19] Sashi Lazar, Analysis of Transposition Tables and Replacement Schemes.Technical report, U-niversity of Maryland, December1995
[20] Breuker D M, Uiterwijk J. W. H. M, Herik H. J. van den. Replacement Schemes for Transposition Tables[J]. ICCA Journal, 1994, 17(4): 183-193
[21] 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
[22] 王骄，徐峥，洪波等．中国象棋计算机博弈问题研究(五)评估函数研究
[23] Holland J H. Adaptation in nature and artificial system[M], Ann Arbor: The University of Michigan Press, 1975
[24] 玄光男，程润伟，遗传算法与工程设计，科学出版社，2000
[25] 杨俊安，李斌，庄镇泉等．基于量子遗传算法的盲源分离算法研究，小型微型计算机系统 Vol．24 No.8 Aug．2003
[26] 熊焰，陈欢欢，苗付友等．一种解决组合优化问题的量子遗传算法QGA，电子学报 Vol．32 No.11 Nov．2004
[27] Yen Shi-Jim, Chen Jr-Chang, Yang Tai-Ning, COMPUTER CHINESE CHESS[J], ICCA, 2004
[28] Michael Buro, Toward Opening Book Learning, NEC research Institute
[29] Thomas R.Lincke, Position Value Representation in Opening Books,Springer Berlin/Heidelberg, 2003
[30] 王骄，魏钦刚，李思仲等．中国象棋计算机博弈问题研究(六)开局库与残局库
[31] 魏钦刚，王骄，徐心和等．中国象棋计算机博弈开局库研究与设计2006中国机器博弈学术研讨会论文集
[33] 陆汝钤．人工智能．北京：科学出版社，1995
[34] Slate D and Atkin L. Chess 4.5: The Northwestern University Chess Program. P. Rey editor, Chess Skill in Man and Machine, Springer Verlag, New York, 1977: 82-118
[2] 徐心和，王骄，徐峥等．中国象棋计算机博弈问题研究(一)中国象棋计算机博弈的难点分析
[3] 黄文奇，宋恩民，关于象棋的不败算法，华中科技大学学报，Vol．23 No.5 May 1995
[4] 王小春，游戏编程(人机博弈)[M]，重庆：重庆大学出版社 2002
[5] T. A. Marsland, COMPUTER CHESS AND SEARCH[D], Computing Science Department, University of Alberta
[6] 戴锦锟，计算机象棋，微计算机应用 Vol．15 No.3 May，1994
[7] Knuth D. E. , Moore R. W. An analysis of alpha-beta pruning[J]. Artificial Intelligence, 1975, 6(4): 293-326
[8] Marsland T A. Computer Chess and Search[M]. Encyclopedia of Artificial Intelligence, S. Shapiro, J. Wiley & Sons, 2nd edition, 1992: 224-241
[9] 王骄，李思仲，徐长明等．中国象棋计算机博弈问题研究(三)基本博弈搜索引擎
[10] Jonathan Schaeffer. The history heuristic and alpha-beta search enhancements in practice.IEEE Transactionson Pattern Analysis and Machine Intelligence, November1989, PAMI-11 (1): 1203～1212
[11] Lu P. Parallel Search of Narrow Game Trees. Master of Science, 1993, University of Alberta
[12] Donninger, C. Null move and deep search: Selective search heuristics for obtuse chess programs[J]. ICCA Journal, 1993, 16(3): 137-143
[13] Heinz E A. Adaptive null-move pruning[J]. ICCA Journal,1999,22(3):123-132.
[14] Sakuta M, Hashimoto T, Nagashima J, et al. Application of the killer-tree heuristic and the lambda-search method to lines of action, Information Science, 2003, 154(3-4): 141-155.
[15] 王骄，徐长明，李维宏等．中国象棋计算机博弈问题研究(二)数据结构与着法生成研
[16] Breuker D M, Uiterwijk J. W. H. M, Herik H.J. van den (1997). Information in transposition tables[C]. Advances in Computer Chess 8 (editors H. J. van den Herik and J.W.H.M. Uiterwijk), pp. 199-212. University of Limburg, Maastricht, The Netherlands. ISBN 9062162347
[17] A.Zobrist.'A New Hashing Method with Application for Game Playing'.Technical Report 88, Computer Science Department, University of Wisconsin, Madison. 1970
[18] 王骄，洪波，叶柠等．中国象棋计算机博弈问题研究(四)高级博弈搜索引擎
[19] Sashi Lazar, Analysis of Transposition Tables and Replacement Schemes.Technical report, U-niversity of Maryland, December1995
[20] Breuker D M, Uiterwijk J. W. H. M, Herik H. J. van den. Replacement Schemes for Transposition Tables[J]. ICCA Journal, 1994, 17(4): 183-193
[21] 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
[22] 王骄，徐峥，洪波等．中国象棋计算机博弈问题研究(五)评估函数研究
[23] Holland J H. Adaptation in nature and artificial system[M], Ann Arbor: The University of Michigan Press, 1975
[24] 玄光男，程润伟，遗传算法与工程设计，科学出版社，2000
[25] 杨俊安，李斌，庄镇泉等．基于量子遗传算法的盲源分离算法研究，小型微型计算机系统 Vol．24 No.8 Aug．2003
[26] 熊焰，陈欢欢，苗付友等．一种解决组合优化问题的量子遗传算法QGA，电子学报 Vol．32 No.11 Nov．2004
[27] Yen Shi-Jim, Chen Jr-Chang, Yang Tai-Ning, COMPUTER CHINESE CHESS[J], ICCA, 2004
[28] Michael Buro, Toward Opening Book Learning, NEC research Institute
[29] Thomas R.Lincke, Position Value Representation in Opening Books,Springer Berlin/Heidelberg, 2003
[30] 王骄，魏钦刚，李思仲等．中国象棋计算机博弈问题研究(六)开局库与残局库
[31] 魏钦刚，王骄，徐心和等．中国象棋计算机博弈开局库研究与设计2006中国机器博弈学术研讨会论文集
[33] 陆汝钤．人工智能．北京：科学出版社，1995
[34] Slate D and Atkin L. Chess 4.5: The Northwestern University Chess Program. P. Rey editor, Chess Skill in Man and Machine, Springer Verlag, New York, 1977: 82-118