15-121: Game Trees 15-121 Summer 2011 Homework Assignment 7 Slide Puzzle Overview: Sliding tile puzzles (follow this link for an interactive puzzle) are common children's games and party favors. The slide puzzle consists of a three by three board with eight numbered tiles and a blank space, denoted by a zero. A tile adjacent to the blank space can slide into the space. The objective is to figure out the steps needed to get from one configuration (which is is an arbitrary arrangement of the tiles), for example, 1 2 3 4 0 5 7 8 6 to the goal configuration: 1 2 3 4 5 6 7 8 0 Finding such a solution of the general n2 - 1 puzzle is known to be NP-complete, and furthermore, the best known algorithm for solving the eight puzzle optimally is A*. Objectives: Representing a seemingly complex problem in a workable form Construct and analyze game trees Understand and implement heuristic search Practice working in small teams to solve problems, design algorithms and write code Assignment: In this assignment you will implement a program that uses BFS search and A* search to solve the Eight Puzzle game. Your program will take an initial board position, and then try to find a sequence of moves from the initial position to the goal position. Moves are represented by moving the blank space left, right, up, or down. For example, suppose we wanted to solve the puzzle shown above. This could be accomplished by the following sequence of moves (we represent a move as the direction the empty space moved):
1 2 3 1 2 3 1 2 3
4 0 5 R 4 5 0 D 4 5 6
7 8 6 7 8 6 7 8 0
initial goal
where R=right, L=left, U=up, D=down. So we can solve this puzzle with the sequence of moves "RD". Game Tree: Given the initial board: 1 2 3 4 0 6 7 5 8 we can determine all the boards that are one move away Repeating this recursively will create a game tree of boards with the initial puzzle at the root This is not a binary tree. Some nodes have two children, some have three, and some have four. Also note that the tree has no leaf nodes, since every board can be transformed into another board by moving a tile. As a consequence of this, there is an infinite number of nodes in our tree. We label the edges connecting the nodes in the tree according to the empty space move. That it is, instead of thinking of moving a specific tile in a specific direction, we can think of moving the empty space in the opposite direction. With this representation, we are interested in the finding the shortest path from the root node to the solution node. Here are some questions to consider about the puzzle: Does every board have a solution? No. All solvable puzzles must be rearrangements (via moving the empty space around) of the solved puzzle. It is possible to make a board that does not fit this description (for example, consider physically breaking a tile out of the puzzle and putting it somewhere else). We will only concern ourselves with solvable puzzles. Does every board have a unique solution? No. Consider a solution to a puzzle. Now add a cycle to that solution (such as "move the empty space to the right and then back to the left") and we have another solution. Does every board have a unique OPTIMAL solution? Not necessarily. There could be several shortest paths to a goal board. Your program should return just one of them. Game board: A board is represented by an instance of the TileBoard class using a string of the puzzle tiles (0 is the empty space). For example, the puzzle:
1 4 6
0 2 3
6 8 7
is stored as "146023687". The class also stores the sequence of moves (a string "LURD..." etc)generated from the start board to this board. You will need to design and implement a functionality for manipulating boards. Try to be efficient in both memory and time. Make sure to comment your design decisions! BFS You implement a BFS over the game tree using a queue (use java.util.LinkedList as a Queue) of TileBoards. You will notice that BFS requires considerable computer memory resources, due to the size of the game tree. We suggest the following two ideas dealing with memory issue: stop BFS when you reach boards with 20 moves away from the initial board, and return SlidingSolution.NO_SOLUTION increase the memory heap size. Here is an example:
java -Xmx500m SlidingSolverDriver
where -Xmx specifies the max heap size. Heap memory is an internal memory pool that dynamically allocated by your application as it's needed. The max heap size for Windows runs from 1.3G to 1.6G depending upon the machine. In Eclipse, you can do this by going Run → Run Configurations → Arguments → VM Arguments. A* Algorithm The A stands for "algorithm", and the * indicates its optimality property. The problem with a breadth-first search is that eats too much resources and takes too long. One way to make it faster is to prioritize boards according to there distances to the goal board. This will avoid considering boards that are relatively far away from the goal board. Such class of search algorithms is called heuristic-based searches. We shall define a heuristic function H(S) that estimates the distance (i.e., the length of the path) from a current board S (also called a state) to the solution board: H(S) = A(S) + E(S) where A(S) is the actual distance from the inital state to this board, and E(S) is the estimated distance from S to the goal state. We will compute A(S) from the game tree we constructed so far, and we will define E(S) as the "Manhattan Distance" between S and the goal state. A*-search uses H(S) as the way of determining which board to consider next. A*-search works correctly as long as H(S) is an underestimate of the distance between the current state and the goal state (try to prove this by yourself). For our implementation, use a java.util.PriorityQueue of TileBoards that is ordered by H(S). You will need to write a comparator to get this work. Manhattan distance: The Manhattan distance heuristic is used for its simplicity and also because it is actually a pretty good underestimate (aka a lower bound) on the number of moves required to bring a given board to the solution board. We simply compute the sum of the distances of each tile from where it belongs, completely ignoring all the other tiles. For example, the Manhattan distance between "213540678" and "123456780" is 9:
2 1 3 1 2 3 1 2 3 4 5 6 7 8
5 4 0 4 5 6 ---------------
6 7 8 7 8 0 1+1+0+1+1+3+1+1 = 9
This is so, because the tile "1" is 1 move away, the tile "2" is 1 move away, the tile "3" is 0 moves away, the tile "4" is 1 move away, the tile "5" is 1 move away, the "6" tile is 3 moves away, the "7" is 1 move away, and the "8" is 1 move away. Note that we do not consider the empty space, as this would cause the Manhattan distance heuristic to not be an underestimate. Another example:
6 4 7 1 2 3 1 2 3 4 5 6 7 8
8 5 0 4 5 6 ---------------
3 2 1 7 8 0 4+2+4+2+0+3+4+2 = 21
Testing: Test your solution on the following starting boards. Recall that the optimal solution is not necessarily unique (so make sure yours works) but there is always an optimal number of moves.
board | number of moves | solution(s)
123405786 2 RD
123745086 4 URRD
123480765 5 DLURD
413726580 8 LLUURDDR
162530478 9 LURDLLDRR
512630478 11 LLURRDLLDRR
126350478 13 ULDLDRRULURDD
356148072 16 RRUULLDRDRUULDRD
436871052 18 URRULDDRULDLUURDRD
302651478 21 DRULDLURRDLLDRRULURDD or DLURDRULDLURDRULDLDRR
012345678 22 RDLDRRULLDRUURDDLLURRD or DRRULLDDRUURDLLURRDLDR
503284671 23 LDDRRULLDRRULLDRUULDDRR
874320651 25 DLULURDRULDDLUURDRDLLURRD
876543021 28 UURDRDLLUURDRULDDRULDLUURDRD or UURDLDRURDLLUURDRULDDLUURDDR
876543210 30 ULLURDDRUULDDLUURDDRUULDDLURRD or ULULDDRUULDDRUURDDLUURDLULDRDR
We recommend that you test your solution rigorously. Try using it to solve puzzles that you create yourself or find on the internet (such as the link provided above). Starter Code: Download the following files SlidingSolverDriver.java SlidingSolution.java SlidingSolver.java TileBoard.java Do not change any of the starter code! What to submit: You need to FTP the following java files SlidingSolver.java TileBoard.java Also turn in the text file you created for Requirement 1 and Requirement 2. Do not submit anything else like zip files, folders, desktops, class files. Failure to do so will result in a 10 point penalty. Grading Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un- commented, or un-readable code as determined by your TA. Here is the point breakdown: Style and design of your TileBoard representation - 15 points Correctness of your Breadth-first search solution algorithm - 25 points Correctness of your A-Star search solution algorithm - 30 points Correct implementation of the "Manhattan Distance" heuristic - 20 points. General coding style - 10 points. Victor S. Adamchik, CMU, 2011
