1

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

Так как в шашках сложно предсказать, какая глубина поиска нужна в конкретной позиции, я хочу использовать итеративное углубление: поиск происходит сначала на глубину 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():
        ...

5
  • А что это за "стартовые глубины"? Не встречал такой термин. 30 июн 2022 в 19:20
  • @Сергей Под стартовыми глубинами я имею в виду те глубины, на которых происходят первые запуски минимакса. В функции iterative_deepening_minimax минимакс последовательно запускает с разными стартовыми глубинами: от 2 до 30. Именно результат запуска минимакса на стартовой глубине является окончательным решением программы на этой глубине 30 июн 2022 в 19:23
  • @Сергей Если бы я не использовал итеративное углубление, был бы всего один запуск минимакса: minimax(позиция, ГЛУБИНА, альфа, бета). Минимакс выдал бы 1 решение на заданной глубине. Но так как я использую итеративное углебление, то минимакс последовательно вызывается на разных (увеличивающихся) глубинах: 2, 3, 4... Это происходит в функции iterative_deepening_minimax(). Эти запуски, а вместе с ними и соответствующие глубины (переменная depth в цикле) я и называю -- стартовыми. Надеюсь, понятно обьяснил 30 июн 2022 в 19:25
  • Ясно. Полагаю, это вы видели, но на всякий случай: часть 4, пункт 6. <acm.mipt.ru/twiki/bin/view/Algorithms/ArlazarovChessAlgo> Сам не писал подобного, так что пишу интуитивно, но хранил бы все, что получается хранить. В принципе, самым разумным было бы сделать оба варианта (вряд ли они сильно отличаются по трудоемкости кодирования) и проверить. 30 июн 2022 в 19:31
  • @Сергей Вау, это очень полезно! Я не видел этой статьи. Я просматривал некоторое количество статей по ИИ для шахмат, однако многие из них не подходили для шашек ввиду существенных различий. Я в основном изучал статьи в целом по теме минимакса. Я думаю, что эту статью я изучу полностью:) Я подожду, чтобы кто-то (или вы) дал ответ. Если что, напишу свой со своими мыслями, основываясь на вашей ссылке:) 30 июн 2022 в 19:43

1 ответ 1

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, которое определяет, является ли найденный ход единственным. Если ход в позиции единственный, то не важно, на какой глубине он был найден, и мы можем использовать его вне зависимости от глубины.

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

1
  • 1
    т.е. интуиция меня не подвела. такой подход и логичен, впрочем. 1 июл 2022 в 20:43

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.