I'm trying to implement a minimax algorithm to create a tic-tac-toe bot, but i'm getting RecursionError: maximum recursion depth exceeded in comparison error. I have the code below. I've added comments that mention what a function is supposed to do. I last Can you take a look at the code below. Thank you
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.
"""
o_counter = 0
x_counter = 0
for i in board:
for j in i:
if j == 'X':
x_counter += 1
elif j == 'O':
o_counter += 1
if x_counter == 0 and o_counter == 0:
return 'O'
elif x_counter > o_counter:
return 'O'
elif o_counter > x_counter:
return 'X'
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
action = []
for i in range(3):
for j in range(3):
if board[i][j] is None:
action.append([i, j])
return action
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
p = player(board)
i, j = action
board[i][j] = p
return board
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
i = 1
if board[0][0] == board[1][1] == board[2][2] and (board[0][0] == 'X' or board[0][0] == 'O'):
return board[0][0]
elif board[0][2] == board[1][1] == board[2][0] and (board[0][2] == 'X' or board[0][2] == 'O'):
return board[0][2]
else:
if board[0][0] == board[0][1] == board[0][2] and (board[0][0] == 'X' or board[0][0] == 'O'):
return board[0][0]
elif board[i][0] == board[i][1] == board[i][2] and (board[i][0] == 'X' or board[i][0] == 'O'):
return board[i][0]
elif board[2][0] == board[2][1] == board[2][2] and (board[2][0] == 'X' or board[2][0] == 'O'):
return board[2][0]
elif board[0][0] == board[1][0] == board[2][0] and (board[0][0] == 'X' or board[0][0] == 'O'):
return board[0][0]
elif board[0][i] == board[1][i] == board[2][i] and (board[0][i] == 'X' or board[0][i] == 'O'):
return board[0][i]
elif board[0][2] == board[1][2] == board[2][2] and (board[0][2] == 'X' or board[0][2] == 'O'):
return board[0][2]
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
check = True
if winner(board) == 'X' or winner(board) == 'O':
return True
elif check:
for i in board:
for j in i:
if j is None:
check = False
return False
if check:
return True
else:
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
elif winner(board) == 'O':
return -1
else:
return 0
def maximum(board):
if terminal(board):
return utility(board)
v = -9999999999999999999999
for action in actions(board):
m = minimum(result(board, action))
if m > v:
v = m
return v
def minimum(board):
if terminal(board):
return utility(board)
v = 9999999999999999999999
for action in actions(board):
m = maximum(result(board, action))
if m < v:
v = m
return v
def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
return_action = None
curr_player = player(board)
states = actions(board)
temp_board = board.copy()
score = 0
temp_score = 0
for state in states:
i, j = state
if curr_player == 'X':
temp_board[i][j] = curr_player
temp_score = maximum(temp_board)
elif curr_player == 'O':
temp_board[i][j] = curr_player
temp_score = minimum(temp_board)
if curr_player == 'X':
if temp_score > score:
score = temp_score
return_action = state
elif curr_player == 'O':
if temp_score < score:
score = temp_score
return_action = state
return return_action
Your issue is your stuck in an infinite condition which means you keep recursively calling the function till you reach the recursion limit. Your issue comes in your player function and how you decide whos turn is next. After O plays in position 0,0 and X plays in position 0,1 you then try to decide who is next to play
So you count and both O and X have placed 1 token each. However your logic to decide who is next doesnt cater for this board state.
if x_counter == 0 and o_counter == 0:
return 'O'
elif x_counter > o_counter:
return 'O'
elif o_counter > x_counter:
return 'X'
so when x_counter and y_counter are equal but are not 0 you dont return anything. This results in None being returned by the function So your stuck and never then place a token in position 0,2. If O always goes first then any time x_counter == o_counter you should return '0' so change it to
if x_counter == o_counter:
return 'O'
elif x_counter > o_counter:
return 'O'
elif o_counter > x_counter:
return 'X'