Skip to main content
Top

2020 | OriginalPaper | Chapter

Fitness Function Design for Neuroevolution in Goal-Finding Game Environments

Authors : K. Vignesh Kumar, R. Sourav, C. Shunmuga Velayutham, Vidhya Balasubramanian

Published in: Advances in Computational Collective Intelligence

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Recently, games like Pac-Man have been hotbeds for neuroevolution research and NEAT has emerged as one of the leading techniques in the game playing domain [14] . In the context of the snake game, the goal of this paper is to enhance neuroevolution strategies with better fitness functions for effective goal finding. We develop greedy and non-greedy fitness functions, and demonstrate the effectiveness of these functions in both environments with and without dynamic obstacles. We then present an alternate implementation using the NEAT algorithm combined with Novelty Search to increase the genetic diversity of the agent population and explore the problem space without specifying direct objectives. These conclusions suggest that even with a low number of simple inputs, and simple fitness functions, agents are quickly able to achieve a novice amount of expertise in the Snake game using NEAT.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
2.
go back to reference Ehlis, T., Hattan, J., Sikora, D.: Application of genetic programming to the snake game. Gamedev. Net 175 (2000) Ehlis, T., Hattan, J., Sikora, D.: Application of genetic programming to the snake game. Gamedev. Net 175 (2000)
3.
go back to reference Eiter, T., Mannila, H.: Computing discrete Frechet Distance. Technical Report CD-TR 94/64, p. 8 (1994) Eiter, T., Mannila, H.: Computing discrete Frechet Distance. Technical Report CD-TR 94/64, p. 8 (1994)
4.
go back to reference Floreano, D., Dürr, P., Mattiussi, C.: Neuroevolution: from architectures to learning. Evol. Intell. 1(1), 47–62 (2008) Floreano, D., Dürr, P., Mattiussi, C.: Neuroevolution: from architectures to learning. Evol. Intell. 1(1), 47–62 (2008)
5.
go back to reference Gomes, J., Mariano, P., Christensen, A.L.: Devising effective novelty search algorithms: a comprehensive empirical study. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 943–950 (2015) Gomes, J., Mariano, P., Christensen, A.L.: Devising effective novelty search algorithms: a comprehensive empirical study. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 943–950 (2015)
6.
go back to reference Hausknecht, M., Lehman, J., Miikkulainen, R., Stone, P.: A neuroevolution approach to general Atari game playing. IEEE Trans. Comput. Intell. AI Games 6(4), 355–366 (2014)CrossRef Hausknecht, M., Lehman, J., Miikkulainen, R., Stone, P.: A neuroevolution approach to general Atari game playing. IEEE Trans. Comput. Intell. AI Games 6(4), 355–366 (2014)CrossRef
7.
go back to reference Kistemaker, S., Whiteson, S.: Critical factors in the performance of novelty search. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 965–972 (2011) Kistemaker, S., Whiteson, S.: Critical factors in the performance of novelty search. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 965–972 (2011)
8.
go back to reference Lehman, J., Stanley, K.O.: Abandoning objectives: evolution through the search for novelty alone. Evol. Comput. 19(2), 189–223 (2011)CrossRef Lehman, J., Stanley, K.O.: Abandoning objectives: evolution through the search for novelty alone. Evol. Comput. 19(2), 189–223 (2011)CrossRef
9.
go back to reference Lockhart, C.: Application of temporal difference learning to the game of Snake. Ph.D. thesis, University of Louisville (2010) Lockhart, C.: Application of temporal difference learning to the game of Snake. Ph.D. thesis, University of Louisville (2010)
10.
go back to reference Ma, B., Tang, M., Zhang, J.: Exploration of reinforcement learning to snake (2016) Ma, B., Tang, M., Zhang, J.: Exploration of reinforcement learning to snake (2016)
11.
go back to reference Ollion, C., Doncieux, S.: Why and how to measure exploration in behavioral space. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation - GECCO 2011, p. 267. ACM Press, Dublin (2011) Ollion, C., Doncieux, S.: Why and how to measure exploration in behavioral space. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation - GECCO 2011, p. 267. ACM Press, Dublin (2011)
12.
go back to reference Risi, S., Togelius, J.: Neuroevolution in games: state of the art and open challenges. IEEE Trans. Comput. Intell. AI Games 9(1), 25–41 (2017)CrossRef Risi, S., Togelius, J.: Neuroevolution in games: state of the art and open challenges. IEEE Trans. Comput. Intell. AI Games 9(1), 25–41 (2017)CrossRef
13.
go back to reference Rodzin, S., Rodzina, O., Rodzina, L.: Neuroevolution: problems, algorithms, and experiments. In: 2016 IEEE 10th International Conference on Application of Information and Communication Technologies (AICT), pp. 1–4. IEEE (2016) Rodzin, S., Rodzina, O., Rodzina, L.: Neuroevolution: problems, algorithms, and experiments. In: 2016 IEEE 10th International Conference on Application of Information and Communication Technologies (AICT), pp. 1–4. IEEE (2016)
14.
go back to reference Samothrakis, S., Perez-Liebana, D., Lucas, S.M., Fasli, M.: Neuroevolution for general video game playing. In: 2015 IEEE Conference on Computational Intelligence and Games (CIG) (2015) Samothrakis, S., Perez-Liebana, D., Lucas, S.M., Fasli, M.: Neuroevolution for general video game playing. In: 2015 IEEE Conference on Computational Intelligence and Games (CIG) (2015)
15.
go back to reference Stanley, K.O., Bryant, B.D., Miikkulainen, R.: Real-time neuroevolution in the nero video game. IEEE Trans. Evol. Comput. 9(6), 653–668 (2005)CrossRef Stanley, K.O., Bryant, B.D., Miikkulainen, R.: Real-time neuroevolution in the nero video game. IEEE Trans. Evol. Comput. 9(6), 653–668 (2005)CrossRef
16.
go back to reference Stanley, K.O., Miikkulainen, R.: Evolving neural networks through augmenting topologies. Evol. Comput. 10(2), 99–127 (2002)CrossRef Stanley, K.O., Miikkulainen, R.: Evolving neural networks through augmenting topologies. Evol. Comput. 10(2), 99–127 (2002)CrossRef
17.
go back to reference Stanton, C., Clune, J.: Curiosity search: producing generalists by encouraging individuals to continually explore and acquire skills throughout their lifetime. PLOS ONE 11(9), 1–20 (2016)CrossRef Stanton, C., Clune, J.: Curiosity search: producing generalists by encouraging individuals to continually explore and acquire skills throughout their lifetime. PLOS ONE 11(9), 1–20 (2016)CrossRef
18.
go back to reference Urbano, P., Georgiou, L.: Improving grammatical evolution in Santa Fe Trail using novelty search. In: Advances in Artificial Life, ECAL 2013, pp. 917–924. MIT Press, September 2013 Urbano, P., Georgiou, L.: Improving grammatical evolution in Santa Fe Trail using novelty search. In: Advances in Artificial Life, ECAL 2013, pp. 917–924. MIT Press, September 2013
19.
go back to reference Wei, Z., Wang, D., Zhang, M., Tan, A.H., Miao, C., Zhou, Y.: Autonomous agents in snake game via deep reinforcement learning. In: 2018 IEEE International Conference on Agents (ICA), pp. 20–25. IEEE, Singapore, July 2018 Wei, Z., Wang, D., Zhang, M., Tan, A.H., Miao, C., Zhou, Y.: Autonomous agents in snake game via deep reinforcement learning. In: 2018 IEEE International Conference on Agents (ICA), pp. 20–25. IEEE, Singapore, July 2018
Metadata
Title
Fitness Function Design for Neuroevolution in Goal-Finding Game Environments
Authors
K. Vignesh Kumar
R. Sourav
C. Shunmuga Velayutham
Vidhya Balasubramanian
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-63119-2_41

Premium Partner