Eight Puzzle Problem Sets
Eight Puzzle (Part IV)
100 points; pair-optional and group-of-three-optional
- NOTE: Part IV and the coding portion of Part V should be submitted as Problem Set 19 by 10:00 p.m. EDT on Saturday, November 18, 2023
Important: This assignment builds on PS18
Part IV: Subclasses for other search algorithms
In this part of the assignment you will implement other state-space search algorithms by defining classes for new types of searcher objects.
Uninformed state-space search: BFS and DFS
-
In
searcher.py
, define a class calledBFSearcher
for searcher objects that perform breadth-first search (BFS) instead of random search. As discussed in class, BFS involves always choosing one the untested states that has the smallest depth (i.e., the smallest number of moves from the initial state).This class should be a subclass of the
Searcher
class that you implemented in Part III, and you should take full advantage of inheritance. In particular, you should not need to include any attributes in yourBFSearcher
class, because all of the necessary attributes will be inherited fromSearcher
.Similarly, you should not need to define many methods, because most of necessary functionality is already provided in the methods that are inherited from
Searcher
.However, you will need to do the following:
-
Make sure that your class header specifies that
BFSearcher
inherits fromSearcher
. -
Because all of the attributes of a
BFSearcher
are inherited fromSearcher
, you will not need to define a constructor for this class. Rather, we can just use the constructor that is inherited fromSearcher
. -
Write a method
next_state(self)
that overrides (i.e., replaces) thenext_state
method that is inherited fromSearcher
. Rather than choosing at random from the list of untested states, this version ofnext_state
should follow FIFO (first-in first-out) ordering – choosing the state that has been in the list the longest. In class, we discussed why this leads to breadth-first search. As with the original version ofnext_state
, this version should remove the chosen state from the list of untested states before returning it.
Examples:
>>> b = Board('142358607') >>> s = State(b, None, 'init') >>> s 142358607-init-0 >>> bfs = BFSearcher(-1) >>> bfs.add_state(s) >>> bfs.next_state() # remove the initial state 142358607-init-0 >>> succ = s.generate_successors() >>> succ [142308657-up-1, 142358067-left-1, 142358670-right-1] >>> bfs.add_states(succ) >>> bfs.next_state() 142308657-up-1 >>> bfs.next_state() 142358067-left-1
-
-
In
searcher.py
, define a class calledDFSearcher
for searcher objects that perform depth-first search (DFS) instead of random search. As discussed in class, DFS involves always choosing one the untested states that has the largest depth (i.e., the largest number of moves from the initial state).DFS, the next state to be tested should be one of the ones that has the largest depth in the state-space search tree.
Here again, the class should be a subclass of the
Searcher
class, and you should take full advantage of inheritance. The necessary steps are very similar to the ones that you took forBFSearcher
, but thenext_state()
method should follow LIFO (last-in first-out) ordering – choosing the state that was most recently added to the list.Examples:
>>> b = Board('142358607') >>> s = State(b, None, 'init') >>> s 142358607-init-0 >>> dfs = DFSearcher(-1) >>> dfs.add_state(s) >>> dfs.next_state() # remove the initial state 142358607-init-0 >>> succ = s.generate_successors() >>> succ [142308657-up-1, 142358067-left-1, 142358670-right-1] >>> dfs.add_states(succ) >>> dfs.next_state() # the last one added, not the first! 142358670-right-1 >>> dfs.next_state() 142358067-left-1
-
In
eight_puzzle.py
, there is a helper function calledcreate_searcher
that is used to create the appropriate type of searcher object. Modify this helper function so that it will be able to create objects that perform BFS and DFS. To do so, simply uncomment the lines that handle cases in which thealgorithm
input is'BFS'
or'DFS'
. Once you do so, you should be able to use theeight_puzzle
driver function to test yourBFSearcher
andDFSearcher
classes.Breadth-first search should quickly solve the following puzzle:
>>> eight_puzzle('142358607', 'BFS', -1) BFS: 0.006 seconds, 56 states Found a solution requiring 5 moves. Show the moves (y/n)?
You may get a different time than we did, but the rest of the results should be the same. As discussed in class, BFS finds an optimal solution for eight-puzzle problems, so 5 moves is the fewest possible moves for this particular initial state.
Depth-first search, on the other hand, ends up going deep in the search tree before it finds a goal state:
>>> eight_puzzle('142358607', 'DFS', -1) DFS: 10.85 seconds, 3100 states. Found a solution requiring 3033 moves. Show the moves (y/n)?
Important: In cases like this one in which the solution has an extremely large number of moves, trying to show the moves is likely to cause an error. That’s because our
print_moves_to
method uses recursion, and the number of recursive calls is equal to the number of moves in the solution. Each recursive call adds a new stack frame to the top of the memory stack, and we can end up overflowing the stack when we make that many recursive calls.To get a solution from DFS with fewer moves, we can impose a depth limit by passing it in as the third argument to the
eight_puzzle
function. For example:>>> eight_puzzle('142358607', 'DFS', 25) DFS: 6.945 seconds, 52806 states Found a solution requiring 23 moves. Show the moves (y/n)?
Using a depth limit of 25 keeps DFS from going too far down a bad path, but the resulting solution requires 23 moves, which is still far from optimal!
Informed state-space search: Greedy and A*
-
In
searcher.py
, define a class calledGreedySearcher
for searcher objects that perform greedy search. As discussed in class, greedy search is an informed search algorithms that uses a heuristic function to estimate the remaining cost needed to get from a given state to the goal state (for the Eight Puzzle, this is just an estimate of how many additional moves are needed). Greedy Search uses this heuristic function to assign a priority to each state, and it selects the next state based on those priorities.Once again, this class should be a subclass of the
Searcher
class that you implemented in Part III, and you should take full advantage of inheritance. However, the changes required in this class will be more substantial that the ones inBFSearcher
andDFSearcher
. Among other things,GreedySearcher
objects will have a new attribute calledheuristic
that will allow you to choose among different heuristic functions, and they will also have a new method for computing the priority of a state.Here are the necessary steps:
-
Make sure that your class header specifies that
GreedySearcher
inherits fromSearcher
. -
Define the constructor for the
GreedySearcher
class. Copy the following code into the GreedySearcher class:def __init__(self, depth_limit, heuristic): """ constructor for a GreedySearcher object inputs: * depth_limit - the depth limit of the searcher * heuristic - a reference to the function that should be used when computing the priority of a state """ # add code that calls the superclass constructor self.heuristic = heuristic
Two things worth noting:
-
GreedySearcher
objects have an extra attribute calledheuristic
(and an associated extra input to their constructor). This attribute stores a reference to
which heuristic function theGreedySearcher
should use. We’re not currently using this attribute in ourpriority
method, but ultimately the method will use this attribute to choose between multiple different heuristic functions for estimating aState
‘s remaining cost. If needed, you should review the powerpoint notes about this on Moodle. -
A
GreedySearcher
object’sstates
attribute is not just a list of states. Rather, it is a list of lists, where each sublist is a [priority, state] pair. This will allow aGreedySearcher
to choose its next state based on the priorities of the states.
Example:
>>> b = Board('142358607') >>> s = State(b, None, 'init') >>> g = GreedySearcher(-1, h1) # no depth limit, basic heuristic
-
-
Write a method
priority(self, state)
that takes aState
object calledstate
, and that computes and returns the priority of that state. For now, the method should compute the priority as follows:priority = -1 * num_misplaced_tiles
where
num_misplaced_tiles
is the number of misplaced tiles in theBoard
object associated withstate
. Take advantage of the appropriateBoard
method to determine this value. -
Write a method
add_state(self, state)
that overrides (i.e., replaces) theadd_state
method that is inherited fromSearcher
. Rather than simply adding the specifiedstate
to the list of untested states, the method should add a sublist that is a[priority, state]
pair, wherepriority
is the priority ofstate
, as determined by calling thepriority
method.Examples:
>>> b = Board('142358607') >>> s = State(b, None, 'init') >>> g = GreedySearcher(-1, h1) >>> g.add_state(s) >>> g.states [[-5, 142358607-init-0]] >>> succ = s.generate_successors() >>> g.add_state(succ[0]) >>> g.states [[-5, 142358607-init-0], [-5, 142308657-up-1]] >>> g.add_state(succ[1]) >>> g.states [[-5, 142358607-init-0], [-5, 142308657-up-1], [-6, 142358067-left-1]]
If you don’t see a priority value of -5, check your
priority
method for possible problems.-
Write a method
next_state(self)
that overrides (i.e., replaces) thenext_state
method that is inherited fromSearcher
. This version ofnext_state
should choose one of the states with the highest priority.Hints:
-
You can use
max
to find the sublist with the highest priority. If multiple sublists are tied for the highest priority,max
will choose one of them. -
You should remove the selected sublist from
states
, and you should return only the state component of the sublist – not the entire sublist.
Examples:
>>> b = Board('142358607') >>> s = State(b, None, 'init') >>> g = GreedySearcher(-1, h1) # no depth limit, basic heuristic >>> g.add_state(s) >>> succ = s.generate_successors() >>> g.add_state(succ[1]) >>> g.states [[-5, 142358607-init-0], [-6, 142358067-left-1]] >>> g.next_state() # -5 is the higher priority 142358607-init-0 >>> g.states [[-6, 142358067-left-1]]
-
-
-
In
searcher.py
, define a class calledAStarSearcher
for searcher objects that perform A* search. Like greedy search, A* is an informed search algorithm that assigns a priority to each state based on a heuristic function, and that selects the next state based on those priorities. However, when A* assigns a priority to a state, it also takes into account the cost that has already been expended to get to that state (i.e. the number of moves to that state). More specifically, the priority of a state is computed as follows:priority = -1 * (heuristic + num_moves)
where
heuristic
is the value that the selected heuristic function assigns to the state, andnum_moves
is the number of moves that it took to get to that state from the initial state.Once again, you should take full advantage of inheritance. However, we’re leaving it up to you decide which class to inherit from and how much new, non-inherited code is needed!
Here’s one thing you need to know: When constructing an
AStarSearcher
object, you will need to specify two inputs: (1) function that specifies which heuristic function should be used, and (2) an integer for the depth limit. See below for an example of constructing one.Examples:
>>> b = Board('142358607') >>> s = State(b, None, 'init') >>> a = AStarSearcher(-1, h1) # no depth limit, basic heuristic >>> a.add_state(s) >>> a.states # init state has same priority as in greedy [[-5, 142358607-init-0]] >>> succ = s.generate_successors() >>> a.add_state(succ[1]) >>> a.states # succ[1] has a priority of -1*(6 + 1) = -7 [[-5, 142358607-init-0], [-7, 142358067-left-1]] >>> a.next_state() # -5 is the higher priority 142358607-init-0 >>> a.states [[-7, 142358067-left-1]]
-
Modify the
create_searcher
helper function ineight_puzzle.py
so that it will be able to createGreedySearcher
andAStarSearcher
objects. To do so, simply uncomment the lines that handle cases in which thealgorithm
input is'Greedy'
or'A*'
.After you do so, try using the
eight_puzzle
driver function to see how the informed search algorithms perform on various puzzles. Here are some digit strings for puzzles that you might want to try, along with the number of moves in their optimal solutions:'142358607'
- 5 moves'031642785'
- 8 moves'341682075'
- 10 moves'631074852'
- 15 moves'763401852'
- 18 moves'145803627'
- 20 moves
A* should obtain optimal solutions; Greedy Search may or may not.
If a given algorithm ends up taking longer than you can afford to wait, you can stop it by using Ctrl-C from the keyboard.
Submitting Your Work
The following instructions are for submitting the eight puzzle code, which
should include your work on all parts of the project, including the
modifications to eight_puzzle.py
described in Part V.
You should use Gradescope to submit the following files:
- your final
board.py
file (even if you submitted the same version of the file for PS 17) - your final
state.py
file (even if you submitted the same version of the file for PS 18) - your
searcher.py
file (including any updates in Part V) - your
eight_puzzle.py
file (including any updates in Part V)
Warnings
-
Make sure to use these exact file names, or Gradescope will not accept your files. If Gradescope reports that a file does not have the correct name, you should rename the file using the name listed in the assignment or on the Gradescope upload page.
-
If you make any last-minute changes to one of your Python files (e.g., adding additional comments), you should run the file in VS Code after you make the changes to ensure that it still runs correctly. Even seemingly minor changes can cause your code to become unrunnable.
-
If you submit an unrunnable file, Gradescope will accept your file, but it will not be able to auto-grade it. If time permits, you are strongly encouraged to fix your file and resubmit. Otherwise, your code will fail most if not all of our tests.