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:
The file 8pdisp.lsp is compiled from 8pdisplay.lsp.