Какая модель лучше всего подходит для стратегии в реальном времени?

Question

В статье в последнее время обсуждаются вопросы использования генетических алгоритмов для оптимизации «заказов на строительство» в StarCraft II.

http://lbrandy.com/blog/2010/11/using-genetic-algorithms-to-find-starcraft-2-build-orders/

Начальное состояние матча StarCraft предварительно определены и постоянным. И, как и в шахматах, решения, принятые на этом раннем этапе матча, имеют давние последствия для способности игрока выступать в средней и поздней игре. Таким образом, различные возможности открытия или «заказы на строительство» находятся под большим вниманием и тщательностью. До распространения вышеупомянутой статьи создание заказа на сборку с использованием компьютера, вероятно, было не таким популярным, как было недавно.

Мой вопрос ... Является ли генетический алгоритм действительно лучшим способом моделирования оптимизирующих заказов на сборку?

Порядок сборки - последовательность действий. В некоторых действиях есть такие предпосылки, как «Вам нужно построить B, прежде чем вы сможете создать здание C, но вы можете построить A в любое время». Таким образом, хромосома может выглядеть как AABAC.

Мне интересно, действительно ли генетический алгоритм является наилучшим способом решения этой проблемы. Хотя я не слишком хорошо знаком с этой областью, у меня есть трудное время, обучая концепцию генов структуре данных, которая представляет собой последовательность действий. Это не самостоятельный выбор, который можно смешивать и сопоставлять, как голова и нога. Итак, какая ценность для таких вещей, как воспроизведение и скрещивание?

Я думаю, что использование любых персонажей в шахматах было бы более уместным, так как массив выборов в любой момент времени можно было бы рассматривать как древовидный.

Answer 1

Как указывал TaslemGuy, генетические алгоритмы не гарантируются оптимальными, хотя они обычно дают хорошие результаты.

Чтобы получить оптимальные результаты, вам нужно будет искать все возможные комбинации действий, пока не найдете оптимальный путь через древовидное представление. Однако делать это для StarCraft сложно, так как существует очень много разных путей для достижения цели. В шахматах вы перемещаете пешку с e2 на e4, а затем противник движется. В StarCraft вы можете перемещать блок в момент x или x + 1 или x + 10 или ...

Шахматный движок может смотреть на различные аспекты доски (например, сколько штук есть и сколько делает противник имеет), чтобы вести поиск. Он может игнорировать большинство доступных действий, если знает, что они строго хуже других.

Для создателя стройного заказа действительно имеет значение только время. Лучше ли построить еще один гул, чтобы быстрее добывать минералы, или быстрее начать этот нерестовый бассейн? Не так прямолинейно, как с шахматами.

Такие решения происходят довольно рано, поэтому вам нужно будет найти каждую альтернативу для заключения, прежде чем вы сможете выбрать более подходящую, которая займет долгое время. Если бы я написать билд заказ Оптимизатор сам, я бы, наверное, попытаться сформулировать эвристики, который оценивает, насколько хорошо (закрыть до целевого состояния) текущее состояние, так же, как движки делают:

Score = a*(Buildings_and_units_done/Buildings_and_units_required) - b*Time_elapsed - c*Minerals - d*Gas + e*Drone_count - f*Supply_left 

Это позволяет сохранить оценку, привязанную к проценту завершения, а также общеизвестным знаниям StarCraft (сохраняйте свои ресурсы на низком уровне, создавайте беспилотные летательные аппараты, не создавайте больше ресурсов, чем вам нужно). Конечно, переменные a-f нуждаются в настройке.

После того, как у вас есть эвристика, которая может несколько оценить ценность ситуации, я бы использовал Best-first search или, может быть, IDDFS, чтобы искать через дерево возможностей.

Edit:

Я недавно нашел paper, что на самом деле описывает строить оптимизацию порядка в StarCraft, в режиме реального времени даже. Авторы используют depth-first search с branch and bound и эвристикой, которые оценивают минимальное количество усилий, необходимых для достижения цели на основе технического дерева (например, зерлинги нуждаются в нерестилище) и времени, необходимого для сбора необходимых минералов.

Answer 2

Было проведено некоторое исследование, проведенное с использованием иерархического обучения усилению, чтобы построить многоуровневое упорядочение действий, которое эффективно максимизирует вознаграждение. Я не нашел много кода, реализующего эту идею, но есть несколько статей, описывающих алгоритмы на основе MAXQ, которые были использованы для явного решения доменов стратегической игры в реальном времени, таких как this и this.

Answer 3

Генетический алгоритм может быть или не может быть оптимальным или не оптимальным решением. Основываясь на сложности Генетического алгоритма, сколько мутаций существует, формы комбинаций и как интерпретируются хромосомы генетического алгоритма.

Итак, в зависимости от того, как реализован ваш ИИ, генетические алгоритмы могут быть лучшими.

Вы смотрите один из способов реализации генетических алгоритмов, забывая о генетическом программировании, использовании математики, функций более высокого порядка и т. Д. Генетические алгоритмы могут быть Чрезвычайно сложными и с использованием умных систем объединения для скрещивания, чрезвычайно умный.
Например, нейронные сети довольно часто оптимизируются генетическими алгоритмами.

---

Посмотрите «Генетическое программирование». Он похож, но использует древовидные структуры вместо строк символов, что позволяет более сложным взаимодействиям лучше развиваться. Для более сложных вещей они обычно работают лучше.

Answer 4

Этот генетический алгоритм оптимизирует стратегию только для одной конкретной части игры: порядок первых нескольких действий по созданию игры. И у него есть очень конкретная цель: иметь как можно больше тараканов.

Единственные аспекты, влияющие на эту систему, кажется, (я не Starcraft игрока):

• времени сборки различных узлов и зданий
• разрешенных единиц и здание с учетом имеющихся единиц и зданий
• Скорость регенерации личинки.

Это относительно ограниченная, относительно четко определенная проблема с большим пространством поиска. Таким образом, он очень хорошо подходит для генетических алгоритмов (и в этом есть немало других алгоритмов оптимизации). Полный ген - это определенный набор заказов на строительство, который заканчивается 7-й плотвой. Насколько я понимаю, вы можете просто «сыграть» этот конкретный ген, чтобы увидеть, как быстро он заканчивается, поэтому у вас очень четкий тест на пригодность. У вас также есть несколько хороших ограничений на порядок сборки, поэтому вы можете комбинировать разные гены немного умнее, чем просто случайным образом.

Генетический алгоритм, используемый таким образом, является очень хорошим инструментом для поиска более оптимального порядка сборки для первого этапа игры в Starcraft. Из-за его случайного характера также хорошо найти удивительную стратегию, которая могла бы стать дополнительной целью автора.

Чтобы использовать генетический алгоритм как алгоритм в игре RTS, вам нужно найти способ кодирования реакций на ситуации, а не просто старые старые заказы. Это также предполагает правильное определение ситуаций, которые могут быть сложной задачей сами по себе. Тогда вы должны позволить этим генам играть в тысячи игр звездных, друг против друга и (возможно) против людей, выбирать и комбинировать победителей (или более длительных неудачников). Это также хорошее применение генетических алгоритмов, но оно включает в себя решение довольно многих очень трудных задач, прежде чем вы даже дойдете до части генетического алгоритма.

Answer 5

Хотя я не слишком хорошо знаком с этим полем, у меня есть трудное время, обуславливающее концепцию генов в структуру данных, которая представляет собой последовательность действий. Это не самостоятельный выбор, который можно смешивать и сопоставлять, как голова и нога. Итак, какая ценность для таких вещей, как воспроизведение и скрещивание?

Хм, это очень хороший вопрос. Возможно, первые несколько шагов в Starcraft действительно могут выполняться практически в любом порядке, поскольку контакт с противником не так близок, как может быть в шахматах, и поэтому не так важно помнить порядок первых нескольких ходов, как он должен знать, какие из многих ходов включены в первые несколько. Но ссылка, по-видимому, подразумевает иное, что означает, что «гены» действительно не все, что поддается замене, если в кодировке, которую мне не хватает, есть что-то хитрое.

В целом, и, глядя на указанную вами ссылку, я бы сказал, что генетические алгоритмы являются плохим выбором для этой ситуации, которая может быть точно математически смоделирована в некоторых частях, а дерево поиска расширено в других. Они могут быть лучше, чем исчерпывающий поиск пространства возможностей, но может и не быть, особенно учитывая, что существует несколько групп населения, а более бедные - просто теряют время обработки.

Однако я имею в виду, что «плохой выбор» заключается в том, что он неэффективен по сравнению с более подходящим подходом; это не означает, что он не смог бы обеспечить 98% оптимальных результатов в течение секунды или что-то еще. В таких ситуациях, когда грубая сила компьютера полезна, обычно важно, чтобы вы правильно смоделировали пространство поиска, чем использовали наиболее эффективный алгоритм.