Part VI: Compare algorithms, and try to speed things up!
In this last part of the project, you will write code to
facilitate the comparison of the different state-space search
algorithms, and you will also attempt to speed things up so that
your code can more easily solve puzzles that require many
moves.
Your tasks
In eight_puzzle.py, write a function
named process_file(filename, algorithm,
param). It should take the following three inputs:
a string filename specifying the name of a text file
in which each line is a digit string for an eight puzzle. For
example, here is a sample file containing 10 digit strings, each of
which represents an eight puzzle that can be solved in 10
moves: 10_moves.txt
a string algorithm that specifies which state-space
search algorithm should be used to solve the puzzles
('random', 'BFS', 'DFS', 'Greedy', or 'A*')
a third input param that allows you to specify a
parameter for the searcher – either a depth limit (for the
uninformed search algorithms) or a choice of heuristic function
(for the informed search algorithms).
Your function should open the file with the
specified filename for reading, and it should use a loop
to process the file one line at a time. We discussed line-by-line
file processing earlier in the semester.
For each line of the file, the function should:
obtain the digit string on that line (stripping off the newline
at the end of the line)
take the steps needed to solve the eight puzzle for that digit
string using the algorithm and parameter specified by the second
and third inputs to the function
report the number of moves in the solution, and the number of
states tested during the search for a solution
In addition, the function should perform the cumulative
computations needed to report the following summary statistics
after processing the entire file:
number of puzzles solved
average number of moves in the solutions
average number of states tested
For example:
>>> process_file('10_moves.txt', 'BFS', -1)
125637084: 10 moves, 661 states tested
432601785: 10 moves, 1172 states tested
025318467: 10 moves, 534 states tested
134602785: 10 moves, 728 states tested
341762085: 10 moves, 578 states tested
125608437: 10 moves, 827 states tested
540132678: 10 moves, 822 states tested
174382650: 10 moves, 692 states tested
154328067: 10 moves, 801 states tested
245108367: 10 moves, 659 states tested
solved 10 puzzles
averages: 10.0 moves, 747.4 states tested
(In this case, because BFS finds optimal solutions, every
solution has the same number of moves, but for other algorithms
this won’t necessarily be the case.)
Notes/hints:
You can model your code for solving a given puzzle on the code
that we’ve given you in the eight_puzzle driver function.
In particular, you can emulate the way that this function:
creates Board and State objects for the
initial state
calls the create_searcher helper function to create
the necessary type of searcher object, and handles the possible
return value of None from that function
Important: Make sure to create a new
searcher object for each puzzle (i.e., for each line of the file).
Otherwise, the searcher will still have information inside it from
previous searches when it starts to solve a new puzzle.
When calling the searcher
object’s find_solution method, you should do so as
follows:
soln = None
try:
soln = searcher.find_solution(s)
except KeyboardInterrupt:
print('search terminated, ', end='')
Making the call to find_solution() in this way will
allow you to terminate a search that goes on too long by
using Ctrl-C. In such
cases, soln will end up with a value
of None (meaning that no solution was found), and you
should make sure to properly handle such cases.
You should not use a timer
in this function.
This function
should not return a value.
Testing your function:
If you haven’t already done so, download
the 10_moves.txt file, putting it in the same folder as
the rest of your files for the project.
Try to reproduce the results for BFS shown above.
Try applying Greedy Search to the same file. You may find that
it takes Greedy a very long time to solve some of the puzzles, at
least when using h1 (the num-misplaced-tiles heuristic).
If this happens, use Ctrl-C as needed to
terminate the problematic searches. When we
processed 10_moves.txt using our implementation of
Greedy, we ended up using Ctrl-C to
terminate two of the searches:
>>> process_file('10_moves.txt', 'Greedy', h1)
125637084: 204 moves, 658 states tested
432601785: 12 moves, 13 states tested
025318467: search terminated, no solution
134602785: 78 moves, 221 states tested
341762085: 26 moves, 339 states tested
125608437: 162 moves, 560 states tested
540132678: 68 moves, 749 states tested
174382650: search terminated, no solution
154328067: 10 moves, 16 states tested
245108367: 48 moves, 49 states tested
solved 8 puzzles
averages: 76.0 moves, 325.625 states tested
It’s also possible for none of the puzzles to
have a solution, and you should handle that situation
appropriately. For example, this can happen if you impose a depth
limit that is too small:
>>> process_file('10_moves.txt', 'DFS', 5) # depth limit of 5
125637084: no solution
432601785: no solution
025318467: no solution
134602785: no solution
341762085: no solution
125608437: no solution
540132678: no solution
174382650: no solution
154328067: no solution
245108367: no solution
solved 0 puzzles
Note that you can’t compute any averages in this case, so you
shouldn’t print the averages line in the results.
Create a plain-text
file named results.txt, and put your name and
email (and those of your partner, if any) at the top of the
file.
Conduct an initial set of experiments in which you try all of
the algorithms on the puzzles in the following files:
5_moves.txt - puzzles that can be solved in 5 moves
10_moves.txt - puzzles that can be solved in 10 moves
15_moves.txt - puzzles that can be solved in 15 moves
More specifically, you should run the following algorithms on
each file:
random
BFS
DFS with a depth limit of 20
DFS with a depth limit of 50
Greedy (using h1 – the num-misplaced-tiles
heuristic)
A* (using the same heuristic)
Note that it may be necessary to
use Ctrl-C to terminate searches that
take too much time. You might want to pick a given amount of time
(e.g., 30 seconds or 1 minute), and
use Ctrl-C to terminate any search that
doesn’t complete in that time.
In your results.txt file,
create three tables that
summarize the results of these initial experiments. Use a separate
table for each file’s results. For example, the results
for 5_moves.txt should be put into a table that looks
like this:
puzzles with 5-move optimal solutions
-------------------------------------
algorithm num. solved avg. moves avg. states tested
------------------------------------------------------------------------
random
BFS
DFS (depth limit 20)
DFS (depth limit 50)
Greedy Search (using h1)
A* (using h1)
Below these tables, write a short reflection (one or two
paragraphs) in which you summarize the key points that are
illustrated by the results. For example, you might discuss whether
the algorithms produce reliably optimal results, and how much work
they do in finding a solution. There’s no one correct reflection;
we just want to see that you have reflected intelligently on the
results and drawn some conclusions.
Even informed search algorithms like Greedy Search and A* can be
slow on problems that require a large number of moves. This is
especially true if the heuristic function used by the algorithm
doesn’t do a good enough job of estimating the remaining cost to
the goal.
Our h1 heuristic function–which uses the number of
misplaced tiles as the estimate of the remaining cost–is one
example of a less than ideal heuristic. For example, consider the
following two puzzles:
Both of them have 4 misplaced tiles (the ones displayed in red),
but the puzzle on the left can be solved in 4 moves, whereas the
puzzle on the right requires 24 moves! Clearly, it would be better
if our heuristic could do a better job of distinguishing between
these two puzzles.
Come up with at least one alternate heuristic, and implement it
as part of your classes for informed searchers
(GreedySearcher and AStarSearcher). To do so, you should
take the following steps:
As needed, add one or more methods to the Board class
that will be used by your new heuristic function. (Adding a new
method to the Board class
is not required, but it can be helpful to add
one so that the heuristic function can obtain the information
needed for its estimate.)
Add your new heuristic function(s) to searcher.py, and
follow these guidelines:
Continue the numbering scheme that we established for the
earlier heuristic functions. Call your first alternate heuristic
function h2, your next heuristic function (if any) h3,
etc.
Make sure that each heuristic function is a regular function,
not a method. In addition, make sure that it takes a
single State object and returns an integer.
When conducting tests using a new heuristic function, use its
name in the same ways that you would use h0 or h1.
For example:
>>> g = GreedySearcher(h2)
>>> eight_puzzle('142358607', 'Greedy', h2)
>>> process_file('15_moves.txt', 'A*', h2)
You are welcome to design more than one new
heuristic function, although only one is
required.
When testing and refining your heuristic(s), you can use the
files that we provided above, as well as the following files:
18_moves.txt - puzzles that can be solved in 18 moves
21_moves.txt - puzzles that can be solved in 21 moves
24_moves.txt - puzzles that can be solved in 24 moves
27_moves.txt - puzzles that can be solved in 27
moves.
Compare the performance of Greedy and A* using
the h1 heuristic to their performance using your new
heuristic(s). Keep revising your heuristic(s) as needed until you
are satisfied. Ideally, you should see the following when using
your new heuristic(s):
Both Greedy and A* are able to solve puzzles more quickly –
testing fewer states on average and requiring fewer searches to be
terminated.
Greedy Search is able to find solutions requiring fewer
moves.
A* continues to find optimal solutions. (If it starts finding
solutions with more than the optimal number of moves, that probably
means that your heuristic is overestimating the
remaining cost for at least some states.)
Although you are welcome to keep more than one new heuristic
function, we will ultimately test only one of
them. Please adjust your code as needed so that
the heuristic function that you want us to test is
named h2. Also, please make sure that we
will still be able to test the num-misplaced-tiles heuristic if we
specify h1 for the heuristic.
In your results.txt file, briefly describe how your
best new heuristic works:
heuristic h2
------------
This heuristic ...
If your code includes other alternate heuristics, you are
welcome to describe them as well, although doing so is not
required.
Conduct a second set of experiments in which you try both your
new heuristic function(s) and the h1heuristic function on the
puzzles in the four new files provided above (the ones that require
18, 21, 24, and 27 moves).
In your results.txt file, create four
tables that summarize the results of these
experiments. Use a separate table for each file’s results. For
example, the results for 18_moves.txt should be put into
a table that looks like this:
puzzles with 18-move optimal solutions
--------------------------------------
algorithm num. solved avg. moves avg. states tested
----------------------------------------------------------------------
Greedy (heuristic h1)
Greedy (heuristic h2)
# Greedy with any other heuristics
A* (heuristic h1)
A* (heuristic h2)
# Greedy with any other heuristics
Below these tables, write a short reflection (one or two
paragraphs) in which you summarize the key points that are
illustrated by the results. Here again, there is no one correct
reflection; we just want to see that you have reflected
intelligently on the results and drawn some conclusions.
