you will implement the A* algorithm to solve the sliding tile puzzle game. Your goal is to return the instructions for solving the puzzle and show the configuration after each move. A majority of the code is written, I need help computing 3 functions in the PuzzleState class from the source code I provided below (see where comments ""TODO"" are). Also is this for Artificial Intelligence
Requirements
You are to create a program in Python 3 that performs the following:
Displays the number of states that A* had to visit in order to get to the solution
Additional Requirements
import numpy as np import queue class PuzzleState(): SOLVED_PUZZLE = np.arange(9).reshape((3, 3)) def __init__(self,conf,g,predState): self.puzzle = conf # Configuration of the state self.gcost = g # Path cost self._compute_heuristic_cost() # Set heuristic cost self.fcost = self.gcost + self.hcost self.pred = predState # Predecesor state self.zeroloc = np.argwhere(self.puzzle == 0)[0] self.action_from_pred = None def __hash__(self): return tuple(self.puzzle.ravel()).__hash__() def _compute_heuristic_cost(self): """ TODO """ def is_goal(self): return np.array_equal(PuzzleState.SOLVED_PUZZLE,self.puzzle) def __eq__(self, other): return np.array_equal(self.puzzle, other.puzzle) def __lt__(self, other): return self.fcost < other.fcost def __str__(self): return np.str(self.puzzle) move = 0 def show_path(self): if self.pred is not None: self.pred.show_path() if PuzzleState.move==0: print('START') else: print('Move',PuzzleState.move, 'ACTION:', self.action_from_pred) PuzzleState.move = PuzzleState.move + 1 print(self) def can_move(self, direction): """ TODO """ def gen_next_state(self, direction): """ TODO """ # load random start state onto frontier priority queue frontier = queue.PriorityQueue() a = np.loadtxt('mp1input.txt', dtype=np.int32) start_state = PuzzleState(a,0,None) frontier.put(start_state) closed_set = set() num_states = 0 while not frontier.empty(): # choose state at front of priority queue next_state = frontier.get() # if goal then quit and return path if next_state.is_goal(): next_state.show_path() break # Add state chosen for expansion to closed_set closed_set.add(next_state) num_states = num_states + 1 # Expand state (up to 4 moves possible) possible_moves = ['up','down','left','right'] for move in possible_moves: if next_state.can_move(move): neighbor = next_state.gen_next_state(move) if neighbor in closed_set: continue if neighbor not in frontier.queue: frontier.put(neighbor) # If it's already in the frontier, it's guaranteed to have lower cost, so no need to update print('\nNumber of states visited =',num_states)
The view of every programmer towards the program is different.
I will try to solve the Puzzle in my own ways and I will try to complete your TODO list.
I was solving this using 3 files
Save the first file as game_state.py (Class name is Gamestate)
CODE:
import numpy as np class GameState(): def __init__(self, state, goal_state, level, parent = None, heuristic_func = "manhattan"): self.__state = state self.__goal_state = goal_state self.__level = level self.__heuristic_func = heuristic_func self.__heuristic_score = level self.__parent = parent self.calculate_fitness() def __hash__(self): return hash(str(self.__state)) def __lt__(self, other): return self.__heuristic_score < other.__heuristic_score def __eq__(self, other): return self.__heuristic_score == other.__heuristic_score def __gt__(self, other): return self.__heuristic_score > other.__heuristic_score def get_state(self): return self.__state def get_score(self): return self.__heuristic_score def get_level(self): return self.__level def get_parent(self): return self.__parent def calculate_fitness(self): if self.__heuristic_func == "misplaced_tiles": for cur_tile, goal_tile in zip(self.__state, self.__goal_state): if cur_tile != goal_tile: self.__heuristic_score += 1 elif self.__heuristic_func == "manhattan": for cur_tile in self.__state: cur_idx = self.__state.index(cur_tile) goal_idx = self.__goal_state.index(cur_tile) cur_i, cur_j = cur_idx // int(np.sqrt(len(self.__state))), cur_idx % int(np.sqrt(len(self.__state))) goal_i, goal_j = goal_idx // int(np.sqrt(len(self.__state))), goal_idx % int(np.sqrt(len(self.__state))) self.__heuristic_score += self.calculate_manhattan(cur_i, cur_j, goal_i, goal_j) else: print('Unknown heuristic function is being used.') def calculate_manhattan(self, x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2)
Save the second file as solver.py (Class name is Solver)
CODE:
from queue import PriorityQueue, Queue from game_state import GameState import numpy as np import time class Solver(): def __init__(self, init_state, goal_state, heuristic_func = "manhattan", max_iter = 2500): self.__init_state = init_state self.__goal_state = goal_state self.__heuristic_func = heuristic_func self.__MAX = 100000 self.__max_iter = max_iter self.__path = [] self.__number_of_steps = 0 self.__summary = "" def set_max_iter(self, max_iter): self.__max_iter = max_iter def get_path(self): return self.__path def get_summary(self): return self.__summary def solve_a_star(self): x_axis = [1, 0, -1, 0] y_axis = [0, 1, 0, -1] level = 0 visited_nodes = set() start_time = time.clock() nodes = PriorityQueue(self.__MAX) init_node = GameState(self.__init_state.flatten().tolist(), self.__goal_state.flatten().tolist(), level, parent = None, heuristic_func = self.__heuristic_func) nodes.put(init_node) epochs = 0 while nodes.qsize() and epochs <= self.__max_iter: epochs += 1 cur_node = nodes.get() cur_state = cur_node.get_state() if str(cur_state) in visited_nodes: continue visited_nodes.add(str(cur_state)) if cur_state == self.__goal_state.flatten().tolist(): self.__summary = str("A* took " + str(cur_node.get_level()) + " steps to get from initial state to the desired goal, visited total of " + str(epochs) + " nodes, and took around " + str(np.round(time.clock() - start_time, 4)) + " seconds to reach the desired solution.") while cur_node.get_parent(): self.__path.append(cur_node) cur_node = cur_node.get_parent() break empty_tile = cur_state.index(0) i, j = empty_tile // self.__goal_state.shape[0], empty_tile % self.__goal_state.shape[0] cur_state = np.array(cur_state).reshape(self.__goal_state.shape[0], self.__goal_state.shape[0]) for x, y in zip(x_axis, y_axis): new_state = np.array(cur_state) if i + x >= 0 and i + x < self.__goal_state.shape[0] and j + y >= 0 and j + y < self.__goal_state.shape[0]: new_state[i, j], new_state[i+x, j+y] = new_state[i+x, j+y], new_state[i, j] game_state = GameState(new_state.flatten().tolist(), self.__goal_state.flatten().tolist(), cur_node.get_level() + 1, cur_node, self.__heuristic_func) if str(game_state.get_state()) not in visited_nodes: nodes.put(game_state) if epochs > self.__max_iter: print('This grid setting is not solvable') return self.__path def solve_bfs(self): x_axis = [1, 0, -1, 0] y_axis = [0, 1, 0, -1] level = 0 visited_nodes = set() start_time = time.clock() nodes = Queue(self.__MAX) init_node = GameState(self.__init_state.flatten().tolist(), self.__goal_state.flatten().tolist(), level, parent = None, heuristic_func = self.__heuristic_func) nodes.put(init_node) epochs = 0 while nodes.qsize() and epochs <= self.__max_iter: epochs += 1 cur_node = nodes.get() cur_state = cur_node.get_state() if str(cur_state) in visited_nodes: continue visited_nodes.add(str(cur_state)) if cur_state == self.__goal_state.flatten().tolist(): self.__summary = str("BFS took " + str(cur_node.get_level()) + " steps to get from initial state to the desired goal, visited total of " + str(epochs) + " nodes, and took around " + str(np.round(time.clock() - start_time, 4)) + " seconds to reach the desired solution.") while cur_node.get_parent(): self.__path.append(cur_node) cur_node = cur_node.get_parent() break empty_tile = cur_state.index(0) i, j = empty_tile // self.__goal_state.shape[0], empty_tile % self.__goal_state.shape[0] cur_state = np.array(cur_state).reshape(self.__goal_state.shape[0], self.__goal_state.shape[0]) for x, y in zip(x_axis, y_axis): new_state = np.array(cur_state) if i + x >= 0 and i + x < self.__goal_state.shape[0] and j + y >= 0 and j + y < self.__goal_state.shape[0]: new_state[i, j], new_state[i+x, j+y] = new_state[i+x, j+y], new_state[i, j] game_state = GameState(new_state.flatten().tolist(), self.__goal_state.flatten().tolist(), cur_node.get_level() + 1, cur_node, self.__heuristic_func) if str(game_state.get_state()) not in visited_nodes: nodes.put(game_state) if epochs > self.__max_iter: print('This grid setting is not solvable') return self.__path
Save the third file as sliding_puzzle.py
CODE:
import numpy as np from solver import Solver import sys, getopt #samples #goal_state = np.array([[3, 1, 2], # [4, 7, 5], # [0, 6, 8]]) # #init_state = np.array([[0, 1, 2], # [3, 4, 5], # [6, 7, 8]]) def BFS(init_state, goal_state, max_iter, heuristic): solver = Solver(init_state, goal_state, heuristic, max_iter) path = solver.solve_bfs() if len(path) == 0: exit(1) init_idx = init_state.flatten().tolist().index(0) init_i, init_j = init_idx // goal_state.shape[0], init_idx % goal_state.shape[0] print() print('INITIAL STATE') for i in range(goal_state.shape[0]): print(init_state[i, :]) print() for node in reversed(path): cur_idx = node.get_state().index(0) cur_i, cur_j = cur_idx // goal_state.shape[0], cur_idx % goal_state.shape[0] new_i, new_j = cur_i - init_i, cur_j - init_j if new_j == 0 and new_i == -1: print('Moved UP from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) elif new_j == 0 and new_i == 1: print('Moved DOWN from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) elif new_i == 0 and new_j == 1: print('Moved RIGHT from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) else: print('Moved LEFT from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) print('Score using ' + heuristic + ' heuristic is ' + str(node.get_score() - node.get_level()) + ' in level ' + str(node.get_level())) init_i, init_j = cur_i, cur_j for i in range(goal_state.shape[0]): print(np.array(node.get_state()).reshape(goal_state.shape[0], goal_state.shape[0])[i, :]) print() print(solver.get_summary()) def A_star(init_state, goal_state, max_iter, heuristic): solver = Solver(init_state, goal_state, heuristic, max_iter) path = solver.solve_a_star() if len(path) == 0: exit(1) init_idx = init_state.flatten().tolist().index(0) init_i, init_j = init_idx // goal_state.shape[0], init_idx % goal_state.shape[0] print() print('INITIAL STATE') for i in range(goal_state.shape[0]): print(init_state[i, :]) print() for node in reversed(path): cur_idx = node.get_state().index(0) cur_i, cur_j = cur_idx // goal_state.shape[0], cur_idx % goal_state.shape[0] new_i, new_j = cur_i - init_i, cur_j - init_j if new_j == 0 and new_i == -1: print('Moved UP from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) elif new_j == 0 and new_i == 1: print('Moved DOWN from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) elif new_i == 0 and new_j == 1: print('Moved RIGHT from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) else: print('Moved LEFT from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j))) print('Score using ' + heuristic + ' heuristic is ' + str(node.get_score() - node.get_level()) + ' in level ' + str(node.get_level())) init_i, init_j = cur_i, cur_j for i in range(goal_state.shape[0]): print(np.array(node.get_state()).reshape(goal_state.shape[0], goal_state.shape[0])[i, :]) print() print(solver.get_summary()) def main(argv): max_iter = 5000 heuristic = "manhattan" algorithm = "a_star" n = 3 try: opts, args = getopt.getopt(argv,"hn:",["mx=", "heur=", "astar", "bfs"]) except getopt.GetoptError: print('python sliding_puzzle.py -h <help> -n <matrix shape ex: n = 3 -> 3x3 matrix> --mx <maximum_nodes> --heur <heuristic> --astar (default algorithm) or --bfs') sys.exit(2) for opt, arg in opts: if opt == '-h': print('python sliding_puzzle.py -h <help> -n <matrix shape ex: n = 3 -> 3x3 matrix> --mx <maximum_nodes> --heur <heuristic> --astar (default algorithm) or --bfs') sys.exit() elif opt == '-n': n = int(arg) elif opt in ("--mx"): max_iter = int(arg) elif opt in ("--heur"): if arg == "manhattan" or arg == "misplaced_tiles": heuristic = (arg) elif opt in ("--astar"): algorithm = "a_star" elif opt in ("--bfs"): algorithm = "bfs" while True: try: init_state = input("Enter a list of " + str(n * n) + " numbers representing the inital state, SEPERATED by WHITE SPACE(1 2 3 etc.): ") init_state = init_state.split() for i in range(len(init_state)): init_state[i] = int(init_state[i]) goal_state = input("Enter a list of " + str(n * n) + " numbers representing the goal state, SEPERATED by WHITE SPACE(1 2 3 etc.): ") goal_state = goal_state.split() for i in range(len(goal_state)): goal_state[i] = int(goal_state[i]) if len(goal_state) == len(init_state) and len(goal_state) == n * n: break else: print("Please re-enter the input again correctly") except Exception as ex: print(ex) init_state = np.array(init_state).reshape(n, n) goal_state = np.array(goal_state).reshape(n, n) if algorithm == "a_star": A_star(init_state, goal_state, max_iter, heuristic) else: BFS(init_state, goal_state, max_iter, heuristic) if __name__ == "__main__": main(sys.argv[1:])
I hope it will help you.
Thanks
you will implement the A* algorithm to solve the sliding tile puzzle game. Your goal is...
Q1. Write a program to simulate a grocery waiting queue. Your program should ask the user if they want to add a customer to the queue, serve the next customer in the queue, or exit. When a customer is served or added to the queue, the program should print out the name of that customer and the remaining customers in the queue. The store has two queues: one is for normal customers, another is for VIP customers. Normal customers can...
9c Python 1) What is the output of the following code? Refer to the Weapon, Blaster, and Bowcaster classes. File 1: weapon.py class Weapon: def init ( self, power ): self.mPower = power return Example: import blaster from bowcaster import Bowcaster def getPower( self ): return self.mPower han = blaster.Blaster( 8000, 20 ) print("HP:", han.getPower( ) ) print( "HR:", han.getFireRate()) chewie = Bowcaster( 3000, 6) print( "CB:", chewie.getBarrelSize()) print( "CR:", chewie.getRange()) File 2: blaster.py import weapon class Blaster( weapon. Weapon):...
The goal of this code is to draw a smiley face and be able to change emotion, mouth and eyes. Use the demo code below to fill in the blanks ( ), as well as add any other methods or data that is needed. All blanks should be completed with a single line of code (or partial line). You should not modify any other code that exists. Only remove the blanks and add other missing methods. Use a radius of...
10q I need help this is a python language For the following question, refer to the Python module on the right, as well as the name of the file that contains each module. 1) What is the output of the following code?. import animals alist = [animals.cat('Garfield'), animals.Dog('odie'), animals. Fox ('Nicholas P. wilde'), animals. Animal ('Judy Hopps')] File animals.py class Animal: def _init__(self, name): self.name = name def getName(self): return self.name for a in alist: print( a.getName() + ', '...
Major Homework #2 Implement a C program major_hw2.c to solve the 15-puzzle problem using the A* search algorithm. Please include pictures that the code runs and shows the different states as it reaches goal state please. 1. Objectives • To gain more experience on using pointers and linked lists in C programs. • To learn how to solve problems using state space search and A* search algorithm. 2. Background A* search and 15-puzzle problem have been introduced in the class....
Major Homework #2 Implement a C program major_hw2.c to solve the 15-puzzle problem using the A* search algorithm. 1. Objectives • To gain more experience on using pointers and linked lists in C programs. • To learn how to solve problems using state space search and A* search algorithm. 2. Background A* search and 15-puzzle problem have been introduced in the class. For more information, please read the wiki page of 15-puzzle problem at https://en.wikipedia.org/wiki/15_puzzle, and the wiki page of...
In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares. Write a function bool Solvable(int start, int[] squares) that takes a starting position of the marker along with the array of squares. The function should return true if it is possible to solve the puzzle from the starting configuration, and false if it is impossible. You may assume all the integers in the array are positive except for the last entry, the goal...
I need to complete the code by implementing the min function and the alpha betta pruning in order to complete the tic tac toe game using pything. code: # -*- coding: utf-8 -*- """ Created on: @author: """ import random from collections import namedtuple GameState = namedtuple('GameState', 'to_move, utility, board, moves') infinity = float('inf') game_result = { 1:"Player 1 Wins", -1:"Player 2 Wins", 0:"It is a Tie" } class Game: """To create a game, subclass this class and implement actions,...
10p Python For the following question, refer to the Python module on the right, as well as the code below. 1) What is the output of the following code? #dodgeable.py #main dodgeable.py import dodgeable class Locatable: def NUM_CARS = 3 init (self,x,y): NUM TRUCKS = 2 self.mX = X WIDTH = 60 self.mY = y def setx (self,x): def main (): self.mX = x object_list = [] def sety (self, y): self.mY = y for i in range (NUM_CARS) :...
11q Language is python need help 1) What is the output of the following code? Refer to the class defined here. Example: File 1: asset.py import asset class Asset: brains = asset.Asset( "Brains" ) strength = asset. Asset( "Strength" ) steel = asset.Asset( "Steel" ) wheelbarrow = asset. Asset( "Wheelbarrow" ) cloak = asset.Asset( "Cloak" ) def _init__( self, name): self.mName = name return def getName( self ): return self.mName al = strength + steel a2 = cloak + wheelbarrow...