Assignment 7: Searching (Bonus)

ECE 473: Introduction to Artificial Intelligence
Assignment: Searching (Bonus)
Submission Instructions
• Only submit sokoban.py and do not change the filename. Our autograder will find “sokoban.py” to
test your assignment. If you change the filename, autograder will crash and you will receive 0 points.
• You are responsible for checking your program runs properly and run on any system.
• Submit early and often. You can submit as many times as you’d like until the deadline: we will only
grade the last submission.
• We will not be accepting any assignments submitted via email.
• You should modify the code in sokoban.py between
# BEGIN_YOUR_CODE
and
# END_YOUR_CODE
but you can add other helper functions outside this block if you want. Do not make changes to files
other than sokoban.py.
• The assignment will be graded on 10 puzzles not provided to students. For each puzzle, if your program
provides a solution fast (less than 60s), you will get 2 points, if it runs slow (no more than 300s), you
will get 1 point. Maximum points that you can get from this assignment is 20 points, and this will be
normalized when we calculate the final grade.
1
Searching (Bonus) April 1, 2021
In this homework, we ask you to extend our provided code for automated Sokoban puzzle solution using state
space search. The code we provide formulates a simple state space and can solve some Sokoban problems
we provide using uniform-cost search, also provided. In addition, we provide the code for A* search, but
we do not provide any heuristic function.
In this homework we are primarily interested in finding puzzle solutions, without regard to the length/cost
of the solution. Many Sokoban puzzles will be completely unsolvable by the code we distribute (and the
solution code and even any known code) and we are interested in that issue, not in optimizing the number
of steps to solve.
The homework involves both coding and design of puzzle levels to illustrate features of the code. Note that
a significant part of this assignment is developing a complete understanding of the code we are providing;
the code is not written to be instructional but to be functional, and reverse engineering an understanding of
this sort of code is an important computer engineering skill. You are free to modify any part of it in direct
service of the assignments below, but creative modifications, especially with purposes outside the suggestions
below, should be checked with the TA before inclusion in your solution.
Please note that you will be graded on levels that are not provided and will not be checked by any grader
we provide you. It is not sufficient to perform well only on the levels provided, we recommend you to design
your own puzzle to ensure it works well on various scenarios.
ECE 473: Introduction to Artificial Intelligence— Spring 2020 2
Searching (Bonus) April 1, 2021
Instruction to the code
Some sample Sokoban maps are provided to you in levels.txt. You can refer to the following table to
interpret the symbols for each map tile.
symbol meaning
# wall
@ player
+ player on target
$ box
* box on target
. target
(space) floor
To run the code, you will need to provide certain command line arguments. You can type
python sokoban.py -h
to see a full list of available arguments. The algorithm argument can take any of the values in the following
table. You will learn more about what each algorithm does as you proceed further in this homework.
algorithm description
ucs basic UCS
a uncompressed actions with A* using basic heuristic
a2 uncompressed actions with A* using heuristic2
f compressed actions with UCS
fa compressed actions with A* using basic heuristic
fa2 compressed actions with A* using heuristic2
For example, you can type
python sokoban.py 1 ucs
to run the solver on level 1 in levels.txt using basic UCS.
[NOTE: For the following problems, your implementation of the described features should demonstrate
improvement in run time in some levels of levels.txt. You may assume that each problem is worth roughly
the same points.]
[NOTE: You are free to add helper functions or make any changes anywhere in the code, but you should
not modify the function signature of any provided functions except to add arguments with default values.
You should not modify the command line interface except to add tagged arguments with default values.]
Problem 1: Dead end detection
The Sokoban domain contains many states where there is no path to a goal. For instance, if a box is pushed
to a wall corner that is not a target location, then there is no way to move the box out and hence it is a
dead end. For problem one you must modify the code in sokoban.py to detect enough dead end states to
pass the grader performance standard.
If the expand function refuses to produce any descendant for the dead end states, we can greatly reduce the
search space. The dead end detection is not meant to be exhaustive; being able to detect every dead end
state is not necessary. In fact, this is both very difficult to achieve and very expensive to compute so it may
actually hurt us. You should try to detect as many dead end states as possible while keeping the detection
algorithm cheap. Precomputing certain quantities could be very helpful: you should probably not be doing
dead-end detection over and over on each state, but once for the entire problem map.
You can type
python sokoban.py 1 ucs -d
to invoke dead end detection.
ECE 473: Introduction to Artificial Intelligence— Spring 2020 3
Searching (Bonus) April 1, 2021
Problem 2: Action compression
In the provided simple state space, the available actions are {up,down,left,right}, which corresponds to
the single step movement of the player in Sokoban. However, certain sequences of actions have the same
effect on the Sokoban puzzle and can be treated as the same “large step”. For instance, the two action
sequences shown in Fig. 1 have exactly the same effect on the puzzle: both of them result in pushing the
box to the right by one step.
(a) rur (b) urr
Figure 1: The two action sequences are equivalent.
Generally speaking, for the sake of solving Sokoban, we care more about the movement of the boxes, rather
than the movement of the player. Instead of finding the available moves for the player, we can focus on
finding the available box pushes in each state. In this way, we effectively compress many equivalent action
sequences into one larger action. In Fig. 1, the available box pushes are “push the box to the right” and
“push the box to the left”.
For this problem, modify the code in sokoban.py to implement the above-mentioned action compression in a new search problem named SokobanProblemFaster, which inherits directly from the provided
SokobanProblem. Redefine the expand function in the derived class so that it overrides the definition in the
base class. You need to modify the solve sokoban function as well to account for the change in the action
sequence returned by the search algorithm. The second variable that the solve sokoban function
returns should be a list of u/d/l/r characters.
Note that a compressed action can be assigned a cost equal to its number of base actions, or a cost that is
always one. These choices lead to different behaviors you can explore, as the latter considers all solutions
with the same number of box pushes at the same cost, regardless of how long a trip the person takes between
pushes.
Use f for the command line argument algorithm to run the Sokoban solver with your implementation of
SokobanProblemFaster. For instance,
python sokoban.py 1 f -d
allows you to solve level 1 using the compressed action search, together with dead end detection.
Problem 3: A* with a simple admissible heuristic
Even with action compression and dead-end detection, UCS cannot solve many Sokoban puzzles in a reasonable amount of time. Let’s see how A* could help.
In the lecture example, we’ve seen that an admissible heuristic for the 8-puzzle is the sum of Manhattan
distances between each pair of block and its destination. However, unlike the 8-puzzle, we do not know the
correspondence between the boxes and the targets in Sokoban, i.e. which box goes to which target location.
Despite this fact, propose a way to build a simple admissible heuristic function for Sokoban that can be
computed quickly, based on Manhattan distance.
Implement your proposed heuristic in the heuristic function in sokoban.py.
ECE 473: Introduction to Artificial Intelligence— Spring 2020 4
Searching (Bonus) April 1, 2021
Problem 4: A* with a better heuristic
In the previous problem, we required the heuristic function to be admissible so that A* is guaranteed to
find the shortest solution (the solution with the least number of box moves). However, for very complicated
Sokoban puzzles, we are happy if the program can find any solution at all, even if the solution found is not
the optimal one. It is worthwhile to use a more complicated heuristic that is not always admissible, as long
as it gives a better chance of finding a solution in a reasonable amount of time.
Bear in mind that a complicated heuristic could be prohibitively expensive to compute, and thus may not
improve the run time although it might reduce the number of states visited. There is a trade-off between
having a good heuristic to guide the search to the goal, and having a fast heuristic that is cheaper to
compute. It is vital that your heuristic be computable very efficiently, possibly leveraging some precomputed
problem-wide information. You should build a heuristic that improves the search in most cases.
Propose a heuristic that improves performance well enough to solve all the provided levels, with some much
faster than the other methods above, and implement it in heuristic2. (Explain your heuristic clearly in
comments near your code.)
Acknowledgement
Professor Bob Givan, and Mai Zhang
ECE 473: Introduction to Artificial Intelligence— Spring 2020 5