# -*- coding: utf-8 -*-"""Spyder EditorThis 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 timeclass 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()

The price is based on these factors:

Academic level

Number of pages

Urgency

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more
## Recent Comments