Inteligência Artificial

Conferência 11

Busca com adversário

Objetivo

● Caracterizar os métodos de busca com adversários.

Bibliografía

● Patrick Henry Winston, Inteligencia Artificial, 3ra edición, 1992.

● AI. A Modern Approach Russell Norvig 3rd ed. 2010. Capítulo 5.

● Elaine Rich & Kevin Knight, Inteligencia Artificial, 2da edición,1994. Capítulo 12.

● Rafael Bello, Métodos de solución de problemas,1998. Tema 10 y 11.

Ponto de partida

Introdução

Posição inicial do jogo

Árvore de jogo

Nodos terminais

Caminho da raiz a uma folha representa uma partida

Introdução

Xadrez

Dama

Otello

Tic Tac Toe

Tic Tac Toe

Tic Tac Toe

Tic Tac Toe

Que movimento conduz a estado ganhador apesar do

que adversário faz?

Busca com adversário

Jogos:● 2 jogadores alternam movimentos (two-player, turn-taking)● Informação completa (perfect information)● De soma zero (zero-sum games)

Geralmente jogos de tabuleiro.

Não jogos de azar nem jogos de guerra.

Os jogos como problemas de Busca

Deep Blue, utiliza um acerto em paralelo de

1,024 chips VSLI especialmente

desenhados para esta aplicação, o qual lhe

permite explorar o equivalente de 10,000

posições por segundo e alcançar

profundidades de 14.

Introdução

● Fator de ramificação médio de 35● Em um jogo médio cada jogador realiza 50 movimentos

Para examinar a árvore do jogo completo é necessário examinar 35100 posições.

Será possível desenvolver o espaço de estado para estes tipos de problemas?

Busca com adversário

● Objetivo:

Decidir melhor jogada em cada momento.

● Função de avaliação estática:

Avalia utilidade de cada nova posição.

Decisões ótimas em jogos

● Initial state

● Successor function

● A terminal test (terminal states)

● A utility function

MAXMIN

Players?

Função de avaliação estática

Uma função de avaliação calcula um estimado da utilidade de uma posição do ponto de vista de um dos jogadores.

● O resultado do jogo depende extremamente da qualidade da função de avaliação.

● A função de avaliação deve estar de acordo com a função de utilidade sobre os estados terminais, e deve ser calculável com um esforço razoável.

● Deve haver um compromisso entre a precisão da função de avaliação e seu custo em tempo.

● Deve refletir com precisão a oportunidade real de ganhar

Função de avaliação estática

Uma forma de construir a função de avaliação é usando a expressão:

onde wi são os pesos e os f

i são os rasgos de uma posição

particular.

f (S)=∑i=1

n

wi∗f i

Tic Tac Toe

Tic Tac ToeFee=(f1+c1+d1) - (f2+c2+d2)

Tic Tac ToeFee=(f1+c1+d1) - (f2+c2+d2)

(1)

(0) (1)

(1)

(-1)

(-1)

(-1)

(-2)

(0)(0)

(0)

(2)

Busca com adversário

Algoritmo Minimax

Procedimento Minimax

Valor minimax

MINIMAX−VALUE (n) =

UTILITY (n)

max s∈Succesors(n)MINIMAX−VALUE (S )

mins∈Succesors(n)MINIMAX−VALUE (S )

if n is a terminal state

if n is a MAX node

if n is a MIN node

Alpha-Beta Pruning

Principio Alfa-Beta:

Se tiver uma idéia que indubitavelmente é má, não se tome o

tempo para constatar que tão má é.

General principle

Consider a node n somewhere in the

tree such that Player has a choice of

moving that node. If Player has

better choice m either at the parent

node of n or at any choice point

further up, then n will never be

reached in actual play.

Parameters α and β

● α = the value of the best choice we have found so far at any

choice point along the path for MAX.

● β = the value of the best choice we have found so far at any

choice point along the path for MAX.

Algorithm

Algorithm

Algorithm

Exemplo

Conclusões