Jogos Busca Competitiva Cap. 6 Russell e Norvig 07/05

Universidade Estadual do Oeste do Paraná
Curso de Bacharelado em Ciência da Computação
Jogos
Busca Competitiva
Cap. 6 Russell e Norvig
07/05/2012
Claudia Brandelero Rizzi
[email protected]
Roteiro
Jogos em IA
Tomada de decisão
Min e Max
Até agora falamos sobre...
Problemas sem interação;
Há total controle sobre as ações e sobre o efeito
das ações;
É possível encontrar a solução ótima.
Agora falaremos sobre...
Cap. 6 Russell & Norvig
Busca competitiva ou jogos “adversariais”
são 2 jogadores de revezando
jogos de soma zero: a vitória de um jogador significa a
derrota do outro.
ambientes determinísticos observáveis.
Situações “simétricas”
Jogos
Os jogos são domínios clássicos em IA porque
abstratos: relativamente fáceis de formalizar e
representar;
podem ter sua complexidade reduzida ou aumentada;
exigem a tomada de decisões (muitas vezes em um
curto intervalo de tempo);
Há interação e pode haver não determinismo.
Jogos e IA
Primeiros pesquisadores de jogos (1950):
Jogos são considerados:
Conrad Zuse, Claude Shannon e Alan Turing
um desafio à inteligência humana.
Desde então, a IA em jogos tem avançado e há
versões (e situações) em que os “jogadores
computadorizados” superam os jogadores
humanos.
Relembrando...
Jogos (toy problems) são temas atraente para
estudo em IA porque:
é 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.
Mas em jogos reais, geralmente essas
“facilidades” não se verificam... Eles são difíceis
de resolver!
Jogos – exemplo Xadrez
Jogo de Xadrez há 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 aproximadamente 35100 ou 10154
embora o grafo de busca tenha “apenas” 1040 nós
distintos.
Jogos
Os jogos (como no mundo real!), exigem a
habilidade de tomar alguma decisão,
especialmente quando o cálculo da decisão
ótima é inviável.
Os jogos penalizam a ineficiência de forma
severa.
Jogos : interação
O oponente é “imprevisível”
Como levar em consideração todos os movimentos
possíveis de oponente?
Limite de tempo
Necessidade de tomar uma decisão, em um período X
de tempo, mesmo que não seja ótima!
Jogos : com adversários
Inicialmente jogos com dois jogadores:
Estratégia:
‘MAX’ e ‘MIN’;
MAX deve maximizar seu ganho
MIN deve minimizar os efeitos das jogadas de MAX
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 (nó folha)
Movimentos possíveis de Max
Árvore de jogo (2 jogadores)
Do ponto de vista de Max, melhor valores altos de utilidade
Algoritmo informal
1. Gerar toda a árvore do jogo
2. Aplicar a função utilidade a cada estado
terminal
3. Propagar a utilidade dos nós terminais
para níveis superiores:
quando no nível superior é a vez de MIN fazer um
movimento, escolher o menor valor
quando no nível superior é a vez de MAX fazer
um movimento, escolher o maior valor
4. No nodo raiz, MAX escolhe o movimento
que leva ao maior valor (decisão Minimax)
Minimax
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.
Trabalho prático
Mãos à obra!!
Referências
RICH, ELAINE, KNIGHT, KEVIN, 1993.
Inteligência Artificial. São Paulo: McGrw-Hill
RUSSEL, S.; NORVIG, P.; 1995. Inteligência
Artificial. 3. ed. Rio de Janeiro: Campus, 2003.
RABUSKE, R. Inteligência Artificial.
Florianópolis: Editora da UFSC, 1995.
GUDWIN, R. Representação e solução de
problemas. São Paulo: Unicamp, sd. (lâminas)
Lâminas de UFPE