Python - Eight Puzzle class Board: \"\"\" A class for objects that represent an
ID: 3820847 • Letter: P
Question
Python - Eight Puzzle class Board: """ A class for objects that represent an Eight Puzzle board. """ def __init__(self, digitstr): """ a constructor for a Board object whose configuration is specified by the input digitstr input: digitstr is a permutation of the digits 0-9 """ # check that digitstr is 9-character string # containing all digits from 0-9 assert(len(digitstr) == 9) for x in range(9): assert(str(x) in digitstr) self.tiles = [[0] * 3 for x in range(3)] self.blank_r = -1 self.blank_c = -1 We have given you the start of a constructor __init__(self, digitstr) that accepts a string input digitstr and assigns preliminary values to the following three attributes: tiles: a reference to a 2-D list of integers with 3 rows and 3 columns that will be used to store the contents of the board. Initially, this 2-D list is filled with zeros. blank_r: an integer representing the row of the blank cell; this is initially set to -1 blank_c: an integer representing the column of the blank cell; this is also initially set to -1 The input digitstr is a 9-character string of digits that specifies the desired configuration of the tiles. For example, consider the following puzzle: 5_moves.gif It would be represented by the string '142358607'. Notice that: the first 3 characters in the string (142) specify the contents of the first row the next 3 characters (358) specify the contents of the second row the final 3 characters (607) specify the contents of the last row, with 0 representing the blank cell. Leaving our starter code alone, add code below it that updates the values of the threeBoard attributes to reflect the input digitstr. For the string 142358607 described above, you should end up with the following values: tiles should be [[1, 4, 2], [3, 5, 8], [6, 0, 7]] blank_r should be 2, since the blank cell is in row 2 blank_c should be 1, since the blank cell is in column 1 There are multiple options for processing the input digitstr, but you should use at least one loop. Here are some hints: The tile at row r, column c gets its value from the digit at position (3*r + c) of the input string digitstr. For example, the tile at row 1, column 2 in the above puzzle is an 8, and that corresponds to digitstr[3*1 + 2] (i.e., position 5 in the string'142358607'). You can use the int() function to convert the string version of a digit to the appropriate integer. Don’t forget to record the row and column numbers of the blank cell in the attributesblank_r and blank_c. Examples: >>> b = Board('142358607') >>> b.tiles [[1, 4, 2], [3, 5, 8], [6, 0, 7]] >>> b.blank_r 2 >>> b.blank_c 1 >>> b2 = Board('631074852') >>> b2.tiles [[6, 3, 1], [0, 7, 4], [8, 5, 2]] >>> b2.blank_r 1 >>> b2.blank_c 0 Write a method __repr__(self) that returns a string representation of a Board object. In the string that __repr__ constructs, each numeric tile should be represented by the appropriate single-character string, followed by a single space. The blank cell should be represented by an underscore character ('_') followed by a space; make sure that you donot accidentally use a hyphen ('-'). There should be a newline character (' ') after the characters for each row, so that each row will appear on a separate line when you evaluate or print a Board object. For example: >>> b = Board('142358607') >>> b 1 4 2 3 5 8 6 _ 7 >>> str(b) '1 4 2 3 5 8 6 _ 7 ' Note that calling str(b) from the Shell allows us to see the full string returned by__repr__, including all of the spaces and newline characters. Make sure that your results for this call match ours. Hints: This __repr__ will be similar to the one that you wrote for the Board class in Problem Set 10. You may want to use that method as a model, and to consult the hints that we gave you for that problem. Remember that the __repr__ method needs to return a string, and that it should notdo any printing. You can use the str() function to convert an integer to a string. Make sure that your __repr__ doesn’t change the object in any way. In particular, thetiles list should not change: >>> b = Board('142358607') >>> b.tiles [[1, 4, 2], [3, 5, 8], [6, 0, 7]] >>> b 1 4 2 3 5 8 6 _ 7 >>> b.tiles [[1, 4, 2], [3, 5, 8], [6, 0, 7]] As discussed in class, we can simplify things by imagining that all Eight-Puzzle moves involve “moving” the blank cell. For example, in the puzzle below 5_moves.gif moving the blank up is equivalent to moving the 5 down, which produces the following board: 4_moves.gif Write a method move_blank(self, direction) that takes as input a string directionthat specifies the direction in which the blank should move, and that attempts to modify the contents of the called Board object accordingly. Not all moves are possible on a givenBoard; for example, it isn’t possible to move the blank down if it is already in the bottom row. The method should return True or False to indicate whether the requested move was possible. Notes/hints: The input direction can have one of the following four values: 'up', 'down','left', 'right'. If any other value is passed in for ‘direction’, the method should print an error message and return False without making any changes to the object. Here is one possible approach to this method: Start by determining the new row and column coordinates of the blank cell, based on the value of direction. At first, you should store these new coordinates in temporary local variables, not in the attributes themselves. Check to see if either of the new coordinates would take you off of the board. If so, simply return False. Otherwise, make the necessary changes to the Board object’s attributes and return True. Draw some pictures to help you figure out the appropriate changes. We recommend changing the necessary elements of self.tiles beforechanging self.blank_r or self.blank_c. Examples: >>> b = Board('142358607') >>> b 1 4 2 3 5 8 6 _ 7 >>> b.move_blank('up') True >>> b 1 4 2 3 _ 8 6 5 7 >>> b.tiles # tiles should still contain only integers [[1, 4, 2], [3, 0, 8], [6, 5, 7]] >>> b.blank_r 1 >>> b.blank_c 1 >>> b.move_blank('left') True >>> b 1 4 2 _ 3 8 6 5 7 >>> b.blank_r 1 >>> b.blank_c 0 >>> b.move_blank('left') # can't go any further left False >>> b # b is unchanged 1 4 2 _ 3 8 6 5 7 >>> b.move_blank('down') True >>> b 1 4 2 6 3 8 _ 5 7 >>> b.move_blank('right') True >>> b 1 4 2 6 3 8 5 _ 7 >>> b.move_blank('RIGHT') unknown direction: RIGHT False >>> b # b is unchanged 1 4 2 6 3 8 5 _ 7 >>> b.blank_r 2 >>> b.blank_c 1 Write a method digit_string(self) that creates and returns a string of digits that corresponds to the current contents of the called Board object’s tiles attribute. For example: >>> b = Board('142358607') >>> b.digit_string() '142358607' Note that this call to digit_string() returns the string of digits that was used when creating the Board. However, this won’t always be the case, because the string returned by digit_string() should reflect any changes that have been made to the tiles. For example, consider this continuation of the above example: >>> b.move_blank('right') True >>> b.move_blank('up') True >>> b.digit_string() '142350678' Write a method copy(self) that returns a newly-constructed Board object that is a deep copy of the called object (i.e., of the object represented by self). This method should use the Board constructor to create a new Board object with the same configuration of tiles as self, and it should return the newly created Board object. Hint: The Board constructor takes a string of digits. How could you easily obtain the appropriate string of digits for the called Board? Examples: >>> b = Board('142358607') >>> b 1 4 2 3 5 8 6 _ 7 >>> b2 = b.copy() >>> b2 1 4 2 3 5 8 6 _ 7 >>> b2.move_blank('up') True >>> b2 1 4 2 3 _ 8 6 5 7 >>> b # the original Board is unchanged 1 4 2 3 5 8 6 _ 7 Write a method num_misplaced(self) that counts and returns the number of tiles in the called Board object that are not where they should be in the goal state. You should not include the blank cell in this count, even if it’s not where it should be in the goal state. For example: >>> b = Board('142358607') >>> b 1 4 2 3 5 8 6 _ 7 >>> b.num_misplaced() # 1,4,5,7,8 tiles are out of place 5 >>> b.move_blank('right') # move 7 tile where it belongs True >>> b 1 4 2 3 5 8 6 7 _ >>> b.num_misplaced() # 1,4,5,8 tiles are still out of place 4 Finally, write a method __eq__(self, other) that overloads the == operator – creating a version of the operator that works for Board objects. The method should return True if the called object (self) and the argument (other) have the same values for the tilesattribute, and False otherwise. This method should be straightforward to implement because you can simply use the ==operator to compare self.tiles and other.tiles. You do not need to explicitly compare the individual tiles yourself, because the == operator already compares the individual elements of 2-D lists. Examples: >>> b1 = Board('012345678') >>> b2 = Board('012345678') >>> b1 == b2 True >>> b2.move_blank('right') True >>> b1 == b2 False Part II: A State class For the second part of the project, you will create a preliminary State class for objects that represent one of the states in a state-space search tree for the Eight Puzzle. We discussedState objects and their connection to the search tree in class. Your tasks Find the file state.py in your project folder and open it in IDLE. It contains starter code for the State class. Read over the comments accompanying the starter code. Write a constructor __init__(self, board, predecessor, move) that constructs a new State object by initializing the following four attributes: an attribute board that stores a reference to the Board object associated with this state, as specified by the parameter board an attribute predecessor that stores a reference to the State object that comes before this state in the current sequence of moves, as specified by the parameterpredecessor an attribute move that stores a string representing the move that was needed to transition from the predecessor state to this state, as specified by the parametermove an attribute num_moves that stores an integer representing the number of moves that were needed to get from the initial state (the state at the root of the tree) to this state. If predecessor is None–which means that this new state is the initial state–thennum_moves should be initialized to 0. Otherwise, it should be assigned a value that is one more that the number of moves for the predecessor state. Because we’ve already given you an __repr__ method for the class, you should be able to test your constructor as follows: >>> b1 = Board('142358607') >>> s1 = State(b1, None, 'init') >>> s1 142358607-init-0 >>> b2 = b1.copy() >>> b2.move_blank('up') True >>> s2 = State(b2, s1, 'up') # s1 is the predecessor of s2 >>> s2 142308657-up-1 Write a method is_goal(self) that returns True if the called State object is a goal state, and False otherwise. At the top of the file, we’ve given you a 2-D list called GOAL_TILES that represents the configuration of the tiles in a goal state. You can simply use the == operator to compare the tiles attribute in the Board object associated with this state to GOAL_TILES. Here are some test cases: >>> s1 = State(Board('102345678'), None, 'init') >>> s1.is_goal() False >>> s2 = State(Board('012345678'), s1, 'left') >>> s2.is_goal() True Write a method generate_successors(self) that creates and returns a list of Stateobjects for all successor states of the called State object. We discussed the concept of successor states in class. At the top of the file, we’ve given you a list called MOVES that contains the names of the four possible ways in which the blank cell can be moved: MOVES = ['up', 'down', 'left', 'right'] For each of these moves, the method should do the following: Create a copy of the Board object associated with this state by using the appropriate method in that Board object. Attempt to apply the move by using the appropriate method in the new Board object (i.e., the copy). Make sure that you apply the move to the copy, and not to the original. If the move was successful, construct a new State object for the new Board, and add that State object to the list of successors. Otherwise, don’t create a State object for that move. Then, once you are done trying all possible moves, return the list of successors. Here’s some pseudocode for the full method: def generate_successors(self): successors = [] for each move m in the list MOVES: b = a copy of self.board try applying the move m to b if you can apply it: construct a new State object for the result of the move add the new State object to successors return successors Hints: Make sure to take advantage of the appropriate methods in the Board objects. When constructing a new State object, you should use the variable self as the second input of the constructor, since the current state (the one represented by the called object) is the predecessor of the new state. Examples: >>> b1 = Board('142358607') >>> b1 1 4 2 3 5 8 6 _ 7 s1 = State(b1, None, 'init') >>> s1 142358607-init-0 >>> succ = s1.generate_successors() >>> succ # 3 successors; blank can't go down from bottom row [142308657-up-1, 142358067-left-1, 142358670-right-1] >>> s1 # s1 should be unchanged 142358607-init-0 >>> succ[2] # in succ[2], blank is in lower-right 142358670-right-1 >>> succ[2].generate_successors() # blank can go up or left [142350678-up-2, 142358607-left-2] >>> succ[0] # in succ[0], blank is in middle 142308657-up-1 >>> succ[0].generate_successors() # blank can go in all four directions [102348657-up-2, 142358607-down-2, 142038657-left-2, 142380657-right-2] Part III: A Searcher class for random search In the next part of the project, you will begin to implement the actual state-space search process. As discussed in class, we will use searcher objects to perform the search for us. Different types of searcher objects will implement different state-space search algorithms, and we’ll take advantage of inheritance when defining the searcher classes. Find the file searcher.py in your project folder and open it in IDLE. It contains some starter code, including the beginnings of a class called Searcher, which will perform a random state-space search. Read over the comments accompanying the starter code. Write a constructor __init__(self, init_state, depth_limit) that constructs a new Searcher object by initializing the following attributes: an attribute states for the Searcher‘s list of untested states; it should be initialized to a list containing the state specified by the parameter init_state an attribute num_tested that will keep track of how many states the Searcher tests; it should be initialized to 0 an attribute depth_limit that specifies how deep in the state-space search tree theSearcher will go; it should be initialized to the value specified by the parameterdepth_limit. (A depth_limit of -1 indicates that the Searcher does not use a depth limit.) Because we’ve already given you an __repr__ method for the class, you should be able to test your constructor as follows: >>> b = Board('142358607') >>> s = State(b, None, 'init') >>> searcher1 = Searcher(s, -1) # -1 means no depth limit >>> searcher1 1 untested, 0 tested, no depth limit >>> searcher2 = Searcher(s, 10) >>> searcher2 1 untested, 0 tested, depth limit = 10 Write a method should_add(self, state) that takes a State object called state and returns True if the called Searcher should add state to its list of untested states, andFalse otherwise. The method should return False if either of these conditions holds: the Searcher has a depth limit (i.e., its depth limit is not -1) and state is beyond the depth limit (i.e., the number of moves used to get to state is greater than the depth limit) state creates a cycle in the search, because the same board already appears in the sequence of moves that led to state. We’ve given you a method in the State class called creates_cycle() that checks for this. Read the comments accompanying that method to understand how it works, and apply it appropriately here. If neither of these conditions holds, the method should return True. Examples: >>> b1 = Board('142358607') >>> s1 = State(b1, None, 'init') # initial state >>> searcher1 = Searcher(s1, -1) # no depth limit >>> searcher2 = Searcher(s1, 1) # depth limit of 1 move! >>> b2 = b1.copy() >>> b2.move_blank('left') True >>> s2 = State(b2, s1, 'left') # s2's predecessor is s1 >>> searcher1.should_add(s2) True >>> searcher2.should_add(s2) True >>> b3 = b2.copy() >>> b3.move_blank('right') # get the same board as b1 True >>> s3 = State(b3, s2, 'right') # s3's predecessor is s2 >>> searcher1.should_add(s3) # adding s3 would create a cycle False >>> searcher2.should_add(s3) False >>> b3.move_blank('left') # reconfigure b3 True >>> b3.move_blank('up') True >>> s3 = State(b3, s2, 'up') # recreate s3 with new b3 (no cycle) >>> s3.num_moves 2 >>> searcher1.should_add(s3) # searcher1 has no depth limit True >>> searcher2.should_add(s3) # s3 is beyond searcher2's depth limit False Write a method add_state(self, new_state) that adds takes a single State object called new_state and adds it to the Searcher‘s list of untested states. This method should only require one line of code! It should not return a value. For the sake of efficiency, we recommend that you do not do something like the following: self.states = self.states + ... # don't do this! Rather, we recommend that you either use the += operator or the append method in thelist object. We will discuss the reasons for this in class. Examples: >>> b = Board('142358607') >>> s = State(b, None, 'init') >>> searcher = Searcher(s, -1) >>> searcher.states [142358607-init-0] >>> succ = s.generate_successors() >>> succ [142308657-up-1, 142358067-left-1, 142358670-right-1] >>> searcher.add_state(succ[0]) # add just the first successor >>> searcher.states [142358607-init-0, 142308657-up-1] Write a method add_states(self, new_states) that takes a list State objects callednew_states, and that processes the elements of new_states one at a time as follows: If a given state s should be added to the Searcher‘s list of untested states (becauses would not cause a cycle and is not beyond the Searcher‘s depth limit), the method should use the Searcher‘s add_state() method to add s to the list of states. If a given state s should not be added to the Searcher object’s list of states, the method should ignore the state. This method should not return a value. Notes/hints: Take advantage of the Searcher‘s method for determining if a state should be added. Make sure that you use add_state() when adding the individual states to the list, rather than adding them yourself. This will will allow you to make fewer changes when you use inheritance to define other types of searchers. Examples: >>> b = Board('142358607') >>> s = State(b, None, 'init') >>> searcher = Searcher(s, -1) >>> searcher.states [142358607-init-0] >>> succ = s.generate_successors() >>> succ [142308657-up-1, 142358067-left-1, 142358670-right-1] >>> searcher.add_states(succ) # add all of the successors >>> searcher.states [142358607-init-0, 142308657-up-1, 142358067-left-1, 142358670-right-1] >>> succ[-1] 142358670-right-1 >>> succ2 = succ[-1].generate_successors() >>> succ2 [142350678-up-2, 142358607-left-2] >>> searcher.add_states(succ2) >>> searcher.states [142358607-init-0, 142308657-up-1, 142358067-left-1, 142358670-right-1, 142350678-up-2] Note that the last call to add_states above took a list of two states (the list given bysucc2), but that only one of them (the state 142350678-up-2) was actually added tosearcher‘s list of states. That’s because the other state (142358607-left-2) has the same board as the initial state and would thus create a cycle. Copy the following method into your Searcher class: def next_state(self): """ chooses the next state to be tested from the list of untested states, removing it from the list and returning it """ s = random.choice(self.states) self.states.remove(s) return s Make sure to maintain the appropriate indentation when you do so. This method will be used to obtain the next state to be tested, and you should review it carefully. Here are two points worth noting: Because Searcher objects perform a random search through the search space, we are using the random.choice method to randomly choose one of the elements of thestates list. We’re using a list method called remove to remove the selected state s from thestates list. Finally, write a method find_solution(self) that performs a full random state-space search, stopping when the goal state is found or when the Searcher runs out of untested states. If the searcher finds a goal state, it should return it. If the searcher runs out of untested states before finding a goal state, it should return the special keyword None. (Note that there should not be any quotes around None, because it is not a string.) The method should increment the Searcher object’s num_tested attribute every time that it tests a state to see if it is the goal. We gave you pseudocode for this method in class on June 20th. Make sure that you take advantage of existing methods – both those available in theSearcher (i.e., in self) and those available in the State objects. Among other methods, you should use the Searcher object’s next_state() method to obtain the next state to be tested. Example 1: >>> b = Board('012345678') # the goal state! >>> s = State(b, None, 'init') # start at the goal >>> s 012345678-init-0 >>> searcher = Searcher(s, -1) >>> searcher 1 untested, 0 tested, no depth limit >>> searcher.find_solution() # returns init state, because it's a goal state 012345678-init-0 >>> searcher 0 untested, 1 tested, no depth limit Example 2 (results may vary because of randomness): >>> b = Board('142358607') >>> s = State(b, None, 'init') >>> s 142358607-init-0 >>> searcher = Searcher(s, -1) >>> searcher 1 untested, 0 tested, no depth limit >>> searcher.find_solution() # returns goal state at depth 11 012345678-up-11 >>> searcher 273 untested, 370 tested, no depth limit >>> searcher = Searcher(s, -1) # a new searcher with the same init state >>> searcher 1 untested, 0 tested, no depth limit >>> searcher.find_solution() # returns goal state at depth 5 012345678-left-5 >>> searcher 153 untested, 205 tested, no depth limit In order to see the full solution (i.e., the sequence of moves from the initial state to the goal state), we need to add a method to the State class that will follow predecessor references back up the state-space search tree in order to find and print the sequence of moves. Open up your state.py file, and add a method print_moves_to(self) that prints the sequence of moves that lead from the initial state to the called State object (i.e., toself). To accomplish this task, you should first review the attributes that each State object has inside it. Consult the guidelines for the State class __init__ method as needed. Next, it’s worth noting that this method will be starting at a given State object and following predecessor references back to the initial state. However, we want to print the sequence of moves in the reverse order – from the initial state to the called State object. One way to do this is using recursion, as shown in the following pseudocode: def print_moves_to(self): if self is the initial state: # base case print('initial state:') print the board associated with self else: make a recursive call to print the moves to the predecessor state print the move that led to self (see format below) print the board associated with self Because the recursive call on the predecessor state comes before the processing ofself, the method will print the sequence of moves in the correct order. Example (results may vary because of randomness): >>> b = Board('142305678') # only 2 moves from a goal >>> b 1 4 2 3 _ 5 6 7 8 >>> s = State(b, None, 'init') >>> searcher = Searcher(s, -1) >>> goal = searcher.find_solution() >>> goal 012345678-left-2 >>> goal.print_moves_to() initial state: 1 4 2 3 _ 5 6 7 8 move the blank up: 1 _ 2 3 4 5 6 7 8 move the blank left: _ 1 2 3 4 5 6 7 8 >>> Although the sequence of moves may vary because of randomness, the format of the output should be the same as what you see above. Once you have completed all of the methods specified above, you can use the driver function that we have provided to facilitate the process of solving a given puzzle. Find the file eight_puzzle.py in your project folder and open it in IDLE. The driver function is called eight_puzzle, and it has two mandatory inputs: a string describing the board configuration for the initial state a string specifying the search algorithm that you want to use; for now, the only option is random. There is also a third, optional input that we will describe later. Here’s an example of how you would call it: >>> eight_puzzle('142358607', 'random') After finding a solution, the function will ask if you want to see the moves. Enter y to see them, or anything else to end the function without seeing them. Important: After making changes to any of your Python files, you should rerun theeight_puzzle.py file before using the driver function to test your changed code. 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 called BFSearcher 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 your BFSearcher class, because all of the necessary attributes will be inherited from Searcher. 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 from Searcher. Because all of the attributes of a BFSearcher are inherited from Searcher, you willnot need to define a constructor for this class. Rather, we can just use the constructor that is inherited from Searcher. Write a method next_state(self) that overrides (i.e., replaces) the next_statemethod that is inherited from Searcher. Rather than choosing at random from the list of untested states, this version of next_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(s, -1) >>> 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 called DFSearcher 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 for BFSearcher, but the next_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(s, -1) >>> 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 called create_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 the algorithm input is 'BFS' or 'DFS'. Once you do so, you should be able to use the eight_puzzle driver function to test your BFSearcher andDFSearcher classes. Breadth-first search should quickly solve the following puzzle: >>> eight_puzzle('142358607', 'BFS') 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') 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 ourprint_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 called GreedySearcher 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 in BFSearcher andDFSearcher. Among other things, GreedySearcher objects will have a new attribute called heuristic 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. Write a method priority(self, state) that takes a State object called state, 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 the Board object associated with state. Take advantage of the appropriate Board method to determine this value. Copy the following constructor into the GreedySearcher class: def __init__(self, init_state, heuristic, depth_limit): """ constructor for a GreedySearcher object inputs: * init_state - a State object for the initial state * heuristic - an integer specifying which heuristic function should be used when computing the priority of a state * depth_limit - the depth limit of the searcher """ self.heuristic = heuristic self.states = [[self.priority(init_state), init_state]] self.num_tested = 0 self.depth_limit = depth_limit Make sure to maintain the appropriate indentation when you do so. Two things worth noting: GreedySearcher objects have an extra attribute called heuristic (and an associated extra input to their constructor). This attribute stores an integer specifying which heuristic function the GreedySearcher should use. We’re not currently using this attribute in our priority method, but ultimately the method will use this attribute to choose between multiple different heuristic functions for estimating a State‘s remaining cost. A GreedySearcher object’s states 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. Thus, we initialize states to be a list containing a sublist in which the initial state is paired with its priority. Example: >>> b = Board('142358607') >>> s = State(b, None, 'init') >>> g = GreedySearcher(s, -1, -1) # basic heuristic, no depth limit >>> g.states # sublist pairing initial state with its priority [[-5, 142358607-init-0]] If you don’t see a priority value of -5, check your priority method for possible problems. Write a method add_state(self, state) that overrides (i.e., replaces) theadd_state method that is inherited from Searcher. Rather than simply adding the specified state to the list of untested states, the method should add a sublist that is a [priority, state] pair, where priority is the priority of state, as determined by calling the priority method. Examples: >>> b = Board('142358607') >>> s = State(b, None, 'init') >>> g = GreedySearcher(s, -1, -1) >>> 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]] Write a method next_state(self) that overrides (i.e., replaces) the next_statemethod that is inherited from Searcher. This version of next_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(s, -1, -1) # basic heuristic, no depth limit >>> 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 called AStarSearcher 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, and num_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 three inputs: (1) a State object for the initial state, (2) an integer that specifies which heuristic function should be used, and (3) 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(s, -1, -1) # basic heuristic, no depth limit >>> 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 in eight_puzzle.py so that it will be able to create GreedySearcher and AStarSearcher objects. To do so, simply uncomment the lines that handle cases in which the algorithm 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. Part V: 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, extra). 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*') an integer extra that can be used to specify an optional parameter for the algorithm being used – either a depth limit or a choice of heuristic To make the third input optional, you should use the following function header: def process_file(filename, algorithm, extra=-1): """ doctring goes here """ Note that this header specifies a default value of -1 for the input extra, which is why this input is optional. If we leave it out (by only specifying two inputs when we call the function), Python will give extra its default value of -1. If we specify a value for extrawhen we call the function, the specified value will be used instead of -1. 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, and you wrote a related function for Problem 3 of Problem Set 9. 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 specified by the second input 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') 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 When calling the searcher object’s find_solution method, you should do so as follows: soln = None try: soln = searcher.find_solution() 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 ofNone (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 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') 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 theaverages 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 the default, 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 for5_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 A* 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 default heuristic–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: two_h4_puzzles.gif 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 for your new heuristic (something like the num_misplaced method that you implemented in Part IV). Choose an integer other than -1 for your new heuristic, and use that integer when constructing a GreedySearcher or AStarSearcher that should employ that heuristic. For example, if init_state is a State object for the initial state of the puzzle, and if one of your heuristics is represented by the integer 1, you could do the following: >>> g = GreedySearcher(init_state, 1, -1) where 1 specifies your new heuristic and -1 specifies no depth limit. When using the eight_puzzle driver function or the process_file function that you wrote earlier, you should specify the heuristic number as the third input. For example: >>> process_file('15_moves.txt', 'A*', 1) # use heuristic 1 Update the code in your informed searcher classes so that the process of assigning priorities to states chooses between the default, num-misplaced-tiles heuristic and your new heuristic. For example, you will need to update the body of the prioritymethod in GreedySearcher to look something like this: def priority(self, state): if self.heuristic == 1: # use my new heuristic else: # use num-misplaced-tiles # possibly other code here You are welcome to design more than one new heuristic function, although only one is required. Give each heuristic its own integer so that you can choose between them. 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 default 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 algorithms 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 isoverestimating 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 that you want us to test is identified using the integer 1. Also, please make sure that we will still be able to test the default, num-misplaced-tiles heuristic if we specify a value of -1 for the heuristic. In your results.txt file, briefly describe how your best new heuristic works: heuristic 1 ----------- 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(s) and the default heuristic 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 for18_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 -1) Greedy (heuristic 1) # Greedy with any other heuristics A* (heuristic -1) A* (heuristic 1) # Greedy with any other heuristics
Explanation / Answer
#!/usr/bin/python # ### Student Info # Smith, Christopher, 02386569, 159.302 # Assignment 1: 8 Puzzle. # ### Language # This assignment was written in Python. An open source, interpreted language # with a mix of imperative, OO and functional programming. Syntax is simple # and easy to learn. # # Developed on Ubuntu Linux but this will run on the interpreter available # from http://python.org. Documentation is also on that site but a good # ### Data Structures # # The state of the board is stored in a list. The list stores values for the # board in the following positions: # # ------------- # | 0 | 3 | 6 | # ------------- # | 1 | 4 | 7 | # ------------- # | 2 | 5 | 8 | # ------------- # # The goal is defined as: # # ------------- # | 1 | 2 | 3 | # ------------- # | 8 | 0 | 4 | # ------------- # | 7 | 6 | 5 | # ------------- # # Where 0 denotes the blank tile or space. goal_state = [1, 8, 7, 2, 0, 6, 3, 4, 5] # # The code will read state from a file called "state.txt" where the format is # as above but space seperated. i.e. the content for the goal state would be # 1 8 7 2 0 6 3 4 5 ### Code begins. import sys def display_board( state ): print "-------------" print "| %i | %i | %i |" % (state[0], state[3], state[6]) print "-------------" print "| %i | %i | %i |" % (state[1], state[4], state[7]) print "-------------" print "| %i | %i | %i |" % (state[2], state[5], state[8]) print "-------------" def move_up( state ): """Moves the blank tile up on the board. Returns a new state as a list.""" # Perform an object copy new_state = state[:] index = new_state.index( 0 ) # Sanity check if index not in [0, 3, 6]: # Swap the values. temp = new_state[index - 1] new_state[index - 1] = new_state[index] new_state[index] = temp return new_state else: # Can't move, return None (Pythons NULL) return None def move_down( state ): """Moves the blank tile down on the board. Returns a new state as a list.""" # Perform object copy new_state = state[:] index = new_state.index( 0 ) # Sanity check if index not in [2, 5, 8]: # Swap the values. temp = new_state[index + 1] new_state[index + 1] = new_state[index] new_state[index] = temp return new_state else: # Can't move, return None. return None def move_left( state ): """Moves the blank tile left on the board. Returns a new state as a list.""" new_state = state[:] index = new_state.index( 0 ) # Sanity check if index not in [0, 1, 2]: # Swap the values. temp = new_state[index - 3] new_state[index - 3] = new_state[index] new_state[index] = temp return new_state else: # Can't move it, return None return None def move_right( state ): """Moves the blank tile right on the board. Returns a new state as a list.""" # Performs an object copy. Python passes by reference. new_state = state[:] index = new_state.index( 0 ) # Sanity check if index not in [6, 7, 8]: # Swap the values. temp = new_state[index + 3] new_state[index + 3] = new_state[index] new_state[index] = temp return new_state else: # Can't move, return None return None def create_node( state, parent, operator, depth, cost ): return Node( state, parent, operator, depth, cost ) def expand_node( node, nodes ): """Returns a list of expanded nodes""" expanded_nodes = [] expanded_nodes.append( create_node( move_up( node.state ), node, "u", node.depth + 1, 0 ) ) expanded_nodes.append( create_node( move_down( node.state ), node, "d", node.depth + 1, 0 ) ) expanded_nodes.append( create_node( move_left( node.state ), node, "l", node.depth + 1, 0 ) ) expanded_nodes.append( create_node( move_right( node.state), node, "r", node.depth + 1, 0 ) ) # Filter the list and remove the nodes that are impossible (move function returned None) expanded_nodes = [node for node in expanded_nodes if node.state != None] #list comprehension! return expanded_nodes def bfs( start, goal ): """Performs a breadth first search from the start state to the goal""" # A list (can act as a queue) for the nodes. nodes = [] # Create the queue with the root node in it. nodes.append( create_node( start, None, None, 0, 0 ) ) while True: # We've run out of states, no solution. if len( nodes ) == 0: return None # take the node from the front of the queue node = nodes.pop(0) # Append the move we made to moves # if this node is the goal, return the moves it took to get here. if node.state == goal: moves = [] temp = node while True: moves.insert(0, temp.operator) if temp.depth == 1: break temp = temp.parent return moves # Expand the node and add all the expansions to the front of the stack nodes.extend( expand_node( node, nodes ) ) def dfs( start, goal, depth=10 ): """Performs a depth first search from the start state to the goal. Depth param is optional.""" # NOTE: This is a limited search or else it keeps repeating moves. This is an infinite search space. # I'm not sure if I implemented this right, but I implemented an iterative depth search below # too that uses this function and it works fine. Using this function itself will repeat moves until # the depth_limit is reached. Iterative depth search solves this problem, though. # # An attempt of cutting down on repeat moves was made in the expand_node() function. depth_limit = depth # A list (can act as a stack too) for the nodes. nodes = [] # Create the queue with the root node in it. nodes.append( create_node( start, None, None, 0, 0 ) ) while True: # We've run out of states, no solution. if len( nodes ) == 0: return None # take the node from the front of the queue node = nodes.pop(0) # if this node is the goal, return the moves it took to get here. if node.state == goal: moves = [] temp = node while True: moves.insert(0, temp.operator) if temp.depthRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.