Scientific research
From Sokoban Wiki
(Pasted the text from the Wikipedia article) |
m (→Scientific research) |
||
| Line 11: | Line 11: | ||
The Sokoban game provides a challenging testbed for developing and evaluating planning techniques. | The Sokoban game provides a challenging testbed for developing and evaluating planning techniques. | ||
| - | The first documented automated solver was [[Rolling Stone]], developed at the University of Alberta. | + | The first documented automated solver was [[Rolling Stone solver | Rolling Stone]], developed at the University of Alberta. |
Its core principles laid the groundwork for many newer solvers. | Its core principles laid the groundwork for many newer solvers. | ||
Current revision as of 18:46, 23 April 2024
Scientific research
Sokoban has been studied using the theory of computational complexity.
The computational problem of solving Sokoban puzzles was first shown to be NP-hard. Further work proved it is also PSPACE-complete.
Search for a solution to a Sokoban puzzle is difficult for computers due to the many possible legal pushes at each turn (branching factor) and the possibly long sequence of moves needed to reach a solution (search tree depth).
Even small puzzles can require hundreds of player moves to solve.
The Sokoban game provides a challenging testbed for developing and evaluating planning techniques.
The first documented automated solver was Rolling Stone, developed at the University of Alberta.
Its core principles laid the groundwork for many newer solvers. It employed a conventional search algorithm enhanced with domain-specific knowledge.
Festival, utilizing its FESS algorithm, was the first automatic solver to complete all 90 puzzles in the widely used XSokoban test suite (Festival results).
However, even the best automated solvers cannot solve many of the more challenging puzzles that humans can solve with time and effort.
