实现极小极大算法时的递归问题
Problem with recursion while implementing a minimax algorithm
我正在尝试实现一个 minimax 算法来创建一个与玩家玩井字游戏的机器人。
gui 功能在另一个文件中并且工作正常。每当轮到机器人进行移动时，gui 文件就会使用下面提到的代码调用该文件。
我已经将每个函数的作用包含在注释中，我相信除了 minimax() 之外的所有函数都有效
每当我 运行 脚本时，都会显示此错误：
"RecursionError: maximum recursion depth exceeded in comparison"
如果有什么不清楚的地方请发表评论，我会尽力简化它。
谢谢你的帮助
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 不复制；它只是为同一块板创建一个新的本地名称。因此，试验移动不会像您从递归中 return 那样得到 "erased"。
有可能没有available_actions（记住抽签是可能的！）。这意味着 for 循环不会 运行，最后一个 return 将尝试索引到 available_actions - 一个空列表 - 具有无效值（这里的一切都无效, 但 [0, 0] 特别是 的初始设置没有意义，因为它不是整数）。
实际上没有什么可以导致 minimax 算法交替最小值和最大值。执行的比较是 if temp_score > score:，无论考虑哪个玩家的移动。那是，呃，maximax，并没有给你一个有用的策略。
最重要的是：您的递归调用不会向调用者提供任何信息。当您递归调用 minimax(temp_board) 时，您想知道该板上的分数是多少。因此，您的整体功能需要 return 得分以及建议的移动，并且在进行递归调用时，您需要考虑该信息。 （您可以忽略临时棋盘上的建议走法，因为它只是告诉您算法期望玩家回答什么；但您需要得分，以便确定此走法是否获胜。）
我们还可以清理很多东西：
没有充分的理由初始化temp_score = 0，因为我们将从递归或注意到游戏结束中得到答案。 temp_score += utility(temp_board) 也没有意义；我们不是汇总值，而是使用一个值。
我们可以清理 utility 函数来考虑平局的可能性，并生成候选动作。这为我们提供了一种简洁的方式来封装 "if the game has been won, don't consider any moves on the board, even though there are empty spaces".
我们可以使用内置的 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
)
我正在尝试实现一个 minimax 算法来创建一个与玩家玩井字游戏的机器人。 gui 功能在另一个文件中并且工作正常。每当轮到机器人进行移动时，gui 文件就会使用下面提到的代码调用该文件。 我已经将每个函数的作用包含在注释中，我相信除了 minimax() 之外的所有函数都有效 每当我 运行 脚本时，都会显示此错误： "RecursionError: maximum recursion depth exceeded in comparison"
如果有什么不清楚的地方请发表评论，我会尽力简化它。 谢谢你的帮助
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不复制；它只是为同一块板创建一个新的本地名称。因此，试验移动不会像您从递归中 return 那样得到 "erased"。有可能没有
available_actions（记住抽签是可能的！）。这意味着 for 循环不会 运行，最后一个return将尝试索引到available_actions- 一个空列表 - 具有无效值（这里的一切都无效, 但[0, 0]特别是 的初始设置没有意义，因为它不是整数）。实际上没有什么可以导致 minimax 算法交替最小值和最大值。执行的比较是
if temp_score > score:，无论考虑哪个玩家的移动。那是，呃，maximax，并没有给你一个有用的策略。最重要的是：您的递归调用不会向调用者提供任何信息。当您递归调用
minimax(temp_board)时，您想知道该板上的分数是多少。因此，您的整体功能需要 return 得分以及建议的移动，并且在进行递归调用时，您需要考虑该信息。 （您可以忽略临时棋盘上的建议走法，因为它只是告诉您算法期望玩家回答什么；但您需要得分，以便确定此走法是否获胜。）
我们还可以清理很多东西：
没有充分的理由初始化
temp_score = 0，因为我们将从递归或注意到游戏结束中得到答案。temp_score += utility(temp_board)也没有意义；我们不是汇总值，而是使用一个值。我们可以清理
utility函数来考虑平局的可能性，并生成候选动作。这为我们提供了一种简洁的方式来封装 "if the game has been won, don't consider any moves on the board, even though there are empty spaces". 的逻辑
我们可以使用内置的
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
)