Python Глубокая копия в минимаксной функции - PullRequest
Новая
       92

Python Глубокая копия в минимаксной функции

1 голос
/ 06 января 2020

Я создаю шахматный движок в Python, используя минимаксный алгоритм с обрезкой альфа-бета. Однако в настоящий момент он очень медленный, и я обнаружил, что выполнение глубокой копии каждой итерации в минимаксе происходит так же медленно, как и все мои другие функции вместе взятые.

Есть ли способ обойти глубокую копию или сделать ее быстрее? Ниже моя минимаксная функция на сегодня. Он может только подумать, что на 3-4 шага вперед или около того, что не очень хороший двигатель ... Любые предложения по ускорению алгоритма очень приветствуются. 

def minimax(board, depth, alpha, beta, maximizing_player):

    board.is_human_turn = not maximizing_player 

    children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

    best_move = random.choice(children)

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
            current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
            if current_eval > max_eval:
                max_eval = current_eval
                best_move = child
            alpha = max(alpha, current_eval)
            if beta <= alpha:
                break
        return best_move, max_eval

    else:
        min_eval = math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child[0][0], child[0][1], child[1][0], child[1][1])
            current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
            if current_eval < min_eval:
                min_eval = current_eval
                best_move = child
            beta = min(beta, current_eval)
            if beta <= alpha:
                break
        return best_move, min_eval

1 Ответ

0 голосов
/ 12 января 2020

Некоторые идеи о том, как оптимизировать вашу программу (в произвольном порядке):

1) Сделайте проверку if depth == 0 or board.is_draw or board.is_check_mate первым делом, которое вы делаете в функции minimax. Прямо сейчас вы вызываете board.get_all_possible_moves(), который может быть избыточным (например, в случае depth == 0).

2) Я не вижу, как реализован метод get_all_possible_moves(), и предполагаю, что он этого не делает любой вид сортировки. Рекомендуется упорядочивать ходы для минимаксного алгоритма, чтобы вы пересекали их oop, начиная с лучшего до худшего (в этом случае вы, скорее всего, будете сокращать больше узлов и ускорять программу).

3) Переменная child в for child in children l oop является двумерной матрицей. Я также предполагаю, что board также является многомерным массивом. Многомерные массивы могут быть медленнее, чем одномерные, из-за их расположения в памяти (например, если вы перебираете их по столбцам). Если возможно, используйте одномерные массивы (например, вы можете представить двухмерный массив как «конкатенацию» одномерных массивов).

4) Использовать генераторы для отложенной оценки. Например, вы можете превратить ваш get_all_possible_moves() в генератор и выполнять итерации по нему, не создавая списки и не занимая дополнительную память. Если условие обрезки альфа / бета срабатывает рано, вам не нужно расширять весь список детей в позиции.

5) Избегайте глубокого копирования доски, делая и отменяя текущий ход. В этом случае вы не создаете копии платы, но повторно используете исходную плату, которая может быть быстрее:

current_move_info = ... # collect and store info necessary to make/unmake the current move

board.move(current_move_info)

current_eval = minimax(board, ...)[1]

board.unmake_move(current_move_info) # restore the board position by undoing the last move

6) Добавьте больше классических оптимизирующих функций шахматного движка, таких как итеративное углубление, поиск главных вариаций, таблицы транспонирования, битборды и т. Д. c.

...