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()
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
