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?
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.
- 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
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.
Please mail feedback to