Evolutionary Algorithm in Game – A Systematic Review

Hendrawan Armanto; Harits Ar  Rosyid; Muladi; Gunawan

doi:10.22219/kinetik.v8i2.1714

Issue

Vol. 8, No. 2, May 2023

Issue Published : May 31, 2023

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Evolutionary Algorithm in Game – A Systematic Review

https://doi.org/10.22219/kinetik.v8i2.1714

Hendrawan Armanto

Universitas Negeri Malang; Institut Sains dan Teknologi Terpadu Surabaya

https://orcid.org/0000-0002-2295-2016

Harits Ar Rosyid

Universitas Negeri Malang

Muladi

Universitas Negeri Malang

Gunawan

Institut Sains dan Teknologi Terpadu Surabaya

Corresponding Author(s) : Harits Ar Rosyid

harits.ar.ft@um.ac.id

Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, Vol. 8, No. 2, May 2023
Article Published : May 31, 2023

Abstract

Research in the game field is increasingly numerous and challenging. The high interest in research on games is influenced by public awareness of the importance of games in developing ways of thinking, although it is undeniable that many people only pursue pleasure in playing games. In the past, not much games research has influenced into topics such as artificial intelligence, education, or other computer topics. But now games are having a tremendous impact on these topics. In fact, not infrequently games are used in various areas of life. Right now, artificial intelligence is an integral part of the game. If before, it was only used for creating an enemy. Right now artificial intelligence can affect various things, starting from assets, game difficulty levels, non-player characters (NPC), and even bots (AI agents) to run player characters. The complexity of artificial intelligence which is getting higher and higher requires a good optimization algorithm. The evolutionary algorithm is one of the optimization algorithms, even though it cannot find the best one, with the high speed it can find a good solution. Through this paper review, good conclusions are drawn regarding the use of evolutionary algorithms, representations made, fitness functions used, ways to prove a success, to what topics should be studied further.

Keywords

Evolutionary Algorithm Game Systematic Review

Armanto, H., Rosyid, H. A. ., Muladi, & Gunawan. (2023). Evolutionary Algorithm in Game – A Systematic Review. Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, 8(2). https://doi.org/10.22219/kinetik.v8i2.1714

Download Citation

References

Z. Hellman and M. Pintér, “Charges and bets: a general characterisation of common priors,” Int. J. Game Theory, vol. 51, no. 3, pp. 567–587, 2022, doi: 10.1007/s00182-022-00805-4.
E. C. Ramón and E. Gutiérrez-López, “The equal collective gains value in cooperative games,” Int. J. Game Theory, vol. 51, no. 1, pp. 249–278, 2022, doi: 10.1007/s00182-021-00791-z.
D. Christopher Opolot, “On the relationship between p-dominance and stochastic stability in network games,” Int. J. Game Theory, vol. 51, no. 2, pp. 307–351, 2022, doi: 10.1007/s00182-021-00794-w.
M. S. O. Almeida and F. S. C. da Silva, “A Systematic Review of Game Design Methods and Tools BT - Entertainment Computing – ICEC 2013,” 2013, pp. 17–29.
P. Lankoski, “Game Design Research: An Introduction to Theory & Practice,” 2017, doi: 10.1184/R1/6686750.v1.
D. Bulut, Y. Samur, and Z. Cömert, “The effect of educational game design process on students’ creativity,” Smart Learn. Environ., vol. 9, no. 1, p. 8, 2022, doi: 10.1186/s40561-022-00188-9.
B. Xia, X. Ye, and A. Abuassba, Recent Research on AI in Games. 2020.
A. Persada, “User experience on games development trends,” J. Phys. Conf. Ser., vol. 1341, p. 42010, Oct. 2019, doi: 10.1088/1742-6596/1341/4/042010.
A. Becker and D. Görlich, Game Balancing – A Semantical Analysis. 2019.
A. N. Sloss and S. Gustafson, “2019 Evolutionary Algorithms Review,” Jun. 2019.
P. A. Vikhar, “Evolutionary algorithms: A critical review and its future prospects,” in 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC), 2016, pp. 261–265, doi: 10.1109/ICGTSPICC.2016.7955308.
M.-P. Song and G.-C. Gu, “Research on particle swarm optimization: a review,” in Proceedings of 2004 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.04EX826), 2004, vol. 4, pp. 2236–2241 vol.4, doi: 10.1109/ICMLC.2004.1382171.
A. Ghaedi, A. K. Bardsiri, and M. J. Shahbazzadeh, “Cat hunting optimization algorithm: a novel optimization algorithm,” Evol. Intell., vol. 16, no. 2, pp. 417–438, 2023, doi: 10.1007/s12065-021-00668-w.
O. W. Khalid, N. A. M. Isa, and H. A. Mat Sakim, “Emperor penguin optimizer: A comprehensive review based on state-of-the-art meta-heuristic algorithms,” Alexandria Eng. J., vol. 63, pp. 487–526, 2023, doi: https://doi.org/10.1016/j.aej.2022.08.013.
S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed. Tools Appl., vol. 80, no. 5, pp. 8091–8126, 2021, doi: 10.1007/s11042-020-10139-6.
A. Lambora, K. Gupta, and K. Chopra, “Genetic Algorithm- A Literature Review,” in 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon), 2019, pp. 380–384, doi: 10.1109/COMITCon.2019.8862255.
M. Kumar, M. Husain, N. Upreti, and D. Gupta, “Genetic algorithm: Review and application,” J. Inf. Knowl. Manag., Jul. 2010.
D. Freitas, L. G. Lopes, and F. Morgado-Dias, “Particle Swarm Optimisation: A Historical Review Up to the Current Developments,” Entropy, vol. 22, no. 3. 2020, doi: 10.3390/e22030362.
Y. Yang, Q. Liao, J. Wang, and Y. Wang, “Application of multi-objective particle swarm optimization based on short-term memory and K-means clustering in multi-modal multi-objective optimization,” Eng. Appl. Artif. Intell., vol. 112, p. 104866, 2022, doi: https://doi.org/10.1016/j.engappai.2022.104866.
C. Zhang, H. Shao, and Y. Li, “Particle swarm optimisation for evolving artificial neural network,” in Smc 2000 conference proceedings. 2000 ieee international conference on systems, man and cybernetics. “cybernetics evolving to systems, humans, organizations, and their complex interactions” (cat. no.0, 2000, vol. 4, pp. 2487–2490 vol.4, doi: 10.1109/ICSMC.2000.884366.
Q. Xiong, X. Zhang, X. Xu, and S. He, “A Modified Chaotic Binary Particle Swarm Optimization Scheme and Its Application in Face-Iris Multimodal Biometric Identification,” Electronics, vol. 10, no. 2. 2021, doi: 10.3390/electronics10020217.
S. Mirjalili, J. Song Dong, A. Lewis, and A. S. Sadiq, “Particle Swarm Optimization: Theory, Literature Review, and Application in Airfoil Design BT - Nature-Inspired Optimizers: Theories, Literature Reviews and Applications,” S. Mirjalili, J. Song Dong, and A. Lewis, Eds. Cham: Springer International Publishing, 2020, pp. 167–184.
S. Pervaiz, Z. Ul-Qayyum, W. H. Bangyal, L. Gao, and J. Ahmad, “A Systematic Literature Review on Particle Swarm Optimization Techniques for Medical Diseases Detection,” Comput. Math. Methods Med., vol. 2021, p. 5990999, 2021, doi: 10.1155/2021/5990999.
A. S. Kholimi, A. Hamdani, and L. Husniah, “Automatic Game World Generation for Platformer Games Using Genetic Algorithm,” in 2018 5th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), 2018, pp. 495–498, doi: 10.1109/EECSI.2018.8752741.
A. M. Connor, T. J. Greig, and J. Kruse, “Evolutionary generation of game levels,” EAI Endorsed Trans. Creat. Technol., vol. 5, no. 15, 2018, doi: 10.4108/eai.10-4-2018.155857.
J. A. Brown, B. Lutfullin, P. Oreshin, and I. Pyatkin, “Levels for Hotline Miami 2: Wrong Number Using Procedural Content Generations,” Comput., vol. 7, p. 22, 2018.
A. Pech, M. Masek, C. Lam, and P. Hingston, “Game level layout generation using evolved cellular automata,” Conn. Sci., vol. 28, pp. 1–20, Feb. 2016, doi: 10.1080/09540091.2015.1130020.
L. Maia, W. Viana, and F. Trinta, “Transposition of Location-based Games: Using Procedural Content Generation to deploy balanced game maps to multiple locations,” Pervasive Mob. Comput., vol. 70, p. 101302, Jan. 2021, doi: 10.1016/j.pmcj.2020.101302.
E. Soares de Lima, B. Feijó, and A. Furtado, Procedural Generation of Quests for Games Using Genetic Algorithms and Automated Planning. 2019.
G. Cui et al., “Reinforced Evolutionary Algorithms for Game Difficulty Control,” 2021, doi: 10.1145/3446132.3446165.
H. Chen, Y. Mori, and I. Matsuba, “Solving the balance problem of massively multiplayer online role-playing games using coevolutionary programming,” Appl. Soft Comput. J., vol. 18, pp. 1–11, May 2014, doi: 10.1016/J.ASOC.2014.01.011.
M. Shakhova and A. Zagarskikh, “Dynamic Difficulty Adjustment with a simplification ability using neuroevolution,” Procedia Comput. Sci., vol. 156, pp. 395–403, 2019, doi: https://doi.org/10.1016/j.procs.2019.08.219.
M. Weber and P. Notargiacomo, “Dynamic Difficulty Adjustment in Digital Games Using Genetic Algorithms,” in 2020 19th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), 2020, pp. 62–70, doi: 10.1109/SBGames51465.2020.00019.
A. Henrique, R. Soares, R. Dazzi, and R. Lyra, Genetic Algorithm in Survival Shooter Games NPCs. 2020.
T. Bullen and M. Katchabaw, “USING GENETIC ALGORITHMS TO EVOLVE CHARACTER BEHAVIOURS IN MODERN VIDEO GAMES,” 2008.
G. T. Galam, T. P. Remedio, and M. A. Dias, “Viral Infection Genetic Algorithm with Dynamic Infectability for Pathfinding in a Tower Defense Game,” in 2019 18th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), 2019, pp. 198–207, doi: 10.1109/SBGames.2019.00034.
G. Díaz and A. Iglesias, “Swarm Intelligence Scheme for Pathfinding and Action Planning of Non-player Characters on a Last-Generation Video Game BT - Harmony Search Algorithm,” 2017, pp. 343–353.
A. Von Moll, P. Androulakakis, Z. Fuchs, and D. Vanderelst, “Evolutionary Design of Cooperative Predation Strategies,” in 2020 IEEE Conference on Games (CoG), 2020, pp. 176–183, doi: 10.1109/CoG47356.2020.9231945.
G. Grossi and B. Ross, “Evolved communication strategies and emergent behaviour of multi-agents in pursuit domains,” in 2017 IEEE Conference on Computational Intelligence and Games (CIG), 2017, pp. 110–117, doi: 10.1109/CIG.2017.8080423.
K. Singh, A. V Singh, and S. K. Khatri, “Advanced Gameplay Strategy Based on Grey Wolf Optimization,” in 2019 4th International Conference on Information Systems and Computer Networks (ISCON), 2019, pp. 183–185, doi: 10.1109/ISCON47742.2019.9036295.
O. Mautschke, “Evolutionary Algorithms for Controllers in Games,” 2019.
S. Nallaperuma, F. Neumann, M. reza Bonyadi, and Z. Michalewicz, EVOR : An Online Evolutionary Algorithm for Car Racing Games. 2014.
P. García-Sánchez, A. Tonda, A. J. Fernández-Leiva, and C. Cotta, “Optimizing Hearthstone agents using an evolutionary algorithm,” Knowledge-Based Syst., vol. 188, Jan. 2020, doi: 10.1016/J.KNOSYS.2019.105032.
R. D. Gaina, S. Devlin, S. M. Lucas, and D. Perez-Liebana, “Rolling horizon evolutionary algorithms for general video game playing,” IEEE Trans. Games, vol. 14, no. 2, pp. 232–242, 2021.
A. Fernández-Ares, A. M. Mora, J. J. Merelo, P. García-Sánchez, and C. Fernandes, “Optimizing player behavior in a real-time strategy game using evolutionary algorithms,” in 2011 IEEE Congress of Evolutionary Computation (CEC), 2011, pp. 2017–2024, doi: 10.1109/CEC.2011.5949863.
A. Fernández-Ares, P. García-Sánchez, A. M. Mora, P. A. Castillo, and J. J. Merelo, “There Can Be only One: Evolving RTS Bots via Joust Selection BT - Applications of Evolutionary Computation,” 2016, pp. 541–557.

References

Z. Hellman and M. Pintér, “Charges and bets: a general characterisation of common priors,” Int. J. Game Theory, vol. 51, no. 3, pp. 567–587, 2022, doi: 10.1007/s00182-022-00805-4.

E. C. Ramón and E. Gutiérrez-López, “The equal collective gains value in cooperative games,” Int. J. Game Theory, vol. 51, no. 1, pp. 249–278, 2022, doi: 10.1007/s00182-021-00791-z.

D. Christopher Opolot, “On the relationship between p-dominance and stochastic stability in network games,” Int. J. Game Theory, vol. 51, no. 2, pp. 307–351, 2022, doi: 10.1007/s00182-021-00794-w.

M. S. O. Almeida and F. S. C. da Silva, “A Systematic Review of Game Design Methods and Tools BT - Entertainment Computing – ICEC 2013,” 2013, pp. 17–29.

P. Lankoski, “Game Design Research: An Introduction to Theory & Practice,” 2017, doi: 10.1184/R1/6686750.v1.

D. Bulut, Y. Samur, and Z. Cömert, “The effect of educational game design process on students’ creativity,” Smart Learn. Environ., vol. 9, no. 1, p. 8, 2022, doi: 10.1186/s40561-022-00188-9.

B. Xia, X. Ye, and A. Abuassba, Recent Research on AI in Games. 2020.

A. Persada, “User experience on games development trends,” J. Phys. Conf. Ser., vol. 1341, p. 42010, Oct. 2019, doi: 10.1088/1742-6596/1341/4/042010.

A. Becker and D. Görlich, Game Balancing – A Semantical Analysis. 2019.

A. N. Sloss and S. Gustafson, “2019 Evolutionary Algorithms Review,” Jun. 2019.

P. A. Vikhar, “Evolutionary algorithms: A critical review and its future prospects,” in 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC), 2016, pp. 261–265, doi: 10.1109/ICGTSPICC.2016.7955308.

M.-P. Song and G.-C. Gu, “Research on particle swarm optimization: a review,” in Proceedings of 2004 International Conference on Machine Learning and Cybernetics (IEEE Cat. No.04EX826), 2004, vol. 4, pp. 2236–2241 vol.4, doi: 10.1109/ICMLC.2004.1382171.

A. Ghaedi, A. K. Bardsiri, and M. J. Shahbazzadeh, “Cat hunting optimization algorithm: a novel optimization algorithm,” Evol. Intell., vol. 16, no. 2, pp. 417–438, 2023, doi: 10.1007/s12065-021-00668-w.

O. W. Khalid, N. A. M. Isa, and H. A. Mat Sakim, “Emperor penguin optimizer: A comprehensive review based on state-of-the-art meta-heuristic algorithms,” Alexandria Eng. J., vol. 63, pp. 487–526, 2023, doi: https://doi.org/10.1016/j.aej.2022.08.013.

S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed. Tools Appl., vol. 80, no. 5, pp. 8091–8126, 2021, doi: 10.1007/s11042-020-10139-6.

A. Lambora, K. Gupta, and K. Chopra, “Genetic Algorithm- A Literature Review,” in 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon), 2019, pp. 380–384, doi: 10.1109/COMITCon.2019.8862255.

M. Kumar, M. Husain, N. Upreti, and D. Gupta, “Genetic algorithm: Review and application,” J. Inf. Knowl. Manag., Jul. 2010.

D. Freitas, L. G. Lopes, and F. Morgado-Dias, “Particle Swarm Optimisation: A Historical Review Up to the Current Developments,” Entropy, vol. 22, no. 3. 2020, doi: 10.3390/e22030362.

Y. Yang, Q. Liao, J. Wang, and Y. Wang, “Application of multi-objective particle swarm optimization based on short-term memory and K-means clustering in multi-modal multi-objective optimization,” Eng. Appl. Artif. Intell., vol. 112, p. 104866, 2022, doi: https://doi.org/10.1016/j.engappai.2022.104866.

C. Zhang, H. Shao, and Y. Li, “Particle swarm optimisation for evolving artificial neural network,” in Smc 2000 conference proceedings. 2000 ieee international conference on systems, man and cybernetics. “cybernetics evolving to systems, humans, organizations, and their complex interactions” (cat. no.0, 2000, vol. 4, pp. 2487–2490 vol.4, doi: 10.1109/ICSMC.2000.884366.

Q. Xiong, X. Zhang, X. Xu, and S. He, “A Modified Chaotic Binary Particle Swarm Optimization Scheme and Its Application in Face-Iris Multimodal Biometric Identification,” Electronics, vol. 10, no. 2. 2021, doi: 10.3390/electronics10020217.

S. Mirjalili, J. Song Dong, A. Lewis, and A. S. Sadiq, “Particle Swarm Optimization: Theory, Literature Review, and Application in Airfoil Design BT - Nature-Inspired Optimizers: Theories, Literature Reviews and Applications,” S. Mirjalili, J. Song Dong, and A. Lewis, Eds. Cham: Springer International Publishing, 2020, pp. 167–184.

S. Pervaiz, Z. Ul-Qayyum, W. H. Bangyal, L. Gao, and J. Ahmad, “A Systematic Literature Review on Particle Swarm Optimization Techniques for Medical Diseases Detection,” Comput. Math. Methods Med., vol. 2021, p. 5990999, 2021, doi: 10.1155/2021/5990999.

A. S. Kholimi, A. Hamdani, and L. Husniah, “Automatic Game World Generation for Platformer Games Using Genetic Algorithm,” in 2018 5th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), 2018, pp. 495–498, doi: 10.1109/EECSI.2018.8752741.

A. M. Connor, T. J. Greig, and J. Kruse, “Evolutionary generation of game levels,” EAI Endorsed Trans. Creat. Technol., vol. 5, no. 15, 2018, doi: 10.4108/eai.10-4-2018.155857.

J. A. Brown, B. Lutfullin, P. Oreshin, and I. Pyatkin, “Levels for Hotline Miami 2: Wrong Number Using Procedural Content Generations,” Comput., vol. 7, p. 22, 2018.

A. Pech, M. Masek, C. Lam, and P. Hingston, “Game level layout generation using evolved cellular automata,” Conn. Sci., vol. 28, pp. 1–20, Feb. 2016, doi: 10.1080/09540091.2015.1130020.

L. Maia, W. Viana, and F. Trinta, “Transposition of Location-based Games: Using Procedural Content Generation to deploy balanced game maps to multiple locations,” Pervasive Mob. Comput., vol. 70, p. 101302, Jan. 2021, doi: 10.1016/j.pmcj.2020.101302.

E. Soares de Lima, B. Feijó, and A. Furtado, Procedural Generation of Quests for Games Using Genetic Algorithms and Automated Planning. 2019.

G. Cui et al., “Reinforced Evolutionary Algorithms for Game Difficulty Control,” 2021, doi: 10.1145/3446132.3446165.

H. Chen, Y. Mori, and I. Matsuba, “Solving the balance problem of massively multiplayer online role-playing games using coevolutionary programming,” Appl. Soft Comput. J., vol. 18, pp. 1–11, May 2014, doi: 10.1016/J.ASOC.2014.01.011.

M. Shakhova and A. Zagarskikh, “Dynamic Difficulty Adjustment with a simplification ability using neuroevolution,” Procedia Comput. Sci., vol. 156, pp. 395–403, 2019, doi: https://doi.org/10.1016/j.procs.2019.08.219.

M. Weber and P. Notargiacomo, “Dynamic Difficulty Adjustment in Digital Games Using Genetic Algorithms,” in 2020 19th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), 2020, pp. 62–70, doi: 10.1109/SBGames51465.2020.00019.

A. Henrique, R. Soares, R. Dazzi, and R. Lyra, Genetic Algorithm in Survival Shooter Games NPCs. 2020.

T. Bullen and M. Katchabaw, “USING GENETIC ALGORITHMS TO EVOLVE CHARACTER BEHAVIOURS IN MODERN VIDEO GAMES,” 2008.

G. T. Galam, T. P. Remedio, and M. A. Dias, “Viral Infection Genetic Algorithm with Dynamic Infectability for Pathfinding in a Tower Defense Game,” in 2019 18th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames), 2019, pp. 198–207, doi: 10.1109/SBGames.2019.00034.

G. Díaz and A. Iglesias, “Swarm Intelligence Scheme for Pathfinding and Action Planning of Non-player Characters on a Last-Generation Video Game BT - Harmony Search Algorithm,” 2017, pp. 343–353.

A. Von Moll, P. Androulakakis, Z. Fuchs, and D. Vanderelst, “Evolutionary Design of Cooperative Predation Strategies,” in 2020 IEEE Conference on Games (CoG), 2020, pp. 176–183, doi: 10.1109/CoG47356.2020.9231945.

G. Grossi and B. Ross, “Evolved communication strategies and emergent behaviour of multi-agents in pursuit domains,” in 2017 IEEE Conference on Computational Intelligence and Games (CIG), 2017, pp. 110–117, doi: 10.1109/CIG.2017.8080423.

K. Singh, A. V Singh, and S. K. Khatri, “Advanced Gameplay Strategy Based on Grey Wolf Optimization,” in 2019 4th International Conference on Information Systems and Computer Networks (ISCON), 2019, pp. 183–185, doi: 10.1109/ISCON47742.2019.9036295.

O. Mautschke, “Evolutionary Algorithms for Controllers in Games,” 2019.

S. Nallaperuma, F. Neumann, M. reza Bonyadi, and Z. Michalewicz, EVOR : An Online Evolutionary Algorithm for Car Racing Games. 2014.

P. García-Sánchez, A. Tonda, A. J. Fernández-Leiva, and C. Cotta, “Optimizing Hearthstone agents using an evolutionary algorithm,” Knowledge-Based Syst., vol. 188, Jan. 2020, doi: 10.1016/J.KNOSYS.2019.105032.

R. D. Gaina, S. Devlin, S. M. Lucas, and D. Perez-Liebana, “Rolling horizon evolutionary algorithms for general video game playing,” IEEE Trans. Games, vol. 14, no. 2, pp. 232–242, 2021.

A. Fernández-Ares, A. M. Mora, J. J. Merelo, P. García-Sánchez, and C. Fernandes, “Optimizing player behavior in a real-time strategy game using evolutionary algorithms,” in 2011 IEEE Congress of Evolutionary Computation (CEC), 2011, pp. 2017–2024, doi: 10.1109/CEC.2011.5949863.

A. Fernández-Ares, P. García-Sánchez, A. M. Mora, P. A. Castillo, and J. J. Merelo, “There Can Be only One: Evolving RTS Bots via Joust Selection BT - Applications of Evolutionary Computation,” 2016, pp. 541–557.

Issue

Vol. 8, No. 2, May 2023

Evolutionary Algorithm in Game – A Systematic Review

Corresponding Author(s) : Harits Ar Rosyid

Abstract

Keywords

Download Citation

References

Downloads