ADD 2010: Отчет Алексеева Алексея/Елена Сагалаева. Искусственный интеллект в играх

Ссылки сюда (3) →

Искусственный интеллект в играх (Елена Сагалаева на ADD-2010)

Докладчик — известный блоггер alenacpp. Я даже немного читал блог. В целом доклад ничего, но его название скорее «Некоторые алгоритмы в играх». Был рассказ про эвристики и немного про алгоритмы на графах, но не было эмуляции человеческой деятельности (особенно творческой), которой характеризуется искусственный интеллект (естественно ИМХО, так как это нечеткие определения).

Было сказано, что игра должна доставлять fun игроку. В качестве примера были приведены следующие эвристики:

• Если при стрельбе игрок попадает с вероятностью 50 %, то на третий раз должен железно попасть. Сказали, что это вероятность с состоянием.
• В гонках соперничающие машины должны ехать неподалеку от игрока. Неважно, выигрывает он или проигрывает. Аналогия — машинки на резинке.

Дальше был рассказ про алгоритмы на графах. Точнее, какие используют: Дейкстра, A* и НA*?. Первый я отлично знаю класса с 9-ого. Он ищет минимальные пути от заданной вершини до все остальных. Про A* — слышал. Это Дейкстра с консистентной эвристикой (удовлетворяет правилу треугольника). В худшем случае работает, как Дейкстра, но в лучшем сильно быстрее. Третий — модификация второго; ничего про него не слышал. Надо будет разобраться. На вопрос про количество вершин — ответили, что было 100, а вообще не знают. Следующим вопросом выяснил, что число ребер порядка вершин (как правило в играх регулярное замощение карты). Вообще, для 100 вершин и такого же порядка ребер можно пускать Дейкстру 10000 раз в секунду. И если граф не меняется, то можно Флойдом все вычислить пути для каждой пары. К сожалению не было рассказано, не были ли использованы инкрементальные алгоритмы a-la Беллман-Форд. Именно они используются в сетевом протоколе RIP, где ребра могу появляться и исчезать.

Также понятно, что если граф почти регулярный то пути можно считать без стандартных алгоритмов (грубо говоря формулой)— это вроде часть HA*?

Далее была рассказано как проходить путь. Проблема связана с появление препятствий, которые к тому же могут двигаться. Решение — прибавлять вектор отклонения от помехи.

Итого: спасибо докладчику, но как-то слабовато. Мало было самих алгоритмов, все было ооочень просто и на пальцах, несмотря на то, что я отвлекался на общение по-поводу своего доклада. И, опять-таки, мое предложение к докладчику сделать нормальную лекцию с обзором алгоритмов (например поиска пути на графах) и с доказательством корректности на пальцах.