Algoritmo Min Max em IA: Componentes, Propriedades, Vantagens e Limitações

O algoritmo min max em IA, popularmente conhecido como minimax, é um algoritmo de retrocesso usado na tomada de decisão, teoria dos jogos e inteligência artificial (IA). Ele é usado para encontrar o movimento ideal para um jogador, assumindo que o oponente também está jogando de maneira ideal. Jogos populares de computador para dois jogadores ou jogos online como Xadrez, Tic-Tac-Toe, Damas, Go, etc. usam este algoritmo.

Um algoritmo de retrocesso é usado para encontrar uma solução para problemas computacionais de tal forma que um candidato seja construído incrementalmente em direção a uma solução, um passo de cada vez. E o candidato que não consegue completar uma solução é imediatamente abandonado.

Como funciona?

No algoritmo min max em IA, existem dois jogadores, Maximizador e Minimizador. Ambos os jogadores jogam o jogo enquanto um tenta obter a pontuação mais alta possível ou o benefício máximo, enquanto o oponente tenta obter a pontuação mais baixa ou o benefício mínimo.

Cada tabuleiro de jogo tem uma pontuação de avaliação atribuída a ele, então o Maximizador selecionará o valor maximizado e o Minimizador selecionará o valor minimizado com movimentos contrários. Se o Maximizador estiver em vantagem, a pontuação do tabuleiro será um valor positivo, e se o Minimizador estiver em vantagem, a pontuação do tabuleiro será um valor negativo.

Isso é baseado no conceito de jogo de soma zero, onde a pontuação total de utilidade é dividida entre os dois jogadores. Assim, um aumento na pontuação de um jogador leva a uma diminuição na pontuação do jogador adversário, fazendo com que a pontuação total seja sempre zero. Então, para um jogador ganhar, o outro tem que perder.

Participe dos cursos de Certificação de Aprendizado de Máquina e IA online das melhores universidades do mundo. Ganhe Masters, Executive PGP ou ACP para acelerar sua carreira.

Quebrando o algoritmo min max na IA

A árvore de jogo completa é explorada com um algoritmo de busca em profundidade no algoritmo min max em IA. Ele prossegue inteiramente até o nó terminal da árvore e então retrocede pela árvore.

O objetivo é encontrar a melhor jogada possível para um jogador. Isso pode ser feito escolhendo o nó com a melhor pontuação de avaliação. A melhor escolha será feita após avaliar todos os movimentos potenciais do oponente. O algoritmo antecipa todos os valores possíveis até o final e toma uma decisão para o jogador.

Fonte

A árvore do jogo acima é uma estrutura de dados aninhada que é usada para avaliar os movimentos. Aqui, o nó raiz é o Nível 0, que se ramifica no Nível 1 ou nós pais, que se ramificam ainda mais no Nível 2 ou nós filhos. A ramificação pode continuar em muitos níveis, tendo o potencial de níveis infinitos. O nível 0 é como o estado atual do tabuleiro, enquanto o nível 1 são todos os estados possíveis dos tabuleiros, dependendo do próximo movimento.

Assim, se o jogador 2 fez uma jogada, podemos supor que o nó raiz é o estado atual do tabuleiro, aguardando a jogada do jogador 1. Os nós de Nível 1 contêm todos os movimentos possíveis para o Jogador 1, e os nós de Nível 2 contêm todos os movimentos possíveis para o Jogador 2 com base em cada movimento possível do Jogador 1.

Considere um exemplo onde há quatro estados finais e o caminho para alcançá-los é da raiz às quatro folhas de uma árvore. Os valores das quatro folhas são 3, 6 à esquerda e 4, 7 à direita. É a vez do Maximizador/Jogador 1 fazer um movimento. Para percorrer o algoritmo, suposições para cada movimento devem ser feitas.

Se o Jogador 1 escolher ir para a esquerda, o Minimizador/Jogador 2 tem que escolher o mínimo entre 3 e 6, então ele escolheria 3. Enquanto que se o Jogador 1 escolher a direita, o Jogador 2 escolherá 4, que é o mínimo dos dois valores, 4 e 7. Assim, o Nível 1 agora tem os valores 3 e 4.

Como é a vez do Jogador 1/Maximizador, ele deve escolher o máximo de nós de Nível 1. Assim, eles vão escolher 3. Então a escolha ideal é ir para a esquerda.

Os passos para o algoritmo min max em AI podem ser declarados da seguinte forma:

1. Crie toda a árvore do jogo.
2. Avalie as pontuações para os nós folha com base na função de avaliação.
3. Retroceder da folha para os nós raiz:

Para Maximizer, escolha o nó com a pontuação máxima.

Para Minimizer, escolha o nó com a pontuação mínima.

4. No nó raiz, escolha o nó com o valor máximo e selecione o respectivo movimento.

Leia também: Ideias de projetos de aprendizado de máquina

Propriedades do algoritmo min max na IA

• O algoritmo está completo, ou seja, em uma árvore de busca finita, uma solução certamente será encontrada.
• É ótimo se ambos os jogadores estiverem jogando de forma otimizada.
• Devido ao Depth-First Search (DFS) para a árvore do jogo, a complexidade de tempo do algoritmo é O(b m ), onde b é o fator de ramificação e m é a profundidade máxima da árvore.
• Como DFS, a complexidade de espaço deste algoritmo é O(bm).

Vantagens

• Uma avaliação completa do espaço de busca é realizada.
• A tomada de decisão em IA é facilmente possível.
• Máquinas novas e inteligentes são desenvolvidas com este algoritmo.

Limitações

• Por causa do enorme fator de ramificação, o processo de atingir a meta é mais lento.
• A avaliação e pesquisa de todos os nós e ramificações possíveis degrada o desempenho e a eficiência do mecanismo.
• Ambos os jogadores têm muitas opções para decidir.
• Se houver restrição de tempo e espaço, não é possível explorar toda a árvore.

Mas com o Alpha-Beta Pruning, o algoritmo pode ser melhorado.

Conclusão

Este artigo explica todos os aspectos do algoritmo min-max na IA. Primeiro, uma introdução da teoria é fornecida com exemplos de onde ela é usada, após o que há uma descrição de como o algoritmo funciona em um jogo.

O algoritmo é dividido para explicar como uma decisão de fazer um movimento ideal é tomada com base nos movimentos e contra-movimentos dos jogadores. As propriedades do algoritmo são então listadas. Por fim, são apresentadas as vantagens e desvantagens do algoritmo.

Se você estiver interessado em aprender mais sobre aprendizado de máquina, confira o Programa PG Executivo do IIIT-B e do upGrad em Machine Learning e IA , projetado para profissionais que trabalham e oferece mais de 450 horas de treinamento rigoroso, mais de 30 estudos de caso e atribuições, IIIT -B Alumni status, mais de 5 projetos práticos práticos e assistência de trabalho com as principais empresas.