Попытка реализовать Ожидание покоя

Question

Я пытаюсь реализовать итеративное углубление до расслабления. Если вы не помните, я имею в виду, что в случае больших различий между уровнями дерева будет продолжаться проверка глубже, пока различия не станут большими. лучший пример - создание длинного обмена инструментами в шахматной игре (мы не хотим, чтобы дерево было посередине). Кто-нибудь может отправить мне Алгоритм или псевдокод?

Это обычный алгоритм минимума-максимума (в PYTHON):

class MiniMaxWithAlphaBetaPruningWithWDeepeningUntilRestfulness(MiniMaxWithAlphaBetaPruning):
def __init__(self, utility, my_color, no_more_time, w):
    MiniMaxWithAlphaBetaPruningWithW.__init__(self, utility, my_color, no_more_time, w)
    # self.treshold_restfulness = TODO

def search(self, state, depth, alpha, beta, maximizing_player):
    """Start the MiniMax algorithm.

    :param state: The state to start from.
    :param depth: The maximum allowed depth for the algorithm.
    :param alpha: The alpha of the alpha-beta pruning.
    :param alpha: The beta of the alpha-beta pruning.
    :param maximizing_player: Whether this is a max node (True) or a min node (False).
    :return: A tuple: (The alpha-beta algorithm value, The move in case of max node or None in min mode)
    """

    print('Enter MiniMaxWithAlphaBetaPruningWithWDeepeningUntilRestfulness.search({},{},{},{},{})'.format(
        state, depth, alpha, beta, maximizing_player))

    if depth == 0 or self.no_more_time():
        return self.utility(state), None

    next_moves = state.legalMoves()
    if not next_moves:
        # This player has no moves. So the previous player is the winner.
        return INFINITY if state.currPlayer != self.my_color else -INFINITY, None

    list = []
    for next_move in next_moves:
        if (self.no_more_time()):
            del list[:]
            return self.utility(state), None
        new_state = copy.deepcopy(state)
        new_state.doMove(next_move)
        list.append((new_state, next_move, self.utility(new_state)))

    list.sort(key=itemgetter(2))
    if (self.no_more_time()):
        del list[:]
        return self.utility(state), None

    if maximizing_player:
        selected_move = next_moves[0]
        best_move_utility = -INFINITY
        for i in range(int(len(list)) - 1, int(len(list)) - int(len(list) * self.w) - 1, -1):
            board_state = list[i][0]
            minimax_value, _ = self.search(board_state, depth - 1, alpha, beta, False)
            alpha = max(alpha, minimax_value)
            if minimax_value > best_move_utility:
                best_move_utility = minimax_value
                selected_move = list[i][1]
            if beta <= alpha or self.no_more_time():
                break
        # print(best_move_utility)
        print('Utility of best Move in deepening in depth of {} is {}'.format(depth, best_move_utility))
        del list[:]
        return alpha, selected_move

    else:
        for i in range(0, int(len(list) * self.w)):
            board_state = list[i][0]
            beta = min(beta, self.search(board_state, depth - 1, alpha, beta, True)[0])
            if beta <= alpha or self.no_more_time():
                break
        del list[:]
        return beta, None

Как я могу продолжить углубление, когда оно не стабильно, пока оно не стабильно?

заранее спасибо

Answer 1

Я нашел его в Википедии: https://en.wikipedia.org/wiki/Quiescence_search

Спасибо всем

Постскриптум Кто-нибудь знает, как я могу узнать, если это достаточно?