CS63 Fall 2005
Lab 2: A* Search for the Eight Puzzle Problem
Due: Friday, September 16 by 11am

CONTENTS


INTRODUCTION

For this lab, we will apply A* search to the eight puzzle problem. The eight puzzle consists of a three by three board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to figure out the steps needed to get from one configuration of the tiles to another.

For this problem, a state should specify the location of each the eight tiles as well as the blank space in the three by three grid. The operators are most efficiently represented as moving the blank left, right, up, or down, rather than creating operators for each of the numbered tiles.

For example, suppose we wanted to get from the initial state to the goal state given below.

 1 2 3      1 2 3
 8   6  ->  8   4
 7 5 4      7 6 5 
 initial    goal
We could accomplish this with the following sequence of operators on the blank, R=right, L=left, U=up, D=down.
 1 2 3     1 2 3     1 2 3     1 2 3     1 2 3
 8   6  R  8 6    D  8 6 4  L  8 6 4  U  8   4
 7 5 4     7 5 4     7 5       7   5     7 6 5
 initial                                 goal
        

LAB INSTRUCTIONS

  1. Save the file pq.py to your own directory. This contains the definition of a PriorityQueue class. Read through the implementation and be sure you understand how it works. You can test it by modifying the test code at the bottom of the file.
  2. Save the file informedSearch.py to your own directory. This contains updated definitions of the classes we used in the last week's lab. The InformedNode class now takes a goal state and has an added method called priority. The InformedSearch class now uses a priority queue and creates instances of the InformedNode class in its execute method. It also keeps track of how many nodes it has expanded during the search process and reports this with the solution. The InformedProblemState now has an added method called heuristic which takes a goal state and returns an estimate of the distance from the current state to the goal state.
  3. Create a file that implements the states, operators, and heuristics needed for the eight puzzle problem. Your EightPuzzle class should inherit from the InformedProblemState class. Remember to make sure that your operators make a copy of the current state before moving the tiles.
  4. Test your solution on the following starting states A-H using the same goal each time. State A should take 2 steps, state B should take 6 steps, and state C should take 8 steps. You'll need to determine the length of the other solutions.
       
     1 2 3  1 3    1 3 4    1 3  7 1 2  8 1 2  2 6 3  7 3 4  7 4 5
     8   4  8 2 4  8 6 2  4 2 5  8   3  7   4  4   5  6 1 5  6   3
     7 6 5  7 6 5    7 5  8 7 6  6 5 4  6 5 3  1 8 7  8   2  8 1 2
     goal     A      B      C      D      E      F      G      H
    
  5. In order to demonstrate that A* is superior to standard BFS and that the manhattan distance heuristic is more informed than the tiles out of place heuristic, you will compare the number of nodes that each search expands on the problems given above (A-H). The only change you'll need to make to do a BFS search rather than an A* search is to replace the priority queue with the standard q that we used in last week's lab. Inside a comment in your eight puzzle file, create and fill in the following table:
                 Node Expansions
    Problem   BFS  A*(tiles)  A*(dist) 
    A
    B
    C
    D
    E
    F
    G
    H
    
  6. Discuss the results within a comment in your file. What is the depth of the shortest path d for each test case? We know that the maximum branching factor for the eight puzzle is 4, but what is the effective branching factor b for this problem? Add code to calculate the effective branching factor. Add a column to your table to record these values for each problem. Explain the values obtained. Do the recorded number of nodes expanded fall within the theoretical limit of O(b^d) discussed in the book for BFS?
  7. Extra credit: Do one or both of the following: (a) Implement a more informed heuristic than the manhattan distance for the eight puzzle problem. Be sure to demonstrate that it is more informed. (b) Store all of the visited states in an efficient data structure so that no state is ever repeated in the search tree. Demonstrate that this version of A* consistently expands fewer nodes than the original version. Also explain the added cost of maintaining the data structure for the search process.

HAND IN

Use cs63handin to submit your eight puzzle file. Your table of test results and discussion of the results should be included in the file as comments. If you need to change the search file, you may turn in an updated version of that as well.