IA_Aula06

Prévia do material em texto

*
PUCC
Inteligência Artificial
*
PUCC
Agenda - Aula 06
 Buscas com Adversários
*
PUCC
Ambiente
Uma diferença dos ambientes que vimos até agora para o ambiente com adversários, é que existe uma população de agentes ativos.
Sem conhecer como o outro agente pode agir, podemos fazer pouco.Entretanto, quando o conhecimento permite, um agente pode construir planos que explicitamente consideram planos de outro agente.
Vamos considerar o caso de 2 agentes.
*
PUCC
2 agentes
Idealmente: os agentes devem ser capazes de levar em consideração ações um do outro. Portanto, as ações devem ser intercaladas. Primeiro um agente age, depois o outro...
Considere o exemplo de dois robôs, uma preto e um branco que podem se mover num grid em células adjacentes. O objetivo do preto é chegar na mesma célula do branco.
Como ficaria a árvore de decisão do preto?
*
PUCC
Minimax
Agora os dois jogadores serão chamados de Max e Min. Nossa tarefa é encontrar o melhor movimento para Max, que faz o primeiro movimento.
Portanto, nós na profundidade de ordem par representam movimento de Max (nós de Max) e nós na profundidade ímpar representam movimento de Min (nós de Min).
Uma jogada de nível k corresponde aos nós de profundidade 2k e 2k+1.
*
PUCC
Minimax
A extensão da busca em árvores que representam jogos, é dada em termos de nível de jogadas.
A busca completa é inviável na maioria dos jogos. Xadrez 1040 nós. 
Busca heurística não reduz de maneira significativa o fator de ramificação da árvore.
Podem ser utilizadas as buscas tradicionais, porém os critérios de parada devem ser modificados (não se encontra alvo)
*
PUCC
Minimax
Vários critérios de parada podem ser utilizados: limite de tempo, de memória, profundidade do nó mais profundo...
Depois que a busca termina, devemos extrair da árvore de busca uma estimativa do melhor movimento.
Pode-se, por exemplo, aplicar uma função estática de avaliação às folhas dessa árvore, a qual tentará medir “o quanto vale a pena” a posição representada por esse nó.
*
PUCC
Minimax
É costume em funções de avaliações de jogos que valores positivos representem posições favoráveis à Max e valores negativos posições favoráveis à Min.
Uma forma de encontrar um bom movimento é o procedimento minimax.
Como seria esse procedimento para o jogo da velha?
*
PUCC
Jogo da Velha
Função de avaliação
e(p)= (número de linhas, ou colunas ou diagonais que ainda estão abertas para MAX) - (número de linhas, ou colunas ou diagonais que ainda estão abertas para MIN).
			 
 e(p)= 6 - 4
x
x
x
x
x
Simetria