docJogos de Tabuleiro e Busca Competitiva
download 
Denúncia Transcrição
Jogos de Tabuleiro e Busca Competitiva
Jogos de Tabuleiro e Busca Competitiva Fabrı́cio Jailson Barth BandTec Março de 2012 Disciplina de Sistemas Inteligentes Sumário • Caracterı́sticas e Exemplos • Histórico • Árvore de busca • Avaliação Estática • Algoritmo Min Max • Poda Alpha Beta • Questões práticas Jogos de Tabuleiro e Busca Competitiva — Sumário BandTec 2 Disciplina de Sistemas Inteligentes Caracterı́sticas e Exemplos • São jogados por duas pessoas (agentes). • Trata-se de uma competição. • Não tem variável aleatória. Jogos de Tabuleiro e Busca Competitiva — Caracterı́sticas e Exemplos BandTec 3 Disciplina de Sistemas Inteligentes Histórico • Shannon. Programming a Computer for Playing Chess. 1950 : O uso do algoritmo Min Max no jogo de Xadrez. • ··· • Deep Blue Wins. 1996 e 1997. Jogos de Tabuleiro e Busca Competitiva — Histórico BandTec 4 Disciplina de Sistemas Inteligentes Árvore de Busca para Jogos • Estado inicial: tabuleiro na posição inicial e jogador. • Operadores: movimentos permitidos. • Estados Objetivo: posições vencedoras para o meu jogador no tabuleiro. • Função de Utilidade: determina um valor para cada estado. • Árvore de Busca: mostra todas as possibilidade de jogo. Jogos de Tabuleiro e Busca Competitiva — Árvore de Busca para Jogos BandTec 5 Disciplina de Sistemas Inteligentes • Não estamos procurando por um caminho. Apenas pelo próximo movimento (espera-se que este movimento me leve à vitória). • Meus melhores movimentos dependem dos movimentos do meu adversário. Jogos de Tabuleiro e Busca Competitiva — Árvore de Busca para Jogos BandTec 6 Disciplina de Sistemas Inteligentes Árvore de Busca b = Fator de ramificação Meus movimentos d = Profundidade Resultado Movimentos do oponente Xadrez b = 36 d > 40 grande! Jogos de Tabuleiro e Busca Competitiva — Árvore de Busca BandTec 7 Disciplina de Sistemas Inteligentes Árvore de Busca Parcial para o Jogo da Velha Jogos de Tabuleiro e Busca Competitiva — Árvore de Busca Parcial para o Jogo da Velha BandTec 8 Disciplina de Sistemas Inteligentes Função de Utilidade Qual a melhor opção? Pontuação (Probabilidade de vencer a partir deste estado) Jogos de Tabuleiro e Busca Competitiva — Função de Utilidade BandTec 9 Disciplina de Sistemas Inteligentes Definição da função de utilidade para o xadrez material = numeroP eao × 1 + · · · + numeroDama × 9 (1) v1 = c1 × material (2) v2 = c2 × mobilidade (3) v3 = c3 × segurancaRei (4) v4 = c4 × controleCentro (5) v5 = · · · (6) n X U tilidade = vi (7) i=0 Jogos de Tabuleiro e Busca Competitiva — Definição da função de utilidade para o xadrez BandTec 10 Disciplina de Sistemas Inteligentes • Muito fraco para predizer o sucesso final do jogo! Jogos de Tabuleiro e Busca Competitiva — Definição da função de utilidade para o xadrez BandTec 11 Disciplina de Sistemas Inteligentes Olhar adiante + função de utilidade (MinMax) 7 max 1 3 min 7 eval 3 5 Jogos de Tabuleiro e Busca Competitiva — 2 1 7 Olhar adiante + função de utilidade (MinMax) P r o f u n d i d a d e 8 BandTec 12 Disciplina de Sistemas Inteligentes Min-Max chamada inicial MAX-VALUE(estado,max-p) function MAX-VALUE(Estado estado, int p) if p==0 then return EVAL(estado) end if v = −∞ for s ∈ SUCESSORES(estado) do v = MAX(v,MIN-VALUE(s,p − 1)) end for return v Jogos de Tabuleiro e Busca Competitiva — Min-Max BandTec 13 Disciplina de Sistemas Inteligentes function MIN-VALUE(Estado estado, int p) if p==0 then return EVAL(estado) end if v=∞ for s ∈ SUCESSORES(estado) do v = MIN(v,MAX-VALUE(s,p − 1)) end for return v Jogos de Tabuleiro e Busca Competitiva — Min-Max BandTec 14 Disciplina de Sistemas Inteligentes Desempenho x Profundidade Jogos de Tabuleiro e Busca Competitiva — Desempenho x Profundidade BandTec 15 Disciplina de Sistemas Inteligentes Deep Blue ' Força Bruta • 256 processadores dedicados. • Examina em torno de 30 bilhões de movimentos por minuto. • A profundidade geralmente é 13. No entanto, em determinadas situações, pode chegar até 30. Jogos de Tabuleiro e Busca Competitiva — Deep Blue ' Força Bruta BandTec 16 Disciplina de Sistemas Inteligentes Min-Max α − β chamada MAX-VALUE(estado,−∞,∞,max-p) function MAX-VALUE(Estado estado, α, β, int p) if p==0 then return EVAL(estado) end if for s ∈ SUCESSORES(estado) do α = MAX(α,MIN-VALUE(s,α,β,p − 1)) if α ≥ β then return α //cutoff end if end for return α Jogos de Tabuleiro e Busca Competitiva — Min-Max α − β BandTec 17 Disciplina de Sistemas Inteligentes function MIN-VALUE(Estado estado,α,β,int p) if p==0 then return EVAL(estado) end if for s ∈ SUCESSORES(estado) do β = MIN(β,MAX-VALUE(s,α,β,p − 1)) if β ≤ α then return β //cutoff end if end for return β Jogos de Tabuleiro e Busca Competitiva — Min-Max α − β BandTec 18 Disciplina de Sistemas Inteligentes Exemplo α − β − 1000, 1000 MAX MIN 2 Jogos de Tabuleiro e Busca Competitiva — 7 Exemplo α − β 1 BandTec 19 Disciplina de Sistemas Inteligentes Material de consulta • Capı́tulo 6 do livro do Russell & Norvig. • http://en.wikipedia.org/wiki/Minimax. • MIT Open Course. 6.034 Artificial Intelligence. • Game Theory - Stanford. www.game-theory-class.org Jogos de Tabuleiro e Busca Competitiva — Material de consulta BandTec 20
