CS 381K: Heuristic Search: 8 Puzzle

Due: October 15, 2007.

Introduction

This assignment is to investigate several state space search algorithms as applied to the 8-puzzle. The 8-puzzle is a small board game for a single player; it consists of 8 square tiles numbered 1 through 8 and one blank space on a 3 x 3 board. (A 15-puzzle, using a 4 x 4 board, is commonly sold as a child's puzzle. We will use an 8-puzzle to keep the search space reasonable.) Moves of the puzzle are made by sliding an adjacent tile into the position occupied by the blank space, which has the effect of exchanging the positions of the tile and blank space. Only tiles that are horizontally or vertically adjacent (not diagonally adjacent) may be moved into the blank space.

Problem Analysis

First, answer the following questions:

What is the number of possible states of the board?
What is the average number of possible moves from a given position of the board?
Estimate how many moves might be required for an optimal (minimum number of moves) solution to a ``worst-case'' problem (maximum distance between starting and goal states). Explain how you made your estimate.
Assuming the answer to question #2 is the ``average branching factor'' and a depth as in the answer to question #3, estimate the number of nodes that would have to be examined to find an answer by brute force (blind) depth-first search.
Assuming that your computer can examine one move per microsecond, how long would such a blind-search solution to the problem require?
Should a depth-first search program for this problem check for duplicated states and consider a duplicated state to be a failure node? Calculate the effect such a test would have on the answers to questions #4 and #5.
The ``worst'' example problem given below is actually one of the easiest for humans to solve. Why do you think that is the case? What lessons for AI programs are suggested by this difference between human performance and performance of your search program?

Programming Assignment

Code for a representation for the state of an 8-puzzle and functions to generate the legal moves and to apply an operator to a given state are provided in the file /projects/cs381k/8puzzle.lsp . Implement the following search algorithms and test them on the start states and goal state shown below; in each case, measure and print out the number of nodes examined and the total time required to solve the puzzle, as well as the sequence of moves to solve the problem.

Goal:        Easy:        Medium:        Hard:        Worst:

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

Depth-first blind search, with testing for duplicate states.
Bounded depth-first search, with testing for duplicate states.
Iterative Deepening search, with testing for duplicate states.
Iterative Deepening A* (IDA*) search, using the heuristic function h = sum of Manhattan distances between all tiles and their correct positions. (Manhattan distance is the sum of the x distance and y distance magnitudes.)
Uniform-cost (breadth-first) search with no heuristic information (h = 0).
Heuristic search using the heuristic function h = number of tiles that are not in the correct place (not counting the blank).
Heuristic search using the Manhattan heuristic function.
Heuristic search using the heuristic function h = (sum of Manhattan distances) * 2.

Note that there should only be two basic search functions (depth-first and breadth-first), of which the searches listed above are parameter variations. If any of these searches is too long to be completed successfully, so state (just be sure you are right!). Suggested top-level interfaces for these functions are:

(bfs board #'hfn)        ; breadth-first with heuristic function hfn
(dfs board n)            ; depth-first search with depth bound n
(itdeep board)           ; iterative deepening
(ida* board #'hfn )      ; iterative deepening A* with heuristic hfn

(defun hf0 (board g) 0)  ; trivial heuristic function, returns 0

For cases #6 and #7, measure the amount of time per node taken by your heuristic function. What fraction of the total time was consumed by the heuristic function? Was it worth it, compared to the previous (weaker but more easily computed) heuristic function? Briefly discuss the relative merits of ``dumb but fast'' and ``smart but slow'' heuristics. If given the opportunity to have special-purpose parallel hardware for a fairly difficult problem (say, chess), would it be better to use this hardware to do search in parallel, thus allowing more move sequences to be searched, or to use an equal amount of hardware to compute a smarter heuristic function, thus searching fewer but more wisely chosen sequences of moves? Explain your answer.

Compare heuristics #7 and #8 in terms of time required and quality of the solution.

8-Puzzle Animation Program

Functions have been written that allow 8-puzzle boards to be displayed graphically under XGCL Lisp. You may use these if you wish. Just after starting XGCL (/p/bin/xgcl) and before loading your files, enter: (load "/projects/cs381k/8pdisp.lsp") . The display function is:

(display-solution start-board moves) This function will display a solution one step at a time. moves is a list of moves. In order to use this function, you must define the function:
```
     (make-move board move)
```
that will make one move and return the resulting board. Example:
```
     (display-solution *easy* (dfs *easy* 5))
```

The file 8pdisp.lsp is compiled from 8pdisplay.lsp.