Algoritmo Minimax - Introdução à Inteligência Artificial


Algoritmo Minimax - Introdução à Inteligência Artificial

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.

Imagem exemplo 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.

Algoritmo Minimax

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 ‘’ 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.

exemplo minimax

Pseudocódigo do Algoritmo Minimax

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.
 

 

 




Por
27/07/2017

Coordenador de Tecnologia na Orgânica Digital. Baixista e Beatlemaníaco.


Assine nosso blog

Não perca nenhuma novidade!

Assine nosso blog

Não perca nenhuma novidade!