In the current assignment, you'll implement several other search algorithms and compare how they perform. You'll be producing a separate Python file for each new algorithm implementation, and you'll also modify one of the given problem formulation files. In addition, you'll produce a report file in .pdf format that contains answers to some questions. Each of the files you turn in will have a file name that begins with your UWNetID and the rest of the file name is specified according to what part of the assignment it is for.

Do the following:

1. Preparation (10 points).

   Run the starter code with the Towers of Hanoi problem formulation given in Assignment 2. Here, make sure the number of disks in the problem is 4. Note the reported statistics at the end of the run, including the number of nodes expanded, the length of the solution path found, and the MAX_OPEN_LENGTH value. In your Report document, include a section "Item 1: DFS Performance". In this section, write a short paragraph of complete English sentences, describing each of these statistics and what they mean. For each one, mention why it is important when comparing alternative search algorithms.

2. Implement Breadth-First Search (10 points).

   Make a copy of the ItrDFS.py file, and name it using your own UWNetID as YourUWNetID_BreadthFS.py. Edit this file so that it implements Breadth-First Search. The resulting code should follow the algorithm description in Slide 8 of the "Basic Search Algorithms" lecture. Test your implementation using the Towers of Hanoi puzzle with 4 disks.

   Hint: the solution path should have length 15.

3. Implement Iterative-Deepening Depth-First Search (10 points).

   Starting with your code from the previous problem, create a new file YourUWNetID_IDDFS.py that implements Iterative-Deepening Depth-First Search. As with your Breadth-First Search implementation, show the states on a shortest solution path for the Towers of Hanoi puzzle with 4 disks. (The path should still have length 15.)

4. Results of Blind Search on TOH (10 points).

   In your Report document, include a section "Item 4: Alternative Search Methods for the Towers of Hanoi". In this section provide a table that has one row for each of the three algorithms above (Iterative depth-first search, breadth-first search, and iterative-deepening depth-first search) and a column for each of the following: Algorithm name, Length of solution path, Number of nodes expanded, MAX_OPEN_LENGTH.

5. Statistics for Your Own A2 Formulations (10 points).

   Using your own two formulations from Assignment 2, determine the same statistics as in the previous part. Then create an "Item 5: Blind Search on My A2 Problem Formulations" section of your report. Include in this section a pair of tables. The first should be for the problem of the Farmer, Fox, etc. The second should be for Find the Number. Clearly label each of these two tables with its problem name. Then, include in each table the same row and column labels as in the previous part, but fill in the new data from your runs of the search algorithms with your problem formulations.

6. A-Star Implementation (20 points).

   Implement an A* search program by modifying a copy of the same starter code used above. This program, like ItrDFS.py, will accept as a command-line argument the name of a problem template such as EightPuzzle but will also accept (a) the name of a heuristic evaluation function to use in the AStar search and (b) the name of a puzzle instance file that contains a particular initial state [BUT SEE UPDATES AT THE END OF THIS FILE FOR AN EASIER ALTERNATIVE WAY TO INPUT PUZZLES.] For example

   python3 AStar.py EightPuzzleWithHeuristics h_euclidean puzzle2a
   

   The contents of puzzle2a.py would have this form:

   CREATE_INITIAL_STATE = lambda x: [3, 1, 2, 4, 0, 5, 6, 7, 8]
   

   In your A* implementation, make the value of your OPEN variable be a priority queue instance based on the module we are providing. That is, your program should import the priority-queue module that is available here. It uses another module called heapdictB, available here, and provided you have placed copies of both of these in the same folder as your search algorithm implementation, the importing should work. If you inspect the file priorityQB.py, you can see the names of its methods, and then you can call these methods in your code.
7. Implementing Heuristics (10 points).

   Implement four heuristic evaluation functions for the Eight Puzzle: h_euclidean, h_hamming, h_manhattan, and h_custom. The first should compute the euclidean distance for each of the eight tiles from its location in the state to its location in the goal state. Then it should add up these distances and return that sum. The second function should determine the number of tiles that, in the state, are not where they should end up in the goal state. (The maximum value of this heuristic is 8, in the case that none of the eight tiles is where it belongs.) The third function should find, for each tile, how many rows it is away from its goal-state row plus how many columns it is away from its goal-state column, and it should add those distances for each of the tiles.

   The fourth heuristic is one that you should design yourself. You should design it to be admissible. Ideally, it will outperform the others. However, it might simply offer a variation or combination of the others. (It must perform differently from any of the others.)

   Include these in a new version of the Eight puzzle formulation, using your own file name constructed as follows: YourUWNetID_EightPuzzleWithHeuristics.py. Define the actual heuristic functions as methods in your State class. The methods should have the following signatures:

     h_euclidean(self):
     h_hamming(self):
     h_manhattan(self):
     h_custom(self):
   

8. Comparing Heuristics (10 points).

   Create a report section called "Item 8: Heuristics for the Eight Puzzle". Compare the performance of these heuristics on each of the example puzzles (given below). For each puzzle-heuristic pair, report whether the puzzle was successfully solved and also report the count of states processed (taken off of OPEN and put on CLOSED). Put this information into the table. The table should have a row for each puzzle instance and columns for the following: puzzle instance name, puzzle instance permutation, success (yes/no), count of expanded nodes, aborted (yes/no). If it takes more than 30 seconds to solve a particular problem with a particular heuristic then note that; you may abort such runs.

9. Evaluating Your Custom Heuristic (10 points).

   Create a report item: "Item 9: Evaluating my Custom Heuristic." (a) First explain how your heuristic works, and the thinking behind it. (b) Second tell whether it actually outperforms any of the other heuristics in terms of lowering the number of expanded states while still solving the problem. (c) Finally, discuss how you believe the computational cost of computing your heuristic compares with the cost of computing the others.

puzzle10a.py:
CREATE_INITIAL_STATE = lambda: State([4, 5, 0, 1, 2, 3, 6, 7, 8])

puzzle12a.py:
CREATE_INITIAL_STATE = lambda: State([3, 1, 2, 6, 8, 7, 5, 4, 0])

puzzle14a.py:
CREATE_INITIAL_STATE = lambda: State([4, 5, 0, 1, 2, 8, 3, 7, 6])

puzzle16a.py:
CREATE_INITIAL_STATE = lambda: State([0, 8, 2, 1, 7, 4, 3, 6, 5])

Each of your Python files should begin with a multiline string that gives, on the first line, your name and UWNetID.

Here is a list of the files to turn in. However, be sure to replace "YourUWNetID" by your own UWNetID in each filename that contains it.

YourUWNetID_BreadthFS.py
YourUWNetID_IDDFS.py
YourUWNetID_EightPuzzleWithHeuristics.py
YourUWNetID_AStar.py
YourUWNetID_A3_Report.pdf

We are going back to Catalyst CollectIt for A3. It's more convenient for the graders to provide feedback through this tool than using Google Forms. Here is the dropbox link.

(Jan. 24) As posted in GoPost: Here is an alternative and simpler method for loading puzzle instances that we will accept in A3. (The method that has been described in the spec worked better in a previous version of the assignment.)

Instead of mentioning the puzzle-file name, simply give a string in the following form to represent the puzzle instance. You can then access it from the sys.argv array, evaluate it to get a list, and pass that into the State constructor to get your initial state.

python3 AStar.py EightPuzzleWithHeuristics h_euclidean "[3, 1, 2, 4, 0, 5, 6, 7, 8]"

(Jan. 23) Here is a link to the EightPuzzle.py formulation file. It has the State __init__ method modified slightly to allow both flat and list-of-list arguments, so you won't have to modify it to work with the sample puzzles that you read in based on command-line arguments. (posted at 10:36 AM, Tues., Jan. 23).

The two support files for the A* implementation were updated and renamed to priorityQB.py and heapdictB.py on Jan. 20. A new method called getEnqueuedElement is provided by priorityQB.py that facilitates implementing A* by making it easier to separately access an old version of a state from an equivalent new version. (This is needed when updating the g value of a state upon re-reaching the state by a new path.)

If necessary, additional updates and corrections will be posted here and/or mentioned in class or on GoPost.

After submitting your solution, please answer this survey