A Inteligência Artificial está ganhando cada vez mais popularidade nas grandes corporações. Pequenas e inovadoras empresas estão em uma corrida contra o tempo para entrarem na vanguarda da tecnologia e ganhar vantagem contra a concorrência.
No meio de tanta informação sobre inteligência artificial, os conceitos básicos que definem grande parte do dicionário de um profissional da área geralmente são esquecidos.
Neste artigo, explicarei o funcionamento de um algoritmo chamado Minimax, muito usado no campo de Teoria de Jogos para desenvolver a inteligência artificial de jogos competitivos, principalmente os chamados jogos de soma zero, onde se um jogador vence, o outro necessariamente perde.
Game Tree
Para jogos como o Xadrez, Damas e Jogo da Velha, podemos representar todas as possibilidades de jogada em uma Game Tree.
Cada ‘nó’ representa uma possível jogada, e cada ‘linha’ representa um turno (um jogador após o outro).
No caso do Jogo da Velha, é possível processar computacionalmente a sua respectiva Game Tree, pois o número de ‘nós’ é igual a 255.168.
Um jogo de Xadrez por exemplo, possui mais possibilidades de jogadas do que átomos no nosso universo observável!
Algoritmo Minimax
Com a Game Tree conseguimos identificar qual caminho seguir para ganhar o jogo de uma maneira que o inimigo não consiga interferir.
Conforme demonstrado na imagem acima, o resultado (Terminal) pode ser -1 (Perder), 0 (Empatar) ou 1 (Ganhar). Basta a inteligência artificial seguir caminhos que o levam para um +1 que terá uma vitória certeira.
Para isso, precisamos de alguma maneira informar o nosso agente qual o caminho mais seguro. E aí entra o papel do Algoritmo Minimax.
O princípio do Minimax é descer os ‘nós’ da Game Tree até chegar no término do jogo, identificando se o jogador perdeu, empatou ou ganhou.
Após isso, o algoritmo sobe um ‘nó’ e identifica de quem é o turno (jogador ou oponente). Caso for o turno do oponente, o algoritmo guarda o menor (Min) resultado de suas respectivas ramificações.
Caso for o turno do jogador, o algoritmo guarda o maior (Max) resultado de suas respectivas ramificações.
Este processo se repete até chegar no primeiro ‘nó’ da Árvore.
Isso significa que, caso a decisão do jogador ganhar ou perder esteja nas mãos do oponente, o Minimax atribui como não sendo seguro entrar por este caminho, indicando somente como ‘1’ os caminhos em que o jogador possa vencer a partida mesmo que o oponente jogue da melhor forma possível.
Pseudocódigo do Algoritmo Minimax
Fonte: Artificial Intelligence a Modern Approach, 3rd edition
A abordagem do pseudocódigo apresentado no livro “Artificial Intelligence a Modern Approach” define duas funções Mutuamente Recursivas que percorrem os ‘nós’ Min e Max para achar o respectivo valor da ramificação, e possui uma função decisiva que escolhe o movimento otimizado.
Também é comum ver o minimax representado como uma simples função recursiva:
Pseudocódigo em Português
ROTINA minimax(nó, profundidade)
SE nó é um nó terminal OU profundidade = 0 ENTÃO
RETORNE o valor da heurística do nó
SENÃO SE o nó representa a jogada de algum adversário ENTÃO
α ← +∞
PARA CADA filho DE nó
α ← min(α, minimax(filho, profundidade-1))
FIM PARA
RETORNE α
SENÃO
α ← -∞
PARA CADA filho DE nó
α ← max(α, minimax (filho, profundidade-1))
FIM PARA
RETORNE α
FIM SE
FIM ROTINA
Fonte: Wikipedia
Minimax é um algoritmo considerado como conhecimento básico dentro das competências de um Engenheiro de Inteligência Artificial e pode ser usado para o desenvolvimento de complexas aplicações, principalmente no âmbito de jogos, valendo-se do seu poderoso potencial de decisão.
- Escrito originalmente por Lorenzo Candiago.
Dica: A Orgânica é uma agência de Marketing Digital especializada. Saiba mais!
