Попытки использовать Alpha-Beta Search для игр в реальном времени?

Question

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

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

Все упомянутые игры пошаговые.

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

Очевидно, что дерево поиска быстро взорвалось бы в размерах. Однако мне интересно, существует ли какой-либо теоретический анализ такого подхода для игр в реальном времени? Или, может быть, даже практические исследования, которые используют очень сокращенную и упрощенную RTS?

Вопрос : Я ищу ссылки (если они есть) на эту тему.

Answer 1

Эта статья "Поиск в видеоиграх в реальном времени" , Cowling et al, 1998, утверждает, что A * широко использовался в поиске видеоигр.

Есть тезис Гайслера на MS 'Эмпирическое исследование алгоритмов машинного обучения, применяемых к поведению модели игрока в видеоигре "Шутер от первого лица" , где он в основном использует ID3 и алгоритм повышения для обученияповедение опытного солдата FPS-игрока Fortune 2 и учесть это в агенте, играющем в игру.

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

«Изучение поведения человека из наблюдения за игровыми приложениями» , Moriarty and Gonzales, 2009, является примеромдля этого.