busca competitiva IA

Prévia do material em texto

Busca Competitiva
Cap. 6.1, 6.2 e 6.3
Até aqui...
• Problemas sem interação com outro agente.
• O agente possui total controle sobre suas 
ações e sobre o efeito de suas ações.
• Muitas vezes encontrar a solução ótima é 
factível.
2
Em Busca de Soluções
3
Tópico 
 Resolução de Problemas por meio de busca
 Busca Competitiva
Jogos
• Os jogos que envolvem adversários são um pouco 
diferentes dos vistos até agora (Xadrez, Damas, …). 
• O jogador não tem que se preocupar apenas em chegar ao 
objetivo final, mas em evitar que algum oponente chegue 
antes dele, ou seja, vença o jogo. 
• O jogador deve se antecipar à jogada do seu adversário 
para poder fazer a sua.
• O oponente é “imprevisível”
– levar em consideração todos os movimentos 
possíveis de oponente;
• Limite de tempo
– tomar uma decisão, mesmo que não seja ótima.
4
Decisões ótimas em jogos
• Inicialmente jogos com dois jogadores:
– ‘MAX’ e ‘MIN’;
• Um jogo pode ser definido como uma árvore de busca:
– estado inicial
– função sucessor (-> movimento, estado)
– teste de término
– função utilidade: dá um valor numérico para os 
estados terminais
5
Decisões ótimas em jogos
Ideia:
• Iniciar na posição corrente e usar o gerador de 
movimentos para gerar o conjunto de possíveis posições 
sucessoras.
• Aplicar a função de avaliação a estas posições e 
simplesmente escolher a melhor.
Meta:
• Minimizar os efeitos da jogada do adversário e maximizar 
o efeito da própria jogada.
6
Decisões ótimas em jogos
• Minimax (ou minmax) é um método para minimizar a 
perda máxima possível. 
• Pode ser considerado como a maximização do ganho 
mínimo (maximin). 
• Pode-se estender o conceito para jogos mais complexos e 
para tomada de decisão na presença de incertezas. 
7
Decisões ótimas em jogos
• Uma versão simples do algoritmo minimax lida com jogos 
como o jogo da velha, no qual cada jogador pode ganhar, 
perder ou empatar. 
– Se o jogador A pode vencer com um movimento, seu melhor 
movimento é o movimento para a vitória. 
– Se o jogador B identifica que um movimento levará a uma 
situação em que o adversário pode ganhar em um movimento, 
enquanto outro movimento levará a uma situação de empate, 
então a melhor jogada do jogador B é a que leva para o empate. 
– Após algumas rodadas é fácil identificar qual é o melhor 
movimento. 
8
Decisões ótimas em jogos
• O algoritmo minimax ajuda a encontrar a melhor jogada 
ao caminhar pelas opções válidas a partir do fim do jogo. 
• A cada passo assume-se que o jogador A está tentando 
maximizar as chances de A ganhar, enquanto na próxima 
rodada o jogador B está tentando minimizar as chances de 
isso acontecer (ao maximizar as chances de que ele 
próprio ganhe).
9
Árvore de jogo (2 jogadores)
10
Do ponto de vista de max, valores altos de utilidade são bons.
Estratégias ótimas
• Dada uma árvore de jogo, a estratégia ótima pode ser 
determinada a partir do valor minimax de cada nó.
• O valor minimax (para MAX) é a utilidade de MAX para 
cada estado, assumindo que MIN escolhe os estados mais 
vantajosos para ele mesmo (i.e. os estado com menor 
valor utilidade para MAX) 
11
Algoritmo minimax
• O algoritmo calcula a decisão minimax a partir do estado 
corrente
• Utiliza uma computação recursiva simples dos valores 
minimax de cada estado sucessor, implementando 
diretamente as equações da definição.
• A recursão percorre todo o caminho descendente até as 
folhas da árvore, e depois os valores minimax são propagados 
de volta pela árvore, à medida que a recursão retorna.
12
Algoritmo minimax - Exemplo
• Movimentos possíveis para MAX no nó raiz: 
a1, a2 e a3.
• Respostas possíveis para a1 correspondentes a 
MIN: b1, b2, b3.
• E assim sucessivamente...
• Este jogo termina depois de um movimento 
realizado por MAX e por MIN (depois de uma 
“jogada) “.
• Utilidades dos estados terminais: variam de 2 
até 14.
13
Minimax
14
A ação a1 é a escolha ótima para MAX, porque leva ao sucessor
com mais alto valor minimax.
A melhor jogada para um jogo determinístico assumindo o 
melhor oponente.
Propriedades do algoritmo minimax
• Equivale a uma busca completa em profundidade na árvore 
do jogo.
– m: profundidade máxima da árvore
– b: movimentos válidos em cada estado
• Completo? Sim (Se a árvore é finita)
• Ótimo? Sim (contra um oponente ótimo)
• Complexidade de tempo? O(bm)
• Complexidade de espaço? O(bm)
• Para xadrez, b ≈ 35, m ≈100 para jogos “razoáveis”
 solução exata não é possível
15
Poda -
• Busca minimax: no de estados do jogo é exponencial em 
relação ao no de movimentos; 
• Poda - : 
– calcular a decisão correta sem examinar todos os nós da árvore;
– retorna o mesmo que minimax, porém sem percorrer todos os 
estados.
• Essa técnica requer a manutenção de dois valores limites, 
um representando o limite inferior que um nó 
maximizante poderá receber em última instância (alfa), e 
outro representando o limite superior de valor que um nó 
minimizante poderá ter (beta).
16
Poda -
17
Poda -
18
Poda -
19
Poda -
20
Poda -
21
Poda - - Exemplo
• O valor do nó raiz é dado por:
VALOR-MINIMAX (raiz) =
= max(min(3,12,8), min(2,x,y), min(14,5,2)
= max(3, min(2,x,y), 2)
= max(3, z, 2), onde z ≤ 2
= 3
22
Jogos não determinísticos
• Elemento aleatório proveniente de jogo de dados, sorteio 
de cartas, etc.
• Não determinismo é inerente em domínios reais.
• O estudo de algoritmos para jogos com elemento 
aleatório é um passo em direção a métodos aplicados no 
mundo real.
23
Jogos não determinísticos
• Uma árvore de um jogo não determinístico deve incluir 
nós de acaso além de nós minimax.
• Ramificações que levam a cada nó de acaso denotam 
“jogadas de dados possíveis” (a probabilidade de cada 
mudança de estado não determinística).
24
Jogos
• Jogo de Damas: O Chinook, que funciona em PCs comuns e utiliza 
busca alfa-beta, encerrou o reinado de 40 anos como campeão 
mundial de Marion Tinsley em 1994. Usa um banco de dados pré-
calculado de todas as posições (444 bilhões) com oito ou menos 
peças no tabuleiro para tornar seu fim de jogo infalível.
• Xadrez: O Deep Blue derrotou o campeão mundial Garry Kasparov 
em uma competição de seis partidas em 1997. A máquina 
vencedora era um computador paralelo com 30 processadores 
IBM RS/6000 e 480 processadores VLSI que buscava 126 milhões 
de nós/segundo, em média. O coração da máquina é uma busca 
alfa-beta de aprofundamento iterativo padrão com uma tabela de 
transposição que chegou a alcançar profundidade de 40 jogadas.
25