Inteligência Artificial para Jogos

Busca de Soluções no Espaço de Busca

Jogos DigitaisInteligência Artificial para Jogos

UNISINOS

Prof. MSc. João Ricardo Bittencourt

Update: 13 Ago. 2012joaorb@unisinos.br

Agradeço e dedico estasaulas ao Prof. Osório

“Tome a pílulavermelha”

UNISINOS - João Ricardo Bittencourt

Sumário1. Introdução2. Espaço de Busca3. Algoritmos de Busca Livre4. Algoritmos de Busca Condicionada

UNISINOS - João Ricardo Bittencourt

Introdução Duas categorias básicas de jogos

Quebra-cabeça (brain teasers) Jogos de tabuleiro (board games)

Uso de técnicas clássicas de Inteligência Artificial Abordagem extremamente importante

O jogo é visto como um problema de busca• Busca o quê? Uma solução ótima

(otimização)

UNISINOS - João Ricardo Bittencourt

Introdução Quebra-cabeça (brain teasers)

Torre de Hanoi, Caixeiro Viajante, puzzle de 8 peças, missionário e os canibais, presa/predador, resta 1, problema dos baldes, alocação de espaço, ...

Jogos de tabuleiro (board games) Jogo da velha, damas, connect-4, othello,

backgammon,xadrez, go, ...

UNISINOS - João Ricardo Bittencourt

Espaço de Busca Usar a seguinte notação (baseada em grafos)

Estado atual Próximo estado

Uma ação

UNISINOS - João Ricardo Bittencourt

Espaço de Busca O problema sendo definido da seguinte maneira:

Estados iniciais (1 ou mais) Estados finais (zero ou mais soluções) Operadores (ações) que efetuam a transição

do estado En para E

n+1

Cria-se uma “árvore de busca”

UNISINOS - João Ricardo Bittencourt

Espaço de Busca1 4 72 53 8 6

8 5 72 34 6 1

...8-puzzle

Vários estados iniciais

1 2 34 5 67 8

Uma solução final

1 72 4 53 8 6

1 4 72 5

3 8 6

1 4 72 53 8 6

1 4 72 8 53 6

...

Diferentes movimentosPeça – N S L O

4S 2L 5O 8N

UNISINOS - João Ricardo Bittencourt

Espaço de Busca8-puzzle

Vários estados iniciais

Uma solução final

Diferentes movimentosPeça – N S L O

S1 S2 SnS3...

E

UNISINOS - João Ricardo Bittencourt

Espaço de Busca

S

A

D E

B C

F

G

3

4

4

5

2 4

5

4

3

Cada aresta tem um custo associado

UNISINOS - João Ricardo Bittencourt

Espaço de BuscaS

A D

E

B

C

D

DA E

F

G

E

B

C

F

G

E

F

G

B

C

F

G

B

CA

UNISINOS - João Ricardo Bittencourt

Busca Livre Algoritmos usados em quebra-cabeças O objetivo é encontrar a solução do problema

explorando o espaço de busca Sem intervenção de oponente Busca cega (força bruta)

Busca em profundidade (Depth search) Busca em largura (Breadth search) Busca exaustiva (British Museum Search) Busca não determinística (Nondeterministic

search)

UNISINOS - João Ricardo Bittencourt

Busca Livre Algoritmos usados em quebra-cabeças Busca heurística (trajetórias e labirintos)

Hill Climbing Search Beam Search Best-First Search Optimal Search

• Branch-and-Bound Search• A* Search

UNISINOS - João Ricardo Bittencourt

Busca em profundidadeS

A

E

B

C

D F

G

Menor complexidade computacional (menor custo)

Pode não encontrar uma solução Permite incluir uma profundidade

máxima Implementado com recursividade ou

com uma pilha Deve-se marcar o nodo visitado Critério de parada:

Achou a solução Atingiu a profundidade máxima

UNISINOS - João Ricardo Bittencourt

Busca em larguraS

A D

E

B

C

D

DA E

FE

B

C

F

G

E

FB

F

G

B

CA

UNISINOS - João Ricardo Bittencourt

Busca em largura Alta complexidade computacional Não se sabe se chega em uma

solução em tempo finito Implementado com recursividade ou

com uma fila Critério de parada:

Achou a solução

UNISINOS - João Ricardo Bittencourt

Busca exaustiva Combina buscas em largura e profundidade Acha todas as soluções possíveis para o

problema Seleciona a melhor solução depois de achar

todas as soluções Necessita definir um critério – o que é uma

melhor solução?

UNISINOS - João Ricardo Bittencourt

Busca condicionada Algoritmos usados em jogos – possui um

adversário O objetivo é encontrar a melhor ação (maximize a

vitória) em um determinado instante de tempo t Tem a presença de um oponente Principais algoritmos

Minimax Minimax +Alpha-beta

UNISINOS - João Ricardo Bittencourt

Busca Minimax São dois jogadores o MAX e o MINI Sempre que o MAX joga este tenta maximizar

uma função (aumentar as chances de vitória) Sempre que o MINI joga este tenta minimizar

uma função (minimizar as chances do adversário)

Quem começa é o MAX A mesma árvore é usada para os dois

adversários

UNISINOS - João Ricardo Bittencourt

Busca Minimax Jogos dos Palitos

Pegar 1 ou 2 palitos e não pode ser o último a jogar

5 Jog1.

3 4

1 2

0 1

3

1

2

0 1 2

0 1

Jog1.

Jog1.

Jog2.

Jog2.

UNISINOS - João Ricardo Bittencourt

Busca Minimax Jogos dos Palitos

Pegar 1 ou 2 palitos e não pode ser o último a jogar

5 Jog1.

3 4

1 2

0 1

3

1

2

0 1 2

0 1

Jog1.

Jog1.

Jog2.

Jog2.

Pontuar os nodos terminaisEm geral: +1 (vitória), 0, -1 (derrota)

-1

-1

+1 -1 +1 +1

+1 -1

UNISINOS - João Ricardo Bittencourt

Busca Minimax Jogos dos Palitos

Pegar 1 ou 2 palitos e não pode ser o último a jogar

5 Jog1. MAX

3 4

1 2

0 1

3

1

2

0 1 2

0 1

Jog1.MAX

Jog1.MAX

Jog2. MINI

Jog2. MINI

Classificar os nodos como Min (tem um traço) e Max (sem traço)

-1

-1

+1 -1 +1 +1

+1 -1

UNISINOS - João Ricardo Bittencourt

Busca Minimax Jogos dos Palitos

Pegar 1 ou 2 palitos e não pode ser o último a jogar

5 Jog1. MAX

3 4

1 2

0 1

3

1

2

0 1 2

0 1

Jog1.MAX

Jog1.MAX

Jog2. MINI

Jog2. MINI

Propagar Mini e MaxMini (menor dos dois filhos)Max (maior dos dois filhos)

-1

-1

+1 -1 +1 +1

+1 -1

-1

+1+1+1

+1-1

+1

UNISINOS - João Ricardo Bittencourt

Busca Minimax Alpha-Beta Maximizar a busca eliminando sub-árvores

A

A

D E F G

G

CB

20 10

10

Faz uma busca pré-fixadaNo momento A é 10 (maior valor)

10?

UNISINOS - João Ricardo Bittencourt

Busca Minimax Alpha-Beta Maximizar a busca eliminando sub-árvores

A

A

D

D

E

E

F

F

G

G

C

C

B

B

20 10

10

Se G for >= 5, C = 5 (sobe o menor)Se G <5, C=<5 (que não vence 10)Logo não precisa procurar em G

10?

5

5?