Algoritmo MiniMax
Luís Carlos Calado – 050509043
João Carlos Sousa – 050509027
José Carlos Campos – 060509007
Rodolfo Sousa Silva – 050509069
Inteligência Artificial 2008/2009
1
Minimax
Minimax (ou minmax) é um método usado na Teoria da Decisão,
Teoria dos Jogos, Estatística e Filosofia para minimizar a perda
máxima possível.
Teorema Minimax
Von Neumann foi um brilhante matemático nascido
em Budapeste em 1903.
Devido à demonstração do teorema minimax, Von
Neumann foi considerado o pai da teoria dos jogos
em 1926.
Inteligência Artificial 2008/2009
2
Minimax
Este teorema surgiu a partir da Zero-Sum Game
Theory:
“Para qualquer jogo para dois jogadores que respeite a teoria
zero-sum, existe uma estratégia mista para cada jogador tal
que o resultado esperado para os dois é o mesmo valor V
quando os jogadores usam esta estratégia. V é o melhor
valor que cada um pode esperar de uma jogada. Isto é, estas
estratégias mistas são as estratégias óptimas para os dois
jogadores.”
Inteligência Artificial 2008/2009
3
Qual o exemplo mais simples para
ilustrar o Minimax?
Inteligência Artificial 2008/2009
4
Xadrez
Damas
Go
Inteligência Artificial 2008/2009
5
Porque não aplicar o Minimax no Xadrez?
Factor médio de ramificação: ~35
Tempo entre duas jogadas: 2,5 minutos (150 segundos)
Computador: analisa 10 000 estados / segundo
Estados analisáveis: 150 segundos * 10^4 estados = 1 500 000
Nº de estados à profundidade p: r^p = 35^p
35^4 = 1 500 625 (à profundidade 4, o computador já não analisa
todas as jogadas)
Um bom jogador humano consegue prever de 6 a 8 jogadas
Conclusão: Minimax é demasiado custoso em tempo
Inteligência Artificial 2008/2009
6
Jogo do Galo
OK
Inteligência Artificial 2008/2009
7
Algoritmo (Pseudo-código)
Determinar
SE {
profundidade limite atingida
OU Nivel é Minimizador
OU Nivel é Maximizador }
ENTÃO
SE profundidade limite
Calcular valor do estado corrente
Retornar resultado
SE Nivel Minimizador
Aplicar minimax aos sucessores
Retornar Mínimo
SE Nivel Maximizador
Aplicar minimax aos sucessores
Retornar Máximo
Inteligência Artificial 2008/2009
8
- Processo de pesquisa com Minimax
- Exemplo de árvore de pesquisa com profundidade 5
- Os valores da função Heurística são relativos ao jogador X
Heurística = ∑ linhas/colunas/diagonais em aberto ->X
∑ linhas/colunas/diagonais em aberto ->O
Inteligência Artificial 2008/2009
9
Exemplo
Max
Min
Para cada nível MINimizador ou MAXimizador,
escolher o MINímo ou MAXimo dos sucessores
Inteligência Artificial 2008/2009
10
Exemplo (continuação)
Max
Min
Inteligência Artificial 2008/2009
11
Será que o minimax em alguma altura
realiza trabalho “inútil”?
Inteligência Artificial 2008/2009
12
Resposta? Sim
Max
Min
Inteligência Artificial 2008/2009
13
Cortes alfa-beta
- Permite diminuir o número de nós visitados e de funções nos nós
avaliados
- Possui profundidade limitada
- Inclui-se um limite inferior para valor a minimizar (beta -> valor mais
baixo que o jogador min já assegurou), e um limite superior para o
valor a maximizar (alfa -> valor mais alto do jogador max)
- A pesquisa dos sucessores de um nó termina quando se verificar
alfa>=beta
Inteligência Artificial 2008/2009
14
Algoritmo (Pseudo-código)
alfa-beta(jogador, mundo, alfa, beta)
SE o jogo terminou no estado actual do mundo
devolve vencedor
filhos = todas as jogadas possíveis a partir do estado actual
SE jogador = MAX
PARA cada filho
avaliação = alfa-beta(adversário, filho, alfa, beta)
SE avaliação > alfa ENTÃO
alfa = avaliação (encontrou-se uma melhor jogada)
SE alfa >= beta ENTÃO
devolve alfa (ignora restante ramos)
devolve alfa (esta é a melhor jogada)
SENÃO jogador = MIN
PARA cada filho
avaliação = alfa-beta(adversário, filho, alfa, beta)
SE avaliação < beta ENTÃO
beta= avaliação (adversário encontrou uma melhor pior jogada)
SE alfa >= beta ENTÃO
devolve beta (ignora restante ramos)
devolve beta (a melhor jogada do adversário)
Inteligência Artificial 2008/2009
15
Exemplo
Max
Min
Inteligência Artificial 2008/2009
16
Exemplo (continuação)
Max
Min
Inteligência Artificial 2008/2009
17
Contras
Apesar de tudo o que foi referido, os cortes Alfa-Beta podem não trazer
melhorias.
Na prática, se as opções surgirem de uma determinada ordem (crescente
no maximizador e decrescente no minimizador), os cortes Alfa-Beta
não trazem melhorias.
Inteligência Artificial 2008/2009
18
Ordem de complexidade
Se a profundidade máxima da árvore for m e em cada ponto houver b
hipóteses possíveis (factor de ramificação):
(*)
com uma ordenação perfeita
Inteligência Artificial 2008/2009
19
Outra abordagem, Negamax
Inteligência Artificial 2008/2009
20
Negamax
Este algoritmo é semelhante ao Minimax mas tira partido das heurísticas
poderem ser as mesmas para o jogador e seu adversário (como é o caso do
Xadrez).
Enquanto que o Minimax maximiza a heurística do jogador e minimiza a do
adversário, o Negamax nega (multiplica por -1) o valor da heurística
correspondente ao nível onde teria de minimizar. Assim não precisa de saber
o nível onde se encontra e maximiza sempre.
Inteligência Artificial 2008/2009
21
Exemplo
Inteligência Artificial 2008/2009
22
Exemplo (continuação)
Inteligência Artificial 2008/2009
23
Resumo - Minimax
- Baseia-se na suposição de que o adversário escolherá sempre
o movimento ideal, e nunca incorrerá ao erro;
- Gera toda a árvore de busca, dentro do limite permitido;
-O Algoritmo é completo apenas no caso de a árvore ser finita
(ex.: Jogo do Galo);
- O tempo gasto para determinar a decisão óptima é totalmente
impraticável para qualquer jogo minimamente complexo, pois
gera caminhos cuja possibilidade de serem seguidos é
praticamente nula.
Inteligência Artificial 2008/2009
24
Resumo – Corte alfa-beta
- Eficiente para determinar quais os ramos que não
devem ser explorados;
- Não afecta o resultado final;
- Uma boa ordenação dos nós aumenta ainda mais a sua
eficiência, no entanto se isso não acontecer este algoritmo pode
não trazer qualquer vantagem;
Inteligência Artificial 2008/2009
25
?
Inteligência Artificial 2008/2009
26
Obrigado pela vossa atenção
E
Boa sorte para o teste
Inteligência Artificial 2008/2009
27