Assignment 3 Solution

In this assignment, you will write components of a program to play a game called Sokoban. This assignment will give you some experience in defining a search space for a practical problem and coming up with a good heuristic to make your program more efficient. The heuristic you invent will also be entered into a class-wide competition for a small portion of your grade.




Submission etc.




You should submit one file called “hw3.lsp” through CCLE by the deadline above. Again, naming of file and functions must follow the instructions strictly. We reserve the rights to impose a heavy penalty on submissions that fail to follow the instructions.




The functions that you are allowed to use are the same as those allowed in hw1 and hw2 plus: butlast, nthcdr, count. You are not permitted to use setq or any looping function in your solution (while, for, etc). (For testing purposes only, you can use setq for defining initial state of the game, as shown in some later examples).




You are allowed to use as many helper functions as you want. In fact, defining small, meaningful functions may simplify your code significantly. Please comment every function briefly with the logic behind the function (what approach was taken). However, you are not allowed to define any global variables. Global variables already defined in the provided code are fine.




Honor code




Remember that you cannot use any outside reference for this or any assignment. However, you are allowed (and encouraged) to experiment with actual Sokoban games (which can be found online). Obtaining test problems and playing Sokoban from the Internet are acceptable. It is not acceptable to copy a solution for any function you have to write (even for a heuristic). In general, any idea that is not originally yours must be attributed to the appropriate sources.




By submitting this homework, you agree to the following honor code.




You are encouraged to work on your own in this class. If you get stuck, you may discuss the problem with up to two other students, PROVIDED THAT YOU SUBMIT THEIR NAMES ALONG WITH YOUR ASSIGNMENT. ALL SOLUTIONS MUST BE WRITTEN UP INDEPENDENTLY, HOWEVER. This means that you should never see another student's solution before submitting your own. You may always discuss any problem with me or the TAs. YOU MAY NOT USE OLD SOLUTION SETS UNDER ANY CIRCUMSTANCES. Making your solutions available to other students, EVEN INADVERTENTLY (e.g., by keeping backups on github), is aiding academic fraud, and will be treated as a violation of this honor code.




You are expected to subscribe to the highest standards of academic honesty. This means that every idea that is not your own must be explicitly credited to its author. Failure to do this constitutes plagiarism. Plagiarism includes using ideas, code, data, text, or analyses from any other students or individuals, or any sources other than the course notes, without crediting these sources by name. Any verbatim text that comes from another source must appear in quotes with the reference or citation immediately following. Academic dishonesty will not be tolerated in this class. Any student suspected of academic dishonesty




will be reported to the Dean of Students. A typical penalty for a first plagiarism offense is suspension for one quarter. A second offense usually results in dismissal from the University of California.




Background




Sokoban is a well-known puzzle video game that was first introduced in Japan in 1980. The word Sokoban means “warehouse keeper” in Japanese which refers to the main character of the game. In this game, the player controls the warehouse keeper (sokoban) who is placed in a closed warehouse with a number of boxes that need to be put in some predefined goal locations. The keeper can walk around the warehouse and push boxes around in order to get them into goal positions. The goal of this game is to put all boxes into goal positions in the fewest number of moves. An initial state of this game is shown in Figure 1 below.









































































Figure 1: A Sokoban game. Boxes are presented by gems and goals are represented by circles.




How to play




The whole game (the warehouse) is on a grid. In each step, the keeper can move in any of the four basic directions (up, down, left, right). The keeper cannot walk into a wall or into a box. However, the keeper can push a box if the square next to the box (in the pushing direction) is either a goal or an empty square. Only one box can be pushed in any given step. In the case of multiple goals, there is no specific goal that a box has to be in. Boxes can be placed in goals in any order. A box can also be pushed out of a goal if needed (to make way for other moves). The game ends as soon as every box is in a goal position (even if there are more goals than boxes). In general, the minimum number of moves is not strictly required by the actual Sokoban game, because even finding a solution to the problem is already hard for a human player. Nevertheless, it is an objective of this assignment.




Sokoban as a search problem




In this assignment, we will turn this game into a search problem. As you have seen from class, a number of components are required for defining a search problem. In this case, they are




A state representation



A successor function that indicates which states can be reached from a given state in one step
A goal test



A cost function



Once all these components are defined (in practice as functions), the problem can be solved by a generic search engine that implements any search algorithm (e.g. DFS, BFS, A*, etc). Of course, the efficiency of the program and the quality of the solution depends on the type of search algorithm used.




Because of the time constraint, in this assignment, we will provide you with a search space formulation. You will then write some LISP functions to implement the above components based on the given formulation. Also, we will assume a uniform cost function. Every move in this game will have cost 1.




Game state representation




Each state of the game will be represented by a list of lists. The content of each square in the game will be represented by an integer. Each row of the game can then be represented by a list of integers that represent the content of each square in the row (left to right). Finally, a state is simply a list of rows (top to bottom). For simplicity, in this assignment we will assume that every row contains the same number of columns. We will assume that each state contains exactly one keeper, at least one box, and that the number of goals is greater than or equal to the number of boxes in the state.




Let us now introduce the representation of square contents. Each square in Sokoban can only contain so many things. A square may contain one of the following:




Nothing (empty floor)



A wall



A box



The keeper



A goal



A box on top of a goal



The keeper on top of a goal.



Table 1 shows a mapping between square contents and integers that we will use to represent them. An ASCII representation of each type of content is also shown in this table. This will be discussed later.




Table 1: Mapping of square contents.




Content
Integer
ASCII






Blank
0
‘ ‘ (white space)






Wall
1
‘#’






Box
2
‘$’






Keeper
3
‘@’






Goal
4
‘.’






Box + goal
5
‘*’






Keeper + goal
6
‘+’












With this convention, we can represent the game state in Figure 1 in LISP (and assign it to variable p1) as:




(setq p1 '((0 0 1 1 1 1 0 0 0)




(111001111)




(100000201)




(101001201)




(104041301)




(111111111)).




What is provided to you




For this assignment, we have provided you with an A* search engine in the file “a-star.lsp”. You do not need to understand the code in this file. You will call the top level A* function defined in it. To call A*, after loading the file, type at the LISP prompt




(a* start-state #’goal-test #’next-states #’heuristic).




Notice that goal-test, next-states, and heuristic have #’ in front of them. In LISP, you must put #’, called “sharp-quote”, in front of functions that you pass as arguments to other functions. You will need to define these functions in your submission. ‘heuristic’ must be substituted by the name of the heuristic function you want to use.




The above call to A* will return a solution of the search problem defined by the initial state and functions in the argument. The solution is returned in the form of a list of states along the solution path. So, if the solution returned takes 10 moves, the list returned will contain 11 elements.




In addition to “a-star.lsp”, we have also provided you with some helper functions that you may need for completing the assignment. These functions are defined in “hw3.lsp”.







What you have to do




(10 pts) Write a function called goal-test that takes a state as the argument and returns true (t) if and only if the state is a goal state of the game. A state is a goal state if it satisfies the game terminating condition described in “How to play” section.



(50 pts) Write a function called next-states that takes a state as the argument and returns the list of all states that can be reached from the given state in one move. This function may require several helper functions. It will be explained in more details in the next section. Your score for this component will depend solely on the correctness. Efficiency will not be evaluated (each function call should never take more than a second anyway. Otherwise there might be a problem).



(5 pts) Write a heuristic function called h0 that returns the constant 0. This is a trivial admissible heuristic.



(10 pts) Write a heuristic function called h1 that returns the number of boxes which are not on goal positions in the given state. Is this heuristic admissible? (Put you answer in the header comment of the function)



(20 pts) Write an admissible heuristic to make the A* search engine perform better. Name this function hUID, where UID is your student ID (for example, h123456789 if 123456789 is your UID). This heuristic function takes in a state and returns an integer (= 0). This function will be evaluated based on its relative performance when it is integrated by our implementation of the search space. The entry of each student will enter the competition against submissions by the rest of the class. The results will be based on the running time of different heuristics (minimizing number of expanded nodes is not enough). Top performers will be awarded with the full score and the worst entry will receive little or no credit for this part.



The remaining 5 percent of the score will be based on comments. All we look for is a brief description of and the logic behind each function you write.




Generating next states




Given a state of the game, each next state can be generated by moving the keeper in one of the valid directions. According to this formulation, each state can have at most four children. The following is one possible strategy for generating next states. You do not need to follow this, as long as your next-states function works as specified.




Implementation strategy




Write a function called get-square that takes in a State S, a row number r, and a column number c. It should return the integer content of state S at square (r,c). If the square is outside the scope of the problem, return the value of a wall.



Write a function called set-square that takes in a state S, a row number r, a column number c, and a square content v (integer). This function should return a new state S’ that is obtained by setting the square (r,c) to value v. This function should not modify the input state.



(For the above two functions, how to index rows and columns is totally internal to your program. However, one reasonable scheme would be to index the top left corner of the game with (0,0) and increase the row and column indices as you move down and move to the right respectively.)




Write a function try-move that takes in a state S and a move direction D. This function should return the state that is the result of moving the keeper in state S in direction D. NIL should be returned if the move is invalid (e.g. there is a wall in that direction). How you represent a move direction is up to you. Remember to update the content of every square to the right value. Refer to Table 1 for the values of different types of square.



You will probably need several small helper functions to make your job easier. In any case, the high-level plan is that your next-states function can call try-move in each of four directions from the current position of the keeper (some of them will return NIL) and collect all returned values into a list. Helper functions are provided for identifying the keeper square and for removing NILs from a list.




The function try-move has to check whether the move is legal. If it is, it will need to update some squares of the current state to reflect the changes. Use set-square to help you do this. According to this strategy, at most three squares need to be updated for any single move (make sure you agree).




More information about each helper function can be found in the comment in “hw3.lsp”.




Visualizing solutions




To make your experience more enjoyable, we have provided in “hw3.lsp” a printing function that will print out a state using the ASCII mapping in Table 1. In particular, you might find it useful to be able to visualize the solution returned by A*. To do so, type at the LISP prompt




(printstates (a* start-state #’goal-test #’next-states #’heuristic) 0.2).




The last argument of printstates is the delay (in seconds) between successive state display. For example, calling




(printstates (a* start-state #’goal-test #’next-states #’heuristic) 0.2) with start-state set to p1 (defined above) results in something like Figure 2 (only the solution visualization part). An individual state can also be displayed using the printstate function. This might be useful for visualizing initial states.

































































































Figure 2: The first 20 states of an optimal solution of p1. States are ordered top-to-bottom and then left-to-right.




Sample outputs of next-states



In this section, we provide some sample outputs of the function next-states. Using printstates or printstate to visualize these inputs/outputs may be useful.




Example 1




(setq s1 '((1 1 1 1 1)




(10041)




(10201)




(10301)




(10001)




(11111)




))




(next-states s1) should return




(((11111)(10241)(10301)(10001)(10001)(11111))




((11111)(10041)(10201)(10031)(10001)(11111))




((11111)(10041)(10201)(10001)(10301)(11111))




((11111)(10041)(10201)(13001)(10001)(11111))).




All four moves are possible in this case. Note how the upward move results in box pushing. Example 2




(setq s2 '((1 1 1 1 1)




(10041)




(10231)




(10001)




(10001)




(11111)




))




(next-states s2) should return




(((11111)(10061)(10201)(10001)(10001)(11111))




((11111)(10041)(10201)(10031)(10001)(11111))

((11111)(10041)(12301)(10001)(10001)(11111))).




Only three moves are possible in this case: up, left, down. Note that the upward move puts the keeper on a goal square (keeper+goal is represented by the number 6, according to Table 1).




Example 3




(setq s3 '((1 1 1 1 1)




(10061)




(10201)




(10001)




(10001)




(11111)




))




(next-states s3) should return




(((11111)(10041)(10231)(10001)(10001)(11111)) ((11111)(10341)(10201)(10001)(10001)(11111))).




Note how the keeper was on a goal square in s3. In this case, there are two possible moves: left and down.




Both moves take the keeper out of the goal square.




Example 4




(setq s4 '((1 1 1 1 1)




(14201)




(10001)




(10001)




(10531)




(11111)




))




(next-states s4) should return




(((11111)(14201)(10001)(10031)(10501)(11111)) ((11111)(14201)(10001)(10001)(12601)(11111))).




A box started in a goal state in s4. There are two possible moves in this case: up and left. Moving the keeper to the left pushes the box out of the goal state and lands the keeper on the goal state.