Busca Contra Adversário ou Jogos
Adversarial Search or Game playing
CIn/UFPE
Jogos
 Em ambientes multiagentes, há pouca previsibilidade
• Ações dos outros agentes
• É preciso tratar as contingências
 Em ambiente competitivos, há conflito de objetivos
• Ex. negociação em comércio eletrônico
 Nestes casos, temos “Busca contra adversário, ou
simplesmente “jogo”
 Em economia, na “teoria dos jogos”, considera-se um
“jogo” qualquer ambiente multiagente onde o impacto de
um agente sobre os outros é considerado “significativo”,
não importa se os agentes são competitivos ou
cooperativos.
CIn/UFPE
Jogos – Exercício
 Tradicionalmente, a IA interessou-se sobretudo com um tipo
particular de jogo
• Dois jogadores (Two-player)
• Soma-zero (Zero-sum): se um ganha, o outro perde
• Discreto (discrete): todos os estados do jogo bem como as decisões
possíveis são valores discretos
• Finite (finito): somente um número finito de estados e decisões
• Determinístico (deterministic): sem “lançamento de dados”
• Observável (perfect information): observável por ambos os jogadores
 Histórico
• Xadrez: desde anos 50, hoje atingiu nível de mestre
• Damas e Othelo: hoje, melhor que qualquer humano
• Gamão: hoje, nível de campeão
• Go, nível amador
CIn/UFPE
Fonte: http://www.cs.cmu.edu/~awm/tutorials
Exercício: Quais desses são jogos: two-player, zero-sum,
discrete, finite, deterministic, with perfect information
CIn/UFPE
Fonte: http://www.cs.cmu.edu/~awm/tutorials
Exercício: Quais desses são jogos: two-player, zero-sum,
discrete, finite, deterministic, with perfect information
CIn/UFPE
Jogos
 Aplicações atrativas para métodos IA desde o início.
• Sinônimo de inteligência
• Ações bem definidas e ambiente acessível
• Abstração (representação simplificada de problemas reais)
 Porém desafiador:
• Complexidade
– Xadrez: 35 movimentos possíveis por turno, 25 jogadas por jogador
por partida => 3550  10154 (1040 nós distintos)
• Incerteza devido ao outro jogador;
• Problema “contingencial”: agente deve agir antes de completar a
busca
CIn/UFPE
Formulando um jogo
 Elementos essenciais da formulação de um jogo
•
•
•
•
Estado inicial: posições do tabuleiro + de quem é a vez
Estado final: posições em que o jogo acaba
Operadores: jogadas legais para um dado estado da partida
Função de utilidade (objetivo ou payoff): valor numérico para
os estados finais (pontuação)
– Xadrez = +1, 0, -1; gamão = [-192,+192]
 Busca: algoritmo minimax
• Idéia: maximizar a utilidade (ganho) supondo que o adversário vai
tentar minimizá-la (todos jogam otimamente!)
– O agente é MAX e o adversário é MIN
• Minimax faz busca cega em profundidade
CIn/UFPE
Formulando um jogo – Mais formalmente...
 Um jogo do tipo two-player, zero-sum, discrete, finite,
deterministic, with perfect information é uma quíntupla: (S, I,
Succs, T, V), onde:
S
Um conjunto finito de estados (observação: com informação suficiente
para deduzir quem vai jogar em seguida)
I
O estado inicial, que especifica como o jogo começa
Succs
Uma função que toma um estado como entrada e retorna um conjunto
de estados seguintes possíveis disponíveis para quem vai jogar
T
Um subconjunto de S que indica os estados terminais: o conjunto de
estados para os quais o jogo terminou
V
Um mapeamento de estados finais para números reais. A pontuação
que o jogador A ganha de B (se é negativo então A perde para B)
Convenção: Assume-se que A joga primeiro
Por conveniência: assume-se turnos alternados: A joga, depois B joga
CIn/UFPE
CIn/UFPE
CIn/UFPE
CIn/UFPE
Formulando um jogo
 Busca: algoritmo minimax
• Idéia: maximizar a utilidade (ganho) supondo que o adversário vai
tentar minimizá-la (todos jogam otimamente!)
– O agente é MAX e o adversário é MIN
• Minimax faz busca cega em profundidade
CIn/UFPE
CIn/UFPE
CIn/UFPE
CIn/UFPE
CIn/UFPE
CIn/UFPE
CIn/UFPE
Jogo da velha (min-max)
Max(X)
x
x
x
x
x
x
x
Min(O)
xo
x
xo x
x
o
...
xo
x
xo
x
...
...
...
...
...
xo x
o x
o
xo x
o o x
xx
xo x
x
xo o
-1
0
+1
o
x
Max(X)
Min(O)
CIn/UFPE
...
Função utilidade
x
Algoritmo Minimax
 Passos
• Gera a árvore inteira até os estados terminais.
• Aplica a função de utilidade nas folhas.
• Propaga os valores dessa função subindo a árvore através do
minimax
• Determinar qual o valor que será escolhido por MAX
 Formalmente: o valor minimax de um nó n é dado por
• Minimax-Value(n) =
Utility(n),
maxssucesssors(n)Minimax-Value(s),
minssucesssors(n)Minimax-Value(s),
CIn/UFPE
se n é terminal
se n é um nó Max
se n é um nó Min
Algoritmo
CIn/UFPE
Críticas
 É completa e ótima mas...
 Problemas
•
•
Tempo gasto é totalmente impraticável, porém o algoritmo
serve como base para outros métodos mais realísticos.
Complexidade: O(bm).
 Para melhorar (combinar duas técnicas)
1) Podar a arvore onde a busca seria irrelevante: poda alfa-beta
(alfa-beta pruning)
2) Substituir a profundidade n de min-max(n) pela estimativa de
min-max(n): função de avaliação
CIn/UFPE
Alpha-Beta Pruning (poda alfa-beta)
 Função:
• Não expandir desnecessariamente nós durante o minimax (mas
devolvendo o mesmo resultado)
 Idéia: não vale a pena piorar, se já achou algo melhor
 Mantém 2 parâmetros
•  - melhor valor (mais alto) encontrado até então para MAX
•  - melhor valor (mais baixo) encontrado até então para MIN
 Teste de expansão:
•  não pode diminuir (não pode ser menor que um ancestral)
•  não pode aumentar (não pode ser maior que um ancestral)
CIn/UFPE
Alfa-Beta
Lembrar que min-max faz
busca em profundidade
[-∞,+∞]
A
O melhor para MIN é 3
e para MAX é +∞
[-∞,3] B
3
[-∞,+∞]
A
[-∞,3] B
3
CIn/UFPE
12
Nada mudou...
Alfa-Beta
[3,+∞]
A
[3,3]
B
3
12
Agora dá para saber
que MIN vai escolher
no máx. 3
8
[3,+∞]
A
CIn/UFPE
[3,3]
B
3
12
[-∞,2] C
8
2
Não vale mais a pena
para MAX explorar C,
porque MIN vai
escolher no máx. 2
e MAX já tem 3
Alfa-Beta
[3,14]
A
[3,3]
B
[-∞,2] C
3
12
[-∞,14] D
2
8
Realisticamante, 14 é o
melhor para max
por enquanto
14
[3,3]
A
CIn/UFPE
[3,3]
B
3
12
[-∞,2] C
8
2
[2,2] D
14
5
2
Balanço da poda alfa-beta
 Poda não afeta o resultado final
 Com um ordenamento perfeito das jogadas,
complexidade = O(bm/2)
 Bom exemplo de raciocínio sobre a relevância de se
cálcular coisas (forma de meta-raciocício)
CIn/UFPE
Funções de Avaliação
 Reflete as chances de ganhar: baseada no valor material
• ex. valor de uma peça independentemente da posição das outras
 Exemplo: Função Linear de Peso de propriedade do nó:
• w1f1+w2f2+...+wnfn
• Ex. Os pesos (w) no xadrez poderiam ser o tipo de pedra do
xadrez (Peão-1, ..., Rainha-9) e os (f) poderiam ser o número de
cada peça no tabuleiro.
 Escolha crucial: compromisso entre precisão e eficiência
CIn/UFPE
Função de avaliação (h) para o jogo da velha:
sugestões?
X
X
0 tem 5 possibilidades
X tem 6 possibilidades
0
0
X
h=6-5=1
0
0
X
CIn/UFPE
h=5-4=1
X 0
h = 4 - 6 = = -2
Uso da Funções de Avaliação
Minimax de duas jogadas (two-ply) aplicado à abertura do jogo da velha
Quando aplicar a função de avaliação?
 Definir uma profundidade máxima ou iterativa não
funciona devido à incerteza inerente ao problema
 Solução: Procura Tranqüila (Quiescence search):
• Idéia: evitar avaliação em situações a partir das quais pode haver
mudanças bruscas
• No caso do jogo da velha, toda posição é tranqüila mas no xadrez
não.... (ex. um peça de xadrez a ser comida)
• Algoritmo: Se a situação (nó) é “tranqüila”, então aplica a função
de avaliação, senão busca até encontrar uma situação “tranqüila”
CIn/UFPE
E aí: é útil mesmo?
 Ainda pode ser complexo...
• bm = 106, b=35  m=4
 Olhar para frente 4-ply (quatro lances) é pouco para um
nível profissional!
• 4-ply ≈ novato humano
• 8-ply ≈ PC típico, mestre humano
• 12-ply ≈ Deep Blue, Kasparov
CIn/UFPE
Jogos com elementos de acaso
 Há jogos com elementos de imprevisibilidade maior do
que os tratados
• Ex. gamão
• Não sabemos quais são as jogadas legais do adversário
• A árvore de jogos (game tree) usada não vai servir!
CIn/UFPE
Jogos com elementos de acaso
 Nova árvore de jogos
• Inclui nós de acaso, além dos nós MAX e MIN
• Os ramos dos nós de acaso, correspondem ao resultados do
jogar dos dados do gamão, por exemplo
– Cada ramo pode ter uma probabilidade associada
• Não podemos mais falar de valor-minimax de um nó, mas sim
de valor-minimax esperado (expectiminimax value)
 Expectiminimax (n) =
Utility(n),
maxsSucesssors(n) Expectiminimax(s),
minsSucesssors(n) Expectiminimax(s),
sSucesssors(n) P(s).Expectiminimax(s),
CIn/UFPE
se n é terminal
se n é um nó Max
se n é um nó Min
se n é um nó de acaso
Árvore do Jogo Gamão
nós de
acaso
Probabilidades
CIn/UFPE
Conclusões
 Jogos é uma área excitante para se trabalhar
 Ela ilustra várias questões importantes da IA
 A perfeição é impossível => é preciso aproximar
 Uma boa idéia é pensar sobre o que pensar
CIn/UFPE
Fontes
 AIMA: Ler capítulo “Adversarial Search”
 Tutorial “Game Tree Search Algorithms, including AlphaBeta Search”, disponível em
http://www.autonlab.org/tutorials/
CIn/UFPE