Давайте рассмотрим сам минимаксный алгоритм, так как остальное кажется нормальным:
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 l oop не запускается, и последний return попытается проиндексировать в available_actions - пустой список - с недопустимым значением (здесь все будет недопустимым, но начальная установка из [0, 0] особенно не имеет смысла, так как это не целое число).
Нет ничего, что могло бы заставить минимаксный алгоритм чередовать min и max , Выполняется сравнение if temp_score > score:, независимо от того, какой ход игрока рассматривается. Это максимум, и он не дает вам полезной стратегии.
Самое главное: ваш рекурсивный вызов не предоставляет никакой информации вызывающей стороне . Когда вы рекурсивно звоните minimax(temp_board), вы хотели бы знать, каков счет на этой доске. Таким образом, ваша общая функция должна возвращать счет, а также предложенный ход, и когда вы делаете рекурсивный вызов, вы должны учитывать эту информацию. (Вы можете игнорировать предложенный ход на временной доске, поскольку он просто говорит вам, что алгоритм ожидает от игрока ответа; но вам нужен счет, чтобы вы могли определить, является ли этот ход выигрышным.)
Мы также можем убрать много вещей:
Нет веских причин для инициализации temp_score = 0, так как мы получим ответ либо из рекурсия или из замечений, что игра окончена. temp_score += utility(temp_board) также не имеет смысла; мы не суммируем значения, а просто используем одно.
Мы можем очистить функцию utility, чтобы учесть возможность розыгрыша игр, а также сгенерировать кандидата движется. Это дает нам аккуратный способ инкапсулировать логи c «если игра выиграна, не рассматривайте какие-либо ходы на доске, даже если есть пустые места».
Вместо цикла с for l oop и выполнения сравнения мы можем использовать встроенные функции 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
)