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

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

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

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

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

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

Answer 2

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

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

Вы ищете ЕДИНЫЙ способ реализации генетических алгоритмов, забывая при этом о генетическом программировании, использовании математических функций, функций высшего порядка и т. д. Генетические алгоритмы могут быть ЧРЕЗВЫЧАЙНО сложными иумные комбинирующие системы для скрещивания, чрезвычайно интеллектуальные.
Например, нейронные сети довольно часто оптимизируются генетическими алгоритмами.

---

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

Answer 3

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

Чтобы получить оптимальные результаты, вам придется искать все возможные комбинации действий, пока не найдете оптимальный путь в древовидном представлении. Тем не менее, сделать это для StarCraft сложно, так как есть много разных путей для достижения цели. В шахматах вы перемещаете пешку с e2 на e4, а затем противник движется. В StarCraft вы можете перемещать юнитов в момент х или х + 1 или х + 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 потребуют настройки.

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

Редактировать

Недавно я нашел бумагу , которая фактически описывает оптимизацию порядка сборки в StarCraft, даже в реальном времени. Авторы используют поиск в глубину с ответвлением и границей и эвристики, которые оценивают минимальный объем усилий, требуемых для достижения цели, на основе технологического дерева (например, зерлингам нужен нерестовый пул) и время, необходимое для сбора необходимых минералов.

Answer 4

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

Answer 5

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

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

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

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

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

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