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

Question

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

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

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

благодарит всех

Postscript Кто-то знает, как я знаю, если это достаточно?