Aula_06_-_Busca_competitiva

Prévia do material em texto

Inteligência Artificial
Busca Competitiva
Professor: Felipe Alberto B. S. Ferreira
felipe.bsferreira@ufrpe.br
mailto:felipe.bsferreira@ufrpe.br
Resolução de Jogos
§ Damas: 1950: Primeira IA. 1994: Primeira IA 
vencedora: Chinook venceu Marion Tinsley 
(campeão humano durante 40 anos) calculando 8 
jogadas à frente. 2007: Jogo Damas resolvido!
§ Xadrez: 1997: Deep Blue derrota campeão
humano Gary Kasparov. Deep Blue avaliava 200M 
de posições por segundo, usava uma função de 
avaliação sofisticada e métodos proprietários para 
buscar em até 40 de profundidade. Agentes atuais
são ainda mais eficientes.
§ Go: Campeões humanos estão iniciando a serem
desafiados por IAs. Em Go, b > 300! Avanços
recentes usam métodos de expansão baseados em
simulações Monte Carlo (aleatoriamente).
Game Playing State-of-the-Art
§ Damas: 1950: Primeira IA. 1994: Primeira IA 
vencedora: Chinook venceu Marion Tinsley 
(campeão humano durante 40 anos) calculando 8 
jogadas à frente. 2007: Jogo Damas resolvido!
§ Xadrez: 1997: Deep Blue derrota campeão
humano Gary Kasparov. Deep Blue avaliava 200M 
de posições por segundo, usava uma função de 
avaliação sofisticada e métodos proprietários para 
buscar em até 40 de profundidade. Agentes atuais
são ainda mais eficientes.
§ Go: 2016: Alpha GO derrota campeão humano. 
Usa Monte Carlo Tree Search e função de 
avaliação aprendida.
§ Pacman
Comportamento através de Computação
Vídeo de Demonstração
Jogos Competitivos
§ Vários diferentes tipos de jogos!
§ Variedades:
§ Determinístico ou estocástico?
§ Um, dois ou mais jogadores?
§ Jogo de soma zero?
§ Informação perfeita (dados disponíveis)?
§ Queremos um algoritmo para calcular uma estratégia que recomenda uma
ação para cada estado
Tipos de Jogos
Jogos Determinísticos
§ Várias formalizações possíveis, uma é:
§ Estados: S (inicia em s0)
§ Jogadores: P = {1...N} (jogam em turnos)
§ Ações: A (pode depender do jogador ou estado)
§ Função de transição: (S, A) ® S
§ Teste de término: S ® {t,f}
§ Função utilidade: (S, P) ® R
§ A solução para um jogador é uma
estratégia: S ® A
Jogos de Soma Zero
§ Jogos de soma zero
§ Agentes tem utilidades opostas
§ Como um único valor em que um jogador
procura maximizar enquanto o outro procura
minimizar
§ Adversarial, pura competição
§ Jogos gerais
§ Agentes possuem utilidades independentes
§ Cooperação, indiferença, competição, etc…
§ Veremos adiante na disciplina…
Busca Adversarial (Competitiva)
Ávore de Jogo com um único Agente
8
2 0 2 6 4 6… …
Valor de um Estado
Estados não-terminais:
8
2 0 2 6 4 6… … Estados terminais:
Valor do estado: O 
melhor resultado
alcançavel (utilidade) 
deste estado
Árvore de Jogo Adversarial (por turnos)
-20 -8 -18 -5 -10 +4… … -20 +8
Valores Minimax
+8-10-5-8
Estados controlados pelo agente
Estados terminais:
Estados controlados pelo oponente:
Árvore de Jogos do Jogo-da-Velha
Busca Adversarial (Minimax)
§ Jogos determinísticos e de soma zero:
§ Jogo-da-velha, damas, xadrez
§ Um jogador maximiza o resultado
§ O outro minimiza o resultado
§ Busca Minimax:
§ Árvore de busca de estados
§ Jogadores alternam turnos
§ Calcula o valor minimax para cada nó: 
máxima utilidade alcançavel contra um 
agente competitivo racional (ótimo)
8 2 5 6
max
min2 5
5
Valores terminais:
depende do jogo
Valores Minimax:
calculados recursivamente
Implementação do Algoritmo Minimax
def min-valor(estado_atual):
inicialize v = +∞
para cada sucessor de estado_atual:
v = min(v, max-valor(sucessor))
retorne v
def max-valor(estado_atual):
inicialize v = -∞
para cada sucessor de estado_atual:
v = max(v, min-valor(sucessor))
retorne v
Implementação do Algoritmo Minimax
def valor(estado_atual):
se estado_atual é terminal: retorne utilidade
se estado_atual é MAX: retorne max-valor(estado_atual)
se estado_atual é MIN: retorne min-value(estado_atual)
def min-valor(estado_atual):
inicialize v = +∞
para cada sucessor de estado_atual:
v = min(v, valor(sucessor))
retorne v
def max-valor(estado_atual):
inicialize v = -∞
para cada sucessor de estado_atual:
v = max(v, valor(sucessor))
retorne v
Exemplo Algoritmo Minimax
12 8 5 23 2 144 6
Características do Minimax
Ótimo contra um oponente ótimo. Caso contrário?
10 10 9 100
max
min
Demo Min vs. Exp (Min)
Demo Min vs. Exp (Exp)
Eficiência do Minimax
§ Quão eficiente é?
§ Assim como DFS (exaustivo)
§ Tempo: O(bm)
§ Espaço: O(bm)
§ Ex.: para xadrez, b » 35, m » 100
§ Solução exata é inviável
§ Mas, precisamos explorar toda a 
árvore?
Limitação de Recursos
Poda na Árvore de Jogos
Minimax: Exemplo
12 8 5 23 2 144 6
Poda na Busca Minimax
12 8 5 23 2 14
Poda Alpha-Beta
§ Configuração geral (versão de MIN)
§ Estamos calculando o valor MIN em algum nó 𝛽
§ Estamos percorrendo os sucessores de 𝛽
§ A estimativa do nó 𝛽 está reduzindo
§ O valor de 𝛽 é de interesse de MAX
§ Seja 𝛼 o melhor valor que MAX pode obter em um dado 
caminho a partir da raiz
§ Se 𝛽 se tornar pior que 𝛼, MAX irá evitar esse caminho e 
podemos desconsiderar os sucessores de 𝛽
§ A versão de MAX é simétrica
MAX
MIN
MAX
MIN
𝛼
𝛽
Implementação da Poda Alpha-Beta
def min-valor(estado_atual, α, β):
inicialize v = +∞
para cada sucessor de estado_atual:
v = min(v, valor(sucessor, α, β))
se v ≤ α retorne v
β = min(β, v)
retorne v
def max-valor(estado_atual, α, β):
inicialize v = -∞
para cada sucessor de estado_atual:
v = max(v, valor(sucessor, α, β))
se v ≥ β retorne v
α = max(α, v)
retorne v
α: melhor opção de MAX
β: melhor opção de MIN
Características
§ A poda não afeta o valor minimax calculado para a raiz!
§ Valores de nós intermediários podem estar errados
§ Importante: sucessores da raiz podem ter o valor errado
§ A forma mas simples não define a seleção das ações
§ A ordenação dos sucessores afeta a efetividade da poda
§ Com uma “ordenação perfeita”:
§ A complexidade reduz para O(bm/2)
§ Duplica a profundidade que pode ser explorada!
§ Busca exaustiva, para xadrez por exemplo, ainda é inviável…
§ Esse é um exemplo de meta-racionalização (calculamos para saber o que calcular)
10 10 0
max
min
Alpha-Beta Quiz
Alpha-Beta Quiz 2
Limitação de Recursos
Limitação de Recursos
§ Problema: em cenários reais, não é possível chegar
até as folhas!
§ Solução: busca em profundidade limitada
§ Busque apenas até um limite de profundidade na árvore
§ Substitua a utilidade terminal por uma função de avaliação
em nós não terminais (aproximação)
§ Exemplo:
§ Suponha que temos 100 segundos e podemos explorar 10K 
nós / seg
§ Logo, podemos verificar 1M de nós por “jogada”
§ a-b alcança profundidade 8 em xadrez
§ Perde-se a garantia de otimalidade
§ Mais níveis fazem MUITA diferença
§ Use aprofundamente iterative quando não se sabe o 
limite de tempo
? ? ? ?
-1 -2 4 9
4
min
max
-2 4
Exemplo com d = 2 (avaliação = pontuação)
Qual foi o Problema?
§ Problema em agente de replanejamento!
§ Ele sabe que a pontuação irá subir ao comer imediatamente (oeste, leste)
§ Ele sabe que a pontuação irá subir igualmente ao comer depois (leste, oeste)
§ Não existem indicativos de melhorias após comer o ponto (em seu campo de visão, que é 2)
§ Logo, esperar parece tão bom quanto comer: ele pode ir para o leste, depois voltar para o 
oeste no segundo turno de replanejamento!
Exemplo com d = 2 (corrigido)
Funções de Avaliação
Funções de Avaliação
§ Funções de avaliação pontuam nós não terminais
§ Função ideal: valor minimax real da posição atual
§ Na prática: normalmente é uma soma ponderada de características
§ ex.: f1(s) = (num de peças brancas – num peças pretas), etc.
Avaliação para o Pacman
Demo Fantasmas “Inteligentes” (coordenação)
Demo Fantasmas “Inteligentes” (coordenação) - 2
O Campo de Visão
§ Funções de avaliação são sempre 
imperfeitas
§ Quanto mais “fundo” na árvore, 
menos importante é a qualidade
da função de avaliação
§ Relação custo-benefício entre a 
complexidade das características
e da computaçãoDemo Profundidade Limitada (d=2)
Demo Profundidade Limitada (d=10)
Sinergia entre a Função de Avaliação e Alpha-Beta?
§ 1) O tamanho da poda depende da ordem de expansão
§ A função de avaliação pode guiar a expandir primeiro os nós mais promissores
(aumenta as chances de encontrar um bom caminho)
§ (similar ao papel da heurística para o A* e filtragem em PSRs)
§ 2) Substituir valor minimax pela função de avaliação
§ O valor em um nó MIN irá apenas diminuir
§ Assim que o valor em um nó MIN é menor que a melhor opção em um nó MAX, 
podemos podar
§ Logo: SE a função de avaliação retorna o limite superior em um nó MIN, e o limite
superior é menor que a melhor opção em um nó MAX, podemos podar
Referência
§ Stuart RUSSEL e Peter NORVIG, Inteligência Artificial. 3ª ed.
§ Capítulo 5: seções 5.1 até 5.4.