Why Sokoban?

Our research has a very practical nature: If a method does not work in practise, what is the point? We are not saying there is no value to theory, in fact, we use a lot of other people's theoretic results in our work, but we are primarily interested in systems that solve real problems. We like the immediate feedback of something that works and then works better because of our investigations and ideas.
What makes Sokoban in particular so attractive to us?

Sokoban is easy to understand and visualize. If we want to see where the search makes mistakes or where the search is very efficient, Sokoban is very easy for me to understand as a domain. Many other problems are difficult just alone in how to picture what is going on.
The availability of test cases: We have an almost unlimited supply of test cases at our disposal. Industrial domains often lack that because companies are reluctant to share vital company data.
Different levels of difficulty: Since Sokoban problems come in all levels of difficulty, we can start with the easier ones, learn and improve the algorithms and thus measure progress on a gradual scale. Most other problems come in one size, you can either solve them or you don't - nothing in between.
Different types of problems: Sokoban problems come in an infinite variety of types, and not just size and difficulty. Different concepts are needed to solve different kinds of problems, leading to a very rich domain that never stops being a challenge. After all, that is what draws humans to it!
Deadlock: Sokoban offers an interesting feature. If you are not careful, you can create an unsolvable configuration. That is very much like most real world problems, where constraints exist that can create situations where no (good or optimal) solution can be had anymore. It is also interesting from a real-time perspective: if you need to make a move every so often without knowing that you can still produce a solution for sure, how do you minimize the risk of deadlock?
And not the least: Sokoban is fun! Why would we want to work on a boring and dry problem when we can work on a domain that humans have a real relationship with: love and/or hate it, loose sleep over it for no other reason but the challenge to tackle a really hard problem!

Humans are incredibly apt in solving Sokoban puzzles. They are able to take advantage of the structure of the puzzles to develop higher level concepts that allow them to decompose the problems into loosely coupled subproblems or subgoals. This is what Artificial Intelligence is all about. And yet, we are having very limited success in carrying this human ability over into algorithms. Apart from the question if we want to make the machine solve the problem in a similar fashion as the humans, the more important aspect here is that if we want to successfully tackle the exponential nature of Sokoban problems, decomposition is essential and exhaustive search strategies are very ill equipped to decompose problems.
Humans, however, can successfully solve Sokoban problems. As a testbed for artificial intelligence techniques, Sokoban offers a real challenge to researchers, since most of the core problems of artificial intelligence need to be addressed to build a successful program that rivals best human performance in solving Sokoban problems.

University of Alberta

Computing Science

Games Homepage

Sokoban Homepage

Please mail feedback to games@cs.ualberta.ca Last modified: