我正在尝试实现一个极小化极大算法来创建一个与玩家对战的井字游戏机器人。GUI功能在另一个文件中，并且运行正常。每当轮到机器人移动时，GUI文件会调用包含下述代码的文件。我已经在注释中说明了每个函数的作用，我认为除了minimax()函数之外，其他函数都正常工作。每当我运行脚本时，会显示以下错误：“RecursionError: maximum recursion depth exceeded in comparison”
如果有不清楚的地方，请评论，我会尽力简化说明。感谢您的帮助
X = "X"O = "O"EMPTY = Nonedef initial_state(): """ 返回棋盘的初始状态。 """ return [[EMPTY, EMPTY, EMPTY], [EMPTY, EMPTY, EMPTY], [EMPTY, EMPTY, EMPTY]]def player(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): """ 返回棋盘上所有可能的动作（i, j）集合。 """ action = [] for i in range(3): for j in range(3): if board[i][j] is None: action.append([i, j]) return actiondef result(board, action): """ 返回在棋盘上执行动作（i, j）后的结果棋盘。 """ p = player(board) i, j = action board[i][j] = p return boarddef winner(board): """ 如果有赢家，返回游戏的赢家。 """ 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): """ 如果游戏结束，返回True，否则返回False。 """ if winner(board) == 'X' or winner(board) == 'O' : return True else: return Falsedef utility(board): """ 如果X赢了游戏，返回1；如果O赢了，返回-1；否则返回0。 """ if winner(board) == 'X': return 1 elif winner(board) == 'O': return -1 else: return 0def minimax(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]回答：
让我们考虑一下极小化极大算法本身，因为其他部分看起来没问题：
def minimax(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]特别没有意义，因为它不是整数）。 -
没有任何东西能使极小化极大算法交替进行最小化和最大化。执行的比较是
if temp_score > score:，无论考虑的是哪个玩家的移动。这就是所谓的最大化最大化，并不能为您提供有用的策略。 -
最重要的是：您的递归调用没有为调用者提供任何信息。当您递归调用
minimax(temp_board)时，您希望知道该棋盘上的得分。因此，您的整体函数需要返回一个得分以及建议的移动，当您进行递归调用时，您需要考虑这些信息。（您可以忽略临时棋盘上的建议移动，因为它只是告诉您算法期望玩家如何回应；但您需要得分，以便确定此移动是否为获胜移动。）
我们还可以清理很多东西：
-
没有好的理由初始化
temp_score = 0，因为我们将从递归或注意到游戏结束中得到答案。temp_score += utility(temp_board)也没有意义；我们不是在总计值，而只是使用一个单一的值。 -
我们可以清理
utility函数以考虑平局游戏的可能性，并生成候选移动。这为我们提供了一种整洁的方式来封装“如果游戏已经赢了，即使有空格也不考虑任何移动”的逻辑。 -
我们可以使用
min和max函数对递归结果序列进行操作，而不是使用for循环并进行比较 – 我们可以通过使用生成器表达式来获取（这是一个你会在很多更高级代码中看到的整洁的Python习惯用法）。这也为我们提供了一种整洁的方式来确保算法的最小化和最大化阶段交替进行：我们只需将适当的函数传递给递归的下一级别即可。
这是我未经测试的尝试：
def score_and_candidates(board): # 您的'utility'函数，扩展为包括候选者。 if winner(board) == 'X': return 1, () if winner(board) == 'O': return -1, () # 如果游戏是平局，将没有动作，0分是合适的。 # 否则，极小化极大算法将不得不细化这个结果。 return 0, actions(board)def with_move(board, player, move): # 制作棋盘的深拷贝，但执行指定的移动。 result = [row.copy() for row in board] result[move[0]][move[1]] = player return resultdef 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) # 我们忽略递归调用中建议的移动，并用当前移动“标记”递归的得分。 # 这样，`min`和`max`函数将首先按得分对元组进行排序， # 选择的元组将具有导致最佳游戏路线的`move`。 return next_score, movedef minimax(board, player): score, candidates = score_and_candidates(board) if not candidates: # 游戏在搜索的这个节点结束 # 我们报告状态，并不建议移动。 return score, None # 否则，我们需要递归。 # 由于逻辑有点棘手，我创建了一个单独的函数来 # 设置递归调用，然后我们可以使用`min`或`max` # 来组合结果。 min_or_max = min if player == 'O' else max return min_or_max( try_move(board, player, move) for move in candidates )