Алгоритмы для стратегии в реальном времени wargame AI
Я разрабатываю стратегию в реальном времени wargame, где AI будет ответственен за управление большим количеством единиц (возможно 1000 +) на большой шестиугольной карте.
Единица имеет много очков действия, которые могут быть израсходованы на перемещение, напав на вражеские единицы или различные специальные действия (например, создав новые единицы). Например, корпус с 5 очками действия мог потратить 3 на перемещение затем 2 в стрельбе во врага в диапазоне. Различные единицы имеют различные затраты для различных действий и т.д.
Некоторые дополнительные примечания:
- Вывод AI является "командой" к любой данной единице
- Очки действия выделяются в начале периода времени, но могут быть потрачены в любой точке в течение периода времени (это должно допускать многопользовательские игры в реальном времени). Следовательно "ничего не делают и на потом сохраняют очки действия", потенциально допустимая тактика (например, орудийная башня, которая не может переместить ожидание врага для прибытия в рамках увольнения диапазона),
- Игра обновляет в в реальном времени, но AI может получить последовательный снимок игрового состояния в любое время (благодаря игровому состоянию, являющемуся одной из персистентных структур данных Clojure)
- Я не ожидаю "оптимального" поведения, просто что-то, что не очевидно глупо и обеспечивает разумную забаву/проблему играть против
Что можно рекомендовать с точки зрения определенных алгоритмов/подходов, которые допускали бы правильный баланс между эффективностью и довольно интеллектуальным поведением?
4 ответа
Во-первых, вы должны стремиться сделать свою игру пошаговой на каком-то уровне для ИИ (то есть вы можете каким-то образом смоделировать ее пошагово, даже если она не может быть полностью пошаговой, в RTS вы можете разбить дискретные интервалы времени в ходы.) Во-вторых, вы должны определить, с каким объемом информации ИИ должен работать. То есть, если ИИ разрешено хитрить и знать каждое движение своего противника (тем самым делая его сильнее) или он должен знать меньше или больше. В-третьих, вы должны определить функцию затрат государства. Идея состоит в том, что более высокая стоимость означает худшее состояние для компьютера. В-четвертых, вам нужен генератор ходов, генерирующий все допустимые состояния, в которые ИИ может перейти из заданного состояния (оно может быть однородным [независимым от состояния] или неоднородным. [зависит от состояния].)
Дело в том, что функция стоимости будет во многом зависеть от того, как именно вы определяете состояние. Чем больше информации вы кодируете в состоянии, тем лучше будет сбалансирован ваш ИИ, но тем труднее будет ему работать, поскольку ему придется искать экспоненциально больше каждой дополнительной переменной состояния, которую вы включаете (при исчерпывающем поиске.)
. Если вы дадите определение состояния и функции стоимости, ваша проблема трансформируется в общую проблему в ИИ, которую можно решить с помощью любого алгоритма по вашему выбору.
Вот краткое изложение того, что, на мой взгляд, будет хорошо работать:
Эволюционные алгоритмы могут работать хорошо, если вы приложите к ним достаточно усилий, но они добавят уровень сложности, который создаст место для ошибок, среди прочего, которые могут пойти не так.Они также потребуют огромного количества настроек фитнес-функции и т. Д. У меня нет большого опыта работы с ними, но если они чем-то похожи на нейронные сети (как я полагаю, так как обе являются эвристикой, вдохновленной биологическими моделями), вы быстро получите обнаруживают, что они непостоянны и далеко не последовательны. Что наиболее важно, я сомневаюсь, что они добавляют какие-либо преимущества по сравнению с вариантом, который я описываю в 3.
С определением функции стоимости и состояния для вас технически возможно применить приличный градиент (с предположением, что функция состояния является дифференцируемой и область переменных состояния являются непрерывными), однако это, вероятно, даст худшие результаты, поскольку самая большая слабость градиентного спуска - застревание в локальных минимумах. Чтобы привести пример, этот метод будет склонен к чему-то вроде атаки врага всегда как можно скорее, потому что есть ненулевой шанс уничтожить его. Ясно, что это может быть нежелательным поведением для игры, однако градиентный приличный - это жадный метод, и он не знает лучшего.
Я бы рекомендовал этот вариант больше всего: имитация отжига. Имитация отжига (ИМХО) будет иметь все преимущества 1. без дополнительной сложности, будучи гораздо более надежной, чем 2. По сути, SA - это просто случайное блуждание между состояниями. Таким образом, в дополнение к стоимости и состояниям вам нужно будет определить способ случайного перехода между состояниями. SA также не склонен застревать в локальных минимумах, но при этом стабильно дает очень хорошие результаты.Единственная настройка, требующаяся для SA, - это график охлаждения, который определяет, насколько быстро SA будет сходиться. Самым большим преимуществом SA, которое я считаю, является то, что он концептуально прост и дает лучшие эмпирические результаты по сравнению с большинством других методов, которые я пробовал. Информацию о SA можно найти здесь с длинным списком общих реализаций внизу.
3b. ( Править. Добавлено намного позже ) SA и перечисленные выше методы являются общими методами ИИ и не совсем специализированы для ИИ в играх. В целом, чем более специализирован алгоритм, тем больше у него шансов на лучшую работу. См. Теорему о запрете бесплатного обеда 2 . Другое расширение 3 - это то, что называется параллельным темперированием, которое значительно улучшает производительность SA, помогая избежать локальных оптимумов. Некоторые из оригинальных работ по параллельному отпуску довольно датированы 3 , но другие были обновлены 4 .
Независимо от того, какой метод вы выберете в конце, будет очень важно разбить вашу проблему на состояния и функцию стоимости, как я сказал ранее. Как правило, я бы начал с 20-50 переменных состояния, поскольку количество этих переменных в вашем пространстве поиска по состоянию экспоненциально.
Если вы прочитаете Russell and Norvig , вы найдете множество алгоритмов для любых целей, обновленных в значительной степени до современного уровня техники. Тем не менее, я был поражен тем, сколько различных классов проблем можно успешно решить с помощью байесовских алгоритмов.
Однако в вашем случае, я думаю, было бы плохой идеей для каждого модуля иметь свою собственную сеть Петри или механизм вывода ... здесь не так много процессора, памяти и времени.Следовательно, другой подход:
Хотя в некотором смысле возможно, псих, Стивен Вольфрам показал, что можно запрограммировать чрезвычайно сложное поведение на основе очень простых правил . Он смело экстраполирует Игру Жизни на квантовую физику и всю Вселенную.
Точно так же многие исследования малых роботов сосредоточены на эмерджентном поведении или интеллекте роя . В то время как классическая военная стратегия и практика в значительной степени основаны на иерархии, я думаю, что армия полностью самоотверженных, бесстрашных бойцов (которые маршируют на вашем компьютере) могла бы быть чрезвычайно эффективной, если бы действовала как самоорганизующиеся кластеры. .
Этот подход, вероятно, немного лучше подошел бы к модели параллелизма на основе акторов Erlang или Scala, чем к STM Clojure: я думаю, что самоорганизация и акторы будут очень хорошо сочетаться. Тем не менее, я мог представить себе просмотр списка юнитов на каждом ходу, и каждый юнит оценивает лишь небольшую горстку очень простых правил для определения своего следующего действия. Мне было бы очень интересно узнать, пробовали ли вы этот подход и как он прошел!
РЕДАКТИРОВАТЬ
Что-то еще, что было у меня на уме, но это снова ускользнуло, пока я писал: я думаю, что вы можете получить замечательные результаты от этого подхода, если объедините его с генетическим или эволюционное программирование; т.е.позвольте вашим виртуальным игрушечным солдатам вести войну друг с другом, пока вы спите, позвольте им кодировать свои стратегии и смешивать, сопоставлять и видоизменять свой код для этих стратегий; и пусть программа судейства отберет наиболее успешных воинов.
Я читал о некоторых поразительных успехах, достигнутых с помощью этих методов, когда юниты действовали так, как мы никогда не думали. Я слышал, что ИИ, работающие по этим принципам, пришлось намеренно заглушить, чтобы не расстраивать человеческих оппонентов.
Это огромный вопрос, и в других ответах указаны удивительные ресурсы, которые стоит изучить.
Я имел дело с этой проблемой в прошлом и нашел подход «простое поведение-проявляется-сложное / возникающее поведение» слишком громоздким для человеческого дизайна, если не рассматривать его генетически / эволюционно.
Вместо этого я решил использовать абстрактные уровни ИИ, подобно тому, как армии работают в реальной жизни. Юниты будут сгруппированы с соседними юнитами того же времени в отряды, которые сгруппированы с соседними отрядами, чтобы создать своего рода мини-батальон.Здесь можно использовать больше уровней (групповые батальоны в регионе и т. Д.), Но в конечном итоге наверху находится стратегический ИИ высокого уровня.
Каждый уровень может отдавать команды только слоям, находящимся непосредственно под ним. Слой под ним затем попытается выполнить команду с имеющимися ресурсами (т. Е. С уровнями ниже этого уровня).
Пример команды, отданной одному отряду, - «Иди сюда» и «стреляй по этой цели». Команды более высокого уровня, отправленные на более высокие уровни, будут «защищать это место», которые этот уровень будет обрабатывать и выдавать соответствующие команды на более низкие уровни.
Главный ИИ высшего уровня отвечает за стратегические решения совета директоров, такие как «нам нужно больше ____ единиц» или «мы должны стремиться двигаться к этому месту».
Здесь работает аналогия с армией; командиры и лейтенанты и командование.
Этот вопрос огромен по своему охвату. Вы в основном спрашиваете, как написать стратегическую игру.
Есть тонны книг и онлайн-статей для этого материала. Я настоятельно рекомендую серии Game Programming Wisdom и AI Game Programming Wisdom. В частности, раздел 6 первого тома AI Game Programming Wisdom охватывает общую архитектуру, раздел 7 охватывает архитектуры принятия решений, а раздел 8 охватывает архитектуры для конкретных жанров (8.2 касается жанра RTS).