Abstract
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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Computer Game Bot — Wikipedia, The Free Encyclopedia. http://en.wikipedia.org/wiki/Computer_game_bot.
Laird J E. Using a computer game to develop advanced AI. Computer, 2001, 34(7): 70–75.
Esparcia-Alcázar A I, Martínez-García A I, Mora A M, Merelo J J, García-Sánchez P. Controlling bots in a first person shooter game using genetic algorithms. In Proc. 2010 IEEE Congress on Evolutionary Computation, July 2010, pp.1–8.
Mora A M, Moreno M A, Merelo J J, Castillo P A, García-Arenas M I, Laredo J L J. Evolving the cooperative behaviour in UnrealTM bots. In Proc. 2010 IEEE Conference on Computational Intelligence and Games (CIG 2010), August 2010, pp.241–248.
Small R, Congdon C B. Agent Smith: Towards an evolutionary rule-based agent for interactive dynamic games. In Proc. 2009 IEEE Congress on Evolutionary Computation (CEC 2009), May 2009, pp.660–666.
Ahlquist J B, Novak J. Game Artificial Intelligence. Thompson Delmar Learning, 2008.
Google AI Challenge 2010. http://ai-contest.com, 2010.
Hong J H, Cho S B. Evolving reactive NPCs for the real-time simulation game. In Proc. 2005 IEEE Symposium on Computational Intelligence and Games (CIG 2005), April 2005.
Jang S H, Yoon J W, Cho S B. Optimal strategy selection of non-player character on real time strategy game using a speciated evolutionary algorithm. In Proc. the 5th Int. Conf. Computational Intelligence and Games (CIG 2009), September 2009, pp.75–79.
Keaveney D, O0Riordan C. Evolving robust strategies for an abstract real-time strategy game. In Proc. Computational Intelligence and Games (CIG 2009), September 2009, pp.371–378.
Bäck T. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, 1996.
Fernández-Ares A, Mora A M, Merelo J J, García-Sánchez P, Fernandes C. Optimizing player behavior in a real-time strategy game using evolutionary algorithms. In Proc. 2011 IEEE Congress on Evolutionary Computation (CEC 2011), June 2011, pp.2017–2024.
Galcon — Wikipedia, The Free Encyclopedia. http://en.wi-kipedia.org/w/index.php?title=Galcon&oldid=399245028.
Goldberg D E, Korb B, Deb K. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems, 1989, 3(5): 493–530.
Mora A M, Fernández-Ares A, Merelo J J, García-Sánchez P. Dealing with noisy fitness in the design of a RTS game bot. In Proc. Applications of Evolutionary Computing — EvoApplications 2012, April 2012, pp.234–244.
Lidén L. Artificial stupidity: The art of intentional mistakes. In AI Game Programming Wisdom 2. Charles River Media Inc., 2004, pp.41–48.
Togelius J, Karakovskiy S, Koutnik J, Schmidhuber J. Super Mario evolution. In Proc. 2009 IEEE Symposium on Computational Intelligence and Games (CIG 2009), September 2009, pp 156–161.
Martín E, Martínez M, Recio G, Saez Y. Pac-mAnt: Optimization based on ant colonies applied to developing an agent for Ms. Pac-Man. In 2010 IEEE Symposium on Computational Intelligence and Games (CIG 2010), August 2010, pp.458–464.
Onieva E, Pelta D A, Alonso J, Milanés V, Pérez J. A modular parametric architecture for the TORCS racing engine. In Proc. 2009 IEEE Symposium on Computational Intelligence and Games (CIG 2009), September 2009, pp.256–262.
Starcraft AI Competition. http://eis.ucsc.edu/StarCraftA-ICompetition.
Sweetser P. Emergence in Games. Charles River Media, 2007.
Buro M. Call for AI research in RTS games. In Proc. AAAI Workshop on AI in Game, July 2004, pp.139–141.
Falke W, Ross P. Dynamic strategies in a real-time strategy game. In Proc Genetic and Evolutionary computation Conference (GECCO 2003), July 2003, pp.1920–1921.
Ontañon S, Mishra K, Sugandh N, Ram A. Case-based planning and execution for real-time strategy games. In Proc. the 7th International Conference on Case-Based Reasoning: Case-Based Reasoning Research and Development, August 2007, pp.164–178.
Hagelbäck J, Johansson S J. A multi-agent potential field-based bot for a full RTS game scenario. In Proc. the 5th Artificial Intelligence for Interactive Digital Entertainment Conference, Oct. 2009.
Ponsen M, Munoz-Avila H, Spronck P, Aha D W. Automatically generating game tactics through evolutionary learning. AI Magazine, 2006, 27(3): 75–84.
Spronck P, Sprinkhuizen-Kuyper I, Postma E. Improving opponent intelligence through offline evolutionary learning. International Journal of Intelligent Games & Simulation, 2003, 2(1): 20–27.
Miles C, Louis S J. Co-evolving real-time strategy game playing influence map trees with genetic algorithms. In Proc. 2006 IEEE International Congress on Evolutionary Computation (CEC 2006), July 2006.
Beume N, Hein T, Naujoks B, Piatkowski N, Preuss M, Wessing S. Intelligent anti-grouping in real-time strategy games. In Proc. 2008 IEEE International Symposium on Computational Intelligence and Games, December 2008, pp.63–70.
Livingstone D. Coevolution in hierarchical AI for strategy games. In Proc 2005 IEEE Symposium on Computational Intelligence and Games (CIG 2005), April 2005.
Avery P, Louis S. Coevolving team tactics for a real-time strategy game. In Proc. 2010 IEEE Congress on Evolutionary Computation (CEC 2010), July 2010, pp.1–8.
Keaveney D, O’Riordan C. Evolving coordination for real-time strategy games. IEEE Trans. Comput. Intellig. and AI in Games, 2011, 3(2): 155–167.
Cook M, Colton S, Gow J. Initial results from co-operative coevolution for automated platformer design. In Proc. 2012 European Conf. Applications of Evolutionary Computing, April 2012, pp.194–203.
Goldberg D. Genetic Algorithms in Search, Optimisation and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., 1989.
Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs (3rd edition). Springer, 1996.
Herrera F, Lozano M, Sánchez A M. A taxonomy for the crossover operator for real-coded genetic algorithms: An experimental study. International Journal of Intelligent Systems, 2003, 18(3): 309–338.
Lucas S. Computational intelligence and games: Challenges and opportunities. International Journal of Automation and Computing, 2008, 5(1): 45–57.
Bäck T, Fogel D B, Michalewicz Z. Evolutionary Computation 1: Basic Algorithms and Operators (1st edition). Taylor and Francis, 2000.
Merelo J J, Mora A M, Cotta C. Optimizing worst-case scenario in evolutionary solutions to the MasterMind puzzle. In Proc. 2001 IEEE Congress on Evolutionary Computation (CEC 2011), June 2011, pp.2669–2676.
Author information
Authors and Affiliations
Corresponding author
Additional information
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 extends two articles previously published by the authors in IEEE CEC 2011 and EVO* 2012, having some text parts in common.
Electronic Supplementary Material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Mora, A.M., Fernández-Ares, A., Merelo, J.J. et al. Effect of Noisy Fitness in Real-Time Strategy Games Player Behaviour Optimisation Using Evolutionary Algorithms. J. Comput. Sci. Technol. 27, 1007–1023 (2012). https://doi.org/10.1007/s11390-012-1281-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11390-012-1281-5