Programming Assignment 3 Solution

In this assignment, you will write components of a program to play a variant of 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.







Submission etc.




You should submit one file called “hw3.lsp” through CCLE submission system by the deadline above.




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.




If you have any questions, please contact the TA.

Background




The original 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. For the purpose of this project, the goal is to let the keeper push all boxes to a goal position and return to any of the remaining goal position in the fewest number of moves. The initial states of two instances of this game are 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 movable entity, including every box and the keeper, is in a goal position (even if there are more goals than the number of movable entities). 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 plus one to accommodate all the boxes and the keeper 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)




(101041201)




(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). The heuristic will be scored using both the number of solved instances under a time limit and the total running time for solving the problem. (minimizing number of expanded nodes is not enough).



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. Please note that the visualization example that we show here has a different objective from this project. In this project, each movable entity, including the keeper, has to land in a goal position, while the keeper in this visualization example does not end in a goal position.

































































































Figure 2: The first 20 states of an optimal solution of p1. States are order 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)




(14041)




(10201)




(10301)




(10001)




(11111)




))




(next-states s1) should return




(((11111)(14241)(10301)(10001)(10001)(11111))




((11111)(14041)(10201)(10031)(10001)(11111))




((11111)(14041)(10201)(10001)(10301)(11111))




((11111)(14041)(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)




(14001)




(11111)




))




(next-states s2) should return




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




((11111)(10041)(10201)(10031)(14001)(11111))

((11111)(10041)(12301)(10001)(14001)(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)




(10041)




(11111)




))




(next-states s3) should return




(((11111)(10041)(10231)(10001)(10041)(11111)) ((11111)(10341)(10201)(10001)(10041)(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)




(14241)




(10001)




(10001)




(10531)




(11111)




))




(next-states s4) should return




(((11111)(14241)(10001)(10031)(10501)(11111)) ((11111)(14241)(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.