Assignment 3 B351 / Q351 Comprehension Questions Due: Tuesday, September 24th, 2019 @ 11:59PM Initial Due: Tuesday, October 1st, 2019 @ 11:59PM 1 Summary • Using various search algorithms, solve the traditional 8-puzzle generalized to any n2 − 1 puzzle. • Demonstrate your understanding of heuristic admissibility. • Incorporate uninformed, Uniform Cost Search expansion, and A* expansion to solve these various puzzles. We will be using Python 3 so be sure you aren’t using older versions. Code that will compile in Python 2.7 may not compile in Python 3. See our installation guide for help removing old versions and installing Python 3. Please submit your completed files to your private Github repository for this class. You may not make further revisions to your files beyond the above deadline without incurring a late penalty. You may collaborate on this assignment (optional) but you can only share ideas. Any shared code will not be tolerated and those involved will be subjected to the university’s cheating and plagiarism policy. If you discuss ideas, each person must write a comment at the top of the assignment file naming the students with whom ideas were shared. 2 Background The 8-puzzle is one of a family of classic sliding tile puzzles dating to the late 1800s and still played today. A puzzle is solved when the numbered tiles are in order from the top left to the bottom right with the blank in the bottom right corner. 1 A legal move is made by simply moving a tile into the blank space. We will be denoting the blank space with a 0 to make computation simpler. If you want to familiarize yourself with the game, you can here. 3 Programming In this assignment’s programming component, you will utilize the starter framework that we have provided to build various search algorithms and expansion algorithms that have been discussed in lecture. 3.1 Data Structures 3.1.1 Board The class ’Board’, as implemented in the Board.py file, has two attributes: 1. matrix: a double subscripted list containing the current puzzle state 2. blankPos: a tuple containing the (row, column) position of the blank. The following are Board’s object methods: 2 1. init (self, matrix): Constructor for the board class. Takes a double-subscripted list as an argument. 2. str (self): The string representation of a board. 3. repr (self): A string of code to produce a board. 4. eq (self, other): Checks two boards for equality. 5. duplicate(self): Creates a copy of given board. 6. find element(self, elem): Returns a tuple (row, col) that gives the position of the element in the board. 7. slide blank(self, move): Function for sliding the blank space around. Takes a tuple (Delta x, Delta y) that represents how far you want to move in each direction. 8. hash (self): Hash function that maps a board to a number. 3.1.2 State This class is implemented in the State.py file. This class encapsulates the following data members: 1. board: The board that belongs to this state. 2. parent: The parent state that this state came from. 3. depth: The depth in the move tree from the original board that this board can be found in (the number of moves the puzzle has undergone thus far). 4. f value: The heuristic value of the board plus the cost to get from the initial board to this board. (May be set to 0.) and has the following methods: 1. init (self, board, parent, depth, f value = 0): Constructor for a State object. This function takes as arguments the board that corresponds to this state, the parent state, the fValue of the state, and the depth of the state in the state tree. 2. lt (self, other): Checks if a state’s fValue is less than that of another state. 3. eq (self, other): Checks if two States contain the same Board. This does not compare parents or depth. 4. str (self): The string representation of a given state. 5. repr (self): A string of code to produce a given state. 6. printPath(self): Prints the path to the given state. 3 3.1.3 a3.py This is the main file in which you will be writing code. The following is a list of functions that are provided for you: 1. uninformed solver(start board, max depth, goal board) Looping function that calls bfs() until a goal state has been found or until STOP has been returned. It does not consider States below max depth. If the goal is reached, this function should return the Goal State, which includes a path to the goal. Otherwise returns None. • start board: The start board. • max depth: The maximum depth of searching for the Goal State. • goal board: The solved board. 2. findManhattanDist(current board, goal board) Function which uses the Manhattan Distance heuristic to give values to the States. This is an example heuristic function that we have provided for testing.. • current board: The current board for which we are calculating a heuristic value. • goal board: The solved board. 3. informed solver(current board, goal board, f function) Looping function that calls informed search() until it finds a solution (a State object) or until STOP has been returned. If the goal is reached, this function should return the Goal State, which includes a path to the goal. Otherwise, returns None. • start board: The starting board. • goal board: The solved board. • f function: Either the ucs f function() or a star f function factory() which allows this looping function to consider either Uniform Cost Search or A* Search when testing. 4. ucs solver(current board, goal board) Function which performs the informed solver() function recursively using Uniform Cost Search. • start board: The starting board. • goal board: The solved board. 5. a star solver(current board, goal board, heuristic Function which performs the informed solver() function recursively using A* Search. • start board: The starting board. 4 • goal board: The solved board. • heuristic: A heuristic function, i.e. either the given Manhattan Distance function or your own implemented heuristic found in new heuristic(). 3.2 Objective Your goal is to provide the implementations to the following functions: 1. fringe expansion 2. bfs 3. ucs f value function 4. a star f value function factory 5. my new heuristic 6. informed expansion 7. informed search to the following specifications: 3.2.1 fringe expansion(current state, fringe) Write a function that adds the possible states that we can get to from the current state to the end of the fringe. This function should not return or yield anything but just update the contents of the fringe. • current state: The current state that is to be used to generate children. • fringe: A list that holds the states that have been added to the fringe. 3.2.2 bfs(fringe, max depth, goal board) Write a function that implements a single iteration of the BFS algorithm by considering the first state from the fringe; NOT the whole thing. 1. Return STOP if the fringe is empty. 2. If the depth of the current state is greater than the max depth, skip the current state and continue searching. 3. Return the current state its board is the goal board. 4. Otherwise expand the fringe and continue. 3.2.3 ucs f value function(board, current depth) Write a function that takes a board and depth and returns the f-value that board should have in a uniform-cost search scenario. 5 3.2.4 a star f value function factory(heuristic, goal board) Given a heuristic function and a goal board, returns an f-value FUNCTION that takes a board and a depth and returns an f-value, as in the A* algorithm. (Using the lambda keyword here may be helpful.) 3.2.5 new heuristic(current board, goal board) Write a function that takes current board and goal board as arguments and returns an estimate of how many moves it will take to reach the goal board. Your heuristic must be admissible (never overestimate the cost to the goal), but it does not have to be consistent (never overestimate step costs). It should always return a value ≥ 0, be a more accurate estimate than (be greater than on average) the Manhattan Distance heuristic, and function competently for A* searches. It may not correlate linearly with the Manhattan Distance. 3.2.6 informed exp
ansion(current state, fringe, f function Write a function that expands the fringe using the f-value function provided. Note that States automatically sort by their f-values. This function should not return any value but just update the contents of the fringe (HINT: Use heap). 3.2.7 informed search(fringe, goal board, f function, explored) Write a function that implements a single iteration of the A*/UCS algorithm by considering the top-priority state from the fringe. (NOTE: explored is a dictionary mapping boards to their lowest encountered f-values.) 1. If the fringe is empty then stop. 2. Otherwise, get the top state from the fringe. 3. If the current state’s board has already been seen and the current state’s f-value is not smaller than the previous f-value, then skip this state and continue. 4. Add the current state’s board and its f-value to the explored dictionary. 5. If the current state is the goal board, return the state. 6. Otherwise expand the fringe and continue. 4 Tests Very simple tests have been given for you in A3.py. Running this file will run the tests. Be sure to use these to make sure your implementations are working generally as requested. These test cases are NOT all encompassing. Passing these does not mean your implementation is completely correct. Each test uses a puzzle that is only 2 moves away from the goal. In order to save submissions, 6 it is advised to write additional unit tests for more complex puzzles as well as to cover cases that these tests do not. One great example is the Competency section of the rubric. This is not covered through the given tests. 5 Grading Problems are weighted according to the percentage assigned in the problem title. For each problem, points will be given based on the criteria met in the corresponding table on the next page and whether your solutions pass the test cases on the online grader. Finally, remember that this is an individual assignment. 5.1 fringe expansion (10%) Criteria Points Tries to make a child board for each possible move 2 Ignores moves that did not successfully produce a child state 1 Initializes child states with the appropriate board and depth 5 Adds each new child state to the end of the fringe 2 Total 10 5.2 bfs (10%) Criteria Points Stops when the fringe is empty 1 Pops the first state in the fringe: the current state 3 Ignores states deeper than max depth 2 Returns the goal state when found 2 Appropriately expands the fringe 2 Total 10 5.3 ucs f value function (5%) Criteria Points Returns the appropriate f-value for a Uniform Cost Search 5 Total 5 7 5.4 a star f value function (10%) Criteria Points Returns a function that accepts a board and a depth and returns an f-value 3 The function returned applies the given heuristic to the board provided at run-time and the given goal board 5 The function returned produces the appropriate f-value for an A* search 2 Total 10 5.5 new heuristic (15%) Criteria Points Returns numerical values; does not call Manhattan distance; does not reimplement Manhattan distance; is not always zero required Never returns a value below zero 2 Is admissible (never overestimates distance to goal) with respect to the standard goal board 5 Is admissible given any possible goal board 3 Returns a value that is closer to the actual distance than (greater than) the Manhattan distance, on average 5 Total 15 5.6 informed expansion (15%) Criteria Points Tries to make a child board for each possible move 2 Ignores moves that did not successfully produce a child state 1 Initializes child states with the appropriate board and depth 5 Initializes child states with the appropriate f-value 4 Adds each child state to the fringe using heappush 3 Total 15 5.7 informed search (10%) Criteria Points Only performs a single search iteration required Stops when the fringe is empty (returns STOP) 1 Uses heappop to get the highest priority state from the fringe 1 Ignores states whose boards have already been explored, if they do not have a lower f-value than before 2 Properly records current board and f-value in explored 2 Returns the goal state when found 2 Appropriately expands the fringe 2 Total 10 8 5.8 Competency (25%) Criteria Points Recognizes goal board 5 Finds optimal path for boards that are less than five moves away from the goal 5 Finds optimal path for boards that are less than ten moves away from the goal 5 Finds optimal path for boards that are less than fifteen moves away from the goal 5 Finds optimal path for boards that are less than twenty moves away from the goal 5 Total 25 6 Bonus (10%) Implement IDS in any way you choose. You will want to write multiple helper functions; be sure to document these appropriately. 6.1 ids(start board, goal board, final depth) Takes a start board and goal board and then performs multiple depth-first searches, with the maximum depth increasing from 0 all the way to final depth. If there is a solution within final depth moves, then ids should return the found board. Otherwise, return None. 9
