Вопросы с собеседования: поведенческий ИИ

Это первая часть вопросов. Все вопросы можно найти здесь.

(1a)Какая разница между конечным автоматом(FSM) и иерархическим конечным автоматом(HFSM)? Дайте пример иерархического конечного автомата, который нельзя будет легко заменить конечным.

Конечные автоматы: http://en.wikipedia.org/wiki/Finite-state_machine
Иерархический конечный автомат, как многие догадались - это автомат, в качестве состояния у которого тоже автомат. http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
Иерархический автомат всегда можно представить в виде неирархического. Но при определенном размере обычный конечный автомат получится такой здоровый, что с ним будет очень тяжело работать.
Также см. ответ тут

(1b)Какие есть недостатки у конечных автоматов? Когда разумно использовать конечные автоматы, а когда их недостаточно, чтобы реализовать нужное поведение в игре?
Не умеют работать с параллельными и асинхронными задачами.

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

(1c)Что такое дерево принятия решений (decision tree)? Когда вы будете использовать такое дерево? Дайте оценки по производительности. Как сгенерировать дерево принятия решений автоматически из набора данных? Реально ли это сделать в рантайме, делалось ли это раньше в коммерческой игре? В каких ситуациях так следует делать и каким образом должны быть организованы данные, чтобы это было возможно?

http://en.wikipedia.org/wiki/Decision_tree
Минусы - каждый раз надо гнать заново сначала, не умеют хранить уже принятые решения, error propagation.
Автоматически генерятся с помощью алгоритмов типа C4.5 и ID3.
Игра Black&White использовала ID3. См. тут и тут[.ppt].

(1d)Вы реализуете схватку с боссом в 3D игре. У босса есть 15 вариантов атаки. Геймдизайнеры попросили вас сделать так, чтобы игрок в течение схватки видел как можно больше из этих 15 вариантов атак и чтобы он редко (а лучше никогда) видел одну и ту же атаку два раза подряд. Каким образом тут следует реализовать алгоритм атаки? Имейте в виду, что не все атаки досупны в каждый момент времени. Например, у босса есть атака, которая возможна только в ближнем бою, атака бомбами, которая возможна только если игрок далеко.

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

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

Узнаем у геймдизайнеров один ли лифт в игре. Скорее всего он один, поэтому скриптуем его.
Здесь можно реализовать групповое поведение, например на blackboard'ах. Основной проблемой тут будут проверки, много проверок. Что убежавший до кнопки добежал и кнопку нажал, убедиться, что лифт приехал и не пихать их всех в шахту, что все влезают в лифт и т.п.
Обсуждение и более подробно описанные варианты решения тут.

(1f)Вам дана задача разработать игру похожую на Thief: The Dark Project и вам нужно сделать стражников с неидеальными слухом и зрением и посадить их в тускло освещенные замки. Они могут искать игрока, если они думают, что к ним кто-то вторгся. Как вы смоделируете систему сенсоров для этих стражников, как вы будете собирать аудио, визуальные и другие стимулы системы? Как вы реализуете различные уровни тревоги стражников и почему?

Система сенсоров Thief'а описана здесь.

(1g)Что такое планирование? Как оно используется и в чем его преимущества? Реально ли использовать планирование в реалтайм игре? Если да, то назовите игры, в которых планирование было реализовано как часть ИИ. Опишите архитектуру систему ИИ с планированием для любого жанра игры.

В целом про планирование: The Planning System.
Правильные ключевые слова: GOAP, STRIPS, HTN.
Также см. тут.

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

Делим все заклинания на "атакующие", "защитные" и еще какие-нибудь по вкусу. В зависимости от того, сколько маны и хитпоинтов у нас, сколько у противника используем заклинание из нужной группы, выбираем его рандомно.
Более подробное описание см. тут.
Этого должно хватить. Если геймдизайнерам это не понравится, можно использовать более умные методы.

Бонусная задачка от senigami:
Вот такая задачка: представьте себе Красную площадь в довольно людное время суток. И много людей которые пытаются перейти площадь с одной стороны на другую( Из одной рандомной точки одной стороны в другую рандомную точку другой) Как сделать так, чтобы люди не сталкивались при движении (т.е. обходили друг друга)?

Что-то не густо с ответами на мою задачу. Как и обещал хозяйке поста - мои варианты решения задачи. Их несколько, ну как и у любой интересно задачи. Первая реализация, которую я сразу придумал занимаясь когда-то этой задачей называется Steering behaviour. Реализация в моем случае была достаточно простая: к НПЦ, идущим по просчитанному заранее пути прикладываются силы. Первая возникает только тогда, когда НПЦ отклоняется от просчитанной траектории и старается "вернуть" НПЦ на траекторию. Вторая возникает когда поблизости возникает другой НПЦ. НПЦ отталкиваются друг от друга как одинаковые заряды. Этот способ конечно не нов и использовался уже в играх (я на КРИ пару раз слышал такие идеи от АИ программистов). Что-то подобное реализовано, как я понимаю, тут http://opensteer.sourceforge.net/
Второй подход - реализовать все с помощью коллижена. НПЦ ходят в виде больших вертикальных цилиндров. Когда на некотором апдейте они заколлизятся то их их скорости просто вычитается проекция вектора скорости на линию центров (нужно конечно немножко читить чтобы при этом скорость не оказалась равна 0). Визуально выглядит этот вариант не очень красиво :(
Третий подход, о котором я сам недавно узнал - на основании данных о размерах и желаемых скоростях объектов составлять и решать некоторую оптимизационную задачу. В результате решения задачи получим скорость, применяя которую на данном апдейте мы гарантированно не заколлизимся. Статья с подробным описанием для интересующихся тут http://gamma.cs.unc.edu/CA/

Я добавила нумерацию, чтобы на вопросы было проще ссылаться из комментариев. Комментируйте, не стесняйтесь. Если стесняетесь, комментируйте анонимно :-).

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