Алгоритмы стратегии в реальном времени wargame AI - PullRequest
23 голосов
/ 18 июля 2010

Я разрабатываю стратегическую варгейм в реальном времени, в которой ИИ будет отвечать за управление большим количеством юнитов (возможно, 1000+) на большой гексагональной карте.

У отряда есть несколько очков действия, которые можно потратить на передвижение, нападение на вражеских отрядов или различные специальные действия (например, создание новых отрядов). Например, танк с 5 очками действия может потратить 3 на движение, а 2 на стрельбу по врагу в пределах досягаемости. Разные юниты имеют разные затраты на разные действия и т. Д.

Некоторые дополнительные примечания:

  • Выход ИИ является «командой» для любого данного подразделения
  • Очки действий распределяются в начале периода времени, но могут быть потрачены в любой момент в течение периода времени (это необходимо для многопользовательских игр в реальном времени). Следовательно, «ничего не делайте и сохраняйте очки действия на потом» - это потенциально допустимая тактика (например, орудийная башня, которая не может двигаться, ожидая, когда противник попадет в зону действия)
  • Игра обновляется в режиме реального времени, но ИИ может получить непротиворечивый снимок состояния игры в любое время (благодаря тому, что состояние игры является одной из постоянных структур данных Clojure)
  • Я не ожидаю "оптимального" поведения, просто что-то явно не глупое и доставляющее разумное удовольствие / вызов, чтобы играть против

Что вы можете порекомендовать с точки зрения конкретных алгоритмов / подходов, которые позволили бы обеспечить правильный баланс между эффективностью и разумным поведением?

Ответы [ 4 ]

11 голосов
/ 18 июля 2010

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

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

Хотя в некоторых отношениях, возможно, идиот, Стивен Вольфрам показал, что можно запрограммировать удивительно сложное поведение на основе очень простых правил .Он смело экстраполирует из Игры Жизни на квантовую физику и всю вселенную.

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

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

РЕДАКТИРОВАТЬ

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

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

8 голосов
/ 19 июля 2010

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

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

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

Вот краткое изложение того, что я думаю, будет хорошо работать:

  1. Эволюционные алгоритмы могут работать хорошо, если вы приложите к ним достаточно усилий, но они добавят слой сложности, который создаст место для ошибок среди других вещей, которые могут пойти не так. Они также потребуют экстремальных настроек фитнес-функции и т. Д. У меня не так много опыта работы с ними, но если они похожи на нейронные сети (как я полагаю, так как обе являются эвристикой, навеянной биологическими моделями), вы быстро найти они непостоянны и далеко не последовательны. Самое главное, я сомневаюсь, что они добавляют какие-либо преимущества по сравнению с опцией, которую я описал в 3.

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

  3. Этот вариант будет моим самым рекомендуемым: имитация отжига. Имитация отжига (ИМХО) будет иметь все преимущества: 1. без дополнительной сложности, будучи гораздо более надежной, чем 2. По сути, SA - это просто случайное блуждание среди состояний. Поэтому в дополнение к стоимости и состояниям вам придется определить способ случайного перехода между состояниями. SA также не склонен застрять в локальных минимумах, хотя и дает очень хорошие результаты достаточно стабильно. Единственная настройка, требуемая для SA, - это график охлаждения, который решает, насколько быстро SA будет сходиться. Самым большим преимуществом SA, которое я нахожу, является то, что он концептуально прост и дает лучшие результаты эмпирически по сравнению с большинством других методов, которые я пробовал. Информацию о SA можно найти здесь с длинным списком общих реализаций внизу.

3b. ( Edit Добавлено намного позже ) SA и методы, которые я перечислил выше, являются общими методами ИИ и не очень специализированы для ИИ в играх. В целом, чем более специализирован алгоритм, тем больше у него шансов на лучшую производительность. См. Теорему об отсутствии бесплатного обеда 2 . Другое расширение 3 - это так называемое параллельное отпускание, которое значительно повышает производительность SA, помогая избежать локальных оптимумов. Некоторые из оригинальных работ по параллельному отпуску довольно датированы 3 , но другие были обновлены 4 .

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

8 голосов
/ 18 июля 2010

Этот вопрос огромен по объему.Вы в основном спрашиваете, как написать стратегическую игру.

Для этого материала есть тонны книг и статей в Интернете.Я настоятельно рекомендую серию Wizard Programming Wisdom и серию AI Game Programming Wisdom .В частности, раздел 6 первого тома Мудрость программирования игр AI охватывает общую архитектуру, раздел 7 - архитектуры принятия решений, а раздел 8 - архитектуры конкретных жанров (8.2 - жанр RTS).

6 голосов
/ 19 июля 2010

Это огромный вопрос, и другие ответы указывают на удивительные ресурсы для изучения.

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

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

Каждый слой может выдавать команды только слоям, расположенным непосредственно под ним. Уровень ниже этого будет затем пытаться выполнить команду с ресурсами под рукой (то есть уровнями ниже этого уровня).

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

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

Здесь действует аналогия с армией; командиры и лейтенанты и командование.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...