中国象棋计算机博弈中的判别剪枝搜索研究
摘要
本文作者针对中国象棋的计算机博弈存在一些问题,提出了一种利用象棋大师知识的新搜索剪枝算法,相关实验证明该方法在博弈树搜索中的有效性。
对于残局阶段的计算机博弈,有学者提出了利用残局库,但这些残局库往往很大,匹配一个残局需要很长的时间,也未必能匹配上,效果也不好。而一般的搜索引擎在对博弈树进行剪枝的时候仅仅依据的是叶子结点评估值,没有考虑残局模式。这和人类大师有点不同。象棋大师们的大脑记住了很多残局的模式,当他们在下棋的过程中,发现当前思考局面能够匹配某个残局模式,就会停止进一步的思考。受到这个思考过程的启发,本文作者设计了一种新的剪枝算法。在搜索引擎中加入了一些经典残局判别规则,来对博弈树进行剪枝。
In this thesis, the author proposes a new game tree pruning algorithm to solve the problem about the computer Chinese chess, which uses the masters'experience on the endgame position judgment. The relevant experiments show the good efficiency on the game tree search.
Researchers had proposed the endgame database to solve the computer Chinese chess problem in the end period of the game. However, since the endgame database is always very huge, it needs much time to match the current position and it maybe failed. Therefore, the result is not satisfying. The ordinary search engines select the best move based on the position values of leaf nodes of game tree, without considering the endgame patterns. But there is a difference between the engines and the masters. When playing the chess, masters will stop the consideration on the position after one move if the current thinking position matches an endgame pattern, which has been remembered in the masters'brains, but the search engines will not. Inspired by this process, the author designs a new algorithm to select the best move. In the algorithm,many patterns have been added into the new search engine to prune the game tree.
对于残局阶段的计算机博弈,有学者提出了利用残局库,但这些残局库往往很大,匹配一个残局需要很长的时间,也未必能匹配上,效果也不好。而一般的搜索引擎在对博弈树进行剪枝的时候仅仅依据的是叶子结点评估值,没有考虑残局模式。这和人类大师有点不同。象棋大师们的大脑记住了很多残局的模式,当他们在下棋的过程中,发现当前思考局面能够匹配某个残局模式,就会停止进一步的思考。受到这个思考过程的启发,本文作者设计了一种新的剪枝算法。在搜索引擎中加入了一些经典残局判别规则,来对博弈树进行剪枝。
In this thesis, the author proposes a new game tree pruning algorithm to solve the problem about the computer Chinese chess, which uses the masters'experience on the endgame position judgment. The relevant experiments show the good efficiency on the game tree search.
Researchers had proposed the endgame database to solve the computer Chinese chess problem in the end period of the game. However, since the endgame database is always very huge, it needs much time to match the current position and it maybe failed. Therefore, the result is not satisfying. The ordinary search engines select the best move based on the position values of leaf nodes of game tree, without considering the endgame patterns. But there is a difference between the engines and the masters. When playing the chess, masters will stop the consideration on the position after one move if the current thinking position matches an endgame pattern, which has been remembered in the masters'brains, but the search engines will not. Inspired by this process, the author designs a new algorithm to select the best move. In the algorithm,many patterns have been added into the new search engine to prune the game tree.
引文
[1]http://encyclopedia.thefreedictionary.com/computer+chess.
[2]http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm.
[3]http://www.elephantbase.net.
[4]C.E. Shannon. Programming a computer for playing chess. Philos. Magazine 41(7):256-275,1950
[5]A. Zobrist. A New Hashing Method with Application for Game playing.technical Report 88 Computer Science Department, University of Wisconsin Madison 1970.
[6]T.Anthony Marsland. A review of game tree pruning. ICCA Journal,March 1986,9(1):3-19.
[7]Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. Construction of Chinese Chess Endgame databases by Retrograde Analysis Proc.2nd International Conference on Computers and Games (CG),2000,Springer-Verlag LNCS# 2063:96-114.
[8]Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. Indefinite Sequence of Moves in Chinese Chess Endgames, Proc.3rd International Conference on Computers and Games (CG), 2002,Springer-Verlag LNCS:1-16.
[9]Ren Wu and Donald F. Beal. A Memory Efficient Retrograde Algorithm and Its Application To Chinese Chess Endgames. More Games of No Chance MSRI Publications 2002,42:213-226.
[10]Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, Shun-Chin Hsu. Computer Chinese Chess. ICGA, 2004(3),3-18.
[11]Chuanqi Li. Using AdaBoost to Implement Chinese Chess Evaluation Functions. University of California,2008.
[12]袁天鑫,傅尧青.中国象棋博弈程序中的博弈树算法.上海交通大学学报,1990,24(4)：86-88.
[13]戴锦锟.计算机象棋.微计算机应用,1994,15(3)：5-11.
[14]黄文奇,宋恩民,陈亮,王权利.关于象棋的不败算法.华中理工大学学报,1995,23(5)：1-4.
[15]肖齐英,王正志.博弈树搜索与静态估值函数.计算机应用研究1997,74-76.
[16]王小春.PC游戏编程.重庆：重庆大学出版社,2002.
[17]楚宇轩.象棋入门提高与实战技巧.广东：广东旅游出版社,2007.
[18]李中健,王国顺.象棋残局大全.成都：成都时代出版社,1993.
[19]洪哲.象棋圣经.北京：团结出版社,2006.
[20]涂志坚.电脑象棋的设计与实现.中山大学,2004.
[21]蒋峥峻graphplan扩展与中国象棋.吉林大学,2004.
[22]王骄,王涛,罗艳红,徐心和.中国象棋计算机博弈系统评估函数的自适应遗传算法实现.2005,26,(10)：949-952.
[23]张赜.计算机中国象棋博弈中的二次估值方法及其优化的研究.东北大学,2006.
[24]徐心和,王骄.中国象棋计算机博弈关键技术分析.小型微型计算机系统,2006,27(6)：961-969.
[25]周玮,张赜,周静怡.基于对弈局势的二次估值方法.系统仿真学报,2006,(09).2665-2668
[26]徐长明,南晓斐,王骄,徐心和.中国象棋机器博弈的时间自适应分配策略研究.智能系统学报,2006,1(2)：39-43.
[27]高强.一种混合博弈树算法在中国象棋人机博弈中的应用研究.大连交通大学2006.
[28]王骐.博弈树搜索算法的研究及改进.浙江大学,2006.
[29]王洪岩,朱峰,张雪峰,李玉倩,安爽,徐心和.一种基于粗神经网络的中国象棋机器博弈评估实现2007中国控制与决策学术年会论文集,2007.687-693.
[30]潘璐.基于增强学习的博弈主体的研究沈阳工业大学,2007.
[31]王一非.具有自学习功能的计算机象棋博弈系统的研究与实现.哈尔滨工程大学,2007.
[32]魏钦刚,王骄,徐心和,南晓斐.中国象棋计算机博弈开局库研究与设计.智能系统学报,2007,2(1)：85-89.
[33]高建良.面向中国象棋的人机博弈系统研究.湖南农业大学学报2007年11月,14-16.
[34]付强,陈焕文.中国象棋人机对弈的自学习方法研究.计算机技术与发展.2007,17(12)：76-79.
[35]邹竞.基于MTD_f_的中国象棋人机博弈算法的设计与优化.计算机与数字工程2008(9)：38-43.
[2]http://www.geocities.com/SiliconValley/Lab/7378/comphis.htm.
[3]http://www.elephantbase.net.
[4]C.E. Shannon. Programming a computer for playing chess. Philos. Magazine 41(7):256-275,1950
[5]A. Zobrist. A New Hashing Method with Application for Game playing.technical Report 88 Computer Science Department, University of Wisconsin Madison 1970.
[6]T.Anthony Marsland. A review of game tree pruning. ICCA Journal,March 1986,9(1):3-19.
[7]Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. Construction of Chinese Chess Endgame databases by Retrograde Analysis Proc.2nd International Conference on Computers and Games (CG),2000,Springer-Verlag LNCS# 2063:96-114.
[8]Haw-ren Fang, Tsan-sheng Hsu and Shun-chin Hsu. Indefinite Sequence of Moves in Chinese Chess Endgames, Proc.3rd International Conference on Computers and Games (CG), 2002,Springer-Verlag LNCS:1-16.
[9]Ren Wu and Donald F. Beal. A Memory Efficient Retrograde Algorithm and Its Application To Chinese Chess Endgames. More Games of No Chance MSRI Publications 2002,42:213-226.
[10]Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, Shun-Chin Hsu. Computer Chinese Chess. ICGA, 2004(3),3-18.
[11]Chuanqi Li. Using AdaBoost to Implement Chinese Chess Evaluation Functions. University of California,2008.
[12]袁天鑫,傅尧青.中国象棋博弈程序中的博弈树算法.上海交通大学学报,1990,24(4)：86-88.
[13]戴锦锟.计算机象棋.微计算机应用,1994,15(3)：5-11.
[14]黄文奇,宋恩民,陈亮,王权利.关于象棋的不败算法.华中理工大学学报,1995,23(5)：1-4.
[15]肖齐英,王正志.博弈树搜索与静态估值函数.计算机应用研究1997,74-76.
[16]王小春.PC游戏编程.重庆：重庆大学出版社,2002.
[17]楚宇轩.象棋入门提高与实战技巧.广东：广东旅游出版社,2007.
[18]李中健,王国顺.象棋残局大全.成都：成都时代出版社,1993.
[19]洪哲.象棋圣经.北京：团结出版社,2006.
[20]涂志坚.电脑象棋的设计与实现.中山大学,2004.
[21]蒋峥峻graphplan扩展与中国象棋.吉林大学,2004.
[22]王骄,王涛,罗艳红,徐心和.中国象棋计算机博弈系统评估函数的自适应遗传算法实现.2005,26,(10)：949-952.
[23]张赜.计算机中国象棋博弈中的二次估值方法及其优化的研究.东北大学,2006.
[24]徐心和,王骄.中国象棋计算机博弈关键技术分析.小型微型计算机系统,2006,27(6)：961-969.
[25]周玮,张赜,周静怡.基于对弈局势的二次估值方法.系统仿真学报,2006,(09).2665-2668
[26]徐长明,南晓斐,王骄,徐心和.中国象棋机器博弈的时间自适应分配策略研究.智能系统学报,2006,1(2)：39-43.
[27]高强.一种混合博弈树算法在中国象棋人机博弈中的应用研究.大连交通大学2006.
[28]王骐.博弈树搜索算法的研究及改进.浙江大学,2006.
[29]王洪岩,朱峰,张雪峰,李玉倩,安爽,徐心和.一种基于粗神经网络的中国象棋机器博弈评估实现2007中国控制与决策学术年会论文集,2007.687-693.
[30]潘璐.基于增强学习的博弈主体的研究沈阳工业大学,2007.
[31]王一非.具有自学习功能的计算机象棋博弈系统的研究与实现.哈尔滨工程大学,2007.
[32]魏钦刚,王骄,徐心和,南晓斐.中国象棋计算机博弈开局库研究与设计.智能系统学报,2007,2(1)：85-89.
[33]高建良.面向中国象棋的人机博弈系统研究.湖南农业大学学报2007年11月,14-16.
[34]付强,陈焕文.中国象棋人机对弈的自学习方法研究.计算机技术与发展.2007,17(12)：76-79.
[35]邹竞.基于MTD_f_的中国象棋人机博弈算法的设计与优化.计算机与数字工程2008(9)：38-43.