Остановить рекурсивную функцию в Python

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

# Initial call
move = ai_make_move()

# AI function with iterative deepending
def ai_make_move():
    best_move_so_far = []

    # Here I init the time
    start_time = time.time()

    # Iterative deepening to go deeper and deeper into tree
    for depth in range(1, max_depth):
        move = negamax(alpha, beta, depth...)
        best_move_so_far.append(move)

# Negamax function
def negamax(alpha, beta, depth....):
    
    # Here I want to make the time check...
    if time.time() - start_time >= time_limit:
        # Return None to ai_make_move() or return best_move_so_far[-1] to initial call
    
    for move in possible moves:
        make_move()
        negamax(-beta, -alpha)
        unmake_move()

    # ...

Проблема, с которой я столкнулся, состоит в том, чтобы остановиться, когда время в функции negamax истекло, и вернуть None в функцию ai_make_move(), чтобы иметь возможность делать что-то вроде if not move: return best_move_so_far[-1]. Или вернуть это сразу к первоначальному вызову.

Можно ли остановить такой рекурсивный вызов? Прямо сейчас, если я что-то верну, оно просто вернется к предыдущему вызову negamax и так далее, что выдаст ошибку.


python algorithm chess minimax negamax
person Eli    schedule 05.01.2021    source источник
comment
Вы можете использовать разные подходы, один из них - запустить функцию как отдельный поток или процесс и заставить ее сообщать результаты по мере ее запуска и уничтожения по истечении заданного времени. Однако более простым решением, вероятно, было бы проверять срок действия в начале каждой итерации и просто возвращаться из функции по истечении срока ее действия.   -  person Grismar    schedule 05.01.2021
comment
Второй подход - это то, как я сейчас это делаю, чтобы вернуться из функции ai_make_move, когда время истекло. Проблема в том, что он может начать расчет, когда время почти истекло, и тогда требуется двойное время, чтобы сделать следующий ход. Это связано с экспоненциальным характером кода. Я хочу вернуться ровно через 5 секунд размышлений.   -  person Eli    schedule 05.01.2021
comment
Отвечает ли это на ваш вопрос? Время ожидания вызова функции   -  person Grismar    schedule 05.01.2021
comment
@Eli проблема не ясна; не работает ли возврат внутри условия проверки времени?   -  person Abhinav Mathur    schedule 05.01.2021
comment
@AbhinavMathur, функция является рекурсивной, поэтому она вернется не к начальному вызову функции, а к предыдущему вызову negamax, пока не завершит рекурсивный цикл. Вместо этого я хочу сломать его именно в это время.   -  person Eli    schedule 05.01.2021

Ответы (2)


arrow_upward
0
arrow_downward

Вы должны добавить timeout к своей функции, что довольно хорошо объяснено здесь: Timeout on a function call< /а>

person Frederik Bode    schedule 05.01.2021
comment
Возможно, но я недостаточно умен, чтобы понять, как разместить эти вещи в своих функциях. Кстати, я работаю в Windows, поэтому, думаю, мне нужно использовать многопроцессорность. Я просто не могу уложить в голове, как разместить эти вещи. Не могли бы вы быть очень любезны и обновить свой ответ, как это будет выглядеть в этом случае? - person Eli; 05.01.2021

arrow_upward
0
arrow_downward

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

if time.time() - start_time >= time_limit:
    return evaluation(board)

Очевидно, что это не остановит функцию немедленно, так как значения должны вернуться в дерево, но это должно быть довольно быстро. Кроме того, зачем вам нужны max_depth и time_limit?

person Honn    schedule 08.01.2021
comment
Если я хочу найти максимальную глубину 2, я установлю для max_depth значение 2, и после этого он вернется. В основном, чтобы иметь возможность контролировать, насколько глубоко он ищет. И ограничение по времени должно остановиться в определенное время, чтобы оно не продолжалось вечно, если для max_depth установлено что-то большое. К сожалению, это утверждение не работает, и кажется, что оно возвращает произвольный ход, который он сыграл в тот момент времени. Тем не менее, он останавливается в нужное время, что всегда что-то :) - person Eli; 09.01.2021