Логическая игра: максимизация (или минимизация) шансов для двух агентов встретиться
Примечание: этот вопрос помечен как language-agnostic и python, поскольку моя главная задача - найти алгоритм для реализации решения задачи, но информация о том, как реализовать его эффективно (=выполнить быстро!) на python, будет плюсом.
Правила игры:
- Представьте себе две команды - одну из агентов A (
An) и другую из агентов B (Bn). - В игровом пространстве существует определенное количество доступных слотов (
Sn), которые могут быть заняты. - На каждом ходу каждому агенту дается подмножество слотов, которые он/она может занять.
- Один агент может занимать только один слот одновременно, однако каждый слот может быть занят двумя разными агентами, при условии, что они каждый из своей команды.
Вопрос:
Я пытаюсь найти эффективный способ вычисления наилучшего возможного хода для агентов A, где "наилучший возможный ход" означает либо максимизацию, либо минимизацию шансов занять те же слоты, которые занимает команда B. Ходы команды B заранее не известны.
Пример сценария:
Этот сценарий намеренно тривиален. Он просто предназначен для иллюстрации игровой механики.
A1 can occupy S1, S2
A2 can occupy S2, S3
B1 can occupy S1, S2
В этом случае решение очевидно: A1 → S1 и A2 → S2 - это вариант, который гарантирует встречу с B1 [поскольку B1 не может избежать занятия ни S1, ни S2], тогда как A2 → S3 и A1 → random(S1, S2) - это те, которые максимизируют шансы избежать B1.
Реальные сценарии:
В реальных сценариях слотов могут быть сотни, а агентов в каждой команде - десятки. Сложность в наивной реализации, которую я пробовал до сих пор, заключается в том, что я в основном рассматриваю каждый возможный набор ходов для команды B, и оцениваю каждый из возможных альтернативных наборов ходов для A. Таким образом, мое время вычислений увеличивается экспоненциально.
Тем не менее, я не уверен, что эта проблема может быть решена только "грубой силой". И даже если это так, я задаюсь вопросом:
- Если оптимальное решение грубой силы обязательно растет экспоненциально (по времени).
- Есть ли способ вычислить неоптимальное, локально лучшее решение.
Спасибо!