Instructions for Coding Component of Assignment 2

Experimenting with the 8-puzzle

In this assignment you will explore some heuristic search algorithms.

Group Work

This assignment requires programming in Python. If you feel you need help with the programming work, you may form a group and submit a joint solution. Each group member will receive the same grade. Every group should have at most five members.

Instructions

In the textbook code from Github file search.py, take a look at the class called EightPuzzle. Take some time read and understand it, including the Problem class that it inherits from.

Put the coding part of you answers to the following questions in a Python 3 file named a2.py that starts like this:

# a2.py

from search import *

# ...

Do not use any modules or code except from the standard Python 3 library, or from the textbook code from Github.

Don’t forget: If you get any kind of help from elsewhere, you must cite that fact in your assignment (a comment in the source code is usually fine). Accidentally forgetting to do this is no excuse!

Question 1: Helper Functions¶

10 points total.

Write a function called make_rand_8puzzle() that returns a new instance of an EightPuzzle problem with a random initial state that is solvable. Note that EightPuzzle has a method called check_solvability that you should use to help ensure your initial state is solvable.

Write a function called display(state) that takes an 8-puzzle state (i.e. a tuple that is a permutation of (0, 1, 2, …, 8)) as input and prints a neat and readable representation of it. 0 is the blank, and should be printed as a * character.

For example, if state is (0, 3, 2, 1, 8, 7, 4, 6, 5), then display(state) should print:

* 3 2
1 8 7
4 6 5

Question 2: Comparing Algorithms¶

24 points total.

Create 10 (more would be better!) random 8-puzzle instances (using your code from above), and solve each of them using the algorithms below. Each algorithm should be run on the exact same set of problems to make the comparison fair.

For each solved problem, record:

the total running time in seconds
the length (i.e. number of tiles moved) of the solution
that total number of nodes that were expanded, i.e. removed from frontier

You will probably need to make some modifications to the A* code to get all this data.

Also, be aware that the time it takes to solve random 8-puzzle instances can vary from less than a second to hundreds of seconds — so solving all these problems might take some time!

The algorithms you should test are:

A*-search using the misplaced tile heuristic (this is the default heuristic in the EightPuzzle class). 6 points
A*-search using the Manhattan distance heuristic Please implement your own (correctly working!) version of the Manhattan heuristic. 9 points
- Be careful: there is an incorrect Manhattan distance function in tests/test_search.py. So don’t use that!
A*-search using the max of the misplaced tile heuristic and the Manhattan distance heuristic. 9 points

Also, show the solution and your results for this test instance (0, 3, 2, 1, 8, 7, 4, 5, 6).

Summarize all your data in a single table in a spreadsheet as described below.

Based on your data, which algorithm is the best? Explain how you came to your conclusion.

Validation Instance¶

To see if your heuristics work well, you can use this state as a validation instance, and you should get similar results.

State:

8 2 3
4 1 6
* 7 5

Results:

A* with misplaced-tiles heuristic:

Expanded nodes : 1070
Solution : ['UP', 'RIGHT', 'RIGHT', 'UP', 'LEFT', 'LEFT', 'DOWN', 'DOWN', 'RIGHT', 'UP', 'UP', 'RIGHT', 'DOWN', 'DOWN', 'LEFT', 'UP', 'RIGHT', 'DOWN']
Solution length : 18

A* with manhattan heuristic:

Expanded nodes : 207
Solution : ['UP', 'RIGHT', 'RIGHT', 'UP', 'LEFT', 'LEFT', 'DOWN', 'DOWN', 'RIGHT', 'UP', 'UP', 'RIGHT', 'DOWN', 'DOWN', 'LEFT', 'UP', 'RIGHT', 'DOWN']
Solution length : 18

A* with max-misplaced-manhattan heuristic:

Expanded nodes : 380
Solution : ['UP', 'RIGHT', 'RIGHT', 'UP', 'LEFT', 'LEFT', 'DOWN', 'DOWN', 'RIGHT', 'UP', 'UP', 'RIGHT', 'DOWN', 'DOWN', 'LEFT', 'UP', 'RIGHT', 'DOWN']
Solution length : 18

Presenting Your Results¶

14 points total.

For questions that ask for more than code, please put all your tables, data, and discussion into a standard Excel worksheet file named a2.xlsx. You can use Excel or Google Sheets to create it.

Make the spreadsheet beautiful, informative, and easy to read. Be sure to include helpful descriptive statistics like the min, max, average, and median values.

You are encouraged to include helpful or informative graphs of your data.

Spelling, grammar, and neatness count!

What to Submit¶

Please put all your code into a single Python 3 file named a2.py, and all your data, tables, charts, discussion, etc. in an Excel file named a2.xlsx. Compress these into a single archive named a2.zip, and submit it on coursys.cs.sfu.ca under "Assignment 2 coding" before the due date listed there.

If you want to make changes to code in search.py, or in files other than a2.py, please copy the code you want to change into a2.py, and change it there. Don’t make any changes to other files in the textbook code.

Hints¶

When you are testing your code, you might want to use a few hard-coded problems that don’t take too long to solve. Otherwise, you may spend a lot of time waiting for tests to finish!

One easy way to time code is to use Python’s standard time.time() function, e.g.:

import time

def f():
   start_time = time.time()

   # ... do something ...

   elapsed_time = time.time() - start_time

   print(f'elapsed time (in seconds): {elapsed_time}s')

Python has other ways to do timing, e.g. check out the timeit module.

If you download the textbook code as a Git repository, then you can create a branch called a2 for this assignment, e.g. something like:
```
git branch a2 git checkout a2
```
This way you can make any changes you like while maintaining a copy of the original code.

You are not required to use Git, but since the code is stored as a Git repository, it’s probably the best way to get it.

Created using Sphinx 1.7.9.

Updated Fri Feb. 26 2021, 19:10 by dca124.

Simon Fraser University
Engaging the World

CourSys