Определение оптимального скоринга на вероятностно представленной двумерной сетке в реальном времени

Question

Я отправляю это в StackOverflow, cstheory.stackexchange.com и math.stackexchange.com, потому что я не совсем уверен, где он лучше всего подходит. Надеюсь, все в порядке.

У меня есть 2D-сетка (размер зависит от каждой карты, от 10X10 до 20X20, обязательно квадрат), где каждая ячейка содержит, между прочим, вероятность (от 0 до 1), что каждая единица (от 10 до 50 в зависимости от карты) находится в этом месте.

Существует 2 основных типа единиц, есть большие единицы, поведение которых контролируется алгоритмом, которым вы, надеюсь, собираетесь помочь мне, и есть небольшие единицы, которые могут двигаться или иметь свое (булево) состояние изменено с помощью больших единиц. Все подразделения принадлежат командам, но любой большой блок может перемещать любую маленькую единицу. Матч определяется как положением, так и по статусу меньших единиц. Каждый блок знает свои собственные координаты.

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

У меня уже есть система отслеживания, так что это не проблема и не вычисляет затраты времени на перемещения, хотя это следует назвать минимально по соображениям производительности.

Мое намерение состоит в том, чтобы система планирования выводила последовательность желаемых состояний/действий. Например, будьте на (9,4) под углом 43 градуса, а затем на (12,4) на 12 градусов и включите малый блок.

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

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

Производительность здесь довольно важна, и я вполне могу согласиться торговать качеством решения для значительного повышения производительности.

Вот мои мысли до сих пор:

• Наиболее полное решение будет исчерпывающий поиск, но производительность исключает это.

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

• Продолжительность работы на единицу времени на среднем современном ПК должна быть < = 25 мс, если возможно - не установлена ​​в камне - это C++, так что это довольно быстро.

• Адаптация шахматного алгоритма может быть хорошим подходом.

• Я плохо разбираюсь в этом, я должен спросить интернет.

• Лучший подход почти наверняка будет оценкой.

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

• Мой вопрос просят несколько подробней.

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

• Этот последний пункт рифмован.

• Если вы все еще читаете это, я могу согласиться выйти за вас замуж.

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

Answer 1

Я честно считаю, что самый быстрый способ получить эту работу - начать просто и строить.

Предлагаю вам начать с базовой теории игр, особенно game trees. Создайте игрока, который может играть в такую ​​игру, глядя вперед на фиксированное количество ходов. Затем выполните A * («Алгоритм звезды»), чтобы сделать его быстрее. Прочитайте эвристику, чтобы угадать значение состояния без решения всего будущего дерева.

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

Answer 2

У вас, похоже, проблема с большим пространством состояний и правилами, которые, по крайней мере, на первый взгляд, не особенно просты. Я видел два заявленных подхода к этому, оба из которых включают в себя повторное моделирование вперед во времени - поиск дерева Монте-Карло (http://en.wikipedia.org/wiki/Monte-Carlo_tree_search) и приближенное динамическое программирование (http://adp.princeton.edu/Papers/Powell-NRLWhat%20you%20should%20know%20about%20approximate%20dynamic%20programming.pdf).

Поиск в дереве Монте-Карло имеет опыт использования игр для игр.