Jogos e Busca. Silvio Lago - PDF
Download "Jogos e Busca. Silvio Lago"
Lara Azambuja Canário
1 1 Jogos e Busca Silvio Lago
2 2 Sumário Jogos adversariais Algoritmo MINIMAX Algoritmo de poda α-β Função de avaliação e corte Jogos de sorte
3 3 Jogos Ambientes competitivos, em que as metas dos agentes estão em conflito, dão origem a problemas de busca competitiva. Em IA, geralmente, jogos são problemas de busca competitiva em ambientes determinísticos e completamente observáveis, em que: existem dois agentes cujas ações se alternam; os valores de utilidade final são sempre simétricos.
4 4 Jogos Primeiros pesquisadores de jogos (1950): Conrad Zuse, Claude Shannon e Alan Turing Jogos são considerados: um desafio à inteligência humana: são problemas muito difíceis de se resolver. um assunto atraente para estudo em IA: é fácil representar o estado corrente de um jogo; há um pequeno número de ações cujos resultados são definidos por regras precisas; apresentam enormes espaços de busca.
5 5 Exemplo: xadrez requer inteligência (raciocínio correto) fácil representar a configuração do tabuleiro pequeno número de regras de movimentação problema de busca complexo: fator de ramificação médio 35 número de movimentos por jogador 50 profundidade da solução 100 árvore de busca
6 6 Jogos Adversariais Características de um jogo adversarial: jogadores adversários que se revezam (MAX e MIN) MAX faz o primeiro movimento (planejamos para ele) vencedor (perdedor) recebe pontos (penalidades) no final, a soma de pontos e penalidades é nula Jogo adversarial é um problema de busca com: estado inicial função sucessor teste de término função utilidade
7 Exemplo: árvore para jogo-da-velha 7
8 8 Estratégia ótima MAX deve: maximizar sua chance de vitória considerar que MIN minimizará sua chance vitória Questão: Como usar a árvore de jogo para encontrar uma estratégia ótima que, independentemente das escolhas feitas pelo adversário, garanta que MAX fará sempre o melhor possível?
9 9 VALOR-MINIMAX Suposição: jogadores jogam otimamente!!! Uma estratégia ótima pode ser determinada usando-se o valor-minimax de cada nó: VALOR-MINIMAX(n) = UTILIDADE(n) se n é um nó terminal max s sucessores(n) VALOR-MINIMAX(s) se n é um nó max min s sucessores(n) VALOR-MINIMAX(s) se n é um nó min
10 10 Escolha da melhor ação num estado s gerar a árvore de busca completa, a partir de s aplicar a função utilidade a cada estado terminal propagar os valores de utilidade, a partir das folhas, até a raiz s (MIN escolhe mínimo e MAX escolhe máximo) escolher a ação que produz o valor utilidade associado ao estado s.
11 Exemplo: um jogo de duas jogadas 11
12 Exemplo: um jogo de duas jogadas 12
13 Exemplo: um jogo de duas jogadas 13
14 Exemplo: um jogo de duas jogadas 14
15 Exemplo: um jogo de duas jogadas 15
16 16 Exemplo: um jogo de duas jogadas melhor escolha Melhor escolha: maximiza o resultado para MAX no pior caso!!!
17 Algoritmo MINIMAX 17
18 18 Propriedades do MINIMAX completo? sim, se a árvore for finita ótimo? sim, se o adversário for ótimo tempo? O(b m ) espaço? O(b m) ou O(m) Para jogos de xadrez, com b 35 e m 100, é praticamente impossível encontrar uma solução exata!!!
19 19 Jogos com vários jogadores muitos jogos permitem mais de dois jogadores valor utilidade vetor de valores utilidades alianças maximiza (minimiza) subvetor
20 20 Exemplo: minimax com 3 jogadores A (1,2,6) B (1,2,6) B (1,5,2) C C C C (1,2,6) (6,1,2) (1,5,2) (5,4,5) A A A A A A A A (1,2,6) (4,2,3) (6,1,2) (7,4,1) (5,1,1) (1,5,2) (7,7,1) (5,4,5)
21 21 Poda α-β na maioria dos casos, não é possível explorar toda a árvore de busca a poda α-β consiste numa estratégia segura para eliminar ramos da árvore de busca, sem ter que examiná-los
22 22 Poda α-β poda α-β devolve a mesma ação que MINIMAX, mas poda ramificações que não influenciam na escolha dessa ação poda α-β pode reduzir a complexidade da busca, dependendo da ordem em que os nós são examinados (no xadrez, pode reduzir b de 35 para 6 [capturar<ameaçar<avançar<retroceder])
23 23 Exemplo de podaα-β [,+ ]
24 24 Exemplo de podaα-β [,+ ] [,+ ]
25 25 Exemplo de podaα-β [,+ ] [,3] 3
26 26 Exemplo de podaα-β [,+ ] [,3] 3 12
27 27 Exemplo de podaα-β [,+ ] [3,3]
28 28 Exemplo de podaα-β [3,+ ] [3,3]
29 29 Exemplo de podaα-β [3,+ ] [3,3] [,+ ]
30 30 Exemplo de podaα-β [3,+ ] [3,3] [,2]
31 31 Exemplo de podaα-β [3,+ ] [3,3] [,2] [,+ ]
32 32 Exemplo de podaα-β [3,+ ] [3,3] [,2] [,14]
33 33 Exemplo de podaα-β [3,+ ] [3,3] [,2] [,5]
34 34 Exemplo de podaα-β [3,3] [3,3] [,2] [2,2]
35 35 Poda α-β como simplificação 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
36 Algoritmo de poda α-β 36
37 Algoritmo de poda α-β 37
38 38 Problemas com MINIMAX e podaα-β MINIMAX gera o espaço de busca do jogo inteiro podaα-β permite eliminar parte desse espaço, mas ainda precisa fazer a busca até os estados terminais em pelo menos um dos ramos em geral, essa profundidade é proibitiva (há limite de tempo para cada jogada) Shannon propôs tratar nós não-terminais como se fossem folhas: função de utilidade função de avaliação (heurística) teste de terminal teste de corte
39 39 Função de avaliação fornece uma estimativa da utilidade de um estado s (semelhante a uma função heurística) o desempenho do programa depende da qualidade da função de avaliação uma função avaliação mal projetada poderá guiar o agente em direção à derrota
40 40 Função linear ponderada combina características do estado que podem ser julgadas de maneira independente: AVALIAÇÃO(s) = w 1 f 1 (s) + w 2 f 2 (s) w n f n (s) Exemplo: valor material de cada peça no xadrez: peão = 1 cavalo e bispo = 3 torre = 5 rainha = 9 AVALIAÇÃO(s) = p(s) + 3c(s) + 3b(s) + 5t(s) + 9r(s)
41 41 Uma boa função de avaliação deve: ordenar os estados terminais da mesma forma que a função de utilidade ser de fácil computação (precisão vs. custo) refletir precisamente a chance de vitória que o estado oferece (a avaliação não é exata!)
42 42 Busca com corte usa função de avaliação quando for apropriado cortar a busca num determinado estado: se TESTE-TERMINAL(s) então devolva UTILIDADE(s) deve ser substituído por: se TESTE-CORTE(s) então devolva AVALIAÇÃO(s) usa profundidade limitada ou profundidade iterativa como critério de corte
43 43 Escolha do ponto de corte dependendo do jogo, um estado favorável pode tornar-se extremamente desfavorável após um único movimento a função de avaliação deve ser aplicada apenas a estados quiescentes (estados em que é improvável que ocorram mudanças num futuro próximo) busca de quiescência (restringe-se às ações que afetam diretamente a função de avaliação)
44 44 Jogos de sorte com a ocorrência de eventos imprevisíveis (= lançamento de dados), não há como construir uma árvore de busca padrão a árvore de busca deve incluir nós de acaso, além dos nós MAX e MIN ramificações nos nós de acaso denotam lançamentos possíveis e respectivas probabilidades
45 45 Exemplo: jogo de gamão o lançamento de dois dados antes de cada jogada determina os movimentos possíveis para cada jogador existem 36 combinações dos dois dados, todas igualmente prováveis apenas 21 combinações distintas (6 5=5 6, ) probabilidade para os 6 duplos (1 1,,6 6) = 1/36 probabilidade para os outros 15 = 1/18 podemos apenas calcular um valor esperado!
46 46 Árvore de busca com nós de acaso MAX dados MIN dados MAX 1/36 d i = 1, 1 A 1 A 2 A N /36 1, b 1/18 1, 2... c... 6, 5 6, 6 1/18 1/18 1, 2 6, 6 6, A N A 1 A 2 A N nós de chance (expectimin) (expectimax) TERMINAL
47 47 EXPECTMINIMAX VALOR-EXPECTMINIMAX(r) = UTILIDADE(r) se r é um nó terminal max s sucessores(r) VALOR-EXPECTMINIMAX(s) se r é um nó max min s sucessores(r) VALOR-EXPECTMINIMAX(s) se r é um nó min Σ s sucessores(r) p(s).valor-expectminimax(s) se r é um nó de acaso Complexidade de tempo: O(b m n m ) b é o fator de ramificação m é a profundidade n é o número de lançamentos distintos
PRINCÍPIOS MÉTODOS EM QUÍMICA MEDICINAL MÉTODOS EM QUÍMICA MEDICINAL.
MÉTODOS EM QUÍMICA MEDICIAL aandrico@ifsc.usp.br MÉTODOS EM QUÍMICA MEDICIAL PRICÍPIOS Isosterismo e bioisosterismo: Estratégia utilizada na modificação estrutural de moléculas com atividade biológica:
OFICINA 10 GEOMETRIA E ARTE: O LOGO DO CAEM 30 ANOS
OFICINA 10 GEOMETRIA E ARTE: O LOGO DO CAEM 30 ANOS Aline dos Reis Matheus, CAEM IME-USP, alinerm@ime.usp.br Marcos Alves dos Santos, CAEM IME-USP, malvess@ime.usp.br Resumo O logotipo CAEM 30 anos foi
Nome : Assinatura : Data : 01/12/2015
Escola Politécnica da Universidade de São Paulo Programa de Pós-Graduação em Engenharia Elétrica Prova de Conhecimento da Área de Engenharia Biomédica 1o. Período de 2016 Nome : Assinatura : Data : 01/12/2015
FORMAS DE PENSAMENTO MATEMÁTICO EVIDENCIADAS EM CONCEITOS BÁSICOS DE TRIGONOMETRIA
Sociedade na Contemporaneidade: desafios e possibilidades FORMAS DE PENSAMENTO MATEMÁTICO EVIDENCIADAS EM CONCEITOS BÁSICOS DE TRIGONOMETRIA Daniele Cristina Gonçalves Universidade do Estado de Minas Gerais
Escola Secundária de Lagoa. Ficha de Trabalho 15. Chamadas de Atenção. Fórmulas Matemáticas. Exercícios
Escola Secundária de Lagoa Física e Química A 11º Ano Turma A Paula Melo Silva Chamadas de Atenção Ficha de Trabalho 15 Forças e trabalho Não se esqueçam do teorema do trabalho-energia W(F resultante )
THE BALANCED SCORECARD Um esquema integrado ( airplane cockpit ) Vantagens da utilização desta metodologia Exemplo ECI: Electronic Circuits Incorporated Evolução do conceito Mapa estratégico na construção