Institut für Theoretische Informatik, Algorithm Engineering

Using an Algorithm Portfolio to Solve Sokoban

  • Forschungsthema:Combinatorial Search
  • Typ:Bachelorarbeit
  • Datum:23.2.2017
  • Betreuer:

    Tomas Balyo

  • Bearbeiter:

    Nils Froleyks

  • Links:PDF
  • 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.