Логическая игра: максимизировать (или минимизировать) шансы встречи двух агентов

Question

Примечание: этот вопрос помечен как language-agnostic и python , так как моей главной задачей является поиск алгоритма для реализации решения проблемы, но информация о том, как это реализовать эффективно (= быстро выполняется!) в python, является плюсом.

Правила игры:

• Представьте себе две команды: одну из агентов (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. Итак, мое время вычислений увеличивается в геометрической прогрессии.

Тем не менее, я не уверен, что это проблема, которая может быть решена только "грубой силой". И даже если это так, мне интересно:

1. Если оптимальное решение о грубой силе обязательно растет в геометрической прогрессии (по времени).
2. Если есть способ вычислить неоптимальное, наилучшее на местном уровне решение.

Спасибо!

Answer 1

Члены двух команд и слоты определяют трехсторонний граф A-S-B, ребра которого определяются возможными ходами. Двухсторонние подграфы, состоящие из слотов и членов одной команды, представляют интерес; Назовите их A-S для графика с членами команды A и S-B для членов команды B. Вы можете использовать график S-B, чтобы назначить значения для слотов, а затем график S-A, чтобы выбрать ходы, которые максимизируют или минимизируют значение для команды A.

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

Учитывая значения для слотов, выбор ходов для команды A становится стандартной проблемой: задача назначения . Это связано с максимальным двойным соответствием, предложенным в ответе отсутствует, но значение слотов необходимо учитывать; Для ребер может быть задан вес, равный значению слота, в котором ребро падает, с максимальным взвешенным двудольным соответствием, эквивалентным задаче назначения. Используйте стандартные алгоритмы, чтобы решить (или приблизить) эту часть проблемы.

Так, как мы можем назначить значения слотам? Я бы посоветовал просто генерировать случайные ходы для членов команды B, подсчитывать, как часто слоты заняты, и делить счетчики на количество выборочных ходов, которые вы рассматриваете. Из вопроса не совсем понятно, насколько сложно будет генерировать случайный набор ходов; при условии, что у каждого члена команды есть возможность остаться на месте, это легко сделать, просто выбрав ходы для каждого участника в случайном порядке.

Упрощающим фактором на обоих этапах является то, что существует простой способ разложить проблему на независимые подзадачи. Связанные компоненты двудольных графиков показывают, какие члены команды могут перемещаться таким образом, который мешает другим, например, если члены команды разбиты на две группы в разных частях доски, группы можно обрабатывать независимо. Это применимо на обоих этапах, как для вероятностной оценки слотов с графиком S-B, так и для оптимизации назначения на графике A-S. Конечно, если какой-либо компонент достаточно мал, вы всегда можете перечислить возможности и точно решить подзадачу.

Answer 2

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

Шаг 1: Вычислите вероятность каждого сайтазанятый B агентом

Построить следующий двудольный граф.Вершинами являются B агенты B1,B2,...,BK и сайты S1,S2,...,SN, и между Bi и Sj существует грань, если агент Bi может занимать сайт Sj.Найдите все максимальные соответствия (или максимальные соответствия, если это ваш алгоритм для B агентов) на этом графике, скажем, есть M из них.Для каждого сайта Si вероятность того, что сайт будет занят агентом B , составляет

Pi = #(matchings using Si) / M

Алгоритмы для рассмотрения :

• Алгоритм Хопкрофта – Карпа

Шаг 2: Найти соответствие наибольшего веса для A агентов

Построить следующий двудольный граф с граничными весами.Вершинами являются A агенты A1,A2,...,AL и сайты S1,S2,...,SN, и существует граница между Ai и Sj, если агент Ai может занимать сайт Sj и этот край имеетвес Pi.Найти максимальное соответствие с максимальным или минимальным весом.

Алгоритмы для рассмотрения :

• Алгоритм Беллмана – Форда
• Алгоритм Дейкстры
• куча Фибоначчи
• венгерский алгоритм

Сейчас это не более чем переформулировка проблемы, новозможно, размышление об этом таким образом приведет к менее грубому подходу грубой силы.Например, после выполнения шага 1 вы можете воспользоваться жадным алгоритмом, чтобы выбрать игру для A агентов, включив в них Si с наибольшей / наименьшей вероятностью.Хотя найти совпадения может быть сложно, зная, существует ли он, нет.Вы можете использовать Теорема Холла о браке , чтобы определить, существует ли идеальное совпадение после выбора наиболее / наименее вероятного Si с.

Answer 3

Если я правильно понимаю, проблема поиска оптимальной стратегии для A, если вы знаете позиции для B, такая же, как и нахождение максимального соответствия в двудольном графе.

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

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

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

while you can find a path, augment the path

a path is a sequence of vertices a1, b1, a2, b2, ... an, bn such that
  ai -> bi is an unmatched edge
  bi -> a(i+1) is a matched edge
  a1 and bn are unmatched

to augment a path
  match all the unmatched edges (ai -> bi)
  unmatch all the matched edges (bi -> a(i+1))
  (this results in one aditional matched edge after the iteration)

Наивной реализацией этого алгоритма является O (V * E), но, возможно, вы найдете где-нибудь более эффективные реализации двухстороннего сопоставления на python.

Answer 4

Это на самом деле не столько вопрос программирования, сколько вопрос теории игр. Далее следует набросок теоретико-игрового анализа проблемы.

У нас есть игра двух игроков (A и B). Игра для двух игроков - это всегда игра с нулевой суммой, то есть выигрыш одного игрока - это проигрыш для другого. Даже если выигрыши в игре не равны нулю (т. Е. Есть результаты, которые дают положительные выплаты обоим игрокам), выплаты всегда можно нормализовать (принимая их разницу), поэтому мы можем без потери общности предположить, что игра здесь также равна нулю Итоговая игра. Из этого мы делаем вывод, что если целью А является максимизировать [минимизировать] количество встреч с агентами Б, то целью Б является минимизация [максимизация] количества встреч с агентами А.

На основании описания далее предполагается, что A и B выбирают свои ходы одновременно, то есть A выбирает слоты для агентов A, не зная, какие слоты будут собирать агенты B, и наоборот. Без этого предположения, т. Е. Если B видит ходы A, B очень легко "выиграть".

Позвольте X быть набором всех возможных назначений агентов A доступным слотам (подчиняющимся ограничениям для текущего раунда или поворота), то есть X является набором подмножеств слотов; каждое подмножество, обозначающее назначение агентов именно этим слотам в подмножестве. Аналогично, пусть Y будет множеством всех возможных назначений агентов B доступным слотам (аналогично, подчиняясь ограничениям для агентов B). Сейчас есть четыре игры. В каждой игре A выбирает элемент x из X, а b выбирает элемент y из Y, после чего:

• В игре I.a, A выигрывает, если x и y делят слот, в противном случае B выигрывает (в этой игре A пытается провести хотя бы одну встречу)
• В игре I.b A получает положительный выигрыш, эквивалентный количеству общих слотов в x и y (в этой игре A пытается максимизировать количество собраний)
• В игре II.a, A выигрывает, если x и y не делят слот, в противном случае B выигрывает (в этой игре A пытается избежать любых встреч)
• В игре II.b A получает отрицательный выигрыш, эквивалентный количеству общих слотов в x и y (в этой игре A пытается минимизировать количество собраний)

Все эти игры могут быть проанализированы с использованием стандартных теоретико-игровых методов. Мы фокусируемся на игре I.a, а остальное оставляем читателю в качестве упражнения. Если имеется элемент y из Y, доступный так, что ни один из x в X не использует общий слот с y, B выбирает y и выигрывает; поэтому предположим, что нет, то есть предположим, что каждый y в Y соответствует по меньшей мере одному x в X, так что x и y совместно используют слот. A не может играть с помощью какой-либо детерминированной стратегии, потому что B может противостоять ей, выбрав y, который не делит слот с детерминистически выбранным x; поэтому А должен играть по смешанной стратегии, то есть по рандомизированной стратегии точно так же, как смешанная стратегия 1/3 - 1/3 - 1/3 оптимальна для Рошамбо (камень-ножницы-бумага). В ответ также будет играть смешанная стратегия. Вероятности различных элементов X и Y продиктованы количеством совпадающих наборов, то есть элементы x из X, имеющие общие слоты со многими Y, будут иметь более высокую вероятность в смешанной стратегии, чем те, которые имеют общие слоты только с несколько Y.

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