Difficulty Rating of Sokoban Puzzle

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

JARUŠEK Petr PELÁNEK Radek

Year of publication 2010
Type Article in Proceedings
Conference STAIRS 2010, Proceedings of the Fifth Starting AI Researchers' Symposium
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords Sokoban; Difficulty rating; Puzzle; Computational model
Description Sokoban puzzle is very challenging problem for both humans and computers. It also illustrates differences between human and artificial intelligence - different problems are difficult for humans and for computers. Whereas algorithmic techniques for Sokoban solving have been intensively studied by previous research, factors determining difficulty for humans have not been sufficiently explained so far. We describe two methods for difficulty rating of Sokoban puzzle - a problem decomposition metric and a computational model which simulates human traversal of a state space. We evaluate these metrics on large scale data on human solving (2000 problems solved, 785 hour of problem solving activity).
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.