8-puzzle Iterative Deepening

The goal of this assignment is to implement A* search for the 8-puzzle. There key observation is that it is dramatically faster than iterative deepening, despite the fact that iterative deepening isn’t even really much slower than BFS/DFS.

This assignment is to be done individually. You can talk to other people in the class, me (Dave), the prefect, and lab assistants for ideas and to gain assistance. You can help each other debug programs, if you wish. The code that you write should be your own, however, and you shouldn’t hand a printout of your program to others. See the course syllabus for more details or just ask me if I can clarify.

This assignment does, however, build on some work that you may have done with a partner (iterative deepening). For summarizing your timing results, you can and should use the iterative deepening code that you wrote with your partner. Likewise, you can certainly use your shared code as a starting point if you find it helpful for coding A* search.

Write the function astar(state,heuristic), which uses A* search with the provided heuristic to perform the same task as the part above. That’s the only difference from the previous assignment; you should otherwise follow all the other directions from the iterative deepening assignment regarding helper functions, order of node expansion, and duplicate states apply here as well.

In order to implement A* search, you’ll need to use a priority queue. The easiest way to go is to use Python’s built-in priority queue. If you’d like to see some sample code on how to do so easily, look at the this sample code in the Python heapq documentation, right after the heapsort example.

You’ll need the heuristic code that you wrote for the first assignment (i.e., the number of wrong tiles, and the Manhattan distance functions). If you were unable to make these work, you can borrow a version from another student (make sure to cite them appropriately!) or you can ask me and I’ll supply them for you.

I have also supplied a file titled itstar-test.py which will test your functions that you have written. You can run it via the command python astar-test.py.

Run the test code I’ve provided, which will use both heuristics. Make sure that the solution produced looks valid. Compare the running time across both heuristics, and compare with iterative deepening from the previous assignment. Indicate what you’ve learned about the relative timing in a readme.txt file that summarizes the results.

Here’s how we will grade this assignment:

You will receive a grade M (meets expectations) for this assignment if…

• when we run python astar-test.py, your program passes the tests.
• the solutions produced are in fact valid solutions.
• when we look at your code, it appears to us that you have coded A* search. Specifically, we will look for either use of a priority queue, and we will make our best attempt to do a quick scan of your code to make sure it looks like you are implementing the correct algorithm.
• your program is written to work in general, and not to only work for the specific tests that we have provided.
• we see the expected behavior when comparing the results for the two different heuristics.

You will receive a grade of E (exemplary) for this assignment if you satisfy the above M requirements, and …

• your code demonstrates a clear sequence of actions to achieve the goal at hand, and each piece is essential. Your code does not have notably more cases or conditions than it needs to.
• Your readme.txt file contains timing measurements that are consistent with the expected behavior.

You should submit your search.py and your readme.txt files via Moodle. Do not put your name in the file; we are going to grade the assignments anonymously, where Moodle will keep track of who you are but we won’t know until we’re done grading.