24 Jan In this project, you will write a Python program for a miniature Isolation game on a 3-by-3 board. Your program should make a suggestion about the best possible move for Player 1 (the pla
In this project, you will write a Python program for a miniature “Isolation” game on a 3-by-3 board. Your program should make a suggestion about the best possible move for Player 1 (the player represented by Max nodes on the Min-Max search tree), and once Player makes his move, make the best move for Player 2 (the player represented by Min nodes on the Min-Max search tree), and iteratively enter rounds of moves till the end of game, in which one player cannot move and thus become the loser.
Project 1 – Minimax Search with Alpha-Beta Pruning
In this project, you will write a Python program for a miniature “Isolation” game on a 3-by-3 board. Your program should make a suggestion about the best possible move for Player 1 (the player represented by Max nodes on the Min-Max search tree), and once Player makes his move, make the best move for Player 2 (the player represented by Min nodes on the Min-Max search tree), and iteratively enter rounds of moves till the end of game, in which one player cannot move and thus become the loser.
In the game of isolation, at the beginning, Player 1 gets to place his piece anywhere on the game board, and Player 2 can place his piece anywhere remaining. From then on, two players move like queens in chess, i.e., for the next move either player can go any square that's horizontal or vertical or diagonal from the current position, except that one can't move through the opponent’s piece. Also, squares between the start and the end position remain obtainable for future moves. In other words, it's just where the piece lands that becomes unobtainable for future moves. Moreover, players do not attack each other. The players cannot go outside the boundaries of the game board, nor through a position that is currently or was previously occupied.
The objective of the game is to be the last player to move. The first player to get isolated (i.e., unable to move on their turn), loses.
You are given a Python program for a tic-tac-toe game on a 3-by-3 board. You need to modify the program such that it plays the isolation game.
Thoroughly test your program to make sure it works correctly in every situation. Submit your program file (the Python source codes in .py or .ipynb format).
,
# -*- coding: utf-8 -*- """ Spyder Editor This is a temporary script file. """ # We'll use the time module to measure the time of evaluating # game tree in every move. It's a nice way to show the # distinction between the basic Minimax and Minimax with # alpha-beta pruning 🙂 import time class Game: def __init__(self): self.initialize_game() def initialize_game(self): self.current_state = [['.','.','.'], ['.','.','.'], ['.','.','.']] # Player X always plays first self.player_turn = 'X' def draw_board(self): for i in range(0, 3): for j in range(0, 3): print('{}|'.format(self.current_state[i][j]), end=" ") print() print() # Determines if the made move is a legal move def is_valid(self, px, py): if px < 0 or px > 2 or py < 0 or py > 2: return False elif self.current_state[px][py] != '.': return False else: return True # Checks if the game has ended and returns the winner in each case def is_end(self): # Vertical win for i in range(0, 3): if (self.current_state[0][i] != '.' and self.current_state[0][i] == self.current_state[1][i] and self.current_state[1][i] == self.current_state[2][i]): return self.current_state[0][i] # Horizontal win for i in range(0, 3): if (self.current_state[i] == ['X', 'X', 'X']): return 'X' elif (self.current_state[i] == ['O', 'O', 'O']): return 'O' # Main diagonal win if (self.current_state[0][0] != '.' and self.current_state[0][0] == self.current_state[1][1] and self.current_state[0][0] == self.current_state[2][2]): return self.current_state[0][0] # Second diagonal win if (self.current_state[0][2] != '.' and self.current_state[0][2] == self.current_state[1][1] and self.current_state[0][2] == self.current_state[2][0]): return self.current_state[0][2] # Is whole board full? for i in range(0, 3): for j in range(0, 3): # There's an empty field, we continue the game if (self.current_state[i][j] == '.'): return None # It's a tie! return '.' # Player 'O' is max, in this case AI def max(self): # Possible values for maxv are: # -1 – loss # 0 – a tie # 1 – win # We're initially setting it to -2 as worse than the worst case: maxv = -2 px = None py = None result = self.is_end() # If the game came to an end, the function needs to return # the evaluation function of the end. That can be: # -1 – loss # 0 – a tie # 1 – win if result == 'X': return (-1, 0, 0) elif result == 'O': return (1, 0, 0) elif result == '.': return (0, 0, 0) for i in range(0, 3): for j in range(0, 3): if self.current_state[i][j] == '.': # On the empty field player 'O' makes a move and calls Min # That's one branch of the game tree. self.current_state[i][j] = 'O' (m, min_i, min_j) = self.min() # Fixing the maxv value if needed if m > maxv: maxv = m px = i py = j # Setting back the field to empty self.current_state[i][j] = '.' return (maxv, px, py) # Player 'X' is min, in this case human def min(self): # Possible values for minv are: # -1 – win # 0 – a tie # 1 – loss # We're initially setting it to 2 as worse than the worst case: minv = 2 qx = None qy = None result = self.is_end() if result == 'X': return (-1, 0, 0) elif result == 'O': return (1, 0, 0) elif result == '.': return (0, 0, 0) for i in range(0, 3): for j in range(0, 3): if self.current_state[i][j] == '.': self.current_state[i][j] = 'X' (m, max_i, max_j) = self.max() if m < minv: minv = m qx = i qy = j self.current_state[i][j] = '.' return (minv, qx, qy) def play(self): while True: self.draw_board() self.result = self.is_end() # Printing the appropriate message if the game has ended if self.result != None: if self.result == 'X': print('The winner is X!') elif self.result == 'O': print('The winner is O!') elif self.result == '.': print("It's a tie!") self.initialize_game() return # If it's player's turn if self.player_turn == 'X': while True: start = time.time() (m, qx, qy) = self.min() end = time.time() print('Evaluation time: {}s'.format(round(end – start, 7))) print('Recommended move: X = {}, Y = {}'.format(qx, qy)) px = int(input('Insert the X coordinate: ')) py = int(input('Insert the Y coordinate: ')) (qx, qy) = (px, py) if self.is_valid(px, py): self.current_state[px][py] = 'X' self.player_turn = 'O' break else: print('The move is not valid! Try again.') # If it's AI's turn else: (m, px, py) = self.max() self.current_state[px][py] = 'O' self.player_turn = 'X' def max_alpha_beta(self, alpha, beta): maxv = -2 px = None py = None result = self.is_end() if result == 'X': return (-1, 0, 0) elif result == 'O': return (1, 0, 0) elif result == '.': return (0, 0, 0) for i in range(0, 3): for j in range(0, 3): if self.current_state[i][j] == '.': self.current_state[i][j] = 'O' (m, min_i, in_j) = self.min_alpha_beta(alpha, beta) if m > maxv: maxv = m px = i py = j self.current_state[i][j] = '.' # Next two ifs in Max and Min are the only difference between regular algorithm and minimax if maxv >= beta: return (maxv, px, py) if maxv > alpha: alpha = maxv return (maxv, px, py) def min_alpha_beta(self, alpha, beta): minv = 2 qx = None qy = None result = self.is_end() if result == 'X': return (-1, 0, 0) elif result == 'O': return (1, 0, 0) elif result == '.': return (0, 0, 0) for i in range(0, 3): for j in range(0, 3): if self.current_state[i][j] == '.': self.current_state[i][j] = 'X' (m, max_i, max_j) = self.max_alpha_beta(alpha, beta) if m < minv: minv = m qx = i qy = j self.current_state[i][j] = '.' if minv <= alpha: return (minv, qx, qy) if minv < beta: beta = minv return (minv, qx, qy) def play_alpha_beta(self): while True: self.draw_board() self.result = self.is_end() if self.result != None: if self.result == 'X': print('The winner is X!') elif self.result == 'O': print('The winner is O!') elif self.result == '.': print("It's a tie!") self.initialize_game() return if self.player_turn == 'X': while True: start = time.time() (m, qx, qy) = self.min_alpha_beta(-2, 2) end = time.time() print('Evaluation time: {}s'.format(round(end – start, 7))) print('Recommended move: X = {}, Y = {}'.format(qx, qy)) px = int(input('Insert the X coordinate: ')) py = int(input('Insert the Y coordinate: ')) qx = px qy = py if self.is_valid(px, py): self.current_state[px][py] = 'X' self.player_turn = 'O' break else: print('The move is not valid! Try again.') else: (m, px, py) = self.max_alpha_beta(-2, 2) self.current_state[px][py] = 'O' self.player_turn = 'X' def main(): g = Game() g.play() #g.play_alpha_beta() if __name__ == "__main__": main()
Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Fill in all the assignment paper details that are required in the order form with the standard information being the page count, deadline, academic level and type of paper. It is advisable to have this information at hand so that you can quickly fill in the necessary information needed in the form for the essay writer to be immediately assigned to your writing project. Make payment for the custom essay order to enable us to assign a suitable writer to your order. Payments are made through Paypal on a secured billing page. Finally, sit back and relax.
About Wridemy
We are a professional paper writing website. If you have searched a question and bumped into our website just know you are in the right place to get help in your coursework. We offer HIGH QUALITY & PLAGIARISM FREE Papers.
How It Works
To make an Order you only need to click on “Order Now” and we will direct you to our Order Page. Fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.
Are there Discounts?
All new clients are eligible for 20% off in their first Order. Our payment method is safe and secure.