Aula3 - Notação

Prévia do material em texto

Inteligência Artificial
Aula 3
Prof. Willian P. Amorim
Notação
• Determinístico
• Um jogador (Monges e Canibais)
• Dois Jogadores (Xadrez, Dama)
• Estocástico
• Jogos com dados (Gamão, Banco Imobiliário)
• Movimentos Aleatórios (Pacman)
Notação
• Observação parcial
• Poker, Truco
• Observação total
• Xadrez, Dama
Notação
• Problemas: Determinístico, Observação total e um jogador
• Solução: Problema de Busca
• Problemas: Determinístico, Observação total e dois jogadores
• Solução: Minimax
Busca Minimax
• Árvore de busca no espaço de estados;
• Jogadas alternadas;
• Cada nó possui um valor minimax: maior valor de utilidade.
Árvore de busca
Algoritmo Minimax
valor(estado)
se estado = estado terminal: retorna estado
se jogador = eu: retorna valorMaximo(estado)
se jogador = oponente: retorna valorMinimo(estado)
Problemas
• b = branching fator (número de nós filhos)
• m = profundidade
• Complexidade de tempo
• O(bm)
• Complexidade de Espaço
• O(bm)
• Jogo do Xadrez
• Média de 35 possibilidades
• Média de 100 movimentos por jogo
• Bm = 2.44 E+154
Voltando a realidade...
• Um computador comum consegue calcular aproximadamente 1M de 
movimentos em 100 segundos
• Profundidade 4: (jogador novato)
• Minimax chegaria próximo a este valor
• Profundidade 8: (jogador mediano)
• Como atingir uma profundidade 8?
Ideia: podar a árvore de busca
Poda α-β na busca em profundidade
• α é o maior valor que 
jogado=eu obtido no 
caminho percorrido até 
então
• Se n é menor que α
jogador=eu irá evita-lo e irá 
desconsiderar todos os 
filhos de n
• Definir β de modo similar 
para jogador=oponente 
Exemplo com a poda
Trabalho Prático
• Criar um agente capaz de jogar o jogo da velha contra um usuário humano.
• A interface gráfica pode ser simples (modo texto), porém deve permitir ao 
usuário perceber qual situação atual do jogo e selecionar sua próxima 
jogada.
• O usuário humano é o “X”, e sempre dá o primeiro lance.
• Implemente o algoritmo básico minimax e decida utilizar uma função 
heurística de sua escolha (explicar).
• A implementação poda alpha e beta terá um acréscimo na avaliação
• Avaliação: Entrevista apresentando/explicando código fonte e 
demonstração do jogo.
• Data: 09/12/2013