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

Question

我正在尝试实现一个 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]

Answer 1

让我们考虑 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: ，无论正在考虑哪个玩家的举动。那是，呃，maximax，并没有给你一个有用的策略。

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

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

没有充分的理由初始化 temp_score = 0 ，因为我们将通过递归或注意到游戏结束得到答案。 temp_score += utility(temp_board)也没有道理；我们没有汇总值，而只是使用单个值。

我们可以清理utility函数来考虑绘制游戏的可能性，并生成候选移动。这为我们提供了一种巧妙的方式来封装“如果游戏赢了，即使有空位也不考虑棋盘上的任何 Action ”的逻辑。

而不是用 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
    )