›› 2012, Vol. 27 ›› Issue (5): 1007-1023.doi: 10.1007/s11390-012-1281-5

• Special Issue on Evolutionary Computation • Previous Articles     Next Articles

Effect of Noisy Fitness in Real-Time Strategy Games Player Behaviour Optimisation Using Evolutionary Algorithms

Antonio M. Mora1, Antonio Fernández-Ares1, Juan J. Merelo1, Pablo García-Sánchez1, and Carlos M. Fernandes1,2   

  1. 1. Computer Architecture and Technology Department, University of Granada, Granada 18071, Spain;
    2. Institute for Systems and Robotics, Technical University of Lisbon, Lisbon 1049-001, Portugal
  • Received:2011-10-21 Revised:2012-08-15 Online:2012-09-05 Published:2012-09-05
  • Supported by:

    This work has been supported in part by Andalusian Autonomous Government (Junta de Andalucía) under Project No. P08-TIC-03903, Ministerio de Ciencia e Innovación under Project No. TIN2011-28627-C04-02, and Foundation for Science and Technology (FCT) of Portugal (ISR/IST plurianual funding) through the PIDDAC Program funds. Carlos M. Fernandes wishes to thank FCT, Ministério da Ciência e Tecnologia, for his Research Fellowship under Grant No. SFRH/BPD/66876/2009.

This paper investigates the performance and the results of an evolutionary algorithm (EA) specifically designed for evolving the decision engine of a program (which, in this context, is called bot) that plays Planet Wars. This game, which was chosen for the Google Artificial Intelligence Challenge in 2010, requires the bot to deal with multiple target planets, while achieving a certain degree of adaptability in order to defeat different opponents in different scenarios. The decision engine of the bot is initially based on a set of rules that have been defined after an empirical study, and a genetic algorithm (GA) is used for tuning the set of constants, weights and probabilities that those rules include, and therefore, the general behaviour of the bot. Then, the bot is supplied with the evolved decision engine and the results obtained when competing with other bots (a bot offered by Google as a sparring partner, and a scripted bot with a pre-established behaviour) are thoroughly analysed. The evaluation of the candidate solutions is based on the result of non-deterministic battles (and environmental interactions) against other bots, whose outcome depends on random draws as well as on the opponents' actions. Therefore, the proposed GA is dealing with a noisy fitness function. After analysing the effects of the noisy fitness, we conclude that tackling randomness via repeated combats and reevaluations reduces this effect and makes the GA a highly valuable approach for solving this problem.

[1] Computer Game Bot —— Wikipedia, The Free Encyclopedia.http://en.wikipedia.org/wiki/Computer game bot.
[2] Laird J E. Using a computer game to develop advanced AI.Computer, 2001, 34(7): 70-75.
[3] Esparcia-Alcázar A I, Martínez-García A I, Mora A M, MereloJ J, García-Sánchez P. Controlling bots in a first personshooter game using genetic algorithms. In Proc. 2010 IEEECongress on Evolutionary Computation, July 2010, pp.1-8.
[4] Mora A M, Moreno M A, Merelo J J, Castillo P A, García-Arenas M I, Laredo J L J. Evolving the cooperative behaviourin UnrealTM bots. In Proc. 2010 IEEE Conference on Com-putational Intelligence and Games (CIG 2010), August 2010,pp.241-248.
[5] Small R, Congdon C B. Agent Smith: Towards an evolu-tionary rule-based agent for interactive dynamic games. InProc. 2009 IEEE Congress on Evolutionary Computation(CEC 2009), May 2009, pp.660-666.
[6] Ahlquist J B, Novak J. Game Artificial Intelligence. Thomp-son Delmar Learning, 2008.
[7] Google AI Challenge 2010. http://ai-contest.com, 2010.
[8] Hong J H, Cho S B. Evolving reactive NPCs for the real-timesimulation game. In Proc. 2005 IEEE Symposium on Com-putational Intelligence and Games (CIG 2005), April 2005.
[9] Jang S H, Yoon J W, Cho S B. Optimal strategy selection ofnon-player character on real time strategy game using a spe-ciated evolutionary algorithm. In Proc. the 5th Int. Conf.Computational Intelligence and Games (CIG 2009), Septem-ber 2009, pp.75-79.
[10] Keaveney D, O0Riordan C. Evolving robust strategies for anabstract real-time strategy game. In Proc. ComputationalIntelligence and Games (CIG 2009), September 2009, pp.371-378.
[11] Bäck T. Evolutionary Algorithms in Theory and Practice:Evolution Strategies, Evolutionary Programming, Genetic Al-gorithms. Oxford University Press, 1996.
[12] Fernández-Ares A, Mora A M, Merelo J J, García-SánchezP, Fernandes C. Optimizing player behavior in a real-timestrategy game using evolutionary algorithms. In Proc. 2011IEEE Congress on Evolutionary Computation (CEC 2011),June 2011, pp.2017-2024.
[13] Galcon —— Wikipedia, The Free Encyclopedia. http://en.wi-kipedia.org/w/index.php?title=Galcon&oldid=399245028.
[14] Goldberg D E, Korb B, Deb K. Messy genetic algorithms: Mo-tivation, analysis, and first results. Complex Systems, 1989,3(5): 493-530.
[15] Mora A M, Fernández-Ares A, Merelo J J, García-SánchezP. Dealing with noisy fitness in the design of a RTS gamebot. In Proc. Applications of Evolutionary Computing ——EvoApplications 2012, April 2012, pp.234-244.
[16] Lidén L. Artificial stupidity: The art of intentional mistakes.In AI Game Programming Wisdom 2. Charles River MediaInc., 2004, pp.41-48.
[17] Togelius J, Karakovskiy S, Koutnik J, Schmidhuber J. SuperMario evolution. In Proc. 2009 IEEE Symposium on Com-putational Intelligence and Games (CIG 2009), September2009, pp 156-161.
[18] Martín E, Martínez M, Recio G, Saez Y. Pac-mAnt: Opti-mization based on ant colonies applied to developing an agentfor Ms. Pac-Man. In 2010 IEEE Symposium on Compu-tational Intelligence and Games (CIG 2010), August 2010,pp.458-464.
[19] Onieva E, Pelta D A, Alonso J, Milanés V, Pérez J. A modu-lar parametric architecture for the TORCS racing engine. InProc. 2009 IEEE Symposium on Computational Intelligenceand Games (CIG 2009), September 2009, pp.256-262.
[20] Starcraft AI Competition. http://eis.ucsc.edu/StarCraftA-ICompetition.
[21] Sweetser P. Emergence in Games. Charles River Media, 2007.
[22] Buro M. Call for AI research in RTS games. In Proc. AAAIWorkshop on AI in Game, July 2004, pp.139-141.
[23] Falke W, Ross P. Dynamic strategies in a real-time strategygame. In Proc Genetic and Evolutionary computation Con-ference (GECCO 2003), July 2003, pp.1920-1921.
[24] Onta~non S, Mishra K, Sugandh N, Ram A. Case-based plan-ning and execution for real-time strategy games. In Proc.the 7th International Conference on Case-Based Reasoning:Case-Based Reasoning Research and Development, August2007, pp.164-178.
[25] Hagelbäck J, Johansson S J. A multi-agent potential field-based bot for a full RTS game scenario. In Proc. the 5th Artiˉcial Intelligence for Interactive Digital EntertainmentConference, Oct. 2009.
[26] Ponsen M, Munoz-Avila H, Spronck P, Aha D W. Automat-ically generating game tactics through evolutionary learning.AI Magazine, 2006, 27(3): 75-84.
[27] Spronck P, Sprinkhuizen-Kuyper I, Postma E. Improving op-ponent intelligence through o2ine evolutionary learning. In-ternational Journal of Intelligent Games & Simulation, 2003,2(1): 20-27.
[28] Miles C, Louis S J. Co-evolving real-time strategy game play-ing influence map trees with genetic algorithms. In Proc.2006 IEEE International Congress on Evolutionary Compu-tation (CEC 2006), July 2006.
[29] Beume N, Hein T, Naujoks B, Piatkowski N, Preuss M, Wess-ing S. Intelligent anti-grouping in real-time strategy games.In Proc. 2008 IEEE International Symposium on Computa-tional Intelligence and Games, December 2008, pp.63-70.
[30] Livingstone D. Coevolution in hierarchical AI for strategygames. In Proc 2005 IEEE Symposium on ComputationalIntelligence and Games (CIG 2005), April 2005.
[31] Avery P, Louis S. Coevolving team tactics for a real-timestrategy game. In Proc. 2010 IEEE Congress on Evolution-ary Computation (CEC 2010), July 2010, pp.1-8.
[32] Keaveney D, O'Riordan C. Evolving coordination for real-time strategy games. IEEE Trans. Comput. Intellig. and AIin Games, 2011, 3(2): 155-167.
[33] Cook M, Colton S, Gow J. Initial results from co-operative co-evolution for automated platformer design. In Proc. 2012 Eu-ropean Conf. Applications of Evolutionary Computing, April2012, pp.194-203.
[34] Goldberg D. Genetic Algorithms in Search, Optimisation andMachine Learning. Addison-Wesley Longman Publishing Co.,Inc., 1989.
[35] Michalewicz Z. Genetic Algorithms + Data Structures = Evo-lution Programs (3rd edition). Springer, 1996.
[36] Herrera F, Lozano M, Sánchez A M. A taxonomy for thecrossover operator for real-coded genetic algorithms: An ex-perimental study. International Journal of Intelligent Sys-tems, 2003, 18(3): 309-338.
[37] Lucas S. Computational intelligence and games: Challengesand opportunities. International Journal of Automation andComputing, 2008, 5(1): 45-57.
[38] Báck T, Fogel D B, Michalewicz Z. Evolutionary Computa-tion 1: Basic Algorithms and Operators (1st edition). Taylorand Francis, 2000.
[39] Merelo J J, Mora A M, Cotta C. Optimizing worst-case sce-nario in evolutionary solutions to the MasterMind puzzle. InProc. 2001 IEEE Congress on Evolutionary Computation(CEC 2011), June 2011, pp.2669-2676.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Yu Shengke;. Reasoning in H-Net: A Unified Approach to Intelligent Hypermedia Systems[J]. , 1996, 11(1): 83 -89 .
[2] Ju Jiubin; Wang Yong; Yin Yu;. Scheduling PVM Tasks[J]. , 1997, 12(2): 167 -176 .
[3] Fu Yuxi;. Symmetric π-Calculus[J]. , 1998, 13(3): 202 -208 .
[4] ZHENG Fang; XU Mingxing; MOU Xiaolong; WU Jian; WU Wenhu; FANG Ditang;. HarkMan—A Vocabulary-Independent Keyword Spotter for Spontaneons Chinese Speech[J]. , 1999, 14(1): 18 -26 .
[5] SHI Zhongzhi; TIAN Qijia; LI Yunfeng;. RAO Logic for Multiagent Framework[J]. , 1999, 14(4): 393 -400 .
[6] WU Jinzhao; LIU Zhuojun;. Linear Strategy for Boolean Ring Based Theorem Proving[J]. , 2000, 15(3): 271 -279 .
[7] Sheng-En Li and Shan Wang. Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time[J]. , 2005, 20(3): 367 -372 .
[8] Ping Hou. Some Representation Theorems for Recovering Contraction Relations[J]. , 2005, 20(4): 536 -541 .
[9] Ben Leslie, Peter Chubb, Nicholas Fitzroy-Dale, Stefan Gotz, Charles Gray, Luke Macpherson, Daniel Potts, Yue-Ting Shen, Kevin Elphinstone, and Gernot Heiser. User-Level Device Drivers: Achieved Performance[J]. , 2005, 20(5): 654 -664 .
[10] Jian-Hui Jiang. An Error Recoverable Structure Based on Complementary Logic and Alternating- Retry[J]. , 2005, 20(6): 885 -894 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved