Scientific research
From Sokoban Wiki
m (→Scientific research) |
(clarification that the challenge is due to TWO main factors: Large search tree AND the difficulty of finding a suitable heuristic for all puzzles.) |
||
| Line 5: | Line 5: | ||
The computational problem of solving Sokoban puzzles was first shown to be <span class="plainlinks">[https://en.wikipedia.org/wiki/NP-hardness NP-hard]</span>. Further work proved it is also <span class="plainlinks">[https://en.wikipedia.org/wiki/PSPACE-complete PSPACE-complete]</span>. | The computational problem of solving Sokoban puzzles was first shown to be <span class="plainlinks">[https://en.wikipedia.org/wiki/NP-hardness NP-hard]</span>. Further work proved it is also <span class="plainlinks">[https://en.wikipedia.org/wiki/PSPACE-complete PSPACE-complete]</span>. | ||
| - | + | Sokoban puzzles are challenging for computers to solve because they require complex decision-making. | |
| + | |||
| + | The two main factors that explain this difficulty: | ||
| + | |||
| + | * Exponentially growing search space: In Sokoban, there are usually multiple boxes, each with numerous possible moves. This causes the number of possible states to grow exponentially, making it challenging to find a solution within a reasonable time. | ||
| + | |||
| + | * Heuristic challenges: Given the vast search space, good heuristics are necessary for efficient problem-solving. However, it's challenging to develop a general heuristic that works well in all situations. | ||
| - | |||
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. | ||
Current revision as of 15:28, 12 November 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.
Sokoban puzzles are challenging for computers to solve because they require complex decision-making.
The two main factors that explain this difficulty:
- Exponentially growing search space: In Sokoban, there are usually multiple boxes, each with numerous possible moves. This causes the number of possible states to grow exponentially, making it challenging to find a solution within a reasonable time.
- Heuristic challenges: Given the vast search space, good heuristics are necessary for efficient problem-solving. However, it's challenging to develop a general heuristic that works well in all situations.
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.
