我正在尝试实现一个minimax算法，以创建一个玩井字游戏与播放器的机器人。gui功能位于另一个文件中，并且工作正常。无论何时，只要该机器人开始移动，gui文件就会使用以下代码调用该文件。我已经包含了每个函数的注释功能，并且我相信除minimax（）之外的所有函数都有效每当我运行脚本时，都会显示此错误：“ RecursionError：在比较中超出了最大递归深度”
如果不清楚，请评论，我会尽力简化它。谢谢您的帮助
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.
"""
if board[0][0] == board[1][1] == board[2][2]:
return board[0][0]
elif board[0][2] == board[1][1] == board[2][0]:
return board[0][2]
else:
for i in range(3):
if board[i][0] == board[i][1] == board[i][2]:
return board[i][0]
elif board[0][i] == board[1][i] == board[2][i]:
return board[0][i]
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
if winner(board) == 'X' or winner(board) == 'O' :
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 minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
return_action = [0, 0]
available_actions = actions(board)
score = 0
temp_board = board
for action in range(len(available_actions)):
temp_score = 0
i, j = available_actions[action]
temp_board[i][j] = player(temp_board)
if winner(temp_board) == 'X' or winner(temp_board) == 'O':
temp_score += utility(temp_board)
else:
minimax(temp_board)
if temp_score > score:
score = temp_score
return_action = action
return available_actions[return_action]
让我们考虑一下minimax算法本身，因为其余的看起来还不错：
def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
return_action = [0, 0]
available_actions = actions(board)
score = 0
temp_board = board
for action in range(len(available_actions)):
temp_score = 0
i, j = available_actions[action]
temp_board[i][j] = player(temp_board)
if winner(temp_board) == 'X' or winner(temp_board) == 'O':
temp_score += utility(temp_board)
else:
minimax(temp_board)
if temp_score > score:
score = temp_score
return_action = action
return available_actions[return_action]
这里有多个问题。
temp_board = board 不复制；它只是为同一块板创建一个新的本地名称。结果，当您从递归中返回时，试用动作不会被“擦除”。
可能没有available_actions（请记住可以进行抽奖游戏！）。这意味着for循环不会运行，并且最后一个return将尝试使用无效值索引到available_actions-一个空列表（此处所有内容均无效，但初始设置为[0, 0] ] 尤其是没有意义，因为它不是整数。
没有什么可实际导致minimax算法交替改变min和max。无论考虑哪个玩家的移动，执行的比较都是if temp_score > score:。那是er，maximax，并且没有给您有用的策略。
最重要的是：您的递归调用不向调用者提供任何信息。当您递归调用minimax(temp_board)时，您想知道该板上的分数。因此，您的总体功能需要返回分数以及建议的举动，并且在进行递归调用时，您需要考虑该信息。 （您可以忽略临时棋盘上的建议举动，因为它仅告诉您算法希望玩家回答的内容；但是您需要得分才能确定此举是否是获胜的。）
我们还可以清理很多东西：
没有充分的理由初始化temp_score = 0，因为我们将从递归或注意到游戏结束后得到答案。 temp_score += utility(temp_board)也没有意义；我们不是在汇总价值，而是只使用一个。
我们可以清理utility函数，以考虑抽签游戏的可能性，并生成候选移动。这为我们提供了一种精巧的方法来封装“如果比赛获胜，即使有空白，也不要考虑棋盘上的任何举动”的逻辑。
代替使用for循环进行比较，我们可以对一系列递归结果使用内置的min和max函数-我们可以使用生成器表达式来获得（一个精巧的Python习惯用法，您将在许多更高级的代码中看到）。这也为我们提供了一种巧妙的方法来确保算法的最小和最大阶段是交替的：我们只是将适当的函数传递给递归的下一个级别。
这是我未经测试的尝试：
def score_and_candidates(board):
# your 'utility', extended to include candidates.
if winner(board) == 'X':
return 1, ()
if winner(board) == 'O':
return -1, ()
# If the game is a draw, there will be no actions, and a score of 0
# is appropriate. Otherwise, the minimax algorithm will have to refine
# this result.
return 0, actions(board)
def with_move(board, player, move):
# Make a deep copy of the board, but with the indicated move made.
result = [row.copy() for row in board]
result[move[0]][move[1]] = player
return result
def try_move(board, player, move):
next_player = 'X' if player == 'O' else 'O'
next_board = with_move(board, player, move)
next_score, next_move = minimax(next_board, next_player)
# We ignore the move suggested in the recursive call, and "tag" the
# score from the recursion with the current move. That way, the `min`
# and `max` functions will sort the tuples by score first, and the
# chosen tuple will have the `move` that lead to the best line of play.
return next_score, move
def minimax(board, player):
score, candidates = score_and_candidates(board)
if not candidates:
# The game is over at this node of the search
# We report the status, and suggest no move.
return score, None
# Otherwise, we need to recurse.
# Since the logic is a bit tricky, I made a separate function to
# set up the recursive calls, and then we can use either `min` or `max`
# to combine the results.
min_or_max = min if player == 'O' else max
return min_or_max(
try_move(board, player, move)
for move in candidates
)