Aula 3 MinMax

Prévia do material em texto

Aula 3
Busca competitiva e MiniMax
Motivação
• Supercomputador e um software 
criados pela IBM especialmente 
para jogar xadrez; 
• Possuía 256 processadores. 
Analisava aproximadamente 200 
milhões de posições por segundo; 
• Em fevereiro de 1996, Garry
Kasparov ganhou 3 partidas, 
empatou 2 e perdeu 1 contra o 
Deep Blue. Kasparov declarou que 
era o último humano a ser 
campeão de xadrez; 
• Em maio de 1997, após uma severa 
atualização, Deep Blue venceu 
Kasparov em um novo confronto 
de 6 partidas, sendo 2 vitórias, 3 
empates e 1 derrota
Busca 
• Diferentemente da busca tradicional vista até 
agora, na qual a situação não troca durante a 
busca, a busca com adversários (competitiva) 
considera que há oponentes hostis em sua 
trajetória.
Garry Kasparov and Deep Blue
Busca competitiva
• Num ambiente multiagente, é necessário 
considerar as ações de outros agentes e o modo 
como essas ações nos afetam. 
• A imprevisibilidade de outros agentes pode 
introduzir contingências no processo de resolução 
de problema. 
• Em ambientes competitivos, as metas dos agentes 
estão em conflito, dando origem a problemas de 
busca competitiva, onde se enquadram os jogos.
Jogos em IA
• Em IA, os jogos são determinísticos, de revezamento de 
dois jogadores, com informações perfeitas. 
• A posição (favorável ou desfavorável) de um jogador 
num determinado instante (estado) do jogo pode ser 
medida por uma função de utilidade. 
• Os valores de utilidade dos agentes no fim do jogo são 
iguais e opostos (simétricos): +1 (ganha), ou –1 (perde). 
• O objetivo da busca competitiva é planejar com 
antecedência num mundo em que outros agentes estão 
fazendo planos contra nós.
Determinísticos: dada uma certa entrada, 
ela produzirá sempre a mesma saída.
Jogos
• Entre os primeiros domínios de aplicação, pois: 
• É fácil representar o estado de um jogo. 
• Em geral, os agentes estão restritos a um pequeno 
número de ações com resultados definidos por regras 
precisas. 
• Constituem uma tarefa estruturada em que é fácil medir 
o sucesso ou fracasso. 
• Supunha-se que os jogos podiam ser solucionados por 
uma busca direta do estado inicial para a posição 
vencedora, sem grandes quantidades de conhecimento.
• Exceção existe?
MiniMax
• É um dos algoritmos estudados na teoria dos jogos, 
onde se tem um adversário:
• Xadrez, dama, jogo da velha.
• Maximizar a utilidade (ganho) supondo que o 
adversário vai tentar minimizá-la.
• O agente é Max e o adversário é Min
• MiniMax faz busca cega em profundidade.
Árvores de Jogos
• É a representação de jogos para dois jogadores utilizando 
árvores, onde: 
• Nó raiz: estado antes de qualquer movimento do jogo; 
• Nós da árvore: possíveis estados do jogo; 
• Arcos (arestas não contidas em círculos): movimentos. 
• Os movimentos dos dois jogadores são os níveis da árvore: 
• Arcos do primeiro nível: movimentos do 1º Jogador; 
• Arcos do segundo nível: movimentos do 2º Jogador; 
• e assim por diante. 
• Folhas da árvore: estados finais (vitória, perda ou empate); 
• O nó objetivo pode ser um estado final onde o computador 
ganhou;
Árvores de Jogos
MiniMax
• Passos: Deve-se gerar toda árvore até os estados 
terminais.
• Em seguida, faz-se a busca em profundidade, aplicando 
a função de utilidade nas folhas.
• Ex: Quantas peças favoráveis ficariam no tabuleiro.
• Em caso de subida da busca, os valores da função são 
propagados através do MiniMax (se tivermos em um nó 
MIN, ele recebe o menor dos valores, se tivermos em 
um nó MAX, ele recebe o maior dos valores).
• Por fim, o MiniMax determina o valor (jogada) que deve 
ser escolhido pelo jogador:
• Max escolher o maior e Min o menor.
MiniMax
4 5 8 6
Min
Max
Sua jogada
Jogada do 
oponente
MiniMax
4
4 5 8 6
Min
Max
Sua jogada
Jogada do 
oponente
MiniMax
4 6
4 5 8 6
Min
Max
Sua jogada
Jogada do 
oponente
MiniMax
6
4 6
4 5 8 6
Min
Max
Sua jogada
Jogada do 
oponente
MiniMax
6
4 6
4 5 8 6
Min
Max
Sua jogada
Jogada do 
oponente
MiniMax
• Como se pode perceber, o algoritmo MiniMax
consegue encontrar a melhor solução, entretanto 
ele precisa percorrer toda a árvore.
• Problemas:
• Tempo gasto para determinar a decisão ótima é 
totalmente impraticável (ir até as folhas), porém o 
algoritmo serve como base para outros métodos mais 
realísticos.
Exemplo: Xadrez...
• Fator médio de ramificação: 35 
• Número médio de jogadas: 50 para cada jogador. 
• Assim, a árvore completa de busca de um jogo terá 
aproximadamente 35100 nós. 
• Portanto, uma busca cega é inviável, mesmo para realizar o 
primeiro movimento. 
• Se deve fazer o melhor uso possível do tempo disponível 
para uma jogada: tomar alguma decisão, mesmo que a 
jogada ótima não seja determinada em tempo.
• Para melhorar:
• Limitar a profundidade da busca.
• Podar a árvore onde a busca seria irrelevante: poda alpha-beta.
MiniMax com poda Alpha-Beta
• Objetivo:
• Não expandir desnecessariamente nós durante o 
MiniMax, ou seja, reduzir a árvore da busca 
(otimização).
• Idéia: 
• Não vale a pena piorar, se já achou algo melhor.
• Mantém 2 parâmetros:
• Melhor valor (no caminho) para Max
• Melhor valor (no caminho) para Min
MiniMax
• Passos: Deve-se gerar toda árvore até os estados 
terminais.
• Em seguida, faz-se a busca em profundidade, aplicando 
a função de utilidade nas folhas.
• Em caso de subida da busca, os valores da função são 
propagados através do MiniMax (se tivermos em um nó 
MIN, ele recebe o menor dos valores, se tivermos em 
um nó MAX, ele recebe o maior dos valores).
• Até aqui, tudo igual ao MiniMax tradicional, porém, na 
busca, não expande nós irrelevantes. Ou seja, poda!
MiniMax
• Duas perguntas:
• Se estivermos no nó min, existe qualquer ancestral max
que seja maior ou igual a min? Se sim, poda o restante 
dos filhos.
• Se estivermos no nó max, existe qualquer ancestral min
que seja menor ou igual a max? Se sim, poda o restante 
dos filhos.
Exercício:
Exercício:
Trabalho Prático
• Criar um agente capaz de jogar contra um usuário 
humano para o Jogo (“Tesouro”)
• Trabalho em dupla.
• A interface gráfica pode ser simples (modo texto), 
porém deve permitir ao usuário perceber qual situação 
atual do jogo e selecionar sua próxima jogada.
• Implemente o algoritmo minimax com poda alpha e 
beta.
• Avaliação: Entrevista apresentando/explicando código 
fonte e demonstração do jogo.
• Data: 31/01/2018
Trabalho Prático
• Regras:
• Movimentos:
• Ataque: qualquer diagonal.
• Objetivo: pegar o tesouro do 
computador.
Computador
Usuário