Jogo do Galo, MinMax

As procuras anteriores consideram que se está a tentar realizar um determinado objectivo, sem qualquer oposição. No caso dos jogos, tenta-se também realizar um objectivo, no entanto há outros agentes a tentar realizar os seus próprios objetivos. O caso mais simples, é quando há apenas dois agentes, com objetivos opostos, um jogo entre dois adversários.

O jogo do galo joga-se num tabuleiro de 3x3, em que cada jogador coloca à vez a sua marca num quadrado vazio. O objectivo do jogo é obter 3 marcas em linha reta (horizontal, vertical ou diagonal).

O MiniMax funciona de modo idêntico ao algoritmo de profundidade primeiro, mas em cada estado final tem o valor de vitória/derrota/empate (para as brancas, que é o jogador que começa a jogar). Se o nível máximo foi atingido e ainda não é um estado final, deve ser retornada uma estimativa para o valor do estado, aproximando-se do valor da vitória no caso da posição estar favorável às brancas, ou próximo do valor derrota no caso da posição estar favorável às pretas. Em cada estado, o MiniMax retorna o valor máximo dos seus sucessores, no caso de ser as brancas a jogar, e o valor mínimo dos seus sucessores, no caso de ser as pretas a jogar. Após correr, obtêm-se uma estratégia de jogo com base nos sucessores que determinaram o valor de cada estado.

No jogo do galo, pode-se remover estados simétricos, considerando a simetria horizontal, vertical e diagonal. Relativamente à função com a estimativa do estado, vamos considerar o seguinte: somar as possibilidades a duas jogadas de ganhar o jogo, e subtrair as do adversário, somando também as possibilidades de ganhar a uma jogada mas com peso 10.

Vamos fazer a procura do MiniMax com nível de profundidade limite 2:

Ficheiro de Excel, passo a passo:

A expansão é feita como se fosse um algoritmo em profundidade. O estado 1 ao ser expandido gera os estados 2 a 4. Não gera mais porque os restantes sucessores são idênticos aos três gerados a menos de operações de simetrias (horizontal, vertical, diagonal). Esses três estados ficam no nível 1, já que o estado 1 está no nível 2, e enquanto o estado 1 procura maximizar, os estados 2 a 4 procuram minimizar, daí a indicação de MAX e MIN.

O estado 4 é expandido, dando lugar aos estados 5 e 6, de nível 0. Como são de nível 0, não há lugar a mais expansões, pelo que é calculado o valor do estado. O estado 5 tem 3 hipóteses de vitória a dois lances para as brancas, e 2 hipóteses de vitória a dois lances para as pretas, ficando portanto com valor 1. Já o estado 6 tem 3 hipóteses para as brancas contra 1 hipótese para as pretas, ficando com valor 2. Como o estado 4 procura minimizar, o valor do estado 4 fica com o valor 1, que é o mínimo entre 1 e 2.

Expande-se o estado 3, resultando nos estados 7 a 11, com valores entre -2 e 0. Como se pretende minimizar, o valor do estado 3 é -2. Repetindo-se o processo para o estado 2, obtêm-se o valor de -1 para esse estado.

Após explorar todos os sucessores do estado 1, pode-se calcular o seu valor, com base no valor máximo dos seus sucessores, dado que é um estado MAX. entre -2, -1 e 1, o valor máximo é 1.

A estratégia resultante é portanto a seguinte: as brancas devem optar pelo estado 4, e no segundo lance, as pretas devem optar pelo estado 5, de forma a cada força maximizar as suas possibilidades: 1,4,5

Naturalmente que a estratégia resultante de uma procura com maior profundidade pode ser diferente.

 Ação: Assuma que as brancas jogaram para o estado 4, e volte a repetir este algoritmo. Indique qual é agora a nova estratégia, com o número dos estados separados por vírgulas, como indicado acima: 1,4,5