Comparative Analysis of Evaluation Functions for Minimax with Alpha-Beta Pruning Applied to the Jaguar Game

• Felipe do Nascimento Universidade do Estado do Amazonas
• Elloá Guedes Universidade do Estado do Amazonas

DOI: https://doi.org/10.5753/eniac.2019.9271

Abstract

Jaguar Game is a board game from the Brazilian indigenous cultural tradition. It is played on an asymmetric board with 31 positions in which a jaguar duels against fourteen dogs and where the adversaries have different goals. In order to present preliminary results regarding the use of Artificial Intelligence techniques in this domain, the game tree complexity was estimated by a brute force approach with prunning and the resulting complexity was verified as being superior than the Checkers game. We also proposed and evaluated utility functions for the Minimax algorithm with Alpha-Beta pruning optimization. Results from simulations emphasize the challenges in designing utility functions for the dogs players.

Keywords: Artificial Intelligence, Minimax, Adversarial search

References

Bettin, A. D. H. e Pretto, V. (2016). A construção do jogo indígena a partir da matemática. In Anais do XXI SIEDUCA – A escola já não é a mesma: novos tempos, novos paradigmas, volume 21, pages 266–273.

Chen, J. X. (2016). The evolution of computing: Alphago. Computing in Science & Engineering, 18(4):4–7.

Chorus, P. (2009). Implementing a computer player for abalone using Alpha-Beta and Monte-Carlo search. Maastricht University, Dissertação.

de Oliveira Sardinha, A. G. e Gaspar, M. T. J. (2010). Jogos indígenas aplicados ao ensino de Matemática. In Anais do X Encontro Nacional de Educação Matemática, pages 1–10, Salvador, Bahia.

Ferreira, M. B. R., Vinha, M., e de Souza, A. F. (2008). Jogos de tabuleiro: um percurso em etnias indígenas. Ciência em Movimento, 16(1):47–55.

Ghory, I. (2004). Reinforcement learning in board games. Technical report, Department of Computer Science, University of Bristol, Inglaterra.

Gobet, F., de Voogt, A., e Retschitzki, J. (2004). Moves in Mind – The psychology of board games. Psychology Press, Taylor & Francis Group, Estados Unidos.

Hsu, F.-H. (2002). Behind Deep Blue. Princeton University Press, Estados Unidos, 1 edição.

Millington, I. e Funge, J. (2009). Articial Intelligence for Games. Elsevier, Estados Unidos, 2 edição.

Russell, S. e Norvig, P. (2016). Articial Intelligence – A Modern Approach. Pearson, Nova Jersey, 3 edição.

Schaeffer, J., Burch, N., Bjornsson, Y., Kishimoto, A., Muller, M., Lake, R., Lu, P., e Sutphen, S. (2007). Checkers is solved. Science, 317(5844):1518–1522.

Secretaria Municipal de Educação (2016). O jogo da onça aprenda a jogar. Prefeitura de São Paulo. Disponível em:https://bit.ly/2YAVX0P. Acessado em 27 de agosto de 2019.

Viegas, O., Lindner, N., e Mallmann, C. S. (2019). Catálogo de jogos e desaos do mundo. Ocina do Aprendiz. Disponível em http://bit.ly/2KIt6nz. Acesso em 28 de junho de 2019.

Yannakakis, G. N. e Togelius, J. (2018). Articial Intelligence and Games. Springer, Estados Unidos.