jeSokoban & jeSokobanSolver

This is the start page of jeSokoban & jeSokobanSolver. I moved it into my blog for easier maintenance. Please visit the menu Projects –> jeSokoban for relevant sub-pages.

jeSokobanSolver is an application that automatically solves sokoban levels.

 

A nice sokoban game for windows can be found here.
My own sokoban game in java can be found here (sorry, removed URL as the global highscore table database access is broken)
More sokoban info at wikipedia

The idea is japanese in origin. Sokoban means warehouse keeper. The original game was created in 1982 by Hiroyuki Imabayashi. There are many different versions of sokoban for a variety of computer platforms as well as thousands of sokoban levels created by enthusiasts. In short the object of the game is to push all the blocks to the vault for storage. Careful planning is required; if you push a block into a corner it can no longer be moved.

I created my original engine for sokoban many years ago for my BBS system New Touch Pro. Back then it hade only character ascii graphics. Later i added a graphics driver for directdraw and ported it to Windows. I’ve also made a version in java. My sokoban engine has also been used in a sokoban game for cellphones created by Pär Andersson and in a version for MacOS X by Christoffer Lernö.

I found, though, that playing the game was not as interesting as solving the levels computationally.

Quote from wikipedia regarding the scientifics:

Sokoban can be studied using the theory of computational complexity. The problem of solving Sokoban puzzles has been proven to be NP-hard. This is also interesting for artificial intelligence researchers, because solving Sokoban can be compared to designing a robot which moves boxes in a warehouse. Further work has shown that solving Sokoban problems is also PSPACE-complete.

Sokoban is difficult not only due to its branching factor (which is comparable to chess), but also its enormous search tree depth; some levels require more than 1000 “pushes”. Skilled human players rely mostly on heuristics; they are usually able to quickly discard futile or redundant lines of play, and recognize patterns and subgoals, drastically cutting down on the amount of search.

Some Sokoban puzzles can be solved automatically by using a single-agent search algorithm, such as IDA*, enhanced by several techniques which make use of domain-specific knowledge. This is the method used by Rolling Stone, a Sokoban solver developed by the University of Alberta GAMES Group. The more complex Sokoban levels are, however, out of reach even for the best automated solvers.

jeSokobanSolver is using a brute force depth-first alghoritm coupled with a number of optimizations that drastically reduces the time needed to find a solution. The goal of jeSokobanSolver is to find the optimal solution for any level, not just any solution. This sets it apart from other sokoban solvers, and unfortunately removes a few algorithm improvements from the ballgame. It can be both move-oriented (the optimal solution is the one that requires the least number of moves) and push-oriented (the optimal solution is the one that requires the least number of pushes).

jeSokobanSolver is not a stand-alone application that you can run on your own computer to solve a certain level, it is designed as a client-server application that communicates with my database of sokoban solutions. There are no restrictions on level size, solution size etc; I don’t like restrictions. Apart from the actual solver algorithms there is also a clever system for finding suitable candidate levels among the many thousands of levels in the database, always resulting in the most solved levels in the shortest amount of time. I have mechanisms for distributing the work among a number of machines and for comparing the work done with previous results to find output errors and to help identify areas for algorithm improvements.

jeSokobanSolver is not a downloadable application. It is a program that is running on my own computers, working day and night to find solutions for all sokoban levels in existence. Any solutions are added to a database which can be freely accessed using the link in the menu. The solutions can also be accessed from any sokoban game that has integrated with my webservice.

Development was halted in early 2006 when i realized i had to start over from scratch to continue improving the software. Development restarted in november 2008

2008-11-27 i cancelled the grid-plans at least for now too many other things to focus on mainly improving the algorithm notes notes notes my solver is using the SokoPath format internally and for storing the level solutions

2008-11-27 I’m working on the project again, I couldn’t stay away. This thing is my nemesis. I’ve almost finished jeSokobanLibrary. I have redesigned the database a little. I’ve completed jeSokobanDatabase and jeConsoleSokoban and I’ve done most of the framework around the solver. All the old code is scrapped. I will keep the old solutions database untouched for now. Will be replaced with the new database later on. I’ve also designed a specification for a new solutions format. I think i will have the solver up and running generating solutions in a few weeks.

2012-11-25 This page is now back from limbo, this time as a part of my blog. Further news and updates can be found in the menu.

Copyright (c) Johan Eliasson & Nebol Software 2003 – 2012+

Leave a Reply

Your email address will not be published. Required fields are marked *