PROGRAMMING PROJECT #2

SOLVING 8-PUZZLES BY SEARCH

1. Write a program (preferably in Lisp :-) that can use a variety of search methods to solve 8-puzzles. The program should take as input an initial state, a goal state (or goal-state test), a search method, and (if appropriate) a heuristic function. You should use at least the following search methods:
   • depth-first (or depth-limited),
   • breadth-first,
   • uniform cost,
   • best-first,
   • A*.

   For best-first and for A*, you should use the three different hs that we discussed in lecture, namely:

   • h_a(n) = W(n) = number of misplaced tiles in node n

   • h_b(n) = P(n) = sum of city-block ("Manhattan") distances that each tile is from its goal-state location

   • h_c(n) = P(n) + 3*S(n), where S(n) = the sequence score =
     for all non-central tiles, if it is not followed by correct successor, score 2 else score 0, & if central tile is not blank, then it scores 1.

   For more information on this heuristic, see the following documents in PDF format that I've put on the Web (also available in SEL):

   • Nilsson, Nils J. (1971), Problem-Solving Methods in Artificial Intelligence (New York: McGraw-Hill): 65-68. (SEL Q335 .N52 1971; on reserve at SEL)

   • Doran, J. E., & Michie, D. (1966), "Experiments with the Graph Traverser Program", Proceedings of the Royal Society of London, Series A. Mathematical and Physical Sciences 294: 235-259, esp. pp. 242-250. (SEL Q41 .R66)

2. For output, your program should be able to do at least the following 2 things:

   • In a "problem-solving" mode, it should print the sequence of states from the initial state to the goal state.

   • In a "verbose" (or "debugging" or "analysis") mode, it should output the entire search tree, with the chosen states highlighted in some way.

   Note that the output can be character-based; i.e., it need not use any fancy graphics.

3. For each search method and each heuristic function, analyze how efficiently it solves the problem. This does not have to be a formal, big-O-style analysis such as you would do in CSE 431/531 (although that would be nice!); an informal comparison will suffice for this project.

4. You should (preferably) write your entire program from scratch. However, you may instead decide to use (or modify) off-the-shelf algorithms. If you do, then, first, you must acknowledge and cite the source of these algorithms, and, second, you must do one of the following variations:

   • Implement one or more other search methods (e.g., iterative deepening, bidirectional, IDA*, SMA*, hill-climbing, etc.) and analyze the performance of your program on them.

   • Extend your algorithm to 15-puzzles (i.e., which use a 4x4 array, rather than a 3x3 array).

5. As usual, your report should be in the form of a paper (e.g., a conference paper), with the annotated code and documented sample runs as an appendix, or embedded in the body of the paper, whichever seems more appropriate For stylistic suggestions, see "Instructions for Word-Processed or Typed Papers".

6. To help you in preparing your report, here are the things we'll be looking for:

   Following both the requirements for projects as stated in the syllabus and the requirements for this project, there are 3 major items of roughly equal importance:

   • the project description
   • annotated sample runs
   • documented code

   Here's the breakdown:

   project description:

   • description of project 2 (including an abstract!)
   • description of representation of 8-puzzle
   • analysis of efficiency of various search procedures
   (all 3 items above of roughly equal importance)

   optional: bug report (if your program doesn't work, you can recoup lost points by explaining your problems and how you might solve them with more time)

   annotated sample runs:

   • depth-first: run & annotation
   • breadth-first: run & annotation
   • uniform cost: run & annotation
   • best-first, h_a: run & annotation
   • best-first, h_b: run & annotation
   • best-first, h_c: run & annotation
   • A*, h_a: run & annotation
   • A*, h_b: run & annotation
   • A*, h_c: run & annotation
   (each of the above of roughly equal importance)

   documented code:

   IF you used your own, original code, THEN:
   • representation of 8-puzzle: code & documentation
   • depth-first: code & documentation
   • breadth-first: code & documentation
   • uniform cost: code & documentation
   • best-first: code & documentation
   • A*: code & documentation
   • h_b: code & documentation
   • h_b: code & documentation
   • h_c: code & documentation

     ELSIF if you used "borrowed" code, THEN:

     (a)

   • representation of 8-puzzle: citation for source & documentation
   • depth-first: citation for source & documentation
   • breadth-first: citation for source & documentation
   • uniform cost: citation for source & documentation
   • best-first: citation for source & documentation
   • A*: citation for source & documentation
   • h_a: citation for source & documentation
   • h_b: citation for source & documentation
   • h_c: citation for source & documentation
   (each of the above of roughly equal importance)

   (b) PLUS:

   variation (other search or 15-puzzle): code, documentation, run, & annotation

   (each of the above of roughly equal importance)

DUE AT START OF LECTURE, FRI, MAR 8 CODE TO BE SUBMITTED BY START OF LECTURE, FRI, MAR 8