O algoritmo Minimax, Corte Alpha-Beta e outros Refinamentos

O algoritmo Minimax

O algoritmo minimax se baseia na construção de uma árvore de decisões (árvore contendo todos os possíveis estados do jogo e de qual estado se pode chegar a qual), pontua cada um dos nós segundo as chances de vitória ou derrota dos jogadores e retorna como melhor solução sempre aquela que busca minimizar as chances de perda e maximizar as chances de vitória.
Desta forma, nós pontuados positivamente (melhores chances para a vitória) serão buscados como solução, enquanto que nós pontuados negativamente (nós onde há a possibilidade de derrota) serão evitados.
Tomemos como exemplo um jogo da velha onde queremos maximizar as chances do computador vencer (tentando, assim, trazer algum desafio ao jogador humano).
Facilmente o computador consegue criar e manter em memória uma árvore contendo todas as possíveis jogadas para o jogo da velha (o mesmo não pode ser dito para o caso de jogos de xadrez, devido às dimensões da árvore de decisões deste). Construamos então uma árvore de decisões na qual é o jogador humano quem começa o jogo.

A construção da árvore é feita de forma bem simples:  há raiz conterá o estado inicial do jogo, com o tabuleiro completamente em branco. Os filhos deste nó devem ser as possíveis jogadas adotadas pelo jogador humano (inicialmente nove, então teremos aqui nove nós-filhos).

Para cada nó, crie seus nós filhos segundo as possibilidades de jogo, lembrando de armazenar em cada nó qual seria o estado atual do jogo se aquele fosse o estado corrente.

Após a construção de toda a árvore, começamos pontuando cada nó da seguinte forma:
1.    Se este nó não é um nó-folha:

  • Se, para este nó, o próximo a jogar é o humano e um dos nós-filhos representa um estado em que ele vence, então este é um nó ruim, pois aumentará as chances do computador perder – pontuaremos ele com valor -1;
  • Caso contrário, pontuamos este nó com o somatório dos valores de seus filhos;

2.    Se este é um nó-folha e representa:

  • A vitória do computador, pontuamos com valor 1;
  • A derrota do computador, pontuamos com valor -1;
  • O empate, pontuamos com valor 0.

Uma vez pontuada a árvore, inicia-se o jogo e, a cada jogada dos participantes, deve-se ir percorrendo a árvore, sendo que o computador para efetuar sua jogada irá checar qual dos nós-filhos do nó atual possui maior pontuação: esta deverá ser a sua jogada.

O corte alpha-beta

Como se pode perceber, o algoritmo minimax consegue encontrar a melhor solução, entretanto ele precisa percorrer toda a árvore. Ela pode ser facilmente mantida para um jogo-da-velha, onde temos “somente” 400 mil nós, mas para um jogo de xadrez, onde podemos ter 10 elevado a 70 nós, construir, avaliar e percorrer toda a árvore torna-se algo inviável.
Sendo assim, é perceptível que precisamos ter algum meio para “podar”, cortar os galhos que jamais serão solução para nós. Tomemos como exemplo um jogo-da-velha onde o computador será o jogador MAX e o jogador humano, o jogador MIN.
Em um dado nó onde o jogador MAX deverá tomar uma decisão, teremos vários nós filhos, cada qual com seus próprios valores. O jogador MAX sempre quer maximizar, então é óbvio que ele escolherá sempre o nó que possuir maior valor, descartando sempre os demais, então, para que manter os outros nós?
Podemos então podar esse “galho” de nossa árvore! O algoritmo de corte alpha-beta, aplicado juntamente com o minimax, possui justamente essa função. A poda pode ser feita após a completa criação da árvore, bem como pode ser feita durante a construção da mesma, após a pontuação completa dos filhos ou por meio de alguma função heurística a fim de avaliar o valor de cada filho.

Movimentos de Livros – Aberturas e Fechamentos

Mesmo empregando o algoritmo de corte alpha-beta, é inviável manter toda a árvore de decisões em memória para determinados problemas, como é o caso do jogo de xadrez.

Nesses casos, podem ser adotadas outras formas de refinamento, sendo uma delas conhecida como movimentos de livros, isto é, sequencias de movimentos consideradas como já sendo as melhores no início da resolução do problema (aberturas) bem como na finalização do mesmo (fechamentos).

Esta técnica é, na verdade, muito adotada por jogadores de xadrez, que estudam e memorizam as principais aberturas e fechamentos do jogo.

Desta forma, nos primeiros passos do algoritmo o mesmo se baseia em movimentos previamente registrados (aberturas) e somente após terminar um dado movimento, ele irá criar toda a árvore de decisão (que é na verdade uma sub-árvore daquela obtida sem aplicar esta técnica) culminando cada um dos nós-folhas em um movimento de finalização (fechamento) de tal forma que, se tal nó for alcançado, basta executar a sequencia de passos de tal movimento.

A aplicação desta técnica tornou possível a implementação do algoritmo de inteligência artificial de Deep Blue, primeiro programa de computador a derrotar um campeão mundial (no caso, Kasparov) em condições de torneio.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS
 

4 comments

  1. […] Aula 3 – O Algoritmo Minimax, o Corte Alpha-Beta e Outros Refinamentos […]

  2. Mistika says:

    Olá, vc tem esse jogo da velha com o algoritmo MIniMax implementado em Java?

  3. admin says:

    Olá Mistika, tudo bem?

    Eu não estou bem certo, mas se bem me lembro tivemos a implementação do jogo da velha utilizando o algoritmo Minimax como atividade em laboratório e um dos meus alunos implementou-o em Java.

    Eu entrarei em contato com ele e, se possível, disponibilizarei mais tarde aqui, mas infelizmente neste exato momento eu não tenho.

Leave a Reply

Your email address will not be published. Required fields are marked *

Email
Print