Análise Comparativa de Funções de Utilidade para o Algoritmo Minimax com Poda Alfa-Beta Aplicadas ao Jogo da Onça
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.
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.
Publicado
15/10/2019
Como Citar
NASCIMENTO, Felipe do; GUEDES, Elloá.
Análise Comparativa de Funções de Utilidade para o Algoritmo Minimax com Poda Alfa-Beta Aplicadas ao Jogo da Onça. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 49-59.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9271.
