Home | english  | Impressum | Sitemap | KIT

Using an Algorithm Portfolio to Solve Sokoban

Using an Algorithm Portfolio to Solve Sokoban
Forschungsthema:Combinatorial Search

Tomas Balyo


Nils Froleyks


The game of Sokoban is an interesting platform for algorithm research. It is hard for humans and computers alike. Even with its simple rules and small average level sizes there are levels that take a lot of computation for all known algorithms. In this thesis we will combine different Sokoban solvers with different domain specific enhancements into one portfolio. This portfolio can then be run in parallel on one problem until one solver finds a solution. Additionally the solvers in the portfolio can exchange data to speed up computation. We will validate the approach of algorithm portfolios for designing a parallel Sokoban solver.