Last active
November 23, 2020 12:25
-
-
Save UrosOgrizovic/4127dadf4f919196dfd4341075400c9c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
tic-tac-toe using minimax | |
Uros Ogrizovic | |
""" | |
from time import sleep | |
empty_space_sign = 'E' | |
spaces = [[empty_space_sign, empty_space_sign, empty_space_sign], | |
[empty_space_sign, empty_space_sign, empty_space_sign], | |
[empty_space_sign, empty_space_sign, empty_space_sign]] | |
def check_vertical_termination(): | |
""" | |
checks for column-wise termination | |
:return: 0 (no termination), 1 (computer wins), -1 (player wins) | |
""" | |
pairs = [(0, 0), (0, 1), (0, 2)] | |
for i, j in pairs: | |
if spaces[i][j] == spaces[(i+1) % 3][j] == spaces[(i+2) % 3][j] != empty_space_sign: | |
player = -1 if spaces[i][j] == 'X' else 1 | |
return player | |
return 0 | |
def check_diagonal_termination(): | |
""" | |
checks for diagonal-wise termination | |
:return: 0 (no termination), 1 (computer wins), -1 (player wins) | |
""" | |
if spaces[0][0] == spaces[1][1] == spaces[2][2] != empty_space_sign: | |
player = -1 if spaces[1][1] == 'X' else 1 | |
return player | |
elif spaces[0][2] == spaces[1][1] == spaces[2][0] != empty_space_sign: | |
player = -1 if spaces[1][1] == 'X' else 1 | |
return player | |
return 0 | |
def check_horizontal_termination(): | |
""" | |
checks for row-wise termination | |
:return: 0 (no termination), 1 (computer wins), -1 (player wins) | |
""" | |
pairs = [(0, 0), (1, 0), (2, 0)] | |
for i, j in pairs: | |
if spaces[i][j] == spaces[i][(j+1) % 3] == spaces[i][(j+2) % 3] != empty_space_sign: | |
player = -1 if spaces[i][j] == 'X' else 1 | |
return player | |
return 0 | |
def check_termination(): | |
""" | |
checks for three types of termination: column-wise, diagonal-wise and row-wise | |
:return: 0 (not over), 1 (computer wins) or -1 (human wins) | |
""" | |
val = check_diagonal_termination() | |
if val != 0: | |
return val | |
val = check_vertical_termination() | |
if val != 0: | |
return val | |
val = check_horizontal_termination() | |
if val != 0: | |
return val | |
return 0 | |
def place_sign(sign, row, col): | |
""" | |
places 'X' or 'O' at [row][col] space on board. | |
Checks if space is already taken. | |
:param sign: 'X' or 'O' | |
:param row: row index | |
:param col: column index | |
:return: -1 if space is already taken | |
""" | |
if spaces[row][col] == empty_space_sign: | |
spaces[row][col] = sign | |
else: | |
print("Space already taken. Try again.") | |
return -1 # used if player tries to play on square that is taken | |
def get_possible_moves(): | |
""" | |
checks which spaces are empty, and | |
returns a list of those spaces/moves | |
:return: list of possible moves | |
""" | |
possible_moves = [] | |
for i in range(len(spaces)): | |
for j in range(len(spaces)): | |
if spaces[i][j] == empty_space_sign: | |
possible_moves.append((i, j)) | |
return possible_moves | |
def minimax(player): | |
""" | |
minimax algorithm. The computer is the maximizer, | |
whereas the human is the minimizer. | |
:param player: 1 (computer), -1 (human) | |
:return: | |
""" | |
winner = check_termination() | |
if winner != 0: # if the game is over | |
return winner, -1, -1 | |
possible_moves = get_possible_moves() | |
if len(possible_moves) == 0: # no possible moves, i.e. no empty spaces | |
return 0, -1, -1 # draw | |
# human minimizes, computer maximizes | |
sign, best_score = ('X', 10) if player == -1 else ('O', -10) | |
score, best_row, best_col = 0, 0, 0 | |
for move in possible_moves: | |
place_sign(sign, move[0], move[1]) | |
score, _, _ = minimax(player * -1) # change player when calling minimax | |
spaces[move[0]][move[1]] = 'E' # undo move | |
if player == 1 and score > best_score: # update best score and best move | |
best_score, best_row, best_col = score, move[0], move[1] | |
if player == -1 and score < best_score: # update best score and best move | |
best_score, best_row, best_col = score, move[0], move[1] | |
return best_score, best_row, best_col | |
def display_board(): | |
""" | |
displays board in console | |
:return: | |
""" | |
for i in range(len(spaces)): | |
for j in range(len(spaces)): | |
print(spaces[i][j], end=' ') | |
print('') | |
if __name__ == "__main__": | |
print("NOTE: Upper-left corner has coordinates (1, 1), bottom-right corner has coordinates (3, 3)") | |
while True: | |
display_board() | |
while True: | |
row = int(input('Which row do you want to place X on? ')) - 1 | |
col = int(input('Which column do you want to place X on? ')) - 1 | |
if place_sign('X', row, col) != -1: | |
break | |
if check_termination() == -1: | |
display_board() | |
print("Human wins.") | |
break | |
display_board() | |
print('Computer\'s turn. Please wait...') | |
score, row, col = minimax(1) | |
sleep(1) # better UX, couldn't resist :) | |
if score == 0 and len(get_possible_moves()) == 0: | |
display_board() | |
print("The game is a draw.") | |
break | |
print('Computer chooses:', row + 1, col + 1) | |
place_sign('O', row, col) | |
if check_termination() == 1: | |
display_board() | |
print("Computer wins.") | |
break |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment