Last active
March 5, 2022 19:36
-
-
Save florestankorp/715d9a97f771e023ae244b682ea42814 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 Player | |
""" | |
import math | |
import random | |
import copy | |
X = "X" | |
O = "O" | |
EMPTY = None | |
turn = 0 | |
WINNING_STATES = [ | |
# HORIZONTAL | |
{(0, 0), | |
(0, 1), | |
(0, 2)}, | |
{(1, 0), | |
(1, 1), | |
(1, 2)}, | |
{(2, 0), | |
(2, 1), | |
(2, 2)}, | |
# VERTICAL | |
{(0, 0), | |
(1, 0), | |
(2, 0)}, | |
{(0, 1), | |
(1, 1), | |
(2, 1)}, | |
{(0, 2), | |
(1, 2), | |
(2, 2)}, | |
# DIAGONAL | |
{(0, 0), | |
(1, 1), | |
(2, 2)}, | |
{(0, 2), | |
(1, 1), | |
(2, 0)} | |
] | |
def initial_state(): | |
""" | |
Returns starting state of the board. | |
""" | |
return [[EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY]] | |
def player(board): | |
""" | |
Returns player who has the next turn on a board. | |
""" | |
x_count = 0 | |
o_count = 0 | |
for row_number, row in enumerate(board): | |
for cell_number, cell in enumerate(row): | |
if cell == X: | |
x_count += 1 | |
if cell == O: | |
o_count += 1 | |
# if X starts, then O goes after and will always have to catch up... | |
if o_count == x_count: | |
return X | |
# if there are more O's then it's X's turn | |
if x_count > o_count: | |
return O | |
else: | |
return X | |
def actions(board): | |
""" | |
Returns set of all possible actions (i, j) available on the board. | |
""" | |
actions = [] | |
for row_number, row in enumerate(board): | |
for cell_number, cell in enumerate(row): | |
if cell == EMPTY: | |
actions.append((row_number, cell_number)) | |
return actions | |
def result(board, action): | |
""" | |
Returns the board that results from making move (i, j) on the board. | |
""" | |
board_copy = copy.deepcopy(board) | |
if not action in actions(board_copy): | |
raise BaseException('The action you provided does not exist') | |
ROW = action[0] | |
CELL = action[1] | |
board_copy[ROW][CELL] = player(board_copy) | |
return board_copy | |
def winner(board): | |
""" | |
Returns the winner of the game, if there is one. | |
""" | |
x_cells = set() | |
o_cells = set() | |
for row_number, row in enumerate(board): | |
for cell_number, cell in enumerate(row): | |
if cell == X: | |
x_cells.add((row_number, cell_number)) | |
if cell == O: | |
o_cells.add((row_number, cell_number)) | |
for winning_state in WINNING_STATES: | |
if all(elements in x_cells for elements in winning_state): | |
return X | |
if all(elements in o_cells for elements in winning_state): | |
return O | |
def terminal(board): | |
""" | |
Returns True if game is over, False otherwise. | |
""" | |
if winner(board) == X or winner(board) == O or len(actions(board)) == 0: | |
return True | |
return False | |
def utility(board): | |
""" | |
Returns 1 if X has won the game, -1 if O has won, 0 otherwise. | |
""" | |
if winner(board) == X: | |
return 1 | |
if winner(board) == O: | |
return -1 | |
return 0 | |
def minimax(board): | |
""" | |
Returns the optimal action for the current player on the board. | |
""" | |
if terminal(board): | |
return None | |
current_player = player(board) | |
acts = actions(board) | |
result_action = {} | |
key = None | |
min_player = X | |
max_player = O | |
for index, action in enumerate(acts): | |
r = result(board, action) | |
result_action[index] = min_value( | |
r) if current_player == max_player else max_value(r) | |
if current_player == min_player: | |
key = min(result_action, key=result_action.get) | |
if current_player == max_player: | |
key = max(result_action, key=result_action.get) | |
return acts[key] | |
def max_value(board): | |
""" | |
Returns highest value for the state provided | |
""" | |
if terminal(board): | |
return utility(board) | |
value = -1000 | |
for action in actions(board): | |
r = result(board, action) | |
value = max(value, min_value(r)) | |
return value | |
def min_value(board): | |
""" | |
Returns lowest value for the state provided | |
""" | |
if terminal(board): | |
return utility(board) | |
value = 1000 | |
for action in actions(board): | |
r = result(board, action) | |
value = min(value, max_value(r)) | |
return value |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment