Eu e meu amigo, Yuri Barbosa, aceitamos o desafio de desenvolver uma Inteligência Artificial utilizando o algoritmo Minimax para jogar uma partida de Gomoku contra um humano. Este desafio se originou em um trabalho de faculdade, mas nós aproveitamos esta oportunidade para ir muito mais longe do que nos foi pedido.
Nesta publicação, você encontrará um resumo do nosso projeto: nossas linhas de raciocínio para tomadas de decisões, como modelamos nosso problema, como superamos as dificuldades encontradas e as conclusões. Tudo isso de forma que seja acessível para qualquer um que esteja interessado!
Esta publicação tem como público alvo pessoas que estejam curiosas com o nosso trabalho mas, não necessariamente, têm conhecimento aprofundado na área. Caso esteja procurando detalhes mais técnicos, veja [esta publicação].
Você pode encontrar o projeto aqui: https://github.com/Yuri-barbosa21/Gomoku-Pygame
Introdução ao problema
O que é o Gomoku?
Gomoku é um jogo que acredita-se ser originado na China, no século XIX. O jogo consiste de um tabuleiro 15x15 em que dois jogadores, cada um com uma cor de peça e jogando alternadamente, têm o objetivo de alinhar 5 peças em qualquer direção: horizontal, vertical ou qualquer diagonal.
Aqui um exemplo de uma partida de gomoku em que o jogador com as peças brancas venceu:
O que é o Minimax?
Minimax é um algoritmo de Inteligência Artificial especializado em jogos de dois jogadores.
Seu método de funcionamento é muito interessante: quando é a vez da Inteligência Artificial jogar, ela simula várias possibilidades de jogadas futuras para ambos os jogadores, alternando entre as jogadas do próprio algoritmo e do oponente, calcula uma pontuação para cada jogada baseada em regras definidas pelos seus desenvolvedores (neste caso, eu e o Yuri) e decide qual a melhor jogada baseada na pontuação mais alta obtida para si mesma, a fim de maximizar suas chances de vitória.
Ao mesmo tempo, o algoritmo também leva em consideração a pontuação mais baixa obtida pelo oponente, com o objetivo de minimizar as chances de vitória do oponente. Dessa forma, o Minimax é capaz de tomar decisões estratégicas de maneira inteligente, considerando tanto a sua própria pontuação quanto a pontuação do adversário.
Agora que você sabe o que é o Gomoku e Minimax, a dúvida é: Por que modelar esta IA para jogar Gomoku é um desafio?
Fundamentos do algoritmo de IA
Para qualquer solução de Inteligência Artificial, é preciso modelar o problema (abstrair as informações para que possam ser computadas) no formato em que o algoritmo usado requer para ser implementado.
Por exemplo, como definimos as regras de cálculo da pontuação de cada jogada que foi mencionada anteriormente? Ou, até um passo antes disso, como fazemos o algoritmo entender o que está acontecendo no jogo?
Dificuldades na Implementação
1. Como pontuamos cada jogada?
Eu estaria mentindo se dissesse que foi fácil definir nosso método de pontuação das jogadas. inicialmente pensamos: "Deve ser simples! Vamos só contar quantas sequências de peças temos e quais são os seus tamanhos. Dessa forma, saberemos se estamos indo bem". Não demorou muito para percebermos que este método é (MUITO) falho.
Se fôssemos pontuar a jogada abaixo baseado no nosso primeiro método, pareceria que as peças brancas estão ganhando, já que têm uma sequência de 4 peças enquanto as pretas têm uma sequência com 3. No entanto, sabemos que essa sequência das peças brancas não tem valor nenhum, pois não há como completá-la. Enquanto isso, a sequência das peças pretas está vitoriosa pois, mesmo que as peças brancas bloqueiem algum dos lados da sequência, esta pode ser completada pelo lado oposto.
Nós decidimos que criaríamos um dicionário com algumas jogadas e quantos pontos aquela jogada vale.
Quando fôssemos calcular a pontuação total da jogada, para cada padrão do dicionário que encontrar no tabuleiro, o valor daquele padrão será somado à pontuação total daquela jogada.
Vale mencionar que nosso programa converte todas as verticais e diagonais em linhas horizontais. Logo, todos os exemplos abaixo funcionam para todas as direções.
Nosso dicionário não é tão longo mas acaba sendo bem repetitivo para alguns casos. Por conta disso, para esta publicação, usarei apenas alguns exemplos de jogadas que mapeamos.
2. O programa estava absurdamente lento
a. A quantidade de jogadas possíveis importa
Não estou exagerando! Em um de nossos testes, o programa levou mais de 20 minutos para calcular uma única jogada. Não preciso dizer que ninguém gostaria de jogar contra um adversário que demora 20 minutos para decidir sua jogada.
Uma explicação um pouco mais detalhada do Minimax:
- Explora todas as jogadas possíveis que podem ser feitas naquele momento.
- Para cada jogada possível, cria um novo tabuleiro filho.
- Calcula a pontuação de cada um dos tabuleiros filhos.
- Escolhe o filho com a maior pontuação.
- Repete os passos 1, 2 e 3.
- Escolhe o filho com a menor pontuação. (pois está simulando a jogada de seu oponente)
- Continua repetindo o processo até que o algoritmo alcance um estado final (por exemplo, um jogador ganhou ou empatou) ou atinja uma profundidade máxima na árvore de busca (Falarei sobre a profundidade máxima mais à frente).
- Quando isso acontece, o algoritmo decide a melhor jogada, baseado na pontuação.
Por que isso é importante? Como mencionado acima, o algoritmo olha todas as casas possíveis do tabuleiro, mas isso é relevante? Faz sentido olhar todas as jogadas possíveis? Veja o exemplo abaixo:
Não faz sentido simular uma jogada em qualquer lugar que esteja vermelho pois isso não terá efeito no jogo.
Por isso, implementamos a restrição de que o algoritmo só simulará jogadas em casas que tiverem alguma peça na vizinhança.
Não só isso, mas nós também programamos as 3 primeiras jogadas iniciais de uma forma mais fixa. O Minimax só começa a jogar na 4º rodada. Dessa forma, economizamos bastante processamento no início do jogo.
Antes de definirmos isso, estávamos usando uma outra estratégia em que o programa gerava um novo tabuleiro apenas com as peças já jogadas e usava um sistema de converter as coordenadas para que fossem equivalentes no tabuleiro original. Se quiser saber mais sobre isso, veja minha outra publicação: Como uma mudança de perspectiva pode mudar completamente sua forma de implementar uma solução.
b. Profundidade da árvore de decisão
A profundidade da árvore de decisão pode ser vista como "quantas jogadas à frente o algoritmo simula". Nós encontramos um comportamento muito curioso em nosso programa: Quando escolhíamos a profundidade máxima como "2", o algoritmo levava até 10 segundos para calcular uma jogada. Quando aumentávamos esse valor para "3", o tempo subia para 2 minutos e meio! Para "4" nós nem tivemos a paciência de esperar terminar.
Após muita pesquisa, encontramos o artigo "New heuristic algorithm to improve the Minimax for Gomoku artificial intelligenceartificial intelligence", escrito por Han Liao
Neste artigo, Han diz que em um computador típico, para que o jogo flua bem, a profundidade máxima da árvore de decisão não pode ser maior que 3. Isso é muito ruim pois o Minimax funciona melhor com profundidades grandes mas, infelizmente, isso é uma das limitações da aplicação de Minimax no Gomoku.
Algumas imagens do projeto
O Yuri tomou a iniciativa de fazer a parte visual do jogo com a biblioteca Pygame e fez um trabalho fenomenal!
Conclusão
Este projeto me proporcionou muitos conhecimentos novos. Trabalhei com técnicas e conceitos que nunca tinha visto antes. Foi muito gratificante trabalhar na prática com a aplicação de inteligência artificial, pois é muito clara a diferença entre saber a teoria e aplicar na prática.
Além disso, este projeto despertou minha curiosidade por muitas outras áreas. Enquanto pesquisava soluções para os problemas que encontramos, aprofundei meu conhecimento em novos conceitos e técnicas de otimização. Um exemplo disso foi o artigo de Han Liao, que explicou outros experimentos com inteligências artificiais aplicadas ao jogo Gomoku.
Descobrimos o artigo de Han muito tarde em nosso projeto, enquanto buscávamos uma forma de tornar nosso programa mais eficiente. Ficamos muito orgulhosos de ter aplicado todas as técnicas de otimização e de ter feito o melhor possível no projeto, considerando que o artigo de Han é uma tese de mestrado em Engenharia da Computação.
Top comments (5)
Mano, ficou muito facil e divertido de ler!! Adorei que você colocou as referencias também o/
Obrigado, Fran!! Tentei ao máximo escrever de uma forma simples para que qualquer um consiga entender o que foi feito no trabalho. Meu próximo post será aprofundado na parte técnica e como as coisas realmente funcionam.
Ficou incrível.
Sério, muito interessante! É nítido o esforço que vocês empenharam e da pra perceber que curtiram trabalhar no problema. Já dei ⭐ no repo, aconselharia adicionar essas imagens e dar uma incrementada no README porque assim chama mais atenção ;)
Olá!! obrigado pelo apoio!
O readme está em contrução. Estamos trabalhando no artigo que descreve o problema tecnicamente para quem é tem mais experiência e o readme vai ser mais ou menos isso. Hoje ele está simples pois estávamos exaustos quando terminamos... Este projeto foi uma fonte absurda de novos conhecimentos mas eu estaria mentindo se disesse que foi fácil.
Mais uma vez, obrigado!!