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):
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):
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:
- Abre o espaço de estados a partir do estado atual do jogo (até uma profundidade configurada - mais detalhes posteriormente)
- De baixo pra cima, transporta os valores de estados, maximizando na sua jogada e minimizando na jogada do adversário
- 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).
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:
- 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).
- 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.
- 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.
- 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.
- 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.
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!)