Попытка реализовать Ожидание покоя
Я пытаюсь реализовать итеративное углубление до расслабления. Если вы не помните, я имею в виду, что в случае больших различий между уровнями дерева будет продолжаться проверка глубже, пока различия не станут большими. лучший пример - создание длинного обмена инструментами в шахматной игре (мы не хотим, чтобы дерево было посередине). Кто-нибудь может отправить мне Алгоритм или псевдокод?
Это обычный алгоритм минимума-максимума (в 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
Как я могу продолжить углубление, когда оно не стабильно, пока оно не стабильно?
заранее спасибо
1 ответ
Я нашел его в Википедии: https://en.wikipedia.org/wiki/Quiescence_search
Спасибо всем
Постскриптум Кто-нибудь знает, как я могу узнать, если это достаточно?