The 8 puzzle game

A simple estimator function for the 8-puzzle game is to count the number of tiles that are in the right place. (This estimator evaluates to an integer between 0 and 8). Devise a better estimator function than this for 8-puzzle. Manhattan distance is a better estimator that was mentioned in class. Please add the Manhattan distance heuristic to the code provided below.

 eight_puzzle_state.py FILE

# CSC 380/480 Winter 2018 # A comparison of eight-puzzle using various forms of search. # In this version, the evaluator for best-first is a count # of the number of tiles that are in the correct position # Built on a generalized state finder in search.py # # To run this, DO NOT load eight_puzzle_state.py -- instead, open # search.py and press the F5 key to load it. from random import shuffle # to randomize the order in which successors are visited class eight_puzzle_state: def __init__(self, tiles): self.tiles = tiles.copy() def __str__(self): answer = '' for i in range(9): answer += '{} '.format(self.tiles[i]) if (i + 1) % 3 == 0: answer += ' ' return answer def __repr__(self): return 'eight_puzzle_state({})'.format(self.tiles) def __eq__(self, other): return self.tiles == other.tiles def __hash__(self): return hash(self.tiles[0]) def successors(self): successor_states = [] neighbors = {0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0, 4, 6], 4: [1, 3, 5, 7], 5: [2, 4, 8], 6: [3, 7], 7: [4, 6, 8], 8: [5, 7]} zero_loc = self.tiles.index(' ') for loc in neighbors[zero_loc]: state = eight_puzzle_state(self.tiles) state.tiles[zero_loc] = state.tiles[loc] state.tiles[loc] = ' ' successor_states.append(state) return successor_states # returns an int between 0 (no tiles in place) to 8 (all in place) def evaluation(self): wrong = 0 for i in range(8): if self.tiles[i] != goal_state().tiles[i]: wrong += 1 return wrong def __lt__(self, other): # CHECK LESS THAN return self.evaluation() < other.evaluation() def goal_state(ignore=None): return eight_puzzle_state(['1', '2', '3', '8', ' ', '4', '7', '6', '5']) # from random import shuffle random puzzle is too many moves from goal state from random import randint # make a start state which is n moves from goal state def start_state(n=5): already_visited = [goal_state()] state = goal_state() # max number of moves from start state to goal state for i in range(n): successors = state.successors() for s in successors: if s in already_visited: successors.remove(s) shuffle(successors) state = successors[0] already_visited.append(state) return state def random_eight_puzzle_state(): tiles = ['1', '2', '3', '4', '5', '6', '7', '8', ' '] shuffle(tiles) return eight_puzzle_state(tiles) 

----------------------------------------------------------------- search.py FILE from random import shuffle # CSC 380/480 Fall 2018 # A comparison of different strategies for 8-puzzle game. from eight_puzzle_state import * # from pegs_state import * #from jealous_state import * # a general search function that is given a start state, a goal state, # a strategy ('dfs', 'bfs, 'best') and a maximum number of states to # visit. Returns the number of states visited in order to find the goal # state, using the given strategy # best-first search expects the state objects to have a __lt__ method, # which will determine how a list of states is sorted. def search(start, goal, strategy, max_states, states_so_far=0): to_visit = [ start ] already_visited = set() while to_visit != [ ]: # input('anything ') state = to_visit.pop() # print('current state {}'.format(state)) if state == goal: return states_so_far elif states_so_far >= max_states: return states_so_far elif state in already_visited: pass else: already_visited.add(state) new_states = state.successors() shuffle(new_states) if strategy == 'dfs': to_visit = to_visit + new_states elif strategy == 'bfs': to_visit = new_states + to_visit elif strategy == 'best': total_states = to_visit + new_states to_visit = sorted(total_states, reverse=True) # print('Sorted states') # for s in to_visit: # print(s) states_so_far += 1 # if verbose: # print('defeat') return states_so_far # this compares search strategies. It runs each # strategy on start states 1 through n (some measure # of difficulty of the problem). Each is run the given # number of trials. A maximum number of states determines # when the search should terminate (and fail) def compare(strategies, max_states=10000, trials=10, easiest=1, hardest=10): for strat in strategies: print(',{}'.format(strat),end='') for level in range(easiest, hardest+1): print(' {}'.format(level),end="") for strat in strategies: total_states = 0 for trial in range(trials): start = start_state(level) goal = goal_state(level) total_states += search(start, goal, strat, max_states, False) print(',{}'.format(total_states//trials), end='') compare(['dfs', 'bfs', 'best'], 2000)