The A* code
Here is the code you will need for Assignment 3:
Note that the A* functions are to a large extent hard coded for the
eight puzzle problem. Look at the "test code" to get started. There
have been a few changes in the test code. See the comments for
explanations on how to use the new test code.
Change in Assignment 3
You will still implement a heuristic function for the
eight puzzle. You must implement some heuristic that is more involved
or more intelligent than the number of tiles out of place.
I encourage you to design your own heuristic --- you can create one
from scratch or create some variation on a known heuristic. However,
you may implement a known heuristic; I'll suggest a few later on.
Your heuristic need not be admissible.
You should turn in:
- electronically: your ep-heuristic function (along with
your ep-manhattan function) to the directory
Submit only these functions (and any functions they call directly)
Do not submit the A* code or the test code --- I already have it and it will just take up extra space and cause trouble.
Starting on this assignment, we will deduct for sumbissions that produce errors when loaded into Scheme. (probably a 5% penalty)
- in writitng:
- whether your heuristic is completely original, an original
variation on a known heuristic, or an implementation of a known
- an explanation of your heuristic
- whether your heuristic is admissible or not. If it is
admissible, explain why. If not, explain why not, possibly with an
- whether your heuristic is monotonic or not. Explain why or why not.
Do not do this problem. It was a "bonus problem" and is now basically
superseded by Problem 4b.
I will award a small prize to the best original heuristic. I have not
decided exactly what the test criteria will be, except that it will
involve a combination of:
I may even create two divisions, one for optimal solutions and one for
- the number of nodes expanded
- the computation time to find a solution
- whether it finds the optimal solution
I discussed a few heuristics in class today (Thurs Sept. 16) as well
as how many heuristics can be derived from a formal description of the
problem. This is discussed in a little detail in you text in Section
Here are a few of the heuristics which I described:
Note that some of these heuristics involve performing a search to find
the value of the heuristic. In these cases, you want the additional
time spent evaluating the heuristic to be more than offset by the
decrease in the effective branching factor.
- Nilsson's Sequence Score: h(n) = P(n) + 3 S(n)
P(n) is the manhattan distance of each tile from its proper position.
"The quantity S(n) is a sequence score obtained by
checking around the noncentral squares in turn, allotting 2 for every
tile not followed by its proper successor and 0 for every other tile,
except that a piece in the center scores 1."
This might be easier to understand if you know that the goal state
that Nilsson uses is represented by: (1 2 3 8 space 4 7 6
5). This heuristic is not admissible.
- X-Y: decompose the problem into two one dimensional problems
where the "space" can swap with any tile in an adjacent row/column.
Add the number of steps from the two subproblems.
- Number out of row plus number out of column
- n-MaxSwap: assume you can swap any tile with the "space". Use
the number of steps it takes to solve this problem as the heuristic
- n-Swap: represent the "space" as a tile and assume you can swap
any two tiles. Use the number of steps it takes to solve this problem
as the heuristic value.
- Distance of blank: In terms of the operator/state representation
used today in class:
- drop from xmove: xloc, yloc, ylocb
- drop from ymove: xloc, yloc, xlocb
- factor into X and Y
You could create the "perfect" heuristic by having it perform an A*
search to find the exact number of steps to reach the goal, but I
would not accept this as a good solution to this problem.
Materials on reserve
I have put two readings on reserve in the library in "Homework folder
#3" These are:
- A paper about ABSOLVER, a program that automatically generates
heuristics from formal descriptions of a problem. Almost all the
heuristics above are listed in this paper (either known heuristics
that were derived by ABSOLVER or original heuristics that were created
- A section from "Problem Solving Methods in Artificial
Intelligence" by Nils J. Nilsson, McGraw-Hill, 1971, pp. 53--68. This
includes some formal proofs about the A* algorithm and also includes
Nilsson's Sequence heuristic described above.
Starting scheme with a larger heap
You may find that you run out of memory. On my computer, I am able to
search about 14,000 nodes before running out of memory which should be
more than enough for reasonable problems with a good heuristic.
You can find out how much heap space you have with the scheme
Look for the "heap free" and "heap in use" sizes. By
default, you probably have about 220,000 words.
You can start Scheme with a larger heap either by specifying the flag
-large, which should start you with about 1,000,000 words, or
by specifying a heap size with -heap <blocks>,
where blocks is the number of 1024 word blocks. To start
with a 2-meg word heap, you would use -heap 2048.
For those of you using Windows, you'll have to edit the alias to
add the appropriate flags.
Last updates: September 14; September 16, 1999