14

Minha primeira pergunta aqui, recentemente comecei um "Jogo Da Velha" em Java e ele já esta pronto, porém eu quero implementar a capacidade de tomada de decisões, ou inteligência-artificial.

Descobri que o melhor meio para tal, é usando MiniMax, porém não encontrei um "start-guide" bom na internet.

Gostaria de saber como começo meu Minimax, ou quem sabe um código comentado com um Minimax.

Ou qualquer sugestão de inteligencia artificial para o meu joguinho, obrigado a todos. :D

2
  • Você já viu isso: isjavado.wordpress.com/2012/06/22/… ? Parece ser exatamente o que procura.
    – gustavox
    Commented 5/05/2015 às 1:03
  • 1
    Já sim, vi vários antes de finalmente vir perguntar aqui, na verdade estou a uma semana procurando, e não achei um claro, esse código ai como pode imaginar, é muito complicado de abstrair só o MINIMAX para alguém com o meu parco conhecimento de programação.
    – Andiie
    Commented 5/05/2015 às 23:56

1 Resposta 1

21

Antes de mais nada, é importante entender o conceito de Espaço de Estados. O Espaço de Estados de um problema é a árvore ou grafo dos estados possíveis do problema ao longo de sua resolução, sendo que cada ação (representada por um arco) leva de um nó de estado a um outro nó. No caso do jogo da velha, a ação é fazer uma jogada (do x ou do o), e o espaço de estados tem aproximadamente 9! = 362.880 nós, pois a partir do primeiro estado vazio há inicialmente 9 estados possíveis (considerando que o x joga primeiro), sob os quais há então 8 estados possíveis (para jogada do o), e para cada um deles mais 7 estados possíveis (para nova jogada do x), e assim sucessivamente até uma condição de término (vitória de alguém ou empate com preenchimento total do tabuleiro):

inserir a descrição da imagem aqui

O MinMax não deixa de ser um algoritmo de busca em árvore (na IA, chamado de busca no espaço de estados), porém tem uma característica fundamental: ele considera que existe um adversário que também é uma entidade inteligente e racional (isto é, que atua/joga da melhor forma possível, tentando maximizar seu próprio desempenho sempre)1.

1Assim, ele não funciona bem caso o adversário jogue de forma aleatória (mesmo que eventualmente).

Ele faz isso escolhendo os nós durante a busca de forma que maximize um valor de ganho em suas próprias jogadas e minimize esse valor de ganho nas jogadas do adversário (note a notação que eu uso, em que círculo azul significa escolha para maximizar e quadrado vermelho significa escolha para minimizar):

inserir a descrição da imagem aqui

A minimização do valor de ganho nas jogadas do oponente significa a consideração de que o adversário também irá jogar de forma ótima (ou seja, tentando diminuir o ganho do computador).

No caso do jogo da velha, é comum usar o valor de cada estado como +1 para estados que são de vitória (ou levam à vitória), -1 para estados que são de derrota (ou levam à derrota) e 0 para estados de empate (ou que levam ao empate). Assim, na execução do algoritmo ele faz o seguinte:

  1. Abre o espaço de estados a partir do estado atual do jogo (até uma profundidade configurada - mais detalhes posteriormente)
  2. De baixo pra cima, transporta os valores de estados, maximizando na sua jogada e minimizando na jogada do adversário
  3. Até chegar ao estado atual, quando então já se tem o caminho ideal

A animação a seguir ilustra como ocorre esse processo. Lá no último nível da árvore há um nó azul, que se trata de uma jogada do computador (e que deve ser maximizada). Abaixo dele há dois possíveis estados, um de vitória outro de derrota (por exemplo), assim o algoritmo escolhe o maior valor (maximiza a jogada). Esse procedimento será efetuado progressivamente para os níveis superiores, até que chega em um nó vermelho (que é uma jogada do adversário, e deve ser minimizada). Logo, se escolhe o menor valor (minimiza na jogada do adversário). Eventualmente todos os nós filhos do nó principal (que é o estado atual) já terão sido computados, então basta escolher aquele que maximiza o valor (afinal, novamente tem-se a jogada do computador).

inserir a descrição da imagem aqui

Os valores utilizados nesse exemplo são interessantes para um jogo da velha, mas outros jogos podem usar valores diferentes (pois podem haver estados mais ou menos interessantes e isso pode ser medido em uma escala particular do problema à escolha do projetista). A implementação do algorítmo é baseada em algoritmos clássicos de processamento de árvores/grafos, como a busca em profundidade ou a busca em largura.

No caso do jogo da velha, a árvore tem uma profundidade máxima de 9 níveis (são no máximo 9 jogadas, em caso de empate), então vale a pena usar a busca em profundidade. Em outros jogos (como o sliding puzzle - não sei o nome em português...), processar toda a árvore pode ser computacionalmente impeditivo. Por isso, há uma técnica para evitar explorar nós desnecessários, chamada de Poda Alpha-Beta. A ideia dessa poda da árvore é manter duas variáveis, alpha com o melhor valor de maximização (valor mais alto encontrado até o momento) e beta com o melhor valor de minimiazação (valor mais baixo encontrado até o momento). Assim, ao abrir os nós, os valores obtidos são comparados com os de alpha e beta para decidir por não explorar os demais nós de mesma filiação.

Considere a animação a seguir com um exemplo fictício:

  1. A busca em profundidade se iniciou no primeiro nó azul (estado atual), desceu para o primeiro nó vermelho do segundo nível (mais à esquerda), e desceu para seus filhos abrindo-os e calculando o valor de cada estado (no exemplo, respectivamente os valores 3, 9 e 7).
  2. Como o nó em questão (o nó de interesse, ou seja, o nó pai) é vermelho, trata-se de uma jogada do adversário que será minimizada. Assim, escolhe-se o valor 3 e passa-se para o próximo nó do mesmo nível (o nó vermelho intermediário, no segundo nível). O valor de beta é definido como 3.
  3. A busca em profundidade vai abrir o primeiro nó filho resultando no valor 2, menor do que o mínimo atual (alpha = 3). Ainda não se sabe o valor dos demais nós irmãos desse nível (e isso pode significar que seus eventuais sub-nós não foram processados para se chegar ao seu valor!). Mas isso não importa, porque o valor resultante (chamado de u no gráfico) vai ser necessariamente menor ou igual a 2 uma vez que o nó vermelho é de minimização (entenda que o adversário vai jogar de forma que o computador vai ganhar no máximo 2 de qualquer jeito nessa ramificação da árvore). Assim, os demais nós desse nível não são explorados, evitando processamento desnecessário. E beta é alterado para 2.
  4. Por fim, faz-se o mesmo com o último nó do segundo nível (o nó vermelho à direita). A busca em profundidade novamente abre o primeiro nó filho que resulta em 14. Se só houvesse esse nó filho, essa ramificação seria interessante porque teria um valor maior (e melhor para o computador) do que o mínimo atualmente obtido (o beta igual a 2). Mas como há mais nós filhos, precisa-se continuar abrindo o próximo nó no mesmo nível. Nele, se obtem o valor 1 que é menor do que o mínimo atual (beta = 2). Aqui, como anteriormente, foi encontrado um valor de minimização menor do que o atual e por isso o processamento dessa ramificação pode ser interrompido já que não importa o que contiver nos demais nós: o valor de ganho obtido aqui vai ser menor ou igual a 1.
  5. Tendo-se essas minimizações do adversário, é processado o nível atual (o primeiro nível, do estado atual do jogo) em que se busca maximizar o ganho (já que é a jogada do computador). Logo, o valor escolhido é o 3, que indica que o caminho ideal (que maximiza o ganho do computador a longo prazo) é pela ramificação da esquerda.

inserir a descrição da imagem aqui

Em outras palavras, isso é o equivalente a fazer:

minimax = max{ min{3, 9, 7}, min{2, ?, ?}, min{14, 1, ?, ?} }
minimax = max{ 3, x, y } com x <= 2 e y <= 1

Logo:

minimax = max{ 3, 2, 1 }
minimax = 3

Esse exemplo foca na poda de nós quando a minimização é verificada, mas é a mesma coisa quando a maximização é verificada - só que invertendo a comparação do ganho (e usando a outra variável):

minimax = min{ max{2, 5, 8}, max{15, ?, ?}, max{7, 9, 22, ?} }
minimax = min{ 8, x, y } com x >= 15 e y >= 22
minimax = min{ 8, 15, 22 }
minimax = 8

Nota: Observe nesse outro exemplo como ao abrir o nó com ganho 9 (na terceira ramificação à direita) o processamento não para porque o valor de alpha, que inicialmente era 8, foi alterado para 15 na segunda ramificação e por isso a terceira ramificação precisa ser aberta até encontrar o valor 22.

No caso de espaços de estado realmente grandes2, há também a possibilidade de se limitar a busca a uma profundidade configurada (por exemplo, as próximas 8 jogadas). Nesse caso, os valores dos nós de níveis mais baixos é simplesmente estimando sem a necessidade de explorar seus estados filhos. No xadrez, por exemplo, essa estimativa pode ser feita com base na ponderação de valores a partir do poder das peças (peão vale 1, peão no centro vale 2, cavalo vale 3, rainha vale 9, etc) e/ou na comparação do estado atual com estados sabidamente bons para o computador (extraídos de livros de aberturas e encerramentos, partidas com estatísticas de vitória, etc).

2Como o caso do Xadrez (cujo número médio de jogadas é 40 e o número médio de ramificação por estado é 35 subestados), em que o espaço de estados estimado é da ordem de 1061 nós (muito próximo ao número de átomos no universo!)

2
  • 1
    Foi uma leitura muito proveitosa, pontuou alguns is, Melhorou o meu conceito de como a lógica funciona, e agora eu vou quebrar a cabeça até encontrar uma forma de "codificar" a minha lógica, porque eu consigo pensar na operação acontecendo, mas ainda não consigo imaginar como implementar isso em código, mas eu agradeço muito, foi uma excelente orientação :D
    – Andiie
    Commented 9/05/2015 às 5:22
  • Eu entendo essa dificuldade. É natural. Mas acho que é importante entender bem o algoritmo, pois assim é mais fácil você entender as implementações de exemplo que existem pela Internet. Se vc tem dificuldades, eu te sugiro começar a implementar o algoritmo de busca em profundidade (sem entrar no mérito do MinMax). Vai te ajudar a entender o princípio da coisa. :) Boa sorte! Commented 9/05/2015 às 15:12

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .