python - 实现极小极大算法时的递归问题

Question

我正在尝试实现一个极小极大算法来创建一个与玩家玩井字游戏的机器人。 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]

Answer 1

让我们考虑一下极小极大算法本身，因为其余的看起来都很好:

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 不制作副本；它只是为同一 block 板创建一个新的本地名称。因此，当您从递归返回时，尝试移动不会被“删除”。

• 有可能没有available_actions(请记住，平局是可能的!)。这意味着 for 循环不会运行，最后一个 return 将尝试使用无效值索引到 available_actions - 一个空列表(一切都会是此处无效，但 [0, 0] 特别是的初始设置没有意义，因为它不是整数)。

• 没有什么可以真正导致极小极大算法交替最小值和最大值。无论考虑哪个玩家的 Action ，执行的比较都是if temp_score > Score:。那是，呃，maximax，并没有给你一个有用的策略。

• 最重要的是:您的递归调用不会向调用者提供任何信息。当您递归调用 minimax(temp_board) 时，您想知道该板上的分数是多少。因此，您的整体函数需要返回分数以及建议的移动，并且当您进行递归调用时，您需要考虑该信息。 (您可以忽略临时棋盘上建议的棋步，因为它只是告诉您算法期望玩家回答什么；但您需要分数才能确定该棋步是否获胜。)

我们还可以清理很多东西:

• 没有充分的理由初始化 temp_score = 0，因为我们将从递归或注意到游戏结束时得到答案。 temp_score += utility(temp_board) 也没有意义；我们不会对值进行总计，而只是使用单个值。

• 我们可以清理utility函数来考虑平局的可能性，并生成候选 Action 。这为我们提供了一种简洁的方式来封装“如果游戏获胜，则不要考虑棋盘上的任何 Action ，即使有空位”的逻辑。

• 我们可以使用内置的 min 和 max 函数，而不是使用 for 循环并执行比较一系列递归结果 - 我们可以通过使用生成器表达式(一个简洁的 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
    )