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

• electronically: your ep-heuristic function (along with your ep-manhattan function) to the directory /dept/cs/ai/submit3

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 heuristic

• 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 example.

• whether your heuristic is monotonic or not. Explain why or why not.
##### 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:
• the number of nodes expanded
• the computation time to find a solution
• whether it finds the optimal solution
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:

• 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 value.

• 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
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:
• 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 by ABSOLVER).

• 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 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