Enhancing Player Levels in the Nim Game Using Genetic Algorithms
Resumo
The Nim game is a fundamental example in combinatorial game theory, exemplifying impartial games where moves depend solely on the current position. Creating difficulty levels in Nim for computer play presents challenges, as small changes in game element positioning can significantly alter the game’s difficulty. Initial ideas, such as randomly applying the winning formula or ensuring constant computer wins, but it proved unsatisfactory due to erratic or discouraging gameplay. This article proposes using Genetic Algorithms (GAs) to develop varied difficulty levels in Nim. Our approach avoids the established winning formula, making defining an independent fitness function complex. Instead, we employ a competitive coevolutionary fitness function, where individuals are evaluated against each other, allowing the fitness criteria to evolve with the population. This method produces more nuanced and engaging difficulty levels, enhancing player experience through a balanced and evolving challenge.
Palavras-chave:
Combinatorial Games, Nim game, Genetic Algorithms
Referências
Angeline, P. e Pollack, J. (1993). Competitive environments evolve better solutions for complex tasks. In Proceedings of the 5th International Conference on Genetic Algorithms, page 264–270. Morgan Kaufmann.
Berseth, G., Haworth, M. B., Kapadia, M., e Faloutsos, P. (2014). Characterizing and optimizing game level difficulty. In Proceedings of the 7th International Conference on Motion in Games, pages 153–160.
Bouton, C. L. (1901). Nim, a game with a complete mathematical theory. The Annals of Mathematics, 3(1/4):35–39.
Fernández-Ares, A., Mora, A., García-Sánchez, P., Castillo, P. A., e Merelo, J. (2017). Analysing the influence of the fitness function on genetically programmed bots for a real-time strategy game. Entertainment Computing, 18:15–29.
Funes, P. e Pujals, E. (2005). Intransitivity revisited coevolutionary dynamics of numbers games. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 515–521.
Hauptman, A. e Sipper, M. (2005). Gp-endchess: Using genetic programming to evolve chess endgame players. In European Conference on Genetic Programming, pages 120–131. Springer.
Hynek, J. (2004). Evolving strategy for game playing. In 4th international ICSC symposium on engineering intelligent systems, pages 1–6.
Jaśkowski, W., Krawiec, K., e Wieloch, B. (2008). Winning ant wars: Evolving a human-competitive game strategy using fitnessless selection. In Genetic Programming: 11th European Conference, EuroGP 2008, Naples, Italy, March 26-28, 2008. Proceedings 11, pages 13–24. Springer.
Ladjici, A. A., Tiguercha, A., e Boudour, M. (2014). Nash equilibrium in a two-settlement electricity market using competitive coevolutionary algorithms. International Journal of Electrical Power & Energy Systems, 57:148–155.
Luke, S., Sullivan, K., e Abidi, F. (2011). Large scale empirical analysis of cooperative coevolution. In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, pages 151–152.
Luke, S. e Wiegand, R. P. (2002). When coevolutionary algorithms exhibit evolutionary dynamics. In 2002 Genetic and Evolutionary Computation Conference Workshop Program, pages 236–241.
Mukhar, K. (2013). Using evolutionary computing to develop game strategy for a non-deterministic game. PhD thesis, University of Colorado Colorado Springs.
Oliehoek, F. A., De Jong, E. D., e Vlassis, N. (2006). The parallel nash memory for asymmetric games. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 337–344.
Panait, L. e Luke, S. (2002). A comparison of two competitive fitness functions. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, pages 503–511.
Popovici, E., Bucci, A., Wiegand, R. P., e De Jong, E. D. (2012). Coevolutionary principles.
Potter, M. A. (1997). The design and analysis of a computational model of cooperative coevolution. George Mason University.
Rosin, C. D. e Belew, R. K. (1995). Methods for competitive co-evolution: finding opponents worth beating. In ICGA, pages 373–381. Citeseer.
Rosin, C. D. e Belew, R. K. (1996). A competitive approach to game learning. In Proceedings of the ninth annual conference on Computational learning theory, pages 292–302.
Rosin, C. D. e Belew, R. K. (1997). New methods for competitive coevolution. Evolutionary computation, 5(1):1–29.
Rougetet, L. (2018). Machines designed to play nim games (1940–1970): A possible (re) use in the modern french mathematics curriculum? Teaching and Learning Discrete Mathematics Worldwide: Curriculum and Research, pages 229–250.
Samothrakis, S., Lucas, S., Runarsson, T. P., e Robles, D. (2012). Coevolving game-playing agents: Measuring performance and intransitivities. IEEE Transactions on Evolutionary Computation, 17(2):213–226.
Sipper, M., Azaria, Y., Hauptman, A., e Shichel, Y. (2007). Designing an evolutionary strategizing machine for game playing and beyond. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 37(4):583–593.
Stoffová, V. et al. (2019). Computer games as a tool for the development of algorithmic thinking. European Proceedings of Social and Behavioural Sciences, 53.
Szubert, M., Jaśkowski, W., Liskowski, P., e Krawiec, K. (2013). Shaping fitness function for evolutionary learning of game strategies. In Proceedings of the 15th annual conference on genetic and evolutionary computation, pages 1149–1156.
Takagi, H. e Pallez, D. (2009). Paired comparison-based interactive differential evolution. In 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), pages 475–480. IEEE.
Vrajitoru, D. (2007). Competitive coevolution versus objective fitness for an autonomous motorcycle pilot. In 2007 IEEE International Conference on Electro/Information Technology, pages 557–562. IEEE.
Watson, R. A. e Pollack, J. B. (2001). Coevolutionary dynamics in a minimal substrate. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pages 702–709.
Wilisowski, Ł. e Dreżewski, R. (2015). The application of co-evolutionary genetic programming and td (1) reinforcement learning in large-scale strategy game vcmi. In Agent and Multi-Agent Systems: Technologies and Applications: 9th KES International Conference, KES-AMSTA 2015 Sorrento, Italy, June 2015, Proceedings, pages 81–93. Springer.
Berseth, G., Haworth, M. B., Kapadia, M., e Faloutsos, P. (2014). Characterizing and optimizing game level difficulty. In Proceedings of the 7th International Conference on Motion in Games, pages 153–160.
Bouton, C. L. (1901). Nim, a game with a complete mathematical theory. The Annals of Mathematics, 3(1/4):35–39.
Fernández-Ares, A., Mora, A., García-Sánchez, P., Castillo, P. A., e Merelo, J. (2017). Analysing the influence of the fitness function on genetically programmed bots for a real-time strategy game. Entertainment Computing, 18:15–29.
Funes, P. e Pujals, E. (2005). Intransitivity revisited coevolutionary dynamics of numbers games. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 515–521.
Hauptman, A. e Sipper, M. (2005). Gp-endchess: Using genetic programming to evolve chess endgame players. In European Conference on Genetic Programming, pages 120–131. Springer.
Hynek, J. (2004). Evolving strategy for game playing. In 4th international ICSC symposium on engineering intelligent systems, pages 1–6.
Jaśkowski, W., Krawiec, K., e Wieloch, B. (2008). Winning ant wars: Evolving a human-competitive game strategy using fitnessless selection. In Genetic Programming: 11th European Conference, EuroGP 2008, Naples, Italy, March 26-28, 2008. Proceedings 11, pages 13–24. Springer.
Ladjici, A. A., Tiguercha, A., e Boudour, M. (2014). Nash equilibrium in a two-settlement electricity market using competitive coevolutionary algorithms. International Journal of Electrical Power & Energy Systems, 57:148–155.
Luke, S., Sullivan, K., e Abidi, F. (2011). Large scale empirical analysis of cooperative coevolution. In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, pages 151–152.
Luke, S. e Wiegand, R. P. (2002). When coevolutionary algorithms exhibit evolutionary dynamics. In 2002 Genetic and Evolutionary Computation Conference Workshop Program, pages 236–241.
Mukhar, K. (2013). Using evolutionary computing to develop game strategy for a non-deterministic game. PhD thesis, University of Colorado Colorado Springs.
Oliehoek, F. A., De Jong, E. D., e Vlassis, N. (2006). The parallel nash memory for asymmetric games. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 337–344.
Panait, L. e Luke, S. (2002). A comparison of two competitive fitness functions. In Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation, pages 503–511.
Popovici, E., Bucci, A., Wiegand, R. P., e De Jong, E. D. (2012). Coevolutionary principles.
Potter, M. A. (1997). The design and analysis of a computational model of cooperative coevolution. George Mason University.
Rosin, C. D. e Belew, R. K. (1995). Methods for competitive co-evolution: finding opponents worth beating. In ICGA, pages 373–381. Citeseer.
Rosin, C. D. e Belew, R. K. (1996). A competitive approach to game learning. In Proceedings of the ninth annual conference on Computational learning theory, pages 292–302.
Rosin, C. D. e Belew, R. K. (1997). New methods for competitive coevolution. Evolutionary computation, 5(1):1–29.
Rougetet, L. (2018). Machines designed to play nim games (1940–1970): A possible (re) use in the modern french mathematics curriculum? Teaching and Learning Discrete Mathematics Worldwide: Curriculum and Research, pages 229–250.
Samothrakis, S., Lucas, S., Runarsson, T. P., e Robles, D. (2012). Coevolving game-playing agents: Measuring performance and intransitivities. IEEE Transactions on Evolutionary Computation, 17(2):213–226.
Sipper, M., Azaria, Y., Hauptman, A., e Shichel, Y. (2007). Designing an evolutionary strategizing machine for game playing and beyond. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 37(4):583–593.
Stoffová, V. et al. (2019). Computer games as a tool for the development of algorithmic thinking. European Proceedings of Social and Behavioural Sciences, 53.
Szubert, M., Jaśkowski, W., Liskowski, P., e Krawiec, K. (2013). Shaping fitness function for evolutionary learning of game strategies. In Proceedings of the 15th annual conference on genetic and evolutionary computation, pages 1149–1156.
Takagi, H. e Pallez, D. (2009). Paired comparison-based interactive differential evolution. In 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), pages 475–480. IEEE.
Vrajitoru, D. (2007). Competitive coevolution versus objective fitness for an autonomous motorcycle pilot. In 2007 IEEE International Conference on Electro/Information Technology, pages 557–562. IEEE.
Watson, R. A. e Pollack, J. B. (2001). Coevolutionary dynamics in a minimal substrate. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pages 702–709.
Wilisowski, Ł. e Dreżewski, R. (2015). The application of co-evolutionary genetic programming and td (1) reinforcement learning in large-scale strategy game vcmi. In Agent and Multi-Agent Systems: Technologies and Applications: 9th KES International Conference, KES-AMSTA 2015 Sorrento, Italy, June 2015, Proceedings, pages 81–93. Springer.
Publicado
30/09/2024
Como Citar
PERES, Matheus; VIANA, Francisco Henrique de Freitas; FERNANDES, Kennedy M.; GONZALEZ, Pedro Henrique; SOARES, Leandro de M. B.; BEZARRA, Eduardo; DOS SANTOS, Joel Andre F.; BRANDÃO, Diego.
Enhancing Player Levels in the Nim Game Using Genetic Algorithms. In: SIMPÓSIO BRASILEIRO DE JOGOS E ENTRETENIMENTO DIGITAL (SBGAMES), 23. , 2024, Manaus/AM.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 532-546.
DOI: https://doi.org/10.5753/sbgames.2024.241335.
