Técnicas de Inteligência
Artificial para Resolução do
Sokoban
Aluna: Jacqueline Rodrigues
Orientadora: Leliane de Nunes Barros
Introdução
O que é o sokoban ?
➔
➔
Objetivo
Regras
figura 1
Motivação
Este jogo tem despertado a atenção de pesquisadores na área de jogos
em Inteligência Artificial pois apesar da simplicidade das regras do
sokoban, existem tabuleiros de grande complexidade, o que o torna um
jogo muito interessante.
Principal desafio: evitar deadlocks
Deadlock de esquina
Deadlock de parede
Implementações
Representação do problema: "modelo de transição de
estados".
Algoritmo para percorrer esse modelo: IDA*
Como o IDA* funciona?
Heurística de Limite
Inferior
Para melhorar o desempenho da busca, é preciso usar uma função heurística
sofisticada que estime a distância de um determinado estado para um
estado solução, dada em termos de número de movimentos de caixas. Essa
distância é considerada um limite inferior, dado que a distância real
será sempre maior considerando-se também os movimentos do sokoban e os
movimentos que rewsolvem conflitos entre os blocos. Técnicas
envolvidas:
–
–
–
–
–
–
Minmatching
Detecção de deadlocks (becos sem saída)
Melhoria de entrada
Posição do homem
Conflitos lineares
Atualizações dinâmicas
Tabela de Hash
Tabelas de Hash são usadas para evitar que o algoritmo visite estados
que já foram visitados anteriormente e que podem ser alcançados por
•diversos caminhos. Hash tables também eliminam ciclos na busca.
Ordenação de Movimentos
Ao invés de visitar estados sucessores em uma ordem arbitrária, essa
técnica permite visitar os melhores estados sucessores antes dos
demais.
Quando usamos o algoritmo IDA*, ordenar os movimentos nos nós
internos não afeta em nada o desempenho da busca, com exceção da
última iteração (profundidade com o maior número de nós a serem
visitados). Como a ultima iteração é a maior de todas e ela será
abortada quando encontrarmos uma solução, se a solução for encontrada
rapidamente pode levar a grandes ganhos de desempenho.
Tabelas de deadlocks
Um programa que roda antes da busca, IDA*, acha todos os deadlocks de
tamanho 5x4 e armazenam esses padrões em um banco de dados que pode
ser consultado durante a busca. Antes de um movimento ser gerado, sua
configuração é consultada no banco de deadlocks, se for considerada um
deadloack, o movimento não é gerado.
Macro Túnel
Túnel - restringe a mobilidade do agente a apenas uma direção.
Macro Túneis tratam esses corredores como se fossem apenas uma única
localização.
Túnel
Macro Meta
O procedimento Macro Meta é chamado pela busca quando uma pedra entra
na área de armazenamento. Macro Meta posiciona as pedras na posição
correta dentro da área de armazenamento de forma eficiente. Essa
técnica reduz drasticamente o tamanho da árvore de busca.
Podas de Metas
Quando usamos a técnica de Macro Meta para posicionar as pedras em sua
posição correta dentro da área de armazenamento, o programa considera
aquela pedra como resolvida (poda de metas)e descarta todas as outras
alternativas de movimentos para aquela caixa.
Busca de Padrões
É um algoritmo que é chamado pela busca IDA* e aprende, em tempo real,
as condições mínimas para detectar um deadlock. Esse algoritmo usa o
aprendizado adquirido para eliminar partes irrelevantes da árvore de
busca. Essa técnica melhora a eficiência da busca do programa.
Podas Relevantes
Essa técnica tenta imitar a noção que os humanos têm de relevância dos
movimentos que fazem no jogo. Ao analisarmos a árvore de busca gerada
pelo IDA* percebemos que o algoritmo gera movimentos que os humanos
jamais considerariam. Com a adição da técnica relevant cuts, ao invés de
buscar em todos os movimentos possíveis nos nós internos, alguns nós
que são irrelevantes para movimentos anteriores são podados.
Caixas B e C influenciam A, estão no
caminho ótimo de A até uma meta
2 sub-problemas que podem
ser resolvidos separadamente
Heurística de Limite
Superior
Ao invés de usar a heurística de limite inferior para calcular a
distância das caixas até a meta, é usada uma estimativa mais
informativa que as vezes superestima essa distância.
•WIDA*
•Limite superior com padrão (pattern overestimation)
Resultados
Após a implementação de algumas dessas técnicas o meu algoritmo
foi capaz de resolver algumas configurações
•Detecção offline de deadlocks
•IDA*
•Heurística de limite inferior
•Posição do homem
•Detecção online de deadlocks
•Tabelas de Hash
Bibliografia
A. Junghanns. Pushing the limits: New development in single agent search.
Ph.D. Thesis, University of Alberta, Department of Computing Science, 1999.
S. Russel e P. Norvig. Inteligência Artificial
• Figura 1 - http://www.pdatungsteno.com/wp-content/imagenes/sokoban2.png
• Figura 2 e 3 - http://www.geocities.com/erimsever/sokoban
• Figuras restantes - A. Junghanns Ph.D. Thesis