Festival

Festival is a Sokoban solver written by Yaron Shoham. It is based on the novel FESS search algorithm (presented in CoG 2020).

Festival is the first program that solves all 90 levels of the XSokoban benchmark. It also scores nicely on many other level sets (see the solvers statistics wiki page).

Running Festival

Festival is a console application, and runs as a shell command. However, it can also be run as a plugin using the YASC graphical user interface.

  • Running from the command line

The program is given the levels set to process, followed by optional arguments. This looks, for example, like that:

The solution moves are saved to a file.

  • Running Festival from a graphical user interface

YASC is an excellent Sokoban GUI written by Brian Damgaard. Brian has added support for running Festival as a plugin solver in YASC. After installing the plugin, it looks like this:

This makes it much easier to import levels and examine the solutions.

Downloading Festival

The current release version is 3.1 . The zip file includes:

  • A README
  • The Festival executable (for Windows)
  • The YASC plugin (YASC version 1.663 or newer is required)
festival_3.1Download (0.7 MB)

A version for YASC 1.676 or newer:

festival_3.1BDownload (0.7MB)

Technical implementation details

Festival is a Win64 application. It is written in C and compiles with MinGW-W64. Festival supports up to 8 threads and 16GB of memory.

The source code of the program is available here:

festival_3.1_srcDownload

See the README.txt file for details.

FESS related resources

  1. A description of the FESS algorithm can be found in the conference paper. The paper was written together with professor Jonathan Schaeffer. I would like to express my gratitude to Jonathan for helping me even though I am not one of his students.
  2. There is also a draft of the paper before professor Schaeffer volunteered to help me. As such, the draft is much worse in terms of presentation, organization and the level of English. However, the draft contains many Sokoban specific details, and should be an interesting read for Sokoban solver programmers.
  3. FESS presentation at the CoG conference (17.5 minutes).
  4. A one-minute promo.
  5. A certificate …

Reinforcement learning

Festival also uses another search algorithm, called “Look back before forward reinforcement learning” (to be published in SoCS 2021). The algorithm combines a forward search and a backward search, and uses reinforcement learning to compute their optimal weights.

A detailed version of the paper is available on arXiv. I would like to thank professor Gal Elidan for his guidance in this research.

Acknowledgements

Special thanks go to Brian Damgaard and Matthias Meger, for reviewing the FESS paper, helping with the statistics on the Wiki site and many other Sokoban programming discussions.