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

Procuras Adversas (implementar)

Execute uma das ações

 Ação 1: Reformule o Jogo do Galo:

• Generalizar para um jogo do 5 em linha, num tabuleiro de 9x9
• Heurística: contar para cada hipótese de se fazer 5 em linha ainda não anulada pelo adversário, 1 ponto se forem necessárias 4 jogadas para fazer 5 em linha, 10 pontos se forem necessárias 3 jogadas, 100 pontos se forem necessárias 2 jogadas e 1000 pontos se for necessário apenas uma jogada.
• O infinito passa para 10000.

 Ação 2: Implemente uma outra versão num tabuleiro de 7x7, em que as peças caiem (apenas se pode colocar uma peça em cima de outra peça), mantendo a mesma função heurística, mas com o objectivo de fazer 4 em linha.

Código exemplo

Para executar esta atividade deve ter os Algoritmos de IIA compilados e podendo ser executados localmente, ou executar o código a partir do VPL no recurso Algoritmos IIA, de forma idêntica à AF2b.

 Ação 1: Correr o programa resultante de Algoritmos Introdução à Inteligência Artificial.

 Ação 2: O Aspirador tem uma função heurística implementada, que pode ser visualizada na exploração dos sucessores: 2.

Na informação sobre o estado, a letra h tem a informação sobre a heurística, h(n) no manual. No estado inicial o valor da heurística é 4, significando que não é possível com menos de 4 movimentos atingir-se o objetivo. A heurística sendo admissível nunca ultrapassa o custo mínimo até à solução final. Esta heurística é feita com base num procedimento simples, que conduz à solução ótima para este problema:

• Começar por um dos lados, para a sala suja mais à esquerda ou à direita (conforme a que estiver mais próxima), e ir limpando até chegar à última sala suja

Esta estratégia é óptima, o que nos ajuda aqui a ter um problema em que identificamos a heurística perfeita, e ver se os algoritmos informados fazem bom uso desta informação. Esta situação já não irá ocorrer em muitos outros problemas, ou numa versão deste problema que se complique, e veremos que os algoritmos ainda assim fazem bom uso desta.

Em vez de se implementar o algoritmo diretamente, o que se tem de definir é o custo para a solução objetivo. Neste caso será somar os movimentos até um extremo das salas sujas, os movimentos para se mover do extremo para outro, e o tempo de limpar todas as salas sujas. Não é preciso dar indicação para ir primeiro para a sala suja mais próxima, embora a ideia por detrás desta heurística foi essa intenção em mente. 

A vantagem de se utilizar um algoritmo genérico, é que se a heurística não for perfeita, mas for admissível, isto é, não sobre-estimar o custo, os algoritmos irão conseguir à mesma encontrar a solução ótima.

Reparar que apenas um estado sucessor a heurística diminui.

Ação 3: Executar manualmente o algoritmo melhor primeiro, em que avança sempre para o sucessor com a menor heurística.

Este foi o resultado da resolução manual, avançando sempre pelo melhor sucessor, com base no valor da heurística. Com uma heurística perfeita, esta solução é também óptima. Pode utilizar esta técnica para instâncias de qualquer dimensão, caso naturalmente exista uma heurística perfeita, o que nem sempre acontece.

Puzzle8, procura melhor primeiro

Mantemos o mesmo exemplo utilizado nas procuras cegas:

A procura melhor primeiro vai expandir primeiro os estados gerados há menos tempo, antes dos restantes, mas de entre os estados com o mesmo pai, expande primeiro os que tiverem um valor heurístico menor, dado serem esses os mais promissores. Portanto tem que se calcular o valor da função heurística, que devolverá uma estimativa para a distância até um estado objetivo. Para este problema podemos ter a distância de Manhattan, que é a distância na horizontal e vertical de cada número até à sua posição final.

Este algoritmo pode ser basicamente idêntico à procura em profundidade cega, mas alterando a ordem de expansão, o que leva a que possa ser também colocado um limite. Neste caso vamos utilizar o limite 10, significando que não deve explorar soluções com mais de 10 passos.

Ficheiro de Excel, passo a passo:

Considerando que o teste de estado objetivo se faz na função heurística, já que é suposto devolver 0 no caso de ser um estado objetivo, a procura leva 3 expansões, tendo sido gerados e avaliados 9 estados.

Após a expansão do estado 1, foram gerados e avaliados 3 estados, dos quais optou-se por expandir o estado 3 já que desses é o que possui o menor valor heurístico, portanto poderá estar mais perto de um estado objetivo. Resultante da expansão do estado 3, foram gerados 3 estados, tendo sido nesse caso o estado 7 o de menor valor, e assim por diante. Não foi preciso voltar atrás neste exemplo; o algoritmo foi direto à solução a três passos. Se por exemplo tivesse atingido o limite, teria de voltar para trás, escolhendo sempre para expandir, de entre os últimos estados gerados mas não expandidos com o mesmo pai (e no mesmo nível), o que tiver menor valor heurístico.

Se a heurística for muito boa, este algoritmo segue a direito sem problemas. No entanto, por vezes a utilização de uma boa heurística tem custos computacionais incomportáveis. Mais: nas procuras informadas, é normalmente mais pesada a função heurística, sendo portanto mais relevante o número de avaliações, podendo no entanto trocar com a geração de sucessores, no caso de se optar por uma heurística leve.

 Ação: Considere que o estado de partida era o estado 4 da resolução acima. Execute este algoritmo e indique o número dos estados expandidos por ordem de expansão, separados por vírgulas sem espaços.