8-puzzle Iterative Deepening

The goal of this assignment is to implement iterative deepening for the 8-puzzle. There are two main goals to observe: the first is that the time to run it isn’t really much slower than regular DFS, because the time to run the last iteration is so much longer than the iterations before it. The second goal, which you’ll have to wait until the next assignment for, is that it the A* algorithm will be dramatically faster yet.

This is a pair assignment, which means that if you are working on a team with someone else, you and your partner should do your best to engage in the pair programming model. At any point in time, one of you is “driving,” i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas.

You should not divide the work into individual pieces. In other words, you should not split the assignment and work on different portions. Likewise, you should not work on the assignment without both of you being present.

You should make sure that over the course of an assignment that you spend roughly the same amount of time each “driving.” I will also ask you to turn in a form rating the work that your partner does. My recommendation is to take turns approximately every 15 minutes or so. Set a timer to help you remember.

If you are working in a pair, only one of you needs to submit your work via Moodle.

Write the function itdeep(state), which uses iterative deepening to return the list describing the path that the blank square takes to reach a solution (as demonstrated earlier). Place it again in a file named search.py, but this should be a different file than the one you used for the last assignment. You likely should just create a different directory on your machine to work on this version.

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

You may use helper functions if you like. In fact, I highly recommend it. Iterative deepening is just a loop around regular depth-first search with a depth limit, so my recommendation is to code up depth-first search with a limit as a separate function, and just call it repeatedly from within a loop elsewhere. You’ll find pseudocode describing precisely this, in figure 3.12 (page 81) of the textbook. Note that when coding up depth-first-search, you can do it recursively, or you can do it iteratively via use of a stack. Both approaches work similarly and its really a matter of preference. The textbook pseudocode uses the iterative-with-a-stack approach. You can do it either way, whichever you prefer.

Any time that you need to expand a node, you should use the puzzle8.neighbors(square) function to determine how to do so. If at any time your algorithm must make a choice as to which state to examine next, you should choose the one that appears first in the neighbors list. This way, everyone in the class should get exactly the same answers even though there are multiple possible solutions.

You should not keep track of duplicate states. If the algorithm checks a state more than once, then so be it. This runs slower, but it is easier to code… and because it runs slower, it helps to make it even more dramatic when the A* solution you’ll do for the next assignment runs faster.

Iterative deepening is not significantly slower than regular depth-first search. To see this, run a few experiments where you time how long iterative deepening takes to run the last iteration through, vs how long it takes in total to run repeatedly in getting down to that level. The difference in time should not be dramatic. Submit the results of your experiments in a readme.txt file that you submit with your code.

Here’s how we will grade this assignment:

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

• when we run python itdeep-test.py, your program passes the tests.
• the timing for successive levels appears right, i.e. the timing seems to go up by approximately a factor of 3-4 at each stage. We won’t be measuring this carefully, but we’ll be looking for this rough behavior.
• the solutions produced at each level are in fact valid solutions.
• when we look at your code, it appears to us that you have coded iterative deepening. Specifically, we will look for either use of a stack or recursion (the two approaches for implementing DFS), 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.

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.