UserPreferences

Exercise 3

CS 372 (Artificial Intelligence) Fall 2004: Exercise 3

Model and Goal Endowed Agents: Puzzle Meister: Search Algorithms

In this exercise you will use uninformed searches: to solve the 8-puzzle. The following files are available in ~dkumar/cs372/Search directory:

  1. SearchQueues.py: Various queue data structures (Stack, Queue, PriorityQueue) used by searches.

  2. Search.py: Defines a search Node and a generic search algorithm that can be used to perform depth-first, breadth-first, and uniform-cost searches.

  3. EightPuzzleState.py: An implementation of the 8-puzzle and operators.

The 8-puzzle consists of a 3 x 3 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 unscramble the tiles to reach the goal configuration. See Chapter 8 of your text (Nilsson) for more information on 8-puzzle.

For this problem, a state is represented as the configuration of the eight tiles and the blank space on the board. The operators are most easily represented as moving the blank up, down, left, or right, rather than creating operators for each of the numbered tiles.

For example, suppose we wanted to get from the start state to the goal state given below: 

  1 2 3     1 2 3
  8   6     8   4
  7 5 4     7 6 5

  Start     Goal

We could accomplish this with the following sequence of operators on the blank: 

   1 2 3   RIGHT   1 2 3   DOWN   1 2 3   LEFT   1 2 3    UP    1 2 3
   8   6    --->   8 6     --->   8 6 4   --->   8 6 4   --->   8   4
   7 5 4           7 5 4          7 5            7   5          7 6 5

The EightPuzzleState class implements states and operators for the 8-puzzle. The EightPuzzleState constructor takes a list of the nine tiles as input, in the order shown: 

   nw    northwest element
   n     north element
   ne    northeast element
   w     west element
   c     central element
   e     east element
   sw    southwest element
   s     south element
   se    southeast element

Values should be the numbers 1 through 8 for the puzzle pieces or a space character for the blank. For example, the above goal state can be created by calling: 

>>> EightPuzzleState([1, 2, 3, 8, ' ', 4, 7, 6, 5])

A method called applyOperators() is provided, which returns a list of (state, action) pairs representing the new states generated by applying all operators to the original state. Each action is a string describing the move that generated the associated state, and should be of the form "RIGHT", "LEFT", "DOWN", "UP".

Do the following:

  1. Understand and test the program on the following starting states A-E (each is progressively harder) using the same goal each time. To save you some typing, these states are already defined at the bottom of the Search.py file. 

      1 2 3    1 3      1 3 4    1 3      7 1 2    8 1 2
  8   4    8 2 4    8 6 2    4 2 5    8   3    7   4
  7 6 5    7 6 5      7 5    8 7 6    6 5 4    6 5 3
  goal       A        B        C        D        E

    Run the program as shown below: 

       >python
   from Search import *
   SolveIt(A, G)
   SolveIt(B, G)
   etc.

    Make sure to test ALL three searches.

  2. Modify the UninformedSearch function in Search.py so that it keeps track of the total number of nodes examined, total number of nodes expanded, and the total number of nodes generated during a search. Also, your program should impose a maximum limit of 5000 node expansions on any search, in order to prevent searches from taking too long.

  3. Make a table showing the length of the solution found by BreadthFirst, DepthFirst, and UniformCost searches on the above starting states, as well as the number of nodes examined, expanded and generated. For each, compute the average branching factor. If the search is unsuccessful record that as well. Extra credit: Does changing the order in which the operators are applied in applyOperators() have any effect on the outcome of a search?

  4. Modify the program to do Iterative Deepening Search. You will need to alter the Node to also keep track of the level (although this is the same as the value of Node.g). You will write a function, IterativeDepthFirst and modify UninformedSearch to a new version called IterativeUninformedSearch that takes an additional parameter that specifies the depth limit. When a solution is found, it should also output the depth where it was found. How does the total number of nodes examined, expanded, and generated compare with that of other searches?

Hand in a printed report with a narrative based on your findings and a printout of all the code you modified. Do not hand in code that was provided that remained unchanged. Highlight the changes in the printout. Your narrative (and implementation) of the extra credit assignment.

Discussion/Q&A:

Start with your questions here...