Inteligência Artificial - Algoritmo Minimax

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.

Entenda um pouco mais sobre a Inteligência Artificial - Algoritmo Minimax

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.

“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...”

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

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

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.

Para continuar se atualizando e se conectando com outros profissionais, sugerimos que você participe do se inscreva em nossa newsletter — Aqui, com a Agência Smart — você encontrará discussões ricas, tutoriais, dicas, oportunidades de colaboração e eventos que podem ajudar a expandir seus conhecimentos e rede de contatos.

Não perca a oportunidade de se inscrever no nosso canal, onde você terá acesso a conteúdos exclusivos e atualizações constantes sobre as últimas tendências e melhores práticas para escalar o resultado de seu negócio.