[1]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]
Copy

Research and development of computer games

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 11 Number of periods: 2016 6 Page number: 788-798 Column: 综述 Public date: 2017-01-20
Title:
Research and development of computer games
Author(s):
WANG Yajie;  QIU Hongkun;  WU Yanyan;  LI Fei;  YANG Zhoufeng
Engineering Training Center, Shenyang Aerospace University, Shenyang 110136, China
Keywords:
artificial intelligence; computer game; Monte Carlo tree search; neural networks; genetic algorithm; deep learning
CLC:
TP391
DOI:
10.11992/tis.201609006
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems