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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Мой вопрос довольно многословный.

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

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

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

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