На этом шаге мы разберем и применим это улучшение.
Минимакс работает хорошо, но сейчас нам не нужен глубокий поиск. Существует небольшое расширение минимакса, известное как альфа-бета-отсечение, которое позволяет улучшить глубину поиска, исключая те позиции, которые не приведут к улучшению по сравнению с уже найденными позициями. Магия достигается отслеживанием между рекурсивными вызовами минимакса двух значений, которые получили названия "альфа" и "бета". Альфа представляет собой оценку наилучшего максимизирующего хода, найденного до этого момента в дереве поиска, а бета - оценку наилучшего минимизирующего хода, найденного для противника. Если в какой-то момент бета окажется меньше альфы или равной ей, то исследовать эту ветвь поиска далее нет смысла, поскольку уже найденный ход - лучший или как минимум не хуже тех, что могут быть найдены далее по этой ветке. Такая эвристика значительно сокращает пространство поиска.
Далее показана функция alphabeta(), работающая по только что описанному алгоритму. Ее следует поместить в уже существующий файл minimax.ру.
def alphabeta(board: Board, maximizing: bool, original_player: Piece, max_depth: int = 8, alpha: float = float("-inf"), beta: float = float("inf")) -> float: # Базовый случай - достигнута финальная позиция # или максимальная глубина поиска if board.is_win or board.is_draw or max_depth == 0: return board.evaluate(original_player) # Рекурсивный случай - максимизируйте свою выгоду # или минимизируйте выгоду противника if maximizing: for move in board.legal_moves: result: float = alphabeta(board.move(move), False, original_player, max_depth - 1, alpha, beta) alpha = max(result, alpha) if beta <= alpha: break return alpha else: # инимизация for move in board.legal_moves: result = alphabeta(board.move(move), True, original_player, max_depth - 1, alpha, beta) beta = min(result, beta) if beta <= alpha: break return beta
Теперь мы можем внести два небольших изменения, чтобы воспользоваться новой функцией. Измените find_best_move() в minimax.py, задействуя alphabeta() вместо minimax(), и замените глубину поиска в pr110_1.py на 5 с 3. Теперь средний игрок в Connect Four больше не сможет выиграть у ИИ.
Архив с измененным файлом можно взять здесь.
На следующем шаге мы рассмотрим другие улучшения минимакса.
