Алгоритмы для стратегической стратегии в реальном времени AI

Ответ 1

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

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

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

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

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

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

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

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

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

Ответ 2

Если вы читаете Russell and Norvig, вы найдете множество алгоритмов для всех целей, обновленных до сегодняшнего дня., Тем не менее, я был поражен тем, как много различных проблемных классов можно успешно подойти с байесовскими алгоритмами.

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

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

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

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

ИЗМЕНИТЬ

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Каждый слой может выдавать команды только нижележащим слоям. Затем слой под ним попытается выполнить команду с ресурсами (т.е. Слоями ниже этого слоя).

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

Мастер AI высшего уровня отвечает за принятие стратегических решений, таких как "нам нужно больше ____ единиц", или "мы должны стремиться двигаться к этому месту".

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