[1]王亚杰,邱虹坤,吴燕燕,等.计算机博弈的研究与发展[J].智能系统学报,2016,11(6):788-798.[doi:10.11992/tis.201609006]
WANG Yajie,QIU Hongkun,WU Yanyan,et al.Research and development of computer games[J].CAAI Transactions on Intelligent Systems,2016,11(6):788-798.[doi:10.11992/tis.201609006]
点击复制
WANG Yajie,QIU Hongkun,WU Yanyan,et al.Research and development of computer games[J].CAAI Transactions on Intelligent Systems,2016,11(6):788-798.[doi:10.11992/tis.201609006]
计算机博弈的研究与发展
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
11
期数:
2016年第6期
页码:
788-798
栏目:
综述
出版日期:
2017-01-20
- Title:
- Research and development of computer games
- Keywords:
- artificial intelligence; computer game; Monte Carlo tree search; neural networks; genetic algorithm; deep learning
- 分类号:
- TP391
- 摘要:
- 计算机博弈是人工智能领域重要而极具挑战性的研究方向。本文首先回顾了计算机博弈的发展历程，以及国内外的计算机博弈赛事情况，各种竞赛为计算机博弈技术的发展提供了一个技术验证与学术交流的平台。然后介绍了计算机博弈系统的构成，一个博弈系统包括博弈平台、博弈树搜索、局面评估、着法生成、机器学习等多方面技术；重点阐述了极大极小搜索、剪枝搜索、蒙特卡罗搜索等常用算法的原理与特点；对局面评估方法和各种优化算法也进行了分析，其中的并行计算、遗传算法和基于神经网络的深度学习算法等都是提升机器智能的有效方法。最后，分析了计算机博弈研究面临的问题，并展望了未来的发展方向与趋势。
- Abstract:
- Computer gaming is one of the most important and challenging research directions in the field of Artificial Intelligence (AI). First, this paper reviewed the development of computer games, and the competitions in China and abroad. All types of competitions provide a platform of technical verification and academic communication for the development of computer game technology. Second, the computer game system was introduced, which includes the game platform, the game tree search, the situation evaluation, the move generation, the machine learning and other technologies. The principles and features of the typically used algorithms were stated, such as the Minimax searching algorithm, the pruning searching algorithm, the Monte Carlo searching algorithm, and so on. The situation evaluation method and many optimization algorithms were also analyzed, among which, parallel computing, the genetic algorithm and the deep learning algorithm, based on a neural network, were effective methods to promote machine intelligence. Finally, the challenges of computer games were analyzed, and the development and future trends were proposed.
- 参考文献/References:
-
[1] 徐心和, 邓志立, 王骄, 等. 机器博弈研究面临的各种挑战[J]. 智能系统学报, 2008, 3(4):288-293. XU Xinhe, DENG Zhili, WANG Jiao, et al. Challenging issues facing computer game research[J]. CAAI transactions on intelligent systems, 2008, 3(4):288-293.
[2] 徐心和. 计算机博弈--对于人类思维的挑战[J]. 中国科技博览, 2009(34):194-195.
[3] SILVER D, HUANG Ajia, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587):484-489.
[4] BENCH-CAPON T J M, DUNNE P E. Argumentation in artificial intelligence[J]. Artificial intelligence, 2007, 171(10/15):619-641.
[5] PENNISI E. Breakthrough of the year:human genetic variation[J]. Science, 2007, 318(5858):1842-1843.
[6] SHANNON C E. Programming a computer for playing chess[J]. Philosophical magazine, 1950, 41(314):2562275.
[7] BERNSTEIN A, ARBUCKLE T, DE V ROBERTS M, et al. A chess playing program for the IBM 704[C]//Proceedings of the May 6-8, 1958, Western Joint Computer Conference:Contrasts in Computers. New York, NY, USA:ACM, 1958:157-159.
[8] SAMUEL A L. Some studies in machine learning using the game of checkers. II:recent progress[J]. IBM journal of research and development, 1967, 11(6):601-617.
[9] FULLER S H, GASCHNIG J G, GILLOGLY J J. Analysis of the alpha-beta pruning algorithm[R]. Carnegie:Carnegie Mellon University, 1973.
[10] KORF R E. Depth-first iterative-deepening:an optimal admissible tree search[J]. Artificial intelligence, 1985, 27(1):97-109.
[11] ROIZEN I, PEARL J. A minimax algorithm better than alpha-beta? Yes and No[J]. Artificial intelligence, 1983, 21(1/2):199-220.
[12] RUMELHART D E, HINTON G E, WILLIAMS R J. Learning representations by back-propagating errors[J]. Nature, 1986, 323(6088):533-536.
[13] GELLY S, SILVER D. Combining online and offline knowledge in UCT[C]//Proceedings of the 24th International Conference on Machine Learning. New York, USA:ACM, 2007:273-280.
[14] 李之棠, 陈华民. 博弈树并行搜索算法[J]. 小型微型计算机系统, 1998, 19(10):53-56. LI Zhitang, CHEN Huamin. Parallel game-tree search[J]. Mini-micro systems, 1998, 19(10):53-56.
[15] DAVID-TABIBI O, KOPPEL M, NETANYAHU N S. Genetic algorithms for automatic search tuning[J]. ICGA journal, 2010, 33(2):67-79.
[16] HINTON G E, SALAKHUTDINOV R R. Reducing the dimensionality of data with neural networks[J]. Science, 2006, 313(5786):504-507.
[17] WU I C, CHANG H C. Threat-based proof search for Connect 6[R]. Taiwan, China:National Chiao Tung University, 2006.
[18] 徐心和, 王骄. 中国象棋计算机博弈关键技术分析[J]. 小型微型计算机系统, 2006, 27(6):961-969. XU Xinhe, WANG Jiao. Key technologies analysis of Chinese chess computer game[J]. Mini-micro systems, 2006, 27(6):961-969.
[19] 王骄, 王涛, 罗艳红, 等. 中国象棋计算机博弈系统评估函数的自适应遗传算法实现[J]. 东北大学学报:自然科学版, 2005, 26(10):949-952. WANG Jiao, WANG Tao, LUO Yanhong, et al. Implementation of adaptive genetic algorithm of evaluation function in Chinese chess computer game system[J]. Journal of northeastern university:natural science, 2005, 26(10):949-952.
[20] 魏钦刚, 王骄, 徐心和, 等. 中国象棋计算机博弈开局库研究与设计[J]. 智能系统学报, 2007, 2(1):85-89. WEI Qingang, WANG Jiao, XU Xinhe, et al. A study and design of opening-book of computer Chinese Chess[J]. CAAI transactions on intelligent systems, 2007, 2(1):85-89.
[21] 徐长明, 南晓斐, 王骄, 等. 中国象棋机器博弈的时间自适应分配策略研究[J]. 智能系统学报, 2006, 1(2):39-43. XU Changming, NAN Xiaofei, WANG Jiao, et al. Adaptive time allocation strategy in computer game of Chinese Chess[J]. CAAI transactions on intelligent systems, 2006, 1(2):39-43.
[22] LIU Zhiqing, DOU Qing. Automatic pattern acquisition from game records in GO[J]. The journal of China universities of posts and telecommunications, 2007, 14(1):100-105.
[23] LIU Zhiqing, DOU Qing, LI Wenhong, et al. Automatic acquisition of pattern collocations in GO[J]. The journal of China universities of posts and telecommunications, 2008, 15(1):61-67.
[24] 马骁, 王轩, 王晓龙. 一类非完备信息博弈的信息模型[J]. 计算机研究与发展, 2010, 47(12):2100-2109. MA Xiao, WANG Xuan, WANG Xiaolong. The information model for a class of imperfect information game[J]. Journal of computer research and development, 2010, 47(12):2100-2109.
[25] ZHANG Jiajia, WANG Xuan, LIN Jing, et al. UCT algorithm in imperfect information multi-player military chess game[C]//Proceedings of the 11th Joint Conference on Information Sciences. Atlantis Press, 2008:1-9.
[26] WANG X, XU Zhaoyang, MA X. TD (Λ) optimization of imperfect information game’s evaluation function[R]. Japan:WCCGC, 2007.
[27] XIA Zhengyou, ZHU Yongping, LU Hui. Using the loopy belief propagation in Siguo[J]. ICGA journal, 2007, 30(4):209-220.
[28] XIA Zhengyou, ZHU Yongping, LU Hui. Evaluation function for siguo game based on two attitudes[C]//Proceedings of the Third International Conference on Fuzzy Systems and Knowledge Discovery. Berlin Heidelberg:Springer, 2006:1322-1331.
[29] BENGIO Y, LAMBLIN P, POPOVICI D, et al. Greedy layer-wise training of deep networks[M]//SCH?LKOPF B, PLATT J, HOFMANN T. Advances in Neural Information Processing Systems, vol 19. Cambridge:MIT Press, 2007:153-160.
[30] COULOM R. Computing "Elo ratings" of move patterns in the game of go[J]. ICGA journal, 2007, 30(4):198-208.
[31] FERREIRA D R. Determining the strength of chess players based on actual play[J]. ICGA journal, 2012, 35(1):3-19.
[32] NIJSSEN J A M, WINANDS M H M. Search policies in multi-player games1[J]. ICGA journal, 2013, 36(1):3-21.
[33] LEIFKER D B, KANAL L N. A hybrid SSS*/Alpha-Beta algorithm for parallel search of game trees[C]//Proceedings of the 9th International Joint Conference on Artificial Intelligence. San Francisco, CA, USA:ACM, 1985, 2:1044-1046.
[34] PLAAT A, SCHAEFFER J, PIJLS W, et al. Best-first fixed-depth game-tree search in practice[C]//Proceedings of the 14th International Joint Conference on Artificial Intelligence. San Francisco, CA, USA:ACM, 1995, 1:273-279.
[35] BURNS E, LEMONS S, ZHOU Rong, et al. Best-first heuristic search for multi-core machines[C]//Proceedings of the 21st International Jont Conference on Artifical Intelligence. San Francisco, CA, USA:ACM, 2009:449-455.
[36] 王骄, 徐心和. 计算机博弈:人工智能的前沿领域--全国大学生计算机博弈大赛[J]. 计算机教育, 2012(7):14-18.
[37] 邱虹坤. 全国计算机博弈大赛网站[EB/OL].[2016-04-22]. 2013.
[38] 张利群. 实现苏拉卡尔塔棋网络博弈平台的吃子算法[J]. 计算机工程与应用, 2016, 52(7):62-66. ZHANG Liqun. Realization of capture algorithm about Surakarta chess network battle platform in computer game[J]. Computer engineering and applications, 2016, 52(7):62-66.
[39] 张小川, 陈光年, 张世强, 等. 六子棋博弈的评估函数[J]. 重庆理工大学学报:自然科学版, 2010, 24(2):64-68. ZHANG Xiaochuan, CHEN Guangnian, ZHANG Shiqiang, et al. Research on evaluation functions for computer game of connect 6[J]. Journal of Chongqing university of technology:natural science, 2010, 24(2):64-68.
[40] 李淑琴, 李静波, 韩裕华, 等. 苏拉卡尔塔博弈系统中评估函数的研究[J]. 北京信息科技大学学报, 2012, 27(6):42-45, 61. LI Shuqin, LI Jingbo, HAN Yuhua, et al. The assessment function in the Surakarta game system[J]. Journal of Beijing information science and technology university, 2012, 27(6):42-45, 61.
[41] TANG Pingzhong, LIN Fangzhen. Discovering theorems in game theory:two-person games with unique pure Nash equilibrium payoffs[J]. Artificial intelligence, 2011, 175(14/15):2010-2020.
[42] RUBIN J, WATSON I. Case-based strategies in computer poker[J]. AI communications, 2012, 25(1):19-48.
[43] FLESCH J, KUIPERS J, SCHOENMAKERS G, et al. Subgame-perfection in free transition games[J]. European journal of operational research, 2013, 228(1):201-207.
[44] GILPIN A, SANDHOLM T. Lossless abstraction of imperfect information games[J]. Journal of the ACM, 2007, 54(5):25.
[45] 何大华, 陈传波. 关于桥牌的取胜策略[J]. 华中科技大学学报:自然科学版, 2004, 32(7):13-15. HE Dahua, CHEN Chuanbo. The strategy for winning bridge game[J]. Journal of Huazhong university of science & technology:nature science edition, 2004, 32(7):13-15.
[46] CHEN Bonian, LIU Pangfeng, HSU S C, et al. Aggregating consistent endgame knowledge in Chinese Chess[J]. Knowledge-based systems, 2012, 34:34-42.
[47] 郭琴琴, 李淑琴, 包华. 亚马逊棋机器博弈系统中评估函数的研究[J]. 计算机工程与应用, 2012, 48(34):50-54. GUO Qinqin, LI Shuqin, BAO Hua. Research on evaluation function computer game of Amazon[J]. Computer engineering and applications, 2012, 48(34):50-54.
[48] SCHADD M P D, WINANDS M H M. Best reply search for multiplayer games[J]. IEEE transactions on computational intelligence and AI in games, 2011, 3(1):57-66.
[49] 李学俊, 王小龙, 吴蕾, 等. 六子棋中基于局部"路"扫描方式的博弈树生成算法[J]. 智能系统学报, 2015, 10(2):267-272. LI Xuejun, WANG Xiaolong, WU Lei, et al. Game tree generation algorithm based on local-road scanning method for connect 6[J]. CAAI transactions on intelligent systems, 2015, 10(2):267-272.
[50] ETESSAMI K, LOCHBIHLER A. The computational complexity of evolutionarily stable strategies[J]. International journal of game theory, 2008, 37(1):93-113.
[51] 高强, 徐心和. 时间复杂性和空间复杂性研究[J]. 智能系统学报, 2014, 9(5):529-535. GAO Qiang, XU Xinhe. Research on time complexity and space complexity[J]. CAAI transactions on intelligent systems, 2014, 9(5):529-535.
[52] GAO Qiang, XU Xinhe. Research on the computational complexity of n x n Chinese chess[J]. ICGA journal, 2015, 38(1):47-53.
[53] VAN DER HERIK H J, UITERWIJK J W H M, VAN RIJSWIJCK J. Games solved:now and in the future[J]. Artificial intelligence, 2002, 134(1/2):277-311.
[54] KAINDL H, SHAMS R, HORACEK H. Minimax search algorithms with and without aspiration windows[J]. IEEE transactions on pattern analysis and machine intelligence, 1991, 13(12):1225-1235.
[55] LU Hui, XIA Zhengyou. AWT:aspiration with timer search algorithm in Siguo[C]//Proceedings of the 6th International Conference on Computers and Games. Berlin Heidelberg:Springer-Verlag, 2008:264-274.
[56] 邹竞. 基于MTD(f)的中国象棋人机博弈算法的设计与优化[J]. 计算机与数字工程, 2008, 36(9):38-43.ZOU Jing. Chinese chess algorithm design and optimize based on MTD(f)[J]. Computer & digital engineering, 2008, 36(9):38-43.
[57] 张明亮, 李凡长. 一种新的博弈树搜索方法[J]. 山东大学学报:工学版, 2009, 39(6):1-8. ZHANG Mingliang, LI Fanzhang. A new search method for a game tree[J]. Journal of Shandong university:engineering science, 2009, 39(6):1-8.
[58] 焦尚彬, 刘丁. 博弈树置换表启发式算法研究[J]. 计算机工程与应用, 2010, 46(6):42-45. JIAO Shangbin, LIU Ding. Research on translation table heuristic algorithm[J]. Computer engineering and applications, 2010, 46(6):42-45.
[59] DONKERS H H L M, UITERWIJK J W H M, VAN DER HERIK H J. Probabilistic opponent-model search[J]. Information sciences, 2001, 135(3/4):123-149.
[60] SCHAEFFER J. The History heuristic and alpha-beta search enhancements in practice[J]. IEEE transactions on pattern analysis and machine intelligence, 1989, 11(11):1203-1212.
[61] SAKUTA M, HASHIMOTO T, NAGASHIMA J, et al. Application of the killer-tree heuristic and the lambda-search method to lines of action[J]. Information sciences, 2003, 154(3/4):141-155.
[62] REINEFELD A, MARSLAND T A. Enhanced iterative-deepening search[J]. IEEE transactions on pattern analysis and machine intelligence, 1994, 16(7):701-710.
[63] MARSLAND T A, REINEFELD A, SCHAEFFER J. Low overhead alternatives to SSS[J]. Artificial intelligence, 1987, 31(2):185-199.
[64] PLAAT A, SCHAEFFER J, PIJLS W, et al. SSS*=alpha-beta + TT[J]. Computer Science, 2014, 8(1):25.
[65] BERLINER H. The B* tree search algorithm:a best-first proof procedure[J]. Artificial intelligence, 1979, 12(1):23-40.
[66] BERLINER H J, MCCONNELL C. B * probability based search[J]. Artificial intelligence, 1996, 86(1):97-156.
[67] LORENTZ R. Using evaluation functions in Monte-Carlo tree search[J]. Theoretical computer science, 2016, 644:106-113.
[68] GUEZ A, SILVER D, DAYAN P. Scalable and efficient Bayes-adaptive reinforcement learning based on Monte-Carlo tree search[J]. Journal of artificial intelligence research, 2013, 48(1):841-883.
[69] BROWNE C B, POWLEY E, WHITEHOUSE D, et al. A survey of Monte Carlo tree search methods[J]. IEEE transactions on computational intelligence and AI in games, 2012, 4(1):1-43.
[70] BAIER H, WINANDS M H M. Time management for Monte Carlo tree search[J]. IEEE transactions on computational intelligence and AI in games, 2016, 8(3):301-314.
[71] RAIKO T, PELTONEN J. Application of UCT search to the connection games of Hex, Y, * Star, and Renkula[C]//Proceedings of the Finnish AI Conference. Espoo, Finland, 2008.
[72] 吕艳辉, 宫瑞敏. 计算机博弈中估值算法与博弈训练的研究[J]. 计算机工程, 2012, 38(11):163-166. LV Yanhui, GONG Ruimin. Study on valuation algorithm and game training in computer game[J]. Computer engineering, 2012, 38(11):163-166.
[73] TAKEUCHI S, KANEKO T, YAMAGUCHI K. Evaluation of game Tree search methods by game records[J]. IEEE transactions on computational intelligence and AI in games, 2010, 2(4):288-302.
[74] LIEBERUM J. An evaluation function for the game of amazons[J]. Theoretical computer science, 2005, 349(2):230-244.
[75] MARSLAND T A, CAMPBELL M. Parallel search of strongly ordered game trees[J]. ACM computing surveys, 1982, 14(4):533-551.
[76] 刘建伟, 刘媛, 罗雄麟. 深度学习研究进展[J]. 计算机应用研究, 2014, 31(7):1921-1930, 1942. LIU Jianwei, LIU Yuan, LUO Xionglin. Research and development on deep learning[J]. Application research of computers, 2014, 31(7):1921-1930, 1942.
[77] XIE Fan, LIU Zhiqing, WANG Yu, et al. Systematic Improvement of Monte-Carlo Tree Search with Self-generated Neural-Networks Controllers[M]//BLUM C, BATTITI R. Learning and Intelligent Optimization:Lecture Notes in Computer Science. Berlin Heidelberg:Springer, 2010:228-231.
[78] 张小川, 唐艳, 梁宁宁. 采用时间差分算法的九路围棋机器博弈系统[J]. 智能系统学报, 2012, 7(3):278-282. ZHANG Xiaochuan, TANG Yan, LIANG Ningning. A 9×9 go computer game system using temporal difference[J]. CAAI transactions on intelligent systems, 2012, 7(3):278-282.
- 相似文献/References:
-
[1]李德毅.网络时代人工智能研究与发展[J].智能系统学报,2009,4(1):1.
LI De-yi.AI research and development in the network age[J].CAAI Transactions on Intelligent Systems,2009,4():1.
[2]赵克勤.二元联系数A+Bi的理论基础与基本算法及在人工智能中的应用[J].智能系统学报,2008,3(6):476.
ZHAO Ke-qin.The theoretical basis and basic algorithm of binary connection A+Bi and its application in AI[J].CAAI Transactions on Intelligent Systems,2008,3():476.
[3]徐玉如,庞永杰,甘?? 永,等.智能水下机器人技术展望[J].智能系统学报,2006,1(1):9.
XU Yu-ru,PANG Yong-jie,GAN Yong,et al.AUV—state-of-the-art and prospect[J].CAAI Transactions on Intelligent Systems,2006,1():9.
[4]王志良.人工心理与人工情感[J].智能系统学报,2006,1(1):38.
WANG Zhi-liang.Artificial psychology and artificial emotion[J].CAAI Transactions on Intelligent Systems,2006,1():38.
[5]赵克勤.集对分析的不确定性系统理论在AI中的应用[J].智能系统学报,2006,1(2):16.
ZHAO Ke-qin.The application of uncertainty systems theory of set pair analysis (SPU)in the artificial intelligence[J].CAAI Transactions on Intelligent Systems,2006,1():16.
[6]秦裕林,朱新民,朱? 丹.Herbert Simon在最后几年里的两个研究方向[J].智能系统学报,2006,1(2):11.
QIN Yu-lin,ZHU Xin-min,ZHU Dan.Herbert Simons two research directions in his lost years[J].CAAI Transactions on Intelligent Systems,2006,1():11.
[7]谷文祥,李 丽,李丹丹.规划识别的研究及其应用[J].智能系统学报,2007,2(1):1.
GU Wen-xiang,LI Li,LI Dan-dan.Research and application of plan recognition[J].CAAI Transactions on Intelligent Systems,2007,2():1.
[8]魏钦刚,王? 骄,徐心和,等.中国象棋计算机博弈开局库研究与设计[J].智能系统学报,2007,2(1):85.
WEI Qin gang,WANG Jiao,XU Xin he,et al.A study and design of openingbook of computer Chinese C h ess[J].CAAI Transactions on Intelligent Systems,2007,2():85.
[9]杨春燕,蔡 文.可拓信息-知识-智能形式化体系研究[J].智能系统学报,2007,2(3):8.
YANG Chun-yan,CAI Wen.A formalized system of extension information-knowledge-intelligence[J].CAAI Transactions on Intelligent Systems,2007,2():8.
[10]黄? 晨.棋类游戏中的先行权[J].智能系统学报,2007,2(3):91.
HUANG Chen.The firstmove advantage in board games[J].CAAI Transactions on Intelligent Systems,2007,2():91.
[11]李淑琴,陈子鹏,郑蓝舟,等.竞技二打一游戏中同等牌力的研究[J].智能系统学报,2021,16(3):466.[doi:10.11992/tis.202007005]
LI Shuqin,CHEN Zipeng,ZHENG Lanzhou,et al.Research on the equal card force competition system of competitive two against one game[J].CAAI Transactions on Intelligent Systems,2021,16():466.[doi:10.11992/tis.202007005]
备注/Memo
收稿日期:2016-09-07。
基金项目:航空科学基金项目（2015ZC54008）；辽宁省教育厅基金项目（L2015407）.
作者简介:王亚杰,女,1968年生,教授,博士,中国人工智能学会常务理事,中国人工智能学会机器博弈专业委员会主任。主要研究方向为机器博弈、模式识别、图像融合,发表学术论文60余篇,主持和参与课题20余项;邱虹坤,男,1971年生,讲师,主要研究方向为机器博弈、智能机器人与飞行器综合设计,指导学生在全国计算机博弈大赛中多次获得亚马逊棋冠军,发表学术论文20余篇;吴燕燕,女,1989年生,硕士,主要研究方向为图像融合、图像处理方面的研究,发表学术论文5篇,主持或参与课题5项。
通讯作者:邱虹坤.E-mail:qiuhk@sina.com.
更新日期/Last Update:
1900-01-01