Assignment 3: Sokoban
General Info
You must read fully and carefully the assignment speci�cation and instructions.
Course: COMP20003 Algorithms and Data Structures @ Semester 2, 2023
Deadline Submission: Friday 20nd October 2023 @ 5 pm (end of Week 12)
Course Weight: 15%
Assignment type: individual
ILOs covered: 2,4
Submission method: via ED
Purpose
The purpose of this assignment is for you to:
Increase your pro�ciency in C programming, your dexterity with dynamic memory allocation
and your understanding of data structures, through programming a search algorithm over
Graphs.
Gain experience with applications of graphs and graph algorithms to solving combinatorial
games, one form of arti�cial intelligence.
Walkthrough

Sokoban
In this programming assignment, you’ll be expected to build an AI algorithm to solve Sokoban. The
game invented in 1980 (program released in 1982) is one of the classics among arcade puzzle games.
You can play the game compiling the code given to you using the keyboard, or using this web
implementation with tutorials (alternative without tutorials).
The code in this assignment was adapted from the open-source terminal version using ncurses made
available by CorrentinB.
Game Rules
As explained in the wikipedia entry, The game is played on a board of squares, where each square is
a �oor or a wall. Some �oor squares contain boxes, and some �oor squares are marked as storage
locations.
The player is con�ned to the board and may move horizontally or vertically onto empty squares
(never through walls or boxes). The player can move a box by walking up to it and pushing it to the
square beyond. Boxes cannot be pulled, and they cannot be pushed to squares with walls or other
boxes.
The number of boxes equals the number of storage locations.
The puzzle is solved when all boxes are placed at storage locations.
For the courious reader
The Science of Sokoban
Sokoban can be studied using the theory of computational complexity. The problem of solving
Sokoban puzzles was �rst proved to be NP-hard [4][5]. Further work showed that it was signi�cantly
more di�cult than NP problems; it is PSPACE-complete [6]. This is of interest for arti�cial intelligence
(AI) research because solving Sokoban can be compared to the automated planning required by some
autonomous robots.
NP-complete problems are hard to solve. The best algorithms to solve NP-Complete problems run in
exponential time as a function of the size of the problem and the shortest accepted solution. Hence,
be aware that your AI solver will struggle more as the number of boxes increases. We talked in the
lectures about the Travelling Salesman Problem as one example of an NP-Complete problem. In fact,
many real-world problems fall under this category. We are going to learn more about NP-Complete
problems in the last lecture of the course via an invited talk in week 12.
Sokoban is di�cult not only because of its large branching factor, but also because of its large search
tree depth. Some level types can even be extended inde�nitely, with each iteration requiring an
exponentially growing number of moves and pushes.[7] Skilled human players rely mostly on
heuristics and are usually able to quickly discard a great many futile or redundant lines of play by
recognizing patterns and subgoals, thereby drastically reducing 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 that make use of domain-speci�c knowledge.[8] This is the
method used by Rolling Stone,[9] a Sokoban solver developed by the University of Alberta GAMES
Group. Festival[10] was the �rst automatic solver to solve all 90 levels in the standard benchmark test
suite. However, the more complex Sokoban levels are out of reach even for the best automated
solvers.[11]
Above and Beyond
Below I added interesting material for those that want to take a deeper dive on Sokoban Solvers.
O�cial benchmarks and results and best Sokoban solvers from 1980-2021. The best solver,
Festival, was introduced at a conference last year, in 2020. A collaboration by a Google
employee and a great professor Jonathan Schae�er who made outstanding contributions to AI
and games.
Relevant publications, A great starting point in that list is to read Andreas Junghanns Ph.D.
dissertation about Sokoban. 1999. Pushing the Limits: New Developments in Single-Agent
Search. Ph.D. Dissertation, University of Alberta, 1999.
Everything about Sokoban: WIKI
The juice of the great computational ideas & insights behind the best Sokoban solvers.
The Algorithm
A con�guration of the Sokoban game is speci�ed by the location of walls, boxes, storage areas and
player. A con�guration is called a state. The Sokoban Graph is implicitly de�ned. The
vertex set is de�ned as all the possible con�gurations (states), and the edges connecting two
vertexes are de�ned by the legal movements (right, left, up, down). All edges have a weight of 1.
G = ⟨V ,E⟩
V E
Your task is to �nd the path traversing the Sokoban Graph from the initial state (vertex) leading to a
state (vertex) where all the boxes are located on a storage area. The best path is the shortest path. A
path is a sequence of movements. You are going to use Dijkstra to �nd the shortest path �rst, along
with some game-speci�c optimizations to speed up your algorithm.
When the AI solver is called (Algorithm 1), it should explore all possible paths (sequence of move
actions) following a Dijktsra strategy, until a path solving the game is found. Note that we use
transposition tables to avoid duplicate states in the search. If a state was already expanded (popped
from the priority queue), we will not include it again in the priority queue (line 23 in Algorithm 1). We
will also ignore states where the player doesn't move as a result of moving towards an adjacent wall,
or a box which cannot move (line 18). We will �nally avoid states where boxes are located in a corner
(line 18, see �le utils.h ). The algorithm should return the best solution found. This path will then
be executed by the game engine if the option play_solution was used as an argument.
You might have multiple paths leading to a solution. Your algorithm should consider the possible
actions in the following order: left, right, up or down.
Make sure you manage the memory well. When you �nish running the algorithm, you have to free all
the nodes from the memory, otherwise you will have memory leaks. You will notice that the
algorithm can run out of memory fairly fast after expanding millions nodes.
The applyAction creates a new node, that
points to the parent,
updates the state with the action chosen,
updates the depth of the node,
updates the priority (used by the priority queue) of the node to be the negative node's depth
(if the node is the dth step of the path, then its priority is -d). This ensures the expansion of the
d
shortest paths �rst, as the priority queue provided is a max heap,
updates the action used to create the node.
Check the �le utils.h, hash_table.h, priority_queue.h where you'll �nd many of the functions
in the algorithm already implemented. Other useful functions are located directly in the �le ai.c ,
which is the only �le you need to edit to write your algorithm inside the function findSolution .
Look for the comment FILL IN THE GRAPH ALGORITHM . All the �les are in the folder src/ai/.
Deliverables
Deliverable 1 - Dijkstra Solver source code
You are expected to hand in the source code for your solver, written in C. Obviously, your source
code is expected to compile and execute �awlessly using the following make�le command: make
generating an executable called sokoban . Remember to compile using the optimization �ag gcc -O3
for doing your experiments, it will run twice as quickly as compiling with the debugging �ag gcc -g
(see Makefile , and change the CC variable accordingly). For the submission, please submit your
make�le with gcc -g option, as our scripts need this �ag for testing. Your program must not be
compiled under any �ags that prevents it from working under gdb or valgrind.
Your implementation should work well over the �rst 3 layouts, but it will not be expected to �nd a
solution to any layout, as it may exceed the available RAM in your computer before �nding a
solution. Feel free to explore maps given in the folder maps_suites. They are taken from the o�cial
benchmarks of sokoban. All you have to do is to copy and paste a single map into a new �le, and
then call it with your solver.
Deadlock Detection (optimizations)
The simplest way to improve the code is by improving the deadlock detection implemented
(SimpleCornerDeadlock) in Algorithm 1-line 18. You can �nd the C implementation inside
utils.c:235 . Implement at least 1 deadlock detection in the link above.
Take a look at these 2 links for further optimization ideas & insights.
If you do any optimizations & changes to the Data Structures & deadlock detection improvement,
please make sure to explain concisely what it is that you implemented, why you chose that
optimization, how it a�ects the performance (show number of expanded nodes before and after the
optimization for a set of test maps), and where the code of the optimizations is located. This
explanation should be included in the �le located at the root of the basecode: README.md . Please
make sure that your solver still returns the optimal solution.
Deliverable 2 - Submission Certi�cation Form
Once you submit your code, please also �ll out the form, no later than 24h after the deadline.
The form is mandatory, and shouldn't take more than 5 minutes.
Rubric
Assignment marks will be divided into three di�erent components.
1. Solver (12)
1. Finds solution for the capability test cases (10)
2. No memory error (1)
3. No Memory leak (1)
2. Code Style (2)
3. Optimizations (1)
Please note that you should be ready to answer any question we might have on the details of your
assignment solution by e-mail, or even attending a brief interview with me, in order to clarify any
doubts we might have.
We will follow the same Ungrading approach used for Assignments 1 and 2.
Maps & Solution formats
Puzzle File Format
We adapted the sokoban �le reader to support the following speci�cation, but we don't support
comments speci�ed by % .
Solution File Format
solutions returned by the solver follow this format
You can load your map and solution into the JS Visualiser.
JS Visualiser
For the visualiser to work, puzzles must be rectangular. If your map is not rectangular, just �lled it in
with walls instead of empty spaces.
The Code Base
You are given a base code. You can compile the code and play with the keyboard (arrows). You are
going to have to program your solver in the �le ai.c . Look at the �le main.c (main function) to
know which function is called to call the AI algorithm.
You are given the structure of a node, the state, a max-heap (priority queue) and a hashtable
implementation to check for duplicate states e�ciently (line 23 in the Algorithm 1). Look into the
utils.* �les to know about the functions you can call to apply an action to update a game state. All
relevant �les are located in the folder src/ai/ .
In your �nal submission, you are free to change any �le, but make sure the command line options
remain the same.
Input
You can play the game with the keyboard by executing
./sokoban