IF67B C71 aula11

Prévia do material em texto

IF71B-C71 - Inteligeˆncia Artificial
Aula 11 - Busca Competitiva
Profa. Dra. Priscila T iemi çaeda Saito
k psaito@utfpr.edu.br
2o Semestre 2016
15/09/16
Roteiro
1 Busca Competitiva
Minimax
Poda Alfa-Beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 2 / 59
Busca Competitiva
Desenhe a a´rvore de busca com todos os estados poss´ıveis a partir do
estado “atual” do jogo da velha
Considere que a pro´xima jogada e´ do jogador 1 (x)
o x
x o x
o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 3 / 59
Busca Competitiva
Desenhe a a´rvore de busca com todos os estados poss´ıveis a partir do
estado “atual” do jogo da velha
Considere que a pro´xima jogada e´ do jogador 1 (x)
o x
x o x
o
Qual seria a “melhor” jogada para o jogador 1(x)?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 4 / 59
Busca Competitiva
o x
x o x
o
o x x
x o x
o
o x
x o x
x o
o x
x o x
o x
o x x
x o x
o o
o x x
x o x
o o
o x o
x o x
x o
o x
x o x
x o o
o x
x o x
o o x
o x o
x o x
o x
o x x
x o x
o o x
o x o
x o x
x o x
o x x
x o x
o o x
o x o
x o x
x o x
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 5 / 59
Busca Competitiva
o x
x
o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 6 / 59
Busca Competitiva
o x
x x
o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 7 / 59
Busca Competitiva
o x
o x
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 8 / 59
Busca Competitiva
o x
x
o x
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 9 / 59
Busca Competitiva
o
x
o x
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 10 / 59
Busca Competitiva
o ?
x ?
? o x
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 11 / 59
Busca Competitiva
Jogos x Busca Cla´ssica
Problemas de busca: na˜o assumem a presenc¸a de um oponente
Jogos: oponente e´ imprevis´ıvel → INCERTEZA!
I na˜o se conhece as jogadas exatas do oponente, na˜o por causa de falta
de informac¸a˜o
I dificuldade de levar em considerac¸a˜o todos os movimentos poss´ıveis do
oponente
Espac¸o de busca muito grande
I Ex.: xadrez, em me´dia fator de ramificac¸a˜o = 35
I Em me´dia, 50 jogadas para cada jogador (profundidade 100), ≈ 10154
no´s
Limites de tempo para cada jogada
I tomar decisa˜o, mesmo que na˜o seja o´tima
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 12 / 59
Busca Competitiva
Deciso˜es em Jogos
Jogos com dois jogadores
I MIN e MAX (MAX inicia o movimento e eles se revezam)
Jogos
I metas em conflito
I jogos de revezamento de dois jogadores
F soma 0
F ex.: jogador que ganha xadrez → +1
F outro jogador necessariamento perde → -1
I gera situac¸a˜o de competic¸a˜o → Busca Competitiva
Objetivo
Planejar com antecedeˆncia os movimentos dos adversa´rios
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 13 / 59
Busca Competitiva
Um jogo pode ser definido como um tipo de problema de busca com
os seguintes componentes
I estado inicial: configurac¸a˜o inicial (posic¸a˜o no tabuleiro do jogo) e
indicac¸a˜o de quem e´ a vez
I ac¸o˜es: movimentos (jogadas legais) e estado resultante
I teste de te´rmino: determina quando o jogo termina (estados
terminais)
I func¸a˜o utilidade: objetivo ou compensac¸a˜o, fornece valor nume´rico do
jogo aos estados terminais
F +1 (vito´ria), 0 (empate), -1 (derrota)
F jogos de soma zero (compensac¸a˜o total e´ a mesma para cada instaˆncia
do jogo)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 14 / 59
Busca Competitiva
A´rvore de busca de jogo
I 2 jogadores, determin´ıstico, turnos
I mostra todas as possibilidades do jogo
MAX = x (jogador), MIN = o (adversa´rio)
Utilidade do ponto de vista de MAX
Valores altos bons para MAX e ruins para MIN
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 15 / 59
Busca Competitiva
Estrate´gias de Busca
A soluc¸a˜o o´tima para MAX depende dos movimentos de MIN, logo:
I MAX deve encontrar uma estrate´gia que especifique o movimento de
MAX no estado inicial, e depois o movimento de MAX nos estados
resultantes de cada movimento de MIN e assim por diante...
I Procura-se pelo pro´ximo movimento
I Espera-se que leve a` vito´ria
I Melhores movimentos dependem dos movimentos do adversa´rio
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 16 / 59
Busca Competitiva
Jogos
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 17 / 59
Busca Competitiva
Jogos
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 18 / 59
Busca Competitiva
Algoritmo Minimax
Jogos
I deve-se levar em conta o cara´ter competitivo
F que MAX fara´ e´ determinado tambe´m por MIN
I supor o jogo:
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 19 / 59
Busca Competitiva
Algoritmo Minimax
MAX prefere mover para estado de minimax ma´ximo
MIN prefere valor m´ınimo
I dada uma a´rvore de jogo, a estrate´gia o´tima pode ser determinada a
partir do valor minimax de cada no´
Ideia
Maximizar a utilidade (ganho) supondo que o adversa´rio vai tentar
minimiza´-la
Minimax faz busca cega em profundidade
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 20 / 59
Busca Competitiva
Valor minimax de um no´ e´ a utilidade de MAX no estado
correspondente
Supondo que ambos jogadores teˆm desempenho o´timo do estado
atual ate´ estado terminal (fim do jogo)
valor minimax(n) =
utilidade(n) se n e´ estado terminal
maxs∈sucessor(n) valor minimax(n) se n e´ um no´ MAX
mins∈sucessor(n) valor minimax(n) se n e´ um no´ MIN
O valor minimax (para MAX) e´ a utilidade de MAX para cada estado,
assumindo que MIN escolhe os estados mais vantajosos para ele mesmo
(i.e. os estados com menor valor utilidade para MAX)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 21 / 59
Busca Competitiva
A ac¸a˜o A1 e´ a escolha o´tima para MAX, porque leva ao sucessor com
mais alto valor minimax
E´ a melhor jogada para um jogo determin´ıstico assumindo o melhor
oponente
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 22 / 59
Busca Competitiva
Algoritmo Minimax
Passos:
1 gera a a´rvore inteira ate´ os estados terminais
2 aplica a func¸a˜o de utilidade nas folhas
3 propaga os valores dessa func¸a˜o subindo a a´rvore atrave´s do minimax
4 determinar qual valor que sera´ escolhido por MAX
Jogada perfeita para jogos determin´ısticos
Ideia: escolher movimento para posic¸a˜o com ma´ximo valor minimax
I melhor alcanc¸a´vel contra melhor jogador
Explorac¸a˜o completa em profundidade da a´rvore do jogo
I calcula recursivamente valores de utilidade
I toma decisa˜o com base nesses valores
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 23 / 59
Busca Competitiva
Algoritmo Minimax
1 expandir a a´rvore inteira abaixo da raiz
2 avaliar os no´s terminais como ganhos/perdas para o MAX - utilidade
3 selecionar um no´ sem utilidade, n, que tenha todos os filhos ja´ com valor. Se na˜o ha´ um no´ desses, a busca terminou:
retornar o valor da raiz
4 Se n e´ movimento MIN, atribu´ı-lo um valor que e´ o m´ınimo dos valores de seus filhos. Se n e´ MAX, atribu´ı-lo um valor
que e´ o ma´ximo dos valores dos seus filhos. Retornar ao Passo 3
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial)Aula 11-Busca Competitiva 24 / 59
Busca Competitiva
MINIMAX-DECISION(A)
I V = MAX-VALUE(A)
MAX-VALUE(A)
I A e´ terminal? Na˜o→ v = -inf
I Para s = B, C e D
F v = max(v, MIN-VALUE(s))
MIN-VALUE(B)
I B e´ terminal? Na˜o→ v = +inf
I Para s = E, F e G
F v = MIN(v, MAX-VALUE(s))
F v = MIN(+inf, 3, 12, 8) = 3
MAX-VALUE(E)
I E e´ terminal? Sim
F v = UTILITY(E) = 3
MAX-VALUE(F)
I F e´ terminal? Sim
I v = UTILITY(F) = 12
MAX-VALUE(G)
I G e´ terminal? Sim
I v = UTILITY(G) = 8
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 25 / 59
Busca Competitiva
MINIMAX-DECISION(A)
I V = MAX-VALUE(A)
MAX-VALUE(A)
I A e´ terminal? Na˜o→ v = -inf
I Para s = B, C e D
F v = max(v, MIN-VALUE(s))
MIN-VALUE(C)
I C e´ terminal? Na˜o→ v = +inf
I Para s = H,I e J
F v = MIN(v, MAX-VALUE(s))
F v = MIN(+inf, 2, 4, 6) = 2
MAX-VALUE(H)
I H e´ terminal? Sim
F v = UTILITY(H) = 2
MAX-VALUE(I)
I I e´ terminal? Sim
I v = UTILITY(I) = 4
MAX-VALUE(J)
I J e´ terminal? Sim
I v = UTILITY(J) = 6
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 26 / 59
Busca Competitiva
MINIMAX-DECISION(A)
I V = MAX-VALUE(A)
MAX-VALUE(A)
I A e´ terminal? Na˜o→ v = -inf
I Para s = B, C e D
F v = max(v, MIN-VALUE(s))
MIN-VALUE(D)
I D e´ terminal? Na˜o→ v = +inf
I Para s = K,L e M
F v = MIN(v, MAX-VALUE(s))
F v = MIN(+inf, 14, 5, 2) = 2
MAX-VALUE(K)
I K e´ terminal? Sim
F v = UTILITY(K) = 14
MAX-VALUE(L)
I L e´ terminal? Sim
I v = UTILITY(L) = 5
MAX-VALUE(M)
I M e´ terminal? Sim
I v = UTILITY(M) = 2
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 27 / 59
Busca Competitiva
MINIMAX-DECISION(A)
I V = MAX-VALUE(A) = 3
I Retorna A1
MAX-VALUE(A)
I A e´ terminal? Na˜o→ v = -inf
I Para s = B, C e D
F v = MAX(v, MIN-VALUE(s))
F MAX(-inf, 3, 2, 2) = 3
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 28 / 59
Busca Competitiva
Desempenho Minimax
Completo: Sim
I se a´rvore e´ finita
O´timo: Sim
I contra um oponente o´timo
complexidade de tempo: O(bm)
I m = profundidade ma´xima
I b = movimentos va´lidos em cada estado
complexidade de espac¸o: O(bm)
I com busca em profundidade
I ou O(m) se gerar um sucessor por vez
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 29 / 59
Busca Competitiva
Poda alfa-beta
Minimax e´ impratica´vel para muitos jogos
I nu´mero de estados do jogo a examinar e´ exponencial
I e´ poss´ıvel reduzir expoente
Poda (Pruning)
I deixar de considerar grandes partes da a´rvore de jogos
I podando ramificac¸o˜es que na˜o influenciam a decisa˜o final
calcular a decisa˜o correta sem examinar todos os no´s da a´rvore (evitar
gerar toda a a´rvore, analisando que suba´rvores na˜o influenciam na decisa˜o)
retorna o mesmo que minimax, pore´m sem percorrer todos os estados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 30 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 31 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 32 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 33 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 34 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 35 / 59
Busca Competitiva
Poda alfa-beta
Alfa
I valor da melhor escolha encontrando em qualquer ponto ao longo do
caminho de busca para MAX
I valor mais alto
Beta
I valor da melhor escolha encontrando em qualquer ponto de escolha do
caminho para MIN
I valor mais baixo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 36 / 59
Busca Competitiva
Poda alfa-beta
α e´ o valor da melhor escolha encontrado ate´ enta˜o para qualquer
ponto de escolha de MAX
I se v e´ pior que α, MAX ira´ evita´-lo
I poda o ramo e na˜o percorre este caminho mais
Se α e´ melhor que v para o jogador, nunca chegara´ a` v
MAX = jogador; MIN = adversa´rio
Se ja´ achou algo melhor, por que piorar?
β e´ definido de maneira similar para MIN
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 37 / 59
Busca Competitiva
Poda alfa-beta
Atualiza valores de alfa e beta a` medida que prossegue em
profundidade
I poda ramificac¸o˜es ta˜o logo sabe que o valor de um no´ corrente e´ pior
que o valor corrente de alfa ou beta para MAX ou MIN
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 38 / 59
Busca Competitiva
Poda alfa-beta
Efetividade depende da ordem em que sucessores sa˜o examinados
Se terceiro sucessor tivesse sido gerado primeiro, outros dois poderiam
ter sido podados
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 39 / 59
Busca Competitiva
Poda alfa-beta
α = limite inferior no resultado de MAX; inicialmente −∞
β = limite superior no resultado de MIN; inicialmente +∞
Chama-se busca alfa-beta recursivamente com intervalos cada vez mais estreitos
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 40 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 41 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 42 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 43 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 44 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 45 / 59
Busca Competitiva
Poda alfa-beta
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 46 / 59
Busca Competitiva
Poda alfa-beta
Regra Geral
Se β e´ menor que α, fac¸a a poda dos ramos restantes na suba´rvore em
que esta´
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 47 / 59
Busca Competitiva
Poda alfa-beta
Supondo que utiliza melhor ordem
I alfa-beta examina O(bm/2) no´s para escolher melhor movimento
F contra O(bm) do minimax
F pode efetuar exame antecipado a uma distaˆncia aproximadamente duas
vezes maior no mesmo tempo
Examinando em ordem aleato´ria
I O(b3m/4)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 48 / 59
Busca Competitiva
Propriedades alfa-beta
Poda na˜o afeta resultado final
Boa ordem de movimento melhora efetividade da poda
Com “ordem perfeita”, complexidade de tempo = O(bm/2)
I dobra profundidade da busca
Exemplo simples do valor de raciocinar sobre que computac¸o˜es sa˜o
relevantes
I forma de meta-racioc´ınio
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 49 / 59
Busca Competitiva
Exemplo - Xadrez
I minimax: 5 jogadas a` frente
F humano me´dio: 6 a 8
I alfa-beta: 10 jogadas a` frente
F desempenho de especialista
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 50 / 59
Busca Competitiva
Buscas adversariais
Minimax gera o espac¸o de busca todo
Poda α− β ainda tem que chegar ate´ os estados terminais
Sa˜o ineficientes para jogos que possuam muitos passos para os estados
terminais
i.e., quase todos os jogos interessantes!
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 51 / 59
Busca Competitiva
Deciso˜es imperfeitas em temporeal
Ambos algoritmos precisam realizar a busca (em toda distaˆncia) ate´
os no´s terminais (folhas)
Nem sempre o melhor movimento e´ feito pelo adversa´rio (deciso˜es
imperfeitas
Precisam ser realizados em per´ıodo de tempo razoa´vel
Soluc¸a˜o: substituir a func¸a˜o utilidade por uma func¸a˜o de avaliac¸a˜o
(heur´ıstica), a qual fornece uma estimativa da utilidade esperada da
posic¸a˜o e o teste de te´rmino
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 52 / 59
Busca Competitiva
Func¸o˜es de Avaliac¸a˜o
“O desempenho do algoritmo esta´ diretamente relacionado com a
func¸a˜o de avaliac¸a˜o projetada”
Deve ordenar os estados terminais
I ex.: 1-vito´rias 2-empates 3-derrotas
A computac¸a˜o na˜o deve demorar tempo demais
Deve estar fortemente relacionada com as chances reais de vito´ria
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 53 / 59
Busca Competitiva
Func¸o˜es de Avaliac¸a˜o
Reflete as chances de ganhar: baseada no valor material
I ex.: valor de uma pec¸a independentemente da posic¸a˜o das outras
Func¸a˜o linear de peso de propriedade do no´:
AVAL(s) = w1f1 + w2f2 + ...+ wnfn
Ex.: os pesos (w) no xadrez poderiam ser o tipo de pedra do xadrez
(pea˜o-1, ..., rainha-9) e os (f) poderiam ser o nu´mero de cada pec¸a
no tabuleiro
Escolha crucial: compromisso entre precisa˜o e eficieˆncia
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 54 / 59
Busca Competitiva
Func¸a˜o de avaliac¸a˜o (h) para o jogo da velha
x
o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 55 / 59
Busca Competitiva
Func¸a˜o de avaliac¸a˜o (h) para o jogo da velha
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 56 / 59
Busca Competitiva
Material complementar:
I https://www.youtube.com/watch?v=STjW3eH0Cik
I https://www.youtube.com/watch?v=zDskcx8FStA
I https://www.youtube.com/watch?v=Eychv62adsI
I https://www.youtube.com/watch?v=6kFKnB6JtcY
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 57 / 59
Busca Competitiva
Exerc´ıcio
I Jogo da velha com minimax
I Execute o algoritmo Minimax
I Considere +1 (vito´ria), -1 (derrota) e 0 (empate)
o x
x
x o o
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 58 / 59
Busca Competitiva
Exerc´ıcio
I Execute o algoritmo de poda α-β
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 11-Busca Competitiva 59 / 59
	Busca Competitiva
	Minimax
	Poda Alfa-Beta