#algorithm #runtime #prediction #minimax #negamax
#алгоритм #время выполнения #прогнозирование #минимакс #negamax
Вопрос:
Проблема
Я пытаюсь решить совершенную информационную игру с нулевой суммой (например, тик-так или шахматы), используя алгоритм negamax с альфа-бета-обрезкой. Цель состоит в том, чтобы доказать, может ли один игрок добиться победы или ничьей. Это означает, что ограничения глубины нет, но алгоритм всегда оценивает игровое дерево до тех пор, пока не будет выигрыша / ничьей.
Я потратил несколько недель на оптимизацию своего кода для своей конкретной игры и, я бы сказал, сократил время выполнения до нескольких дней. Но в этом и заключается проблема:
Из-за альфа-бета-обрезки время выполнения минимаксного алгоритма крайне непредсказуемо. Я не могу сказать, будет ли это сделано в ближайшие 5 минут или будет выполняться еще 5 недель, пока я на самом деле не смоделировал это. Я хотел бы иметь возможность прогнозировать оставшееся время выполнения и не отключаться на несколько порядков.
Что я пробовал до сих пор
Я записываю результаты всех дочерних и дочерних ветвей до 5 * дочерних ветвей и время, которое потребовалось моей машине для их имитации. Тогда я просто предполагаю, что позиции на том же уровне занимают одинаковое время для оценки и называют это днем. Эти прогнозы иногда отклоняются в 10 или более раз.
Я также просмотрел записанные данные, чтобы узнать, верно ли мое предположение. Время, необходимое для оценки подотрасли 5 *, варьировалось от 0.01s до 180s . Вот почему мои прогнозы ошибочны. Кто бы оценил.
Мой вопрос
Как я полагаю, это применимо ко всем реализациям минимакса:
- Существует ли более сложный алгоритм для точного прогнозирования оставшегося времени выполнения минимаксного алгоритма с альфа-бета-обрезкой? Или минимакс просто непредсказуем по замыслу?
- Если да, то как они работают?
Ответ №1:
Я потратил много времени на алгоритмы Negamax, на которые я настоятельно рекомендую вам переключиться. Это даст те же результаты, что и Minimax, но гораздо проще отлаживать и оптимизировать дальше, поскольку это всего лишь половина кода.
Я понятия не имею об игре, которую вы пытаетесь решить, но если она даже самая сложная, я предполагаю, что это будет невозможно без суперкомпьютера. Чтобы ответить на ваши вопросы, хотя:
- Минимакс с альфа-бета-обрезкой сильно зависит от порядка, в котором вы пробуете свои ходы (используя термины настольной игры). Сначала вы хотите попробовать лучшие ходы, это делается в шахматах путем упорядочения функции возможных ходов, например, с захватом ходов выше, чем рокировка.
Вы также можете оптимизировать алгоритм намного больше с помощью различных методов в зависимости от того, что вы пытаетесь решить. Например, таблицы транспозиции, если одна и та же позиция может встречаться в другой ветке.
- Нам нужно больше знать об игре, которую вы пытаетесь решить, чтобы знать, какой алгоритм может работать лучше всего.
Заключительные слова: если вы хотите получить представление о том, сколько времени потребуется для решения и как далеко вы продвинулись через некоторое время, я предлагаю вам использовать итеративное углубление. Это также ускорит ваш поиск, поскольку вы можете сначала попробовать лучшие предположения из предыдущих итераций и, следовательно, получить более быстрые бета-отсечки на следующей итерации:
for depth in range(1, inf):
score = minimax(alpha, beta, depth....)
time = elapsed_time()
Теперь вы можете распечатать прошедшее время для каждой глубины и посмотреть, как далеко она продвинулась за определенный период времени. Это также полезно для измерения, если ваши оптимизации дают какие-либо результаты. Поскольку минимаксное дерево экспоненциально увеличивается для каждой глубины, вы можете получить представление о том, сколько времени займет у вас следующая глубина.
Итак, если вы знаете, сколько ходов потребуется для победы / ничьей / проигрыша, вы можете довольно легко оценить, будет ли это возможно или нет с помощью этой техники.
Надеюсь, я проясню, английский не мой родной язык 🙂 Не стесняйтесь спрашивать в комментариях, если что-то непонятно.