Assignment 3 information

• Announcements
• Support code
• Tips
• Links
• Eight puzzle heuristics
• Challenge problem

• [9/30] When I said "take advantage that your [ep-heuristic] procedure only has to work for the eight puzzle," I meant that you can assume:
  • The geometry of the puzzle is 3 rows and 3 columns
  • The tiles will all be numbers

  Do not assume any specific goal state.

• [9/29] The sbp-manhattan Oracle is up!

• [9/29] The web tester/sumbission pages are up!

• [9/29] All heuristics for this assignment have two arguments: state and goal. These should be more properly named current-state and goal-state. (It doesn't matter what you name the arguments to your procedure; this is just a clarification of what they are.) You heuristic should return an estimate of the cost from the currenvt state to the goal state.

• [9/28] I'm still putting the web tester together. I'll be finishing it tonight and sending it off to Paul to put it on the web server.

• [9/26] Corrected 9/21 announcement on A* (I said at the beginning of the second iteration of A*, nodes A and B should be on the OPEN list. That should be nodes A and D.)

• [9/25] For problem 3, your procedure should be named sbp-manhattan. (It is misspelled in the assignment handout.)

• [9/24] I've released a (slightly) new version of the A* code. The only difference is that this code will properly tell you if no path is found rather than causing an error. This shouldn't be a problem because all the problems I've given you have solutions. However, if you sbp-children procedure isn't working properly, you would get an error in the old version.

  Also note that I took the "Panama Canal" problem out of the a3tests.scm file because it did not satisfy the assumptions of having unique tiles. This is one of the examples for the challenge problem, however.

• [9/24] Challenge problem is up!

• [9/22] Support code for DrScheme is now available. Again, this was delayed because of differences in the support for hash tables and weight balanced trees in DrScheme and MIT Scheme.

• [9/22] Here's a revision of the announcement from 9/20 (now removed) about how to use the support code from your program file.

  • DO NOT copy provided support code into the file that you will eventually turn in. This just makes your file bigger than it has to be and could mess things up with the web tester if I use a special version of the support code for running tests.

  • INSTEAD, load the support code from your file. That way, you don't have to manually load it yourself.

  • It seems that DrScheme requires you to specify the file extension for the load command. MIT Scheme does not require the extension (because it will load a compiled file if it is there but will otherwise load the source code). Also note that the extension for DrScheme compiled code is different than for MIT Scheme.

  • Thus, your file should look like this:

    ; Joe Student
    ; CSCI 4150 Introduction to Artificial Intelligence, Fall 2001
    ; Assignment 3
    
    (load "a3code")
    (load "a3tests")
    ; comment out above and uncomment below for DrScheme
    ;(load "a3code.zo")
    ;(load "a3tests.scm")
    
    ; Problem 2
    ;
    (define (sbp-children s)
      )
    
    ; Problem 3
    ;
    (define (sbp-manhattan state goal)
      )
    
    ; Problem 4
    ;
    (define (ep-heuristic state goal)
      )
    

• [9/22] You can assume that a sliding block puzzle has more than one row and more than one column.

• [9/22] Manhattan distance is the sum of horizontal and vertical distance. For example, in the eight puzzle, the manhattan distance between the top left corner and the bottom right corner is 4. The manhattan distance between the center and the lower left corner is 2. We'll talk more about this heuristic for the eight puzzle in class on Monday.

• [9/21] Several corrections/clarifications on problem 1:
  • I forgot to put h(S) = 9.0 in the table for the heuristic value.

  • The wording of the last sentence is not exactly what I intended. Instead of showing which nodes are on the OPEN and CLOSED lists after each step of the search, show the contents of these lists at the beginning of each iteration. So, at the beginning of the first iteration, the node S is on the OPEN list, and the CLOSED list is empty. At the beginning of the second iteration, node S is on the CLOSED list, and nodes A and D are on the OPEN list.

  • Show the f() value and the path for each node on the OPEN and CLOSED list for each iteration. For any new or updated node on the OPEN or CLOSED list, show the g() and h() values used to compute the f() value.

  • In class, I said that you could ignore children that went back to the grandparent, but I take back that statement. However, you will see that this will make no difference in the contents of the lists which you must record at each iteration.

• [9/20] The web tester will be up and running for this assignment, so make sure you have your CS account and kerberos password. We'll put up a "web tester testing" page so you can try it out...

1. a3code --- this file contains code for the A* search. (Current version is 1.1 released 9/24).

   This code contains a reasonably efficient implementation of the A* search which uses hash tables for the OPEN and CLOSED lists. A priority queue (implemented with a weight balanced tree) is also used to implement the OPEN list. This implementation is somewhat customized for working with the representation for sliding block puzzles.

   • a3code.com for MIT Scheme; this is compiled code! See the announcements on how to load this file from your code.

   • a3code.zo for DrScheme; this is compiled code! See the announcements on how to load this file from your code.

     To use this code for DrScheme, you will need SLIB, a library of data structures and other stuff in Scheme. Here's what you need to do:

     • Download slib2d2.zip. (There is a RPM file available for Linux systems, but it produced errors while installing for me.)

     • For Windows users: unzip the file in the folder c:\Program Files\PLT\collects. It will create an slib folder with a lot of files in it.

     • For Linux/FreeBSD users: you could unzip this file in /usr/local/lib/plt-103p1/collects/, but a more standard location for it would be in /usr/share/ (because this source code library can be used by different Scheme implementations). In either case, it will create an slib directory with a lot of files in it.

       If you put the files in /usr/share, you will have to add the line export SCHEME_LIBRARY_PATH=/usr/share/slib in your .bashrc.

       The first time you try to run it, it will want to create the file /usr/local/lib/plt-103p1/slibcat, so make sure you have temporary write access to that directory.

     • You must use "Full Scheme" and you must select the "MzScheme" option.

2. a3tests.scm --- this file contains some tests and sample inputs which you can use to run your code

For those of you using MIT Scheme, you will need to increase the amount of memory for your Scheme process in order to solve some of these problems. You should increase the heap size to something like 4096 (that's 4096 K-words of memory; the default is somwhere around 100 or 300) by doing one of the following

• running from the command line, add the switch -heap 4096
• running from gnu-emacs, add the line (setq scheme-program-arguments "-heap 4096") in your .emacs file (after you have loaded the xscheme library). You could also do a M-x set-variable <RET> VAR <RET> VALUE <RET>
• for Edwin, you will have to add the switch -heap 4096 either by editing the properties of your shortcut (for Windows users) or changing your alias or command line for UNIX users

• Don't worry too much about efficiency (within reason) --- correctness is more important.

• I have a few suggestions for procedures that would be useful in your solution. (However, you might decide to structure your solution differently.)
  • a procedure that finds the "coordinates" of a specified tile
  • a procedure that replaces a tile at given "coordinates" with a given tile

  Remember that your solution should work for a sliding block puzzle of any geometry.

• Your heuristic need not be admissible. As the text puts it, it can be much faster to find a nonoptimal solution than it is to find an optimal solution. The trade-off is speed versus optimality.

• Although you can implement one of these know heuristics, I'd encourage you to create your own. The manhattan distance heuristic is pretty good, so I'd encourage you to either try one of the more sophisticated admissible heuristics or to try finding a fast nonadmissible heuristic.

• Take advantage of the fact that your heuristic only has to work for the eight puzzle (and not for a general sliding block puzzle).

• I'll announce in a day or two how your heuristic will be tested, i.e. what the tradeoff will be between optimality and speed.

In class on Thursday 9/27, we'll talk about how heuristics can be generated by starting with a formal description of a problem and removing some of the constraints.

Here are some heuristics:

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

  This involves doing a search to solve these two simplified puzzles.

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

• Number of tiles out of row plus number of tiles 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.

+-------------+        +-------------+
| C A N A M A |   ==>  | P A N A M A |
| P A N A L   |   ==>  | C A N A L   |
+-------------+        +-------------+

+---------+       +---------+
| R A T E |       | R A T E |
| Y O U R |  ==>  | Y O U R |
| M I N D |  ==>  | M I N D |
| P A L   |       | P L A   |
+---------+       +---------+

+-------------+       +-------------+
|  1  2  3  4 |       |  1  2  3  4 |
|  5  6  7  8 |  ==>  |  5  6  7  8 |
|  9 10 11 12 |  ==>  |  9 10 11 12 |
| 13 14 15    |       | 13 15 14    |
+-------------+       +-------------+

One simple heuristic for puzzles with multiple identical tiles is to take the minimum manhattan distance from a tile in the current state to any copy of that tile in the goal state. This heuristic is admissible, but certainly a better heuristic can be designed!

For this challenge problem, write at least one of the following procedures:

• (multi-heuristic state goal) which is a general purpose heuristic for any sliding block puzzle with multiple identical tiles,
• (pc-heuristic state goal) with a heuristic specifically for the "Panama Canal" problem,
• (rym-heuristic state goal) with a heuristic specifically for the "Rate Your Mind" problem.

Turn in this code separately from the rest of your assignment. In the comments of your code:

• Describe how each heuristic works
• Tell whether it is admissible or not (and why)

Testing for this problem will be done offline, so you will not get any immediate feedback from the web tester. You could just implement the heuristic described above, but you'd get more points if you make up your own (hopefully better) heuristic. Writing a non-admissible heursitic is fine, though it should find a solution faster than an admissible heuristic. Here is a Scheme source code file which contains the two problems above:

• challenge.scm

• the Sliding block home page which has classic as well as modern puzzles. Many have been implemented in Java applets so you can play them on your computer.

• the Sliding block puzzles introduction page which has a number of puzzles, but no applets.