Learning deadlocks in sokoban

Abstract

In this thesis, we present an approach for deadlock detection in Sokoban based on neural networks. Sokoban is a challenging state space problem in artificial intelligence due to many characteristics, being the presence of deadlocks one of them. A deadlock is a state reachable from the initial state which cannot reach any goal state. An informed search algorithm aims to find in a state space an ordered sequence of actions that transform the initial state into a goal state. Deadlock detection is essential to increase the performance of an informed search algorithm. Pattern databases are the current state of the art heuristic for deadlock detection in Sokoban. We present methods to generate a training set and train a neural network to detect deadlocks. Our approach has a similar performance to a pattern database. When compared to the standard heuristic function of Sokoban we solved two more instances while exploring an order of magnitude fewer states.

Nesta tese, apresentamos uma abordagem para detecção de deadlocks em Sokoban baseada em redes neurais. Sokoban é um problema de espaço de estados desafiador na inteligência artificial devido a muitas características, sendo a presença de deadlocks uma delas. Um deadlock é um estado alcançável a partir do estado inicial que não consegue atingir nenhum estado de objetivo. Um algoritmo de busca informada visa encontrar em um espaço de estados uma sequência ordenada de ações que transformam o estado inicial em um estado objetivo. A detecção de deadlocks é essencial para aumentar o desempenho de um algoritmo de busca informada. Pattern databases são a atual heurística estado da arte para detecção de deadlock em Sokoban. Apresentamos métodos para gerar um conjunto de treinamento e treinar uma rede neural para detectar deadlocks. Nossa abordagem tem um desempenho semelhante a pattern databases. Quando comparado com a função heurística padrão do Sokoban resolvemos duas instâncias a mais enquanto exploramos uma ordem de grandeza menos estados.