This will be a presentation offered at the Search-Based and Fuzz Testing Workshop in 2024.
Tutorials information offered by SBFT'24.
Abstract
Sokoban, a puzzle game developed in the early 1980s, has proven to be a challenging search optimisation problem often aligned with autonomous agent research. The eponymous "warehouse keeper" attempts to move crates into desired positions, often encountering difficult terrain and situations as crates the players themselves have moved block the path. These puzzles prove to be difficult for humans and computers alike, and general-purpose solving for Sokoban puzzles is PSPACE-complete as shown by previous research. To improve the academic understanding of the problem, we propose a King-of-the-Hill (KotH) competition in which competitors develop both automated puzzle solvers and generators. With this, we hope to identify what puzzle features weaken which optimisation strategies, what strategies can be used to defeat new challenges, and observe specialised adversarial techniques to target and disrupt tactics employed by various competitors.