Минимакс с итеративным углублением: как использовать предыдущие вычисления?

Я использую алгоритм минимакс для ИИ для игры в шашки.
Для лучшей производительности я использую альфа-бета отсечение.

Так как в шашках сложно предсказать, какая глубина поиска нужна в конкретной позиции, я хочу использовать итеративное углубление: поиск происходит сначала на глубину 1, затем 2, 3 и так далее.

Как я понял, смыслом итеративного углубления является то, что на при расчете на глубину n мы используем ранее уже выполненный расчет на глубину n-1, результаты которого сохраняются (в хеш-таблице/файле...)

Однако мне не совсем понятно, что конкретно мне нужно сохранять в этой хеш таблице? Я должен сохранять ВСЕ позиции, которые встречаются в процессе минимакса или только позиции на стартовых глубинах?

Сейчас моя программа просто последовательно проходит по всем глубинам, никак не используя результаты предыдущих менее глубоких вычислений.

class AI:
    def get_best_move (self, board, time_limit):
        self.analysed_positions = 0
        self.best_move = None
        self.calculation_process = True

        calculation_process = threading.Thread(target=self.iterative_deepening_minimax, args=(board, ))
        calculation_process.start()
        calculation_process.join(time_limit)
        self.calculation_process = False

        return self.best_move


    def iterative_deepening_minimax (self, board):
        for depth in range(2, 30):
            if self.calculation_process:
                # Начинаем поиск на глубине depth, который возвращает лучший ход в этой позиции
                self.best_move = self.minimax(board, depth, -INFINITY, INFINITY, board.whitesMove)[1]
            else:
                break


    def minimax (self, board, depth, alpha, beta, maximizingPlayer):
        if self.calculation_process == False:
            return (0, None)

        board.find_all_moves()

        game_state = board.get_game_state()
        if game_state != STATE_OK:
            self.analysed_positions += 1
            return (INFINITY + depth, None) if game_state == WHITE_WIN else (-INFINITY - depth, None)
        if depth == 0:
            self.analysed_positions += 1
            eval = self.evaluate(board)
            return (eval, None)

        bestMove = None
        if maximizingPlayer:
            maxEval = -INFINITY
            for move in board.moves:
                next_pos = Board(board, search_all_moves=False)
                next_pos.make_move(move)
                next_pos.change_turn()

                eval = self.minimax(next_pos, depth - 1, alpha, beta, False)[0]
                if eval > maxEval:
                    maxEval = eval
                    bestMove = move
                # Pruning
                alpha = max(alpha, eval)
                if beta <= alpha:
                    break
            return (maxEval, bestMove)

        else:
            minEval = INFINITY
            for move in board.moves:
                next_pos = Board(board, search_all_moves=False)
                next_pos.make_move(move)
                next_pos.change_turn()

                eval = self.minimax(next_pos, depth-1, alpha, beta, True)[0]
                if eval < minEval:
                    minEval = eval
                    bestMove = move
                # Pruning
                beta = min(beta, eval)
                if beta <= alpha:
                    break

            return (minEval, bestMove)

    # Возвращает статическую оценку позиции
    def evaluate():
        ...


Ответы (1 шт):

Автор решения: Максим Фисман

Кратко: правильным решением будет запоминать все позиции, встречаемые в процессе минимакса. Это называется таблица транспозиций.


Когда минимакс на определенной глубине делает вывод о лучшем ходе в позиции (в коде это происходит в строках return (maxEval, bestMove) и return (minEval, bestMove)), нужно запоминать следующие характеристики:

  • Сама позиция (с учетом очереди хода)
  • Оценка позиции
  • Глубина, на которую производился поиск в этой позиции
  • Лучший ход, найденный в этой позиции на этой глубине
class Transposition:
    def __init__ (self, pos, eval, depth, best_move):
        self.pos = pos
        self.eval = eval
        self.depth = depth
        self.best_move = best_move

Каждый раз, когда мы просим минимакс определить лучший ход в заданной позиции, мы ищем, есть ли в таблице транспозиций эта позиция. Если нет, продолжаем минимакс, как обычно. Если есть, то нужно проверить глубину: если глубина, на которой эта позиция записана в таблицу транспозиций, больше или равна той, на которые мы ищем, то мы можем воспользоваться лучшим ходом, записанным в таблице транспозиций для этой позиции.

Если же в таблице позиция записана на меньшей глубине, то, увы, она нам не поможет, так как нам надо искать глубже. Однако мы все же можем использовать лучший ход: если в позиции на глубине N найден лучший ход, то велика вероятность, что на глубине больше D этот же ход будет лучшим.

    def minimax (self, board, depth, alpha, beta, maximizingPlayer):
        # ...
     
        # Ищем позицию
        position_index = board.convert_to_number()
        transposition = next((tr for tr in self.transpositions if tr.pos == position_index), None)
        # Если позиция уже встречалась
        if transposition != None:
            # Если глубина нам подходит
            if transposition.depth >= depth:
                # Используем ранее найденный результат
                return (transposition.eval, transposition.best_move)

Несколько комментариев:

  1. Когда мы добавляем позицию в таблицу, нужно убедиться, что там нет той же позиции на меньшей глубине.
  2. Полезным решением будет добавить в транспозицию свойство isOnly, которое определяет, является ли найденный ход единственным. Если ход в позиции единственный, то не важно, на какой глубине он был найден, и мы можем использовать его вне зависимости от глубины.

Аналогичное решение (которое мне представляется костылем): если ход в позиции единственный, записывать эту позицию в таблицу транспозиций как проанализированную с глубиной БЕСКОНЕЧНОСТЬ.

→ Ссылка