中国象棋博弈·局面评估研究
|
摘要
计算机博弈是博弈领域长期的奋斗目标,也是人工智能学科极具挑战性的研究课题之一。凭借计算机的高速运算能力和设计严谨的算法,计算机可以在人机对弈中表现出相当高的“智能”。
国际象棋已经有了“深蓝”这样震惊世界的成果,更加复杂的中国象棋计算机博弈水平却远远落后。
一款象棋博弈程序的实现主要被分为两大部分:界面(程序辅助)+引擎(人工智能)。本文将介绍如何实现一款中国象棋博弈程序。其中包括:搜索算法、局面评估、哈希表、历史启发、局面库以及中盘研究;打谱;复盘等功能的实现。
Computer Game is the aim of game fields for long, and is the one of the challenging topics in artificial intelligence research. With the computer's high-speed computing power and Well-structured algorithms, the performance of computer can be very "smart" in Man-machine chess.
Though we have chess like "Deep Blue" which shocked the world, the more complicated Chinese Chess levels are far behind.
The implementation of Chess game program shall be divided into two parts: interface (program assist) + engine (artificial intelligence). This article will introduce how to implement a Chinese Chess Game program. About: search Algorithm、Research of Situation Assessment、HashTable、Historical inspiration、Situation Library and Mid-Cap Research、Make Situation、Recovery disk as the realization of functions such.
国际象棋已经有了“深蓝”这样震惊世界的成果,更加复杂的中国象棋计算机博弈水平却远远落后。
一款象棋博弈程序的实现主要被分为两大部分:界面(程序辅助)+引擎(人工智能)。本文将介绍如何实现一款中国象棋博弈程序。其中包括:搜索算法、局面评估、哈希表、历史启发、局面库以及中盘研究;打谱;复盘等功能的实现。
Computer Game is the aim of game fields for long, and is the one of the challenging topics in artificial intelligence research. With the computer's high-speed computing power and Well-structured algorithms, the performance of computer can be very "smart" in Man-machine chess.
Though we have chess like "Deep Blue" which shocked the world, the more complicated Chinese Chess levels are far behind.
The implementation of Chess game program shall be divided into two parts: interface (program assist) + engine (artificial intelligence). This article will introduce how to implement a Chinese Chess Game program. About: search Algorithm、Research of Situation Assessment、HashTable、Historical inspiration、Situation Library and Mid-Cap Research、Make Situation、Recovery disk as the realization of functions such.
引文
[1]摩尔根与果蝇[PPT/OL],Tomas Hunt Morgan and drosophila http://basic.shsmu.edu cn/jpkc/Marx_philosophy/yxyzx/256,1,Thomas Hunt Morgan
[1] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior[M]. Princeton: Princeton University Press, 1944
[2] Shannon, Claude E. Programming a computer for playing chess[J]. Philosophical Magazine, 1950,41:256-275
[3] A. Turing. Digital computers applied to games. Father than Thought [C] (B. Bowden, editor), Pitman, 1953, 286-295
[4] S. H. Fuller, J. G. Gasching and J. J. Gillogly, An analysis of the alpha-beta pruning algorithm[D]. Department of Computer Science Report, Caregie-Mellon University, Pittsburg, 1973
[5] D.E Knuth and R.N Moore, An analyze of alpha-beta pruning[J]. Artificial Intelligence, 1975,6: 293-326
[6] R.Korf. Iterative deepening: An optimal admissible tree search[J]. Artificial Intelligence, 1985, 27(1):97-109
[7] Jonathan Schaeffer,The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Patton Analysis and Machine Intelligence,November 1989, PAMI-11 (1): 1203-1212
[8] Breakthrough of the year, S, cience[J], 2007, Vol. 318, 1842-1849
[9] T.A. Marsland , COMPUTER CHESS AND SEARCH[D], Computing Science Department, University of Alberta
[10] Berliner H J. An Examination of Brute Force Intelligence[C]. International Joint Conference on Artificial Intelligence, 1981:581-587
[11] E. Heinz, "How DarkThought plays chess," Journal of the International Computer Chess Association, Vol. 20, No. 3, pp. 166-176 (1997)
[12] Cracraft, S.M. (1984). Bitmap move generation in chess. 1CCA Journal, Vol. 7, No. 3, pp. 1984: 146-153
[13] Andreas Junghanns, J. Schaeffer, Search Vesus Knowledge in Game- Playing Program Revisited. Technical Report, Dept. of Computer Science, University of Albama, 1998
[14] Hsu, S.C. and Tsao, K.M. (1991). Design and Implementation of an Opening Game Knowledge-Base System for Computer Ch Endgame Database by Retrograde Analysis
[15] A.Zobrist. 'A New Hashing Method with Application for Game Playing' . Technical Report 88, Computer Science Department, University of Wisconsin, Madison. 1970
[16] Haw-ren Fang, Tsan-sheng Hsu, and Shun-chin Hsu, Construction of Chinese Chess
[17] REN WU, Donald F.Beal, A Memory Efficient Retrograde lgorithm and Its Application To Chinese Chess Endgames, More Games of No Chance MSRI Publications Volume 42, 2002
[18] Holland J H.Adaptation in nature and artificial system[M].Ann Arbor : The University of Michigan Press, 1975. inese Chess[J]. Bulletin of the College of Engineering, N.T.U., No. 53, pp. 75-86
[19]王小春:《PC游戏编程(人机博弈)》[M],2002年,第一版,重庆大学出版社
[20]网冠科技:《Visual C++.NET小游戏开发时尚编程百例》[M],2004年,第一版,机械工业出版社
[21]陈建春:《Visual C++高级编程技术--开发实例剖析》[M],1999年,第一版,电子工业出版社
[22]涂光平,黄敏,钟坚成等:《Visual C++.NET基础教程与上机指导》[M],2005年,第一版,清华大学出版社
[23]伍红兵:《Visual C++编程深入引导》[M],2002年,第一版,中国水利水电出版社
[24]何斌,马天予,王运坚等编著:《Visual C++数字图像处理》[M],2002年(第二版),人民邮电出版社
[25]范如国,韩民春:《博弈论》[M],武汉大学出版社,2006.1
[26]李光久:《博弈论基础教程》[M],化学工业出版社,2005
[27]徐心和,徐长明,邓志立:积极开展民间棋类的计算机博弈活动[G],《2007中国自动化教育年会论文集》,机械工业出版社
[28]徐心和,王骄:中国象棋计算机博弈关键技术分析[J],《小型微型计算机系统》,2006年第6期
[29]徐心和,王浩,孔凡禹:事件对策理论及在棋类游戏中的应用[G],《2007年中国智能自动化会议论文集》
[30]徐阳东,刘弘:遗传算法在机器博弈中的创新应用[J],《电脑知识与技术》,2008年第1卷第7期
[31]何大华,陈传波:弈棋程序的设计思路[G],《2004年全国理论计算机科学学术年会计算机科学》
[32]韩逢庆:基于选手风格的中国象棋博弈树搜索[G],《2006中国机器博弈学术研讨会》
[33]王晓鹏,王骄,徐心和等:中国象棋与国际象棋比较分析[G],《2006中国机器博弈学术研讨会》
[34]徐心和,郑新颖:棋牌游戏与事件对策[G],《2006中国机器博弈学术研讨会》
[35]褚泽永,黄鸿,黄远灿:浅析中国象棋计算机博弈关键技术[G],《2006中国机器博弈学术研讨会》
[36]叶品星:一种博弈树静态估值算法-△Feature状态估值[J],《计算机工程与设计》,2004年第25卷第7期
[37]周玮,张赜,周静怡:基于对弈局势的二次估值方法[J],《系统仿真学报》,2006年第9期
[38]张越,芦东昕:面向目标的博弈搜索策略及其应用[J],《计算机技术与发展》,2007年第3期
[39]王骄,王涛,罗艳红等:中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J],《东北大学学报(自然科学版)》,2005年第10期
[40]周玮,王水涛,孙旸:中国象棋计算机博弈中的一种数据结构方法[J],《计算机工程与应用》,2006年第35期
[41]陈光:遗传算法在人工智能中的应用[J],《福建电脑》,2005年第11期
[42]付强,陈焕文:基于RL算法的自学习博弈程序设计及实现[J],》长沙理工大学学报(自然科学版)》,2007年第4期
[43]ICGA赛:电脑棋类程序竞赛[EB/OL]。http://www.grappa.univ-lille3.fr/icga/?lang=4
[44]象棋百科全书论坛[EB/OL]。http://www.elepllantbase.net
[1] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior[M]. Princeton: Princeton University Press, 1944
[2] Shannon, Claude E. Programming a computer for playing chess[J]. Philosophical Magazine, 1950,41:256-275
[3] A. Turing. Digital computers applied to games. Father than Thought [C] (B. Bowden, editor), Pitman, 1953, 286-295
[4] S. H. Fuller, J. G. Gasching and J. J. Gillogly, An analysis of the alpha-beta pruning algorithm[D]. Department of Computer Science Report, Caregie-Mellon University, Pittsburg, 1973
[5] D.E Knuth and R.N Moore, An analyze of alpha-beta pruning[J]. Artificial Intelligence, 1975,6: 293-326
[6] R.Korf. Iterative deepening: An optimal admissible tree search[J]. Artificial Intelligence, 1985, 27(1):97-109
[7] Jonathan Schaeffer,The history heuristic and alpha-beta search enhancements in practice. IEEE Transactions on Patton Analysis and Machine Intelligence,November 1989, PAMI-11 (1): 1203-1212
[8] Breakthrough of the year, S, cience[J], 2007, Vol. 318, 1842-1849
[9] T.A. Marsland , COMPUTER CHESS AND SEARCH[D], Computing Science Department, University of Alberta
[10] Berliner H J. An Examination of Brute Force Intelligence[C]. International Joint Conference on Artificial Intelligence, 1981:581-587
[11] E. Heinz, "How DarkThought plays chess," Journal of the International Computer Chess Association, Vol. 20, No. 3, pp. 166-176 (1997)
[12] Cracraft, S.M. (1984). Bitmap move generation in chess. 1CCA Journal, Vol. 7, No. 3, pp. 1984: 146-153
[13] Andreas Junghanns, J. Schaeffer, Search Vesus Knowledge in Game- Playing Program Revisited. Technical Report, Dept. of Computer Science, University of Albama, 1998
[14] Hsu, S.C. and Tsao, K.M. (1991). Design and Implementation of an Opening Game Knowledge-Base System for Computer Ch Endgame Database by Retrograde Analysis
[15] A.Zobrist. 'A New Hashing Method with Application for Game Playing' . Technical Report 88, Computer Science Department, University of Wisconsin, Madison. 1970
[16] Haw-ren Fang, Tsan-sheng Hsu, and Shun-chin Hsu, Construction of Chinese Chess
[17] REN WU, Donald F.Beal, A Memory Efficient Retrograde lgorithm and Its Application To Chinese Chess Endgames, More Games of No Chance MSRI Publications Volume 42, 2002
[18] Holland J H.Adaptation in nature and artificial system[M].Ann Arbor : The University of Michigan Press, 1975. inese Chess[J]. Bulletin of the College of Engineering, N.T.U., No. 53, pp. 75-86
[19]王小春:《PC游戏编程(人机博弈)》[M],2002年,第一版,重庆大学出版社
[20]网冠科技:《Visual C++.NET小游戏开发时尚编程百例》[M],2004年,第一版,机械工业出版社
[21]陈建春:《Visual C++高级编程技术--开发实例剖析》[M],1999年,第一版,电子工业出版社
[22]涂光平,黄敏,钟坚成等:《Visual C++.NET基础教程与上机指导》[M],2005年,第一版,清华大学出版社
[23]伍红兵:《Visual C++编程深入引导》[M],2002年,第一版,中国水利水电出版社
[24]何斌,马天予,王运坚等编著:《Visual C++数字图像处理》[M],2002年(第二版),人民邮电出版社
[25]范如国,韩民春:《博弈论》[M],武汉大学出版社,2006.1
[26]李光久:《博弈论基础教程》[M],化学工业出版社,2005
[27]徐心和,徐长明,邓志立:积极开展民间棋类的计算机博弈活动[G],《2007中国自动化教育年会论文集》,机械工业出版社
[28]徐心和,王骄:中国象棋计算机博弈关键技术分析[J],《小型微型计算机系统》,2006年第6期
[29]徐心和,王浩,孔凡禹:事件对策理论及在棋类游戏中的应用[G],《2007年中国智能自动化会议论文集》
[30]徐阳东,刘弘:遗传算法在机器博弈中的创新应用[J],《电脑知识与技术》,2008年第1卷第7期
[31]何大华,陈传波:弈棋程序的设计思路[G],《2004年全国理论计算机科学学术年会计算机科学》
[32]韩逢庆:基于选手风格的中国象棋博弈树搜索[G],《2006中国机器博弈学术研讨会》
[33]王晓鹏,王骄,徐心和等:中国象棋与国际象棋比较分析[G],《2006中国机器博弈学术研讨会》
[34]徐心和,郑新颖:棋牌游戏与事件对策[G],《2006中国机器博弈学术研讨会》
[35]褚泽永,黄鸿,黄远灿:浅析中国象棋计算机博弈关键技术[G],《2006中国机器博弈学术研讨会》
[36]叶品星:一种博弈树静态估值算法-△Feature状态估值[J],《计算机工程与设计》,2004年第25卷第7期
[37]周玮,张赜,周静怡:基于对弈局势的二次估值方法[J],《系统仿真学报》,2006年第9期
[38]张越,芦东昕:面向目标的博弈搜索策略及其应用[J],《计算机技术与发展》,2007年第3期
[39]王骄,王涛,罗艳红等:中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J],《东北大学学报(自然科学版)》,2005年第10期
[40]周玮,王水涛,孙旸:中国象棋计算机博弈中的一种数据结构方法[J],《计算机工程与应用》,2006年第35期
[41]陈光:遗传算法在人工智能中的应用[J],《福建电脑》,2005年第11期
[42]付强,陈焕文:基于RL算法的自学习博弈程序设计及实现[J],》长沙理工大学学报(自然科学版)》,2007年第4期
[43]ICGA赛:电脑棋类程序竞赛[EB/OL]。http://www.grappa.univ-lille3.fr/icga/?lang=4
[44]象棋百科全书论坛[EB/OL]。http://www.elepllantbase.net