基于剪枝策略的中国象棋搜索引擎研究
|
摘要
在人工智能(AI)领域,计算机博弈历来都是一个重要的研究方向。对中国象棋计算机博弈的研究始于上世纪八十年代,经过二十多年的努力,出现了大量优秀的博弈系统,在对弈能力方面,有些系统目前已经达到了专家级水平。然而与国际象棋所取得的成就相比仍有较大差距。
本文针对中国象棋博弈系统的搜索引擎进行研究,主要分析了各种基于剪枝策略的搜索算法应用于中国象棋博弈时表现出来的特点和性能,总结出了除算法之外其他影响系统棋力的因素以及改进的方法。B*算法很少被应用于中国象棋博弈系统之中,本文实现了基于最佳优先搜索的B*算法,并设计了适合此算法的局面评估函数。在实验中详细分析了B*算法的优缺点和实战能力,实验结果证明B*算法应用于中国象棋博弈系统当中是可行的。
Computer game playing is a very important domain in Artificial Intelligence(AI). The research of Chinese Chess Computer Game started from the 1980s. After more than 20 years' development, many excellent game playing systems have emerged. Some of them have reached the human expert-level. However, comparing with the achievements of international chess systems, Chinese chess systems need to be improved.
In this thesis, the search engine of Chinese chess system is studied and the performance of search algorithms is analyzed. Some factors which can influence the systems'capability are studied and methods witch can improve the capability of the chess system are introduced. B* algorithm, witch is rarely used in Chinese chess system, is applied to our system. An evaluation function is constructed and combined with B*. The advantages, disadvantages and performance of B* algorithm are analyzed. Experimental results show that B* algorithm is feasible and effective in Chinese chess system.
本文针对中国象棋博弈系统的搜索引擎进行研究,主要分析了各种基于剪枝策略的搜索算法应用于中国象棋博弈时表现出来的特点和性能,总结出了除算法之外其他影响系统棋力的因素以及改进的方法。B*算法很少被应用于中国象棋博弈系统之中,本文实现了基于最佳优先搜索的B*算法,并设计了适合此算法的局面评估函数。在实验中详细分析了B*算法的优缺点和实战能力,实验结果证明B*算法应用于中国象棋博弈系统当中是可行的。
Computer game playing is a very important domain in Artificial Intelligence(AI). The research of Chinese Chess Computer Game started from the 1980s. After more than 20 years' development, many excellent game playing systems have emerged. Some of them have reached the human expert-level. However, comparing with the achievements of international chess systems, Chinese chess systems need to be improved.
In this thesis, the search engine of Chinese chess system is studied and the performance of search algorithms is analyzed. Some factors which can influence the systems'capability are studied and methods witch can improve the capability of the chess system are introduced. B* algorithm, witch is rarely used in Chinese chess system, is applied to our system. An evaluation function is constructed and combined with B*. The advantages, disadvantages and performance of B* algorithm are analyzed. Experimental results show that B* algorithm is feasible and effective in Chinese chess system.
引文
[1]D. E. Knuth, R. W. Moore. An Analysis of Alpha-Beta Pruning. Artificial Intelligence 1975,6(4): 293-326.
[2]A. J. Palay, Searching with Probabilities, Pitman Advanced Publishing Program Boston,1985. Also, Ph.D. Thesis, CMU, 1983.
[3]Richard S. Sutton. Learning to Predict by the Methods of Temporal Differences. Machine Learning, 1988, No.3:9-44.
[4]Bruce Abramson, Control Strategies for Two-Player Games, ACM Computing Surveys, 1989, Vol.21, No.2:137-161.
[5]顾立尧.解空间搜索中的B*树算法,上海机械学院学报,1989,Vol.11,No.4：59-64.
[6]许舜钦.电脑西洋棋和电脑象棋的回顾与前瞻.电脑学刊,1990,第二卷第二期：1-8.
[7]黄文奇,宋恩民,陈亮,等.关于象棋的不败算法.华中理工大学学报.1995,Vol.32,No5：1-4.
[8]Eyal Amir. Game Search Trees. http://citeseerx.ist.psu.edu/viewdoc/download,1996.
[9]Berliner. H.J. and McConnell. C. B* probability based search. Artificial Intelligence,1996, Vol.86, No.1:97-156.
[10]肖齐英,王正志.博弈树搜索与静态估值函数,计算机应用研究,1997,第4期：74-76.
[11]DF Beal, MC Smith. Learning Piece Values Using Temporal Differences. Journal of The International Computer Chess Association,1997.
[12]Andreas Junghanns Are There Practical Alternatives to Alpha-Beta in Computer Chess, http://citeseerx.ist.psu.edu/viewdoc/download,1998.
[13]TB Trinh, AS Bashi, and N Dashpande Temporal Difference Learning in Chinese Chess, Lecture Notes In Computer Science; Vol.1416 http://citeseerx.ist.psu.edu/viewdoc/download,1998.
[14]陆汝钤.人工智能.北京：科学出版社,2000：363-373.
[15]莫建文.机器自学习博弈策略研究与实现：广西师范大学硕士学位论文,2002.
[16]王小春.PC游戏编程[M].重庆：重庆大学出版社,2002.
[17]Jaime. Carbonell. Artificial Intelligence 15-381 Heuristic Search Methods, www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15381-f01/www/handouts/083001.ppt,2003.
[18]涂志坚.电脑象棋的设计与实现：中山大学硕十学位论文,2004.
[19]Shi-Jim Yen, Jr-Chang Chen, and Tai-Ning Yang. et al. Computer Chinese Chess. ICGA Journal, Taipei, Taiwan 2004:3-18.
[20]徐心和,王骄.中国象棋计算机博弈关键技术分析J.小型微型计算机系统,2006,27(6)：961-965.
[21]王骐.博弈树搜索算法的研究及改进：浙江大学硕士学位论文,2006.
[22]付强.基于激励学习的中国象棋研究：长沙理工大学硕十学位论文,2006.
[23]高强.一种混合博弈树算法在中国象棋人机博弈中的应用研究：大连交通大学硕士学位论文,2006.
[24]Michael Bowling, Johannes Furnkranz and Thore Graepel et al. Machine Learning and Games. Machine Learning, 2006, No.63:211-215.
[25]王赠凯,吕维先.机器博弈搜索技术分析.软件导刊,2007,Vol.2,No.1：26-27.
[26]魏钦刚,王骄,徐心和,等.中国象棋计算机博弈开局库研究与设计.智能系统学报,2007 Vol.2,No.1：85-89.
[27]Bouke van der Spoel. Algorithms for Selective Search. http://people.cs.uu.nl. March 8th,2007.
[28]付强,陈焕文.中国象棋人机对弈的自学习方法研究.计算机技术与发展,2007,Vol.17,No.12：76-79.
[29]王洪岩,朱峰,张雪峰等.一种基于神经网络的中国象棋及其博弈评估实现.2007中国控制与决策学术年会论文集,2007：687-693.
[30]危春波.中国象棋博弈系统的研究与实现：昆明理工大学硕士学位论文,2008.
[31]黄晨等.象棋百科全书www.elephantbase.net.
[2]A. J. Palay, Searching with Probabilities, Pitman Advanced Publishing Program Boston,1985. Also, Ph.D. Thesis, CMU, 1983.
[3]Richard S. Sutton. Learning to Predict by the Methods of Temporal Differences. Machine Learning, 1988, No.3:9-44.
[4]Bruce Abramson, Control Strategies for Two-Player Games, ACM Computing Surveys, 1989, Vol.21, No.2:137-161.
[5]顾立尧.解空间搜索中的B*树算法,上海机械学院学报,1989,Vol.11,No.4：59-64.
[6]许舜钦.电脑西洋棋和电脑象棋的回顾与前瞻.电脑学刊,1990,第二卷第二期：1-8.
[7]黄文奇,宋恩民,陈亮,等.关于象棋的不败算法.华中理工大学学报.1995,Vol.32,No5：1-4.
[8]Eyal Amir. Game Search Trees. http://citeseerx.ist.psu.edu/viewdoc/download,1996.
[9]Berliner. H.J. and McConnell. C. B* probability based search. Artificial Intelligence,1996, Vol.86, No.1:97-156.
[10]肖齐英,王正志.博弈树搜索与静态估值函数,计算机应用研究,1997,第4期：74-76.
[11]DF Beal, MC Smith. Learning Piece Values Using Temporal Differences. Journal of The International Computer Chess Association,1997.
[12]Andreas Junghanns Are There Practical Alternatives to Alpha-Beta in Computer Chess, http://citeseerx.ist.psu.edu/viewdoc/download,1998.
[13]TB Trinh, AS Bashi, and N Dashpande Temporal Difference Learning in Chinese Chess, Lecture Notes In Computer Science; Vol.1416 http://citeseerx.ist.psu.edu/viewdoc/download,1998.
[14]陆汝钤.人工智能.北京：科学出版社,2000：363-373.
[15]莫建文.机器自学习博弈策略研究与实现：广西师范大学硕士学位论文,2002.
[16]王小春.PC游戏编程[M].重庆：重庆大学出版社,2002.
[17]Jaime. Carbonell. Artificial Intelligence 15-381 Heuristic Search Methods, www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15381-f01/www/handouts/083001.ppt,2003.
[18]涂志坚.电脑象棋的设计与实现：中山大学硕十学位论文,2004.
[19]Shi-Jim Yen, Jr-Chang Chen, and Tai-Ning Yang. et al. Computer Chinese Chess. ICGA Journal, Taipei, Taiwan 2004:3-18.
[20]徐心和,王骄.中国象棋计算机博弈关键技术分析J.小型微型计算机系统,2006,27(6)：961-965.
[21]王骐.博弈树搜索算法的研究及改进：浙江大学硕士学位论文,2006.
[22]付强.基于激励学习的中国象棋研究：长沙理工大学硕十学位论文,2006.
[23]高强.一种混合博弈树算法在中国象棋人机博弈中的应用研究：大连交通大学硕士学位论文,2006.
[24]Michael Bowling, Johannes Furnkranz and Thore Graepel et al. Machine Learning and Games. Machine Learning, 2006, No.63:211-215.
[25]王赠凯,吕维先.机器博弈搜索技术分析.软件导刊,2007,Vol.2,No.1：26-27.
[26]魏钦刚,王骄,徐心和,等.中国象棋计算机博弈开局库研究与设计.智能系统学报,2007 Vol.2,No.1：85-89.
[27]Bouke van der Spoel. Algorithms for Selective Search. http://people.cs.uu.nl. March 8th,2007.
[28]付强,陈焕文.中国象棋人机对弈的自学习方法研究.计算机技术与发展,2007,Vol.17,No.12：76-79.
[29]王洪岩,朱峰,张雪峰等.一种基于神经网络的中国象棋及其博弈评估实现.2007中国控制与决策学术年会论文集,2007：687-693.
[30]危春波.中国象棋博弈系统的研究与实现：昆明理工大学硕士学位论文,2008.
[31]黄晨等.象棋百科全书www.elephantbase.net.