It was really stark to see how the additions in each new algorithm causes order-of-magnitude changes in solver capability. This post will cover these search algorithms and concretely show how they progressively improve on each other Sokoban problems of increasing complexity. As such, I naturally started by writing some of the very basic search algorithms from my search appendix chapter. I did learn a lot about Pascal and about efficient Sokoban solving from the code base, and ended up translating the overall gist of many algorithms in order to learn how Goal room packing works.īefore I fleshed out YASS’s goal room packing algorithm, I needed a good baseline and a way to verify that my Sokoban game code was correct. After trying to translate the Pascal code into Julia directly, I both determined that the languages are sufficiently different that this was not really possible (Pascal, for example, has a construct similar to a C union, which Julia does not have), and that it also ultimately wasn’t what I wanted to get out of the exercise. I had heard that this solver could solve the “XSokoban #50” level in under a second, and had found the wiki overview and the code, so felt it was a good place to dive in. This renewed my interest in Sokoban, and I spent a fair amount of free time looking into solvers.Įarly in my investigation, I downloaded an implementation of YASS (Yet Another Sokoban Solver), a 27538-line Pascal program principally written by Brian Damgaard, which I found via the Sokoban wiki.

While the solo pushing of blocks in Sokoban is not quite the same as simultaneously moving multiple robots under trays and having them lift them up, the problems are fairly related. I am responsible for the scheduler, which is the centralized planner that orchestrates all garage operations.

I started work at Volley Automation in January of 2021, a startup working on fully automated parking garages. While search problems are not front and center in Algorithms for Decision Making, I did end up writing an appendix chapter on them, and looking back on it see how well comparatively the thesis covers the space.

The thesis serves as a great background for search in general, that is, whenever one wants to find the best sequence of deterministic transitions to some goal state.

At that time I stumbled upon Solving Sokoban by Timo Virkkala, a great Master’s Thesis that covers the basics of the game and the basics used by many solvers.

Sokoban solver online edit