Assignment 3

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

Problem 4b
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:

Problem 4c
Do not do this problem. It was a "bonus problem" and is now basically superseded by Problem 4b.

A prize

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 suboptimal solutions.

Heuristics

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 4.2.

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.

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:

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 command:

(print-gc-statistics)
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.

whuang@cs.rpi.edu
Last updates: September 14; September 16, 1999