游戏中基于规则与机器学习的智能技术应用研究
|
摘要
近年来,游戏的图形质量已发展到近乎极致的地步,人工智能(AI)已经成为决定一款游戏以及游戏开发工作室命运的重要因素。下一代的3D游戏不仅会有优秀的视觉效果,更会像人一样狡猾和聪明。由于国内还没有展开全面研究和应用,而且本文研究并实现的AI技术在一定程度上提高了游戏智能,因此该课题具有一定的学术和应用价值。
本文目标是构建一个基本图形渲染引擎,以这个渲染引擎为平台,对若干基于规则和机器学习的AI技术进行了深入研究和实现,并应用若干机器学习技术实现了游戏中一些常见问题的求解。
首先构建图形渲染引擎,功能有:完整流水线,物体剔除,背面消除,欧拉相机,光照模型,固定、恒定和Gouraud着色方法,3D裁剪,深度排序。
然后研究实现了若干基于规则的AI技术。基于规则的AI技术包括:确定性运动算法、随机运动算法、跟踪闪避算法、群聚算法、模式运动技术、行为建模的有穷自动机技术和A*算法等。
最后采用机器学习中的遗传算法和人工神经网络,实现了游戏中以下问题的求解:
1.寻路问题。一条染色体代表一条路径。实验表明遗传算法对结果的不可预知性可以有效地提高寻路的智能;
2.飞行物体的着陆问题。染色体由飞行物体的运行方式组成。实验表明遗传算法对结果的不可预知性使得降落更加智能化,不需要人工的干预;
3.障碍物绕行问题。使用遗传算法改进神经网络的权值;利用以智能体中心为出发点的5条射线模拟传感器感知环境。经过768代的进化,遗传算法种群最优适应度和平均适应度都有了明显提高,绕行成功率从12.5%上升到85%;
4.鼠标轨迹识别问题。神经网络权值由反向传播算法学习更新;采用1200个样例训练,误差阈值为34.0037,另外1200个样例测试,将神经网络与SVM做了实验对比,得出结论:神经网络和SVM的正确分类样本数分别为1125和1185,错误分类样本数分别为75和15,正确率分别为93.75%和98.75%。
下一步工作,希望将这些AI技术有机地结合起来,整合为一个AI引擎,应用在实际的游戏项目中。
Recent years, because of perfect development of graphic hardware and rendering quality in video games, artificial intelligence has become a more and more important factor for success of game developing studios. Next generation of 3D video games not only has perfect optical effect, but also advanced AI.Due to lack of game AI papers and applications, these techniques in this paper, which can improve AI level in games indeed, achieve a measure of academic and applied values.
The target of paper is that building a basic graphic rendering engine first, then based on the engine, several Rules-Based AI techniques are researched and implemented, finally, some usual problems in games are resolved by some machine learning techniques.
Firstly, the graphic rendering engine has an whole pipeline, the functions of the engine as follows: Object culling, Back-face removing, Euler camera model, Lighting model, Constant shading, Flat shading, Gouraud shading, 3D clipping and Depth sorting.
Secondly, some Rules-Based AIs are researched. These Rules-Based AIs include: Deterministic movement algorithm, random movement algorithm, chasing (evading) algorithm,Flocking algorithm, Pattern movement technique, FSM technique and A* algorithm.
Finally, These 4 problems are resolved by using Genetic Algorithm(GA) and Artificial Neural Network(ANN):
1. Pathfinding.The experiment shows that the unpredictable feature of GA can improve intelligence of Pathfinding.
2. spaceship landing. Chromosome consists of movement pattern of spaceship. The result shows that the unpredictable feature of GA can improve intelligence of spaceship landing, no artificial controlling needed.
3. obstacle avoidance. ANN’s weights are updated by GA. Sensors are simulated by 5 line segments that radiate outward from the agent body, the agent can sense the game environment by the 5 sensors. After iterating for 768 times, average fitness and best fitness of the population have been improved quickly, the ratio of avoiding successfully has been improved from 12.5% to 85%.
4. Resolved mouse track recognition. ANN’s weights are updated by Back Propagation algorithm. The size of training data set is 1200, error threshold is 37.0037, the size of testing data set is 1200, according to contrastive analysis of ANN and SVM, the result is that the right recognition number of testing samples for ANN is 1125, for SVM is 1185, the wrong recognition number of testing samples for ANN is 75, for SVM is 15, the precision for ANN is 93.75%, for SVM is 98.75%.
Next step,AI techniques in this paper will be integrated into an AI engine,and this AI engine is expected to actual game projects.
本文目标是构建一个基本图形渲染引擎,以这个渲染引擎为平台,对若干基于规则和机器学习的AI技术进行了深入研究和实现,并应用若干机器学习技术实现了游戏中一些常见问题的求解。
首先构建图形渲染引擎,功能有:完整流水线,物体剔除,背面消除,欧拉相机,光照模型,固定、恒定和Gouraud着色方法,3D裁剪,深度排序。
然后研究实现了若干基于规则的AI技术。基于规则的AI技术包括:确定性运动算法、随机运动算法、跟踪闪避算法、群聚算法、模式运动技术、行为建模的有穷自动机技术和A*算法等。
最后采用机器学习中的遗传算法和人工神经网络,实现了游戏中以下问题的求解:
1.寻路问题。一条染色体代表一条路径。实验表明遗传算法对结果的不可预知性可以有效地提高寻路的智能;
2.飞行物体的着陆问题。染色体由飞行物体的运行方式组成。实验表明遗传算法对结果的不可预知性使得降落更加智能化,不需要人工的干预;
3.障碍物绕行问题。使用遗传算法改进神经网络的权值;利用以智能体中心为出发点的5条射线模拟传感器感知环境。经过768代的进化,遗传算法种群最优适应度和平均适应度都有了明显提高,绕行成功率从12.5%上升到85%;
4.鼠标轨迹识别问题。神经网络权值由反向传播算法学习更新;采用1200个样例训练,误差阈值为34.0037,另外1200个样例测试,将神经网络与SVM做了实验对比,得出结论:神经网络和SVM的正确分类样本数分别为1125和1185,错误分类样本数分别为75和15,正确率分别为93.75%和98.75%。
下一步工作,希望将这些AI技术有机地结合起来,整合为一个AI引擎,应用在实际的游戏项目中。
Recent years, because of perfect development of graphic hardware and rendering quality in video games, artificial intelligence has become a more and more important factor for success of game developing studios. Next generation of 3D video games not only has perfect optical effect, but also advanced AI.Due to lack of game AI papers and applications, these techniques in this paper, which can improve AI level in games indeed, achieve a measure of academic and applied values.
The target of paper is that building a basic graphic rendering engine first, then based on the engine, several Rules-Based AI techniques are researched and implemented, finally, some usual problems in games are resolved by some machine learning techniques.
Firstly, the graphic rendering engine has an whole pipeline, the functions of the engine as follows: Object culling, Back-face removing, Euler camera model, Lighting model, Constant shading, Flat shading, Gouraud shading, 3D clipping and Depth sorting.
Secondly, some Rules-Based AIs are researched. These Rules-Based AIs include: Deterministic movement algorithm, random movement algorithm, chasing (evading) algorithm,Flocking algorithm, Pattern movement technique, FSM technique and A* algorithm.
Finally, These 4 problems are resolved by using Genetic Algorithm(GA) and Artificial Neural Network(ANN):
1. Pathfinding.The experiment shows that the unpredictable feature of GA can improve intelligence of Pathfinding.
2. spaceship landing. Chromosome consists of movement pattern of spaceship. The result shows that the unpredictable feature of GA can improve intelligence of spaceship landing, no artificial controlling needed.
3. obstacle avoidance. ANN’s weights are updated by GA. Sensors are simulated by 5 line segments that radiate outward from the agent body, the agent can sense the game environment by the 5 sensors. After iterating for 768 times, average fitness and best fitness of the population have been improved quickly, the ratio of avoiding successfully has been improved from 12.5% to 85%.
4. Resolved mouse track recognition. ANN’s weights are updated by Back Propagation algorithm. The size of training data set is 1200, error threshold is 37.0037, the size of testing data set is 1200, according to contrastive analysis of ANN and SVM, the result is that the right recognition number of testing samples for ANN is 1125, for SVM is 1185, the wrong recognition number of testing samples for ANN is 75, for SVM is 15, the precision for ANN is 93.75%, for SVM is 98.75%.
Next step,AI techniques in this paper will be integrated into an AI engine,and this AI engine is expected to actual game projects.
引文
[1]艾瑞咨询集团.中国网络游戏行业发展报告2007-2008年简版[Z].www.iresearch.co m.cn.,2007/2008:14.
[2]网易科技.国产网络游戏市场占有率已达64.8 % [Z].http://tech.163.com/07/1123/02/ 3TUVH7SI000915BF.html,2007.11.23.
[3]新浪游戏.网络游戏研发纳入863计划国家投资500万元支持[Z].http://games. sina.com.cn/newgames/2003/09/09015040.shtml,2003.09.
[4] Steve Rabin.庄越挺,吴飞译.人工智能游戏编程真言[M].北京:清华大学出版社,2005.
[5] Michael van Lent. Game Smarts[J]. Entertainment Computing. April 2007,40(4):99-101..
[6]胡丹桂.基于游戏引擎的3D图形系统的研究[D].武汉理工大学,硕士学位论文,2005.11.
[7] Blizzard Entertainment.WarCraft II:Tides of Darkness[Z]. www.blizzard.com,1995.
[8] Ensemble Studio/Microsoft.Age of Empires II:The Age of Kings[Z].www. ensemblestudios.com/aoeii/index.html.shtml,1999.
[9] Valve Software.Inc./Sierra.Half-Life[Z].www.sierrastudios.com/games/half-life,1998.
[10] Epic Games.Unreal:Tournament[Z]. www.epicgames.com,2008.
[11] CyberLife Technologies/Millennium Interactive,Warner Brothers Interactive Entertainment. Creatures[Z]. www.creaturelabs.com,1996.
[12] Lionhead Studios/Electronic Arts.Black&White[Z]. www.bwgame.com,2001.
[13] Steven Woodcock. AI Roundtable Moderator’s Report. 2003 Game Developer’s Conference [Z].http://www.gameai.com/stevestuff.html,2003,March 6~8.
[14] David M. Bourg, Glenn Seemann. AI for Game Developers(影印本)[M].南京:东南大学出版社,2005.5.
[15] Steve Woodcock.Games Making Interesting Use of Artificial Intelligence Techniques [Z].http://www.gameai.com/games.html.
[16] Daniel Johnson, Janet Wiles. Computer Games with Intelligence[C].2001 IEEE International Fuzzy Systems Conference,2001,3:1356~1358.
[17] Steve Woodcock.Game AI: The State of the Industry[Z].http://www. gamasutra.com /features/20001101/woodcock_01.htm,November 1, 2000.
[18] Steve Woodcock.Game AI: The State of the Industry [Z].http://www. gamasutra.com /features/19990820/game_ai_01.htm, August 20, 1999.
[19] Craig W. Reynolds. Flocks, Herds, and Schools:A Distributed Behavioral Model[C]. ACM SIGGRAPH '87 Conference Proceedings, Anaheim, California, July 1987,21(4):35-34.
[20] Matt Parker, Gary B.Parker.The Evolution of Multi-Layer Neural Networks for the Control of Xpilot Agents[C].Proceeding of the 2007 IEEE Symposium on Computational Intelligence and Games(CIG 2007), Honolulu, Hawaii, USA,2007: 232-237.
[21] Hisao Ishibuchi, Teppei Seguchi.Successive Adaptation of Neural Networks in a Multi- Agent Model[C]. Neural Networks, 2002. IJCNN '02. Proceedings of the 2002 International Joint Conference,Honolulu, HI, USA,2002,3:2454-2459.
[22] Kumar Chellapilla,David B.Fogel. Evolving an Expert Checkers Playing Program Without Using Human Expertise[J]. Evolutionary Computation, IEEE Transactions,,Aug 2001,5(4): 422-428.
[23] Daniel S. McFarlin, Peter M. Todd. Evolving a Better Adversary: A Case Study in a German Castle[C]. Artificial Life, 2007. ALIFE '07. IEEE Symposium, 1-5 April 2007: 229-235.
[24] S. Y. Chong, D. C. Ku, H. S., Lim, M. K. Tan, and J. D. White. Evolved Neural Networks Learning Othello Strategies[C]. Evolutionary Computation, 2003. CEC '03. The 2003 Congress, 8-12 Dec. 2003,3: 2222- 2229.
[25] Yi Jack Yau and Jason Teo. An Empirical Comparison of Non-adaptive, Adaptive and Self-Adaptive Co-evolution for Evolving Artificial Neural Network Game Players[C]. Cybernetics and Intelligent Systems, 2006 IEEE Conference, June 2006: 1-6.
[26] Steve Woodcock.Games with Extensible AIs[Z]. http://www.gameai.com/exaigames.html.
[27] Bruce Shelley.Guidelines for Developing Successful Games[Z].http://www.gamasutra.com/ features/20010815/shelley_01.htm,August 15, 2001.
[28] James Matthews. How To Get Started with Gaming AI [Z].http:// www. generat- ion5.org/content/2001/howto00.asp,March,2,2001.
[29]任爱华.计算机图形学[M].北京:北京航空航天大学出版社,2005.
[30] AndréLaMothe.沙鹰译.Windows游戏编程大师技巧(第2版)[M].北京:中国电力出版社,2003.
[31] AndréLaMothe.Tricks of the 3D Game Programming Gurus—Advanced 3D Graphics and Rasterization[M]. United States of America:Sams Publishing,2003.
[32] Stefan Zerbst,Oliver Duvel.3D Game Engine Programming[M]. United States of America:Thomson Cource Technology PTR/Premier Press.2004.
[33] Stanley B. Lippman,侯捷译.Essential C++中文版[M].武汉:华中科技大学出版社.2001.8.
[34] Stanley B.Lippman,Josee Lajoie.C++ Primer(Third Edition)[M]. United States of America: Addison Wesley.March 26,1998.
[35] Michael Dawson.Beginning C++ Game Programming[M]. United States of America: Thomson Cource Technology PTR/Premier Press.2004.
[36]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社.2002.2.
[37] Mat Buckland.Programming Game AI by Example[M].United States of America:Wordware Publishing,Inc.2005.
[38] Peter Linz,孙家骕译.形式语言与自动机导论[M].北京:机械工业出版社,2005.
[39]王永庆.人工智能原理与方法[M].西安:西安交通大学出版社,2002.
[40]任巍.人工智能技术在计算机游戏软件中的应用[D].西安电子科技大学,硕士学位论文.2006.02.
[41] Tom M. Mitchell.曾华军,张银奎等译.机器学习[M].北京:机械工业出版社,2003.
[42]顾亦然,王锁萍.遗传算法与神经网络在接纳控制中的应用[J].计算机工程与应用,2005,19.
[43] Mat Buckland.AI Techniques for Game Programming[M]. United States of America: Premier Press,2002.
[44]像素软件.像素软件-刀剑封魔录[Z]. http://www.pixelgame.net/games/bs,2007.
[45] Nello Cristianini,John Shawe-Taylor.李国正,王猛,曾华军译.支持向量机导论[M].北京:电子工业出版社,2004:3-5.
[46] Chih-Chung Chang and Chih-Jen Lin. LIBSVM -- A Library for Support Vector Machines [Z]. http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html,2008.
[47]张贝贝.支持向量机多分类方法的研究及应用[D].重庆大学,硕士学位论文,2007.04.
[48] GarageGames.Torque:GarageGames[Z].http://www.garagegames.com/mg/projects/tge/,2008.
[49] Gregory Junker.Pro OGRE 3D Programming[M]. United States of America:Apress,2006.
[50] OGRE.OGRE 3D:Open source graphics engine[Z].http://www.ogre3d.org/,2008.
[51] BigWorld Pty Ltd.Bigworld Technology. http://www.bigworldtech.com/index/index.php [Z],2007.
[52]蒋宁,翟玉庆.一个基于神经网络和遗传算法的游戏自主角色的设计[J].计算机应用, 2007年05期:p1280~1282.
[53]龚向宇,徐东平.优化的遗传算法在游戏编程中的应用[J].电脑知识与技术(学术交流), 2007年02期.
[54]胡俊.游戏开发中的人工智能研究与应用[D].电子科技大学,硕士学位论文,2007.6.
[2]网易科技.国产网络游戏市场占有率已达64.8 % [Z].http://tech.163.com/07/1123/02/ 3TUVH7SI000915BF.html,2007.11.23.
[3]新浪游戏.网络游戏研发纳入863计划国家投资500万元支持[Z].http://games. sina.com.cn/newgames/2003/09/09015040.shtml,2003.09.
[4] Steve Rabin.庄越挺,吴飞译.人工智能游戏编程真言[M].北京:清华大学出版社,2005.
[5] Michael van Lent. Game Smarts[J]. Entertainment Computing. April 2007,40(4):99-101..
[6]胡丹桂.基于游戏引擎的3D图形系统的研究[D].武汉理工大学,硕士学位论文,2005.11.
[7] Blizzard Entertainment.WarCraft II:Tides of Darkness[Z]. www.blizzard.com,1995.
[8] Ensemble Studio/Microsoft.Age of Empires II:The Age of Kings[Z].www. ensemblestudios.com/aoeii/index.html.shtml,1999.
[9] Valve Software.Inc./Sierra.Half-Life[Z].www.sierrastudios.com/games/half-life,1998.
[10] Epic Games.Unreal:Tournament[Z]. www.epicgames.com,2008.
[11] CyberLife Technologies/Millennium Interactive,Warner Brothers Interactive Entertainment. Creatures[Z]. www.creaturelabs.com,1996.
[12] Lionhead Studios/Electronic Arts.Black&White[Z]. www.bwgame.com,2001.
[13] Steven Woodcock. AI Roundtable Moderator’s Report. 2003 Game Developer’s Conference [Z].http://www.gameai.com/stevestuff.html,2003,March 6~8.
[14] David M. Bourg, Glenn Seemann. AI for Game Developers(影印本)[M].南京:东南大学出版社,2005.5.
[15] Steve Woodcock.Games Making Interesting Use of Artificial Intelligence Techniques [Z].http://www.gameai.com/games.html.
[16] Daniel Johnson, Janet Wiles. Computer Games with Intelligence[C].2001 IEEE International Fuzzy Systems Conference,2001,3:1356~1358.
[17] Steve Woodcock.Game AI: The State of the Industry[Z].http://www. gamasutra.com /features/20001101/woodcock_01.htm,November 1, 2000.
[18] Steve Woodcock.Game AI: The State of the Industry [Z].http://www. gamasutra.com /features/19990820/game_ai_01.htm, August 20, 1999.
[19] Craig W. Reynolds. Flocks, Herds, and Schools:A Distributed Behavioral Model[C]. ACM SIGGRAPH '87 Conference Proceedings, Anaheim, California, July 1987,21(4):35-34.
[20] Matt Parker, Gary B.Parker.The Evolution of Multi-Layer Neural Networks for the Control of Xpilot Agents[C].Proceeding of the 2007 IEEE Symposium on Computational Intelligence and Games(CIG 2007), Honolulu, Hawaii, USA,2007: 232-237.
[21] Hisao Ishibuchi, Teppei Seguchi.Successive Adaptation of Neural Networks in a Multi- Agent Model[C]. Neural Networks, 2002. IJCNN '02. Proceedings of the 2002 International Joint Conference,Honolulu, HI, USA,2002,3:2454-2459.
[22] Kumar Chellapilla,David B.Fogel. Evolving an Expert Checkers Playing Program Without Using Human Expertise[J]. Evolutionary Computation, IEEE Transactions,,Aug 2001,5(4): 422-428.
[23] Daniel S. McFarlin, Peter M. Todd. Evolving a Better Adversary: A Case Study in a German Castle[C]. Artificial Life, 2007. ALIFE '07. IEEE Symposium, 1-5 April 2007: 229-235.
[24] S. Y. Chong, D. C. Ku, H. S., Lim, M. K. Tan, and J. D. White. Evolved Neural Networks Learning Othello Strategies[C]. Evolutionary Computation, 2003. CEC '03. The 2003 Congress, 8-12 Dec. 2003,3: 2222- 2229.
[25] Yi Jack Yau and Jason Teo. An Empirical Comparison of Non-adaptive, Adaptive and Self-Adaptive Co-evolution for Evolving Artificial Neural Network Game Players[C]. Cybernetics and Intelligent Systems, 2006 IEEE Conference, June 2006: 1-6.
[26] Steve Woodcock.Games with Extensible AIs[Z]. http://www.gameai.com/exaigames.html.
[27] Bruce Shelley.Guidelines for Developing Successful Games[Z].http://www.gamasutra.com/ features/20010815/shelley_01.htm,August 15, 2001.
[28] James Matthews. How To Get Started with Gaming AI [Z].http:// www. generat- ion5.org/content/2001/howto00.asp,March,2,2001.
[29]任爱华.计算机图形学[M].北京:北京航空航天大学出版社,2005.
[30] AndréLaMothe.沙鹰译.Windows游戏编程大师技巧(第2版)[M].北京:中国电力出版社,2003.
[31] AndréLaMothe.Tricks of the 3D Game Programming Gurus—Advanced 3D Graphics and Rasterization[M]. United States of America:Sams Publishing,2003.
[32] Stefan Zerbst,Oliver Duvel.3D Game Engine Programming[M]. United States of America:Thomson Cource Technology PTR/Premier Press.2004.
[33] Stanley B. Lippman,侯捷译.Essential C++中文版[M].武汉:华中科技大学出版社.2001.8.
[34] Stanley B.Lippman,Josee Lajoie.C++ Primer(Third Edition)[M]. United States of America: Addison Wesley.March 26,1998.
[35] Michael Dawson.Beginning C++ Game Programming[M]. United States of America: Thomson Cource Technology PTR/Premier Press.2004.
[36]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社.2002.2.
[37] Mat Buckland.Programming Game AI by Example[M].United States of America:Wordware Publishing,Inc.2005.
[38] Peter Linz,孙家骕译.形式语言与自动机导论[M].北京:机械工业出版社,2005.
[39]王永庆.人工智能原理与方法[M].西安:西安交通大学出版社,2002.
[40]任巍.人工智能技术在计算机游戏软件中的应用[D].西安电子科技大学,硕士学位论文.2006.02.
[41] Tom M. Mitchell.曾华军,张银奎等译.机器学习[M].北京:机械工业出版社,2003.
[42]顾亦然,王锁萍.遗传算法与神经网络在接纳控制中的应用[J].计算机工程与应用,2005,19.
[43] Mat Buckland.AI Techniques for Game Programming[M]. United States of America: Premier Press,2002.
[44]像素软件.像素软件-刀剑封魔录[Z]. http://www.pixelgame.net/games/bs,2007.
[45] Nello Cristianini,John Shawe-Taylor.李国正,王猛,曾华军译.支持向量机导论[M].北京:电子工业出版社,2004:3-5.
[46] Chih-Chung Chang and Chih-Jen Lin. LIBSVM -- A Library for Support Vector Machines [Z]. http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html,2008.
[47]张贝贝.支持向量机多分类方法的研究及应用[D].重庆大学,硕士学位论文,2007.04.
[48] GarageGames.Torque:GarageGames[Z].http://www.garagegames.com/mg/projects/tge/,2008.
[49] Gregory Junker.Pro OGRE 3D Programming[M]. United States of America:Apress,2006.
[50] OGRE.OGRE 3D:Open source graphics engine[Z].http://www.ogre3d.org/,2008.
[51] BigWorld Pty Ltd.Bigworld Technology. http://www.bigworldtech.com/index/index.php [Z],2007.
[52]蒋宁,翟玉庆.一个基于神经网络和遗传算法的游戏自主角色的设计[J].计算机应用, 2007年05期:p1280~1282.
[53]龚向宇,徐东平.优化的遗传算法在游戏编程中的应用[J].电脑知识与技术(学术交流), 2007年02期.
[54]胡俊.游戏开发中的人工智能研究与应用[D].电子科技大学,硕士学位论文,2007.6.