#python #algorithm #minimax #negamax
#python #алгоритм #минимакс #negamax
Вопрос:
У меня есть обычный алгоритм Negamax с альфа-бета-обрезкой, который инициируется с итеративным углублением (ID). Я подумал, что для того, чтобы действительно использовать ID, я сохраняю вычисленные допустимые ходы с глубины 1 в таблице, поэтому в следующий раз, когда я перейду на глубину 2 и появится та же исходная позиция, я могу просто взять допустимые ходы из таблицы, чтобы сэкономить время. Однако я нахожу, что эта идея вообще не экономит время, что заставляет меня задуматься:
- Я никогда не видел, чтобы кто-нибудь делал это, разве это не стоит по какой-то причине?
- Моя реализация этого неверна?
- Я смущен тем, как работает Negamax, и, возможно, это вообще невозможно сделать?
Вот исходный итеративный вызов вместе с фрагментом самой функции Negamax:
self.valid_moves_history = []
for depth in range(1, s.max_search_depth):
move, evaluation = self.negamax(gamestate, depth, -math.inf, math.inf, s.start_color)
# ----------------------------------------------------------------------------
def negamax(self, gamestate, depth, alpha, beta, color):
if self.zobrist_key in self.valid_moves_history:
children = self.valid_moves_history[self.zobrist_key]
else:
children = gamestate.get_valid_moves()
self.valid_moves_history[key] = children
if depth == 0 or gamestate.is_check_mate or gamestate.is_stale_mate:
return None, e.evaluate(gamestate, depth) * color
# Negamax loop
max_eval = -math.inf
for child in reversed(children):
gamestate.make_move(child[0], child[1])
score = -self.negamax(gamestate, depth - 1, -beta, -alpha, -color)[1]
gamestate.unmake_move()
if score > max_eval:
max_eval = score
best_move = child
alpha = max(alpha, max_eval)
if beta <= alpha:
break
Наиболее трудоемкие задачи моей полной программы распределяются примерно так (% от общего времени выполнения игры):
- Вычисление допустимых ходов: 60%
- Функция оценки (средняя сложность на данный момент): 25%
- Сам Negamax с поиском, сохранением таблицы и т. Д.: 5%
- Сделать / отменить ходы: 4%
Является ли нормальным / разумным, чтобы время вычисления хода было таким высоким? Это основная причина, по которой я решил сохранить допустимые ходы в списке в первую очередь.
Или кто-нибудь может объяснить, почему это хорошая / плохая идея и что я должен делать вместо этого? Спасибо за любой вклад.
Комментарии:
1. Как вы думаете, почему ID ускоряет ваш алгоритм? Это для отмены поиска по истечении заданного времени или по желанию пользователя и выбора хода. Попытка выбрать лучший ход последней итерации для следующей не полностью компенсирует то, что у вас больше усилий, чем прямой поиск с последней глубиной.
2. @TheSlater, это определенно ускоряет процесс, время, необходимое для вычисления глубины от 1 до N-1, незначительно по сравнению с вычислением глубины N. Мой единственный порядок перемещения заключается в том, что я беру лучший ход из предыдущей итерации в качестве наилучшего предположения, и ID примерно на 50% быстрее только от этого, по сравнению с без ID. При большем упорядочении ходов разница будет еще больше. Я не уверен, откуда взялось ваше утверждение.
Ответ №1:
Я знаю, что на данный момент этот поток довольно старый, но я думаю, что это все еще может быть полезно для некоторых людей. Вся тема, о которой вы говорите, называется таблицами транспозиции в Minimax, и вы можете найти много ссылок на эту тему. Negamax — это то же самое, что и Minimax, за исключением того, что у вас нет отдельных функций для игроков Max и Min, и вместо этого вы просто вызываете функцию max и превращаете ее в минус. Я думаю, что для вас, вероятно, более полезно сначала реализовать порядок перемещения, поскольку это может удвоить скорость вашей программы. Вы также можете найти более эффективный способ поиска допустимых ходов для ускорения работы программы.