For CS50 AI Problem 0B, an error occurs when I try to deep copy the board in result(). What can I do?
Code:
"""
Tic Tac Toe Player
"""
import math
import copy
X = "X"
O = "O"
EMPTY = None
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_num = 0
O_num = 0
for i in board:
for j in i:
if j == X:
X_num += 1
else:
O_num += 1
if X_num == O_num:
return X
else:
return O
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
i_num = 0
j_num = 0
possible_actions = set()
for i in board:
for j in i:
if j == EMPTY:
possible_actions.add((i_num, j_num))
j_num += 1
i_num += 1
return possible_actions
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
new_board = copy.deepcopy(board)
for i in new_board:
for j in new_board:
if (i, j) == action:
if j != EMPTY:
raise ValueError('Action not possible')
else:
playing = player(new_board)
if playing == X:
j = X
else:
j = O
return new_board
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
vertical = []
diagonal1 = []
diagonal2 = []
for i in board:
if i[0] == i[1] == i[2] != EMPTY:
return i[0]
vertical.append([i[0], i[1], i[2]])
if i == board[0]:
diagonal1.append(i[0])
diagonal2.append(i[2])
elif i == board[1]:
diagonal1.append(i[1])
diagonal2.append(i[1])
else:
diagonal1.append(i[2])
diagonal2.append(i[0])
for i in vertical:
if i[0] == i[1] == i[2] != EMPTY:
return i[0]
if diagonal1[0] == diagonal1[1] == diagonal1[2] != EMPTY:
return diagonal1[0]
if diagonal2[0] == diagonal2[1] == diagonal2[2] != EMPTY:
return diagonal2[0]
return None
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
won = winner(board)
if won == X or won == O:
return True
else:
return False
def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
won = winner(board)
if won == X:
return 1
elif won == O:
return -1
else:
return 0
def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
set_possible_actions = actions(board)
possible_actions = []
playing = player(board)
for action in set_possible_actions:
action_result = main_minimax(result(board, action))
possible_actions.append([action, action_result])
best_action = possible_actions[0]
for action in possible_actions:
if playing == X:
if action[1] > best_action[1]:
best_action = action
else:
if action[1] < best_action[1]:
best_action = action
if terminal(board):
return None
return best_action[0]
def main_minimax(board):
if terminal(board):
return winner(board)
possible_actions = actions(board)
results = []
playing = player(board)
for action in possible_actions:
one_result = main_minimax(result(board, action))
results.append(one_result)
if playing == X:
best = results[0]
for one_result in results:
if one_result > best:
best = one_result
else:
best = results[0]
for one_result in results:
if one_result < best:
best = one_result
return best