Análise Comparativa de Funções de Utilidade para o Algoritmo Minimax com Poda Alfa-Beta Aplicadas ao Jogo da Onça

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

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

Resumo

O Jogo da Onça é um legado da tradição cultural indígena brasileira. É jogado em um tabuleiro assimétrico com 31 posições no qual uma onça duela contra catorze cachorros e onde os adversários possuem diferentes objetivos. Com o intuito de apresentar resultados preliminares da utilização de técnicas de Inteligência Artificial neste domínio, a árvore de complexidade do jogo foi estimada a partir de uma abordagem força bruta com poda e cuja complexidade resultante mostra-se superior à do Jogo de Damas. Também foram propostas e avaliadas funções de utilidade para o algoritmo Minimax com Otimização de Poda Alfa-Beta. Os resultados das simulações enfatizam desafios no projeto das funções de utilidade para o jogador associado aos cachorros.

Palavras-chave: Inteligência Artificial, Minimax, Busca Adversarial

Referências

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.