Busca Competitiva

Prévia do material em texto

1
Mestrado em Ciência da 
Computação
UERN/UFERSA
Busca Competitiva
Prof. Marcelino Pereira
 2
Tópicos
 Jogos
 Decisões Ótimas em Jogos
 Poda Alfa-Beta
 Decisões Imperfeitas em Tempo Real
 Jogos que Incluem um Elemento de Acaso
 3
Jogos
 Ambientes multiagente
 Considerar ações de outros agentes
 Modo como estas ações afetam bem-estar
 Competitivos
 Metas dos agentes estão em conflito
 Originam problemas de busca competitiva (jogos)
 Teoria dos jogos
 Economia
 Ambientes multiagentes são visualizados como jogos
 O impacto de cada agente sobre o outro é relevante
 4
Jogos
 IA – jogos (ambiente especializado)
 Determinístico
 Completamente observável
 Dois agentes com ações alternadas
 Valores de utilidade no fim do jogo 
 Sempre iguais e opostos
 Exemplo: xadrez
 Um jogador ganha o jogo (+1)
 O outro jogador necessariamente perde (-1)
 Esta oposição gera a situação de competição
 5
Jogos
 6
Jogos
 Para a IA a natureza abstrata dos jogos é
 Assunto atraente para estudos
 É fácil representar o estado de um jogo
 Em geral, os agentes se restringem a um pequeno 
número de ações
 Os resultados destas ações são definidos por regras 
precisas
 Jogos físicos 
 Descrições muito mais complicadas
 Faixa muito maior de ações possíveis
 Regras muito imprecisas (legalidade das ações)
 Ex.: Futebol de robôs
 7
Jogos
 Xadrez (1950)
 Claude Shannon
 Norbert Wiener
 Alan Turing
 Progresso constante
 Derrotaram campeões humanos–xadrez/gamão
 Competitivos em muitos outros jogos
 Go: computador = nível avançado 
 http://www.scientificamerican.com/article/how-
the-computer-beat-the-go-master/
 8
Jogos
 Jogos e mundo real
 Exigem a habilidade de tomar alguma decisão
 Mesmo quando seu cálculo é inviável
 Penalizam a ineficiência de forma severa
 Ideias interessantes sobre como fazer o melhor 
uso possível do tempo
 Movimento ótimo
 Bom movimento quando o tempo é limitado
 Ignorar movimentos que não fazem diferença – poda
 Funções de avaliação – realização de aproximações
 Elemento de sorte e elemento de informação 
imperfeita
 9
Decisões ótimas em jogos
 Considerar 2 jogadores: MAX e MIN
 Jogo: problema de busca
 Estado inicial
 Posição do tabuleiro e jogador que fará o 1º. movimento
 Função sucessor
 Retorna lista de pares (movimento, estado)
 Indica movimento válido e estado resultante
 Teste de término
 Determina quando o jogo acaba
 Estados terminais: estados em que o jogo é encerrado
 Função de utilidade
 Atribui valor numérico aos estados terminais (Ex:+1, -1, 0)
 10
Decisões ótimas em jogos
Árvore de jogo: estado inicial e movimentos válidos p/ cada lado
 11
Decisões ótimas em jogos
 Estratégias ótimas
 Solução ótima
 Seqüência de movimentos que levasse à vitória
 MIN tem alguma relação com este estado
 MAX deve
 Encontrar uma estratégia de contingência p/ seus 
movimentos no estado inicial
 Idem para os estados resultantes de cada resposta 
possível de MIN
 E assim por diante
 12
Decisões ótimas em jogos
Exemplo de árvore de jogo – profundidade: 1 movimento = 2 jogadas
 13
Decisões ótimas em jogos
Exemplo de árvore de jogo – profundidade: 1 movimento = 2 jogadas
 14
Decisões ótimas em jogos
 Valor minimax de cada nó
 Utilidade (p/ MAX) de se encontrar no estado 
correspondente, supondo-se que ambos os jogadores 
têm um desempenho ótimo deste estado até o fim 
do jogo
 O valor minimax de um estado terminal é 
simplesmente sua utilidade
 Preferências (dada uma escolha)
 MAX preferirá mover-se para um estado de valor máximo
 MIN preferirá mover-se para um estado de valor mínimo
 Suposição: MIN joga de forma ótima
 E se MIN não jogar de forma ótima?
 15
Decisões ótimas em jogos
 Algoritmo para calcular decisões minimax
 16
Decisões ótimas em jogos
 Jogos com mais de 2 jogadores
 Vetor de valores
 Ex: jogadores A, B e C –> vetor (vA, vB, vC)
 A função de utilidade retorna um vetor de utilidades
 O valor propagado de volta de um nó n é o vetor de 
utilidade do sucessor que tem o mais alto valor para 
a escolha do jogador em n
 A questão das alianças
 Colaboração emerge de comportamento egoísta
 Rompimento de alianças (confiabilidade)
 17
Decisões ótimas em jogos
Exemplo de árvore de jogo com três jogadores
 18
Poda alfa-beta
 Problema da busca minimax
 Número de estados de jogo a examinar (exp.)
 Artifício para redução: calcular a decisão minimax 
correta sem examinar todos os nós na árvore de jogo 
(poda)
 Poda alfa-beta
 Retorna o mesmo movimento que minimax retornaria 
 Mas poda as ramificações que não terão influência sobre a 
decisão final
 Pode ser aplicada a árvores de qualquer profundidade
 É possível podar subárvores inteiras
 19
Poda alfa-beta
 Considere um nó n 
em algum lugar na 
árvore
 O jogador tem a 
escolha de 
movimento até esse 
nó
 Se o jogador tiver 
uma escolha melhor 
m no nó pai de n ou 
em qualquer outro 
ponto acima dele, 
então n nunca será 
alcançado
 20
Poda alfa-beta
Exemplo
 21
Poda alfa-beta
 Limites sobre os valores propagados de volta
 Alfa: valor da melhor escolha (valor mais alto) encontrado até o 
momento em qualquer ponto de escolha ao longo do caminho 
para MAX
 Beta: valor da melhor escolha (valor mais baixo) encontrado 
até o momento em qualquer ponto de escolha ao longo do 
caminho para MIN
 Os valores de alfa e beta são atualizados à medida que 
prossegue a busca
 Poda as ramificações restantes em um nó tão logo saiba-se que 
o valor do nó corrente é pior que o valor corrente de alfa (para 
MAX) ou beta (para MIN)
 A efetividade da poda alfa-beta é altamente dependente 
da ordem em que os sucessores são examinados
 22
Decisões Imperfeitas em Tempo Real
 Mesmo com poda, alfa-beta ainda precisa fazer a 
busca em todos os estados terminais, pelo menos 
para uma parte do estado de busca
 Solução: cortar a busca mais cedo e aplicar uma 
função de avaliação heurística aos estados da busca
 Transformar nós não-terminais em folhas terminais
 Substituir a função de utilidade por uma função de 
avaliação de heurística
 Fornece uma estimativa da utilidade da posição
 O teste de término é substituído por um teste de corte
 Julgar o valor de uma posição
 O desempenho de um programa de jogos depende de sua 
função de avaliação
 23
Decisões Imperfeitas em Tempo Real
 Projetando boas funções de avaliação
 A função deve ordenar os estados terminais
 A computação não deve demorar muito tempo
 Para estados não terminais, a função de avaliação deve 
estar fortemente relacionada com as chances reais de 
vitória
 Consideram
 Características do estado. Ex: peões tomados (xadrez)
 Em conjunto
 Características definem diversas categorias ou classes 
de equivalência de estados
 Os estados de cada categoria têm os mesmo valores para 
todas as características
 24
Decisões Imperfeitas em Tempo Real
 Exemplo: a experiência mostra p/ uma categoria que
 72% dos estados da categoria levam a vitória (+1)
 20% levam a uma derrota (-1)
 8% levam a um empate (0)
 Valor esperado 
 (0,72 x +1) + (0,20 x -1) + (0,08 x 0) = 0,52
 Valor esperado pode ser determinado para cada categoria
 Exige muitas categorias e muita experiência
 Alternativa – valor material
 Calcular contribuições numéricas separadas
 Combinar estas contribuições para encontrar valor total
 Ex: peão vale 1, cavalo/bispo 3, torre 5, rainha 9
 25
Decisões Imperfeitas em Tempo Real
 Outras características
 Boa estrutura de peões, segurança do rei A soma dos valores avalia a posição
 Função linear ponderada
 AVAL(s) = w1f1(s) + w2f2(s) + ... + wnfn(s)
 Onde cada wi é um peso e cada fi é uma característica
 Suposição desta função
 A contribuição de cada característica é independente dos valores 
das outras características
 Entretanto, por ex., os bispos são mais fortes no fim do jogo
 Solução: combinações não lineares
 26
Decisões Imperfeitas em Tempo Real
 Modificar busca alfa-beta
 Chamar a função heurística AVAL
 se TESTE-DE-CORTE(estado, profundidade)
então retornar AVAL(estado)
 Definir um limite de profundidade fixo
 A profundidade é escolhida de modo que o período 
de tempo utilizado não exceda o período permitido 
pelas regras do jogo
 27
Jogos que Incluem um 
Elemento de Acaso
 28
Jogos que Incluem um 
Elemento de Acaso
 29
Bibliografia
 Russel e Norvig. Inteligência Artificial. 
 Capítulo 6 (2a Ed.) Capítulo 5 (3a Ed.)
 Exercícios
 Estudar Jogos que Incluem um Elemento de Acaso
 Estudar e implementar o algoritmo da Fig. 5.3 (6.3)
 Case!
 Aplicar o algoritmo da Fig. 5.7 (6.7) à árvore da Fig. 
5.5 (6.5)
==> PROVA dia 09/04
==> SEMINÁRIOS dia 07/05
 30
SEMINÁRIOS
Pontos de avaliação 
 Domínio do tema, clareza, objetividade
 Apresentação oral, qualidade da exposição, 
organização do PPT
 Ferramentas & implementações na área; 
Estado-da-arte (pesquisa na área)
 Tempo (40 min. + - 10%)
 31
(Orientador!)
 Cidades Inteligentes
 Agentes em Jogos
 Meios de Transporte Autônomos
 Armas Inteligentes
 IA e Mercado Financeiro
 Humanóides
 Temas dos capítulos do livro não 
contemplados no cronograma
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31