NP-Hard? Алгоритмическая сложность обнаружения сговора в онлайн-покере? - PullRequest
Новая
       17

NP-Hard? Алгоритмическая сложность обнаружения сговора в онлайн-покере?

10 голосов
/ 26 апреля 2009

Как лучше всего описать алгоритмическую сложность обнаружения сговора для сайта онлайн-покера с десятью миллионами игроков?

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

  • Что на сайте зарегистрировано 10 000 000 пользователей.
  • что эти игроки сыграли в общей сложности 5 миллиардов рук.
  • Единственная информация, которую вы предоставляете, - это «база данных истории мастер-рук» для сайта, содержащая все закрытые карты игроков и действия по ставкам для каждой руки.
  • Другими словами, вы НЕ МОЖЕТЕ использовать ярлыки, такие как проверка IP-адресов, поиск необычных схем рейка / прибыли и т. Д.
  • Предположим, вам дана функция, которая при прохождении группы из ровно N (где N от 2 до 10) игроков возвращает TRUE, если ВСЕ игроки в группе сговорились ВМЕСТЕ. Если некоторые, но не все игроки являются тупиками, функция возвращает FALSE. Возвращаемое значение TRUE выполняется с (например) доверительной вероятностью 75%.

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

Спасибо!

Ответы [ 4 ]

4 голосов
/ 26 апреля 2009

Подход грубой силы, который я сразу вижу, таков: 

Set colluders = new Set();
for(Player p1 : allPlayers)
{
  for(Player p2 : allPlayers)
  {
    if(!p1.equals(p2) && haveColluded(p1, p2))
    {
      colluders.add(p1);
      colluders.add(p2);
    }
  }
}

Я не вижу смысла вызывать haveColluded с большим числом аргументов, чем 2, потому что это может привести к ложным отрицаниям. Я полагаю, хотя это зависит от того, насколько дорогая функция. Но вышеприведенное приводит к O (n ^ 2) вызовам функции hasColluded (n - количество игроков). Сама функция, по-видимому, будет O (m), где m - количество игр, в которые они играли вместе. Таким образом, алгоритм кажется хорошо при O (n ^ 3). Чтобы быть NP-сложным, вы должны доказать, что «проблема H является NP-трудной в том и только в том случае, если существует NP-полная задача L, полиномиальное время Тьюринга-сводимо к H [...] Другими словами, L может решаться за полиномиальное время с помощью оракула с оракулом для Х. " (http://en.wikipedia.org/wiki/NP-hard). Я изучил NP-полные проблемы (например, 3-SAT, Задача коммивояжера и т. Д.) И не вижу, как вы это докажете. Но опять же, это кажется подозрительно похожим на проблема клики .

3 голосов
/ 27 апреля 2009

Похоже на обнаружение клики , что является NP-сложным. С другой стороны, размер клики здесь ограничен (10), поэтому грубая сила в худшем случае равна n ^ 10.

Редактировать: Ключевой вопрос здесь заключается в том, каковы свойства функции сговора. Могут ли 10 игроков, вступающих в сговор вместе, всегда быть обнаружены путем вызова функции на двух меньших наборах (скажем, 5) игроков?

1 голос
/ 07 января 2010

Я бы разделил это на два шага:

  1. Итерируйте более 5 миллиардов рук в покер, изучая игру в каждой руке. Используйте какой-нибудь алгоритм, назовем его алгоритм A с каждой стороны. По ходу дела вы строите график сговора, где вершины представляют игроков, а ненаправленные взвешенные ребра представляют некоторую уверенность в сговоре между двумя игроками. Когда алгоритм A срабатывает по подозрению в сговоре игрока X с игроком Y, некоторое значение добавляется к взвешенному ребру XY в графе сговора. По мере того, как вы прогрессируете через разыгранные руки, веса с течением времени накапливаются. Когда некоторый порог достигнут, тогда край представляет сговор между X и Y.

  2. Тогда функция, определяющая, есть ли в списке из N вершин игрока все , объединенные вместе, является вопросом проверки того, что подграф, содержащий N вершин, полностью связан (то есть каждый узел имеет вес ребра больше, чем порог сговора с каждым другим узлом в подграфе). IIRC, определяя это O (n * lg (n)).

1 голос
/ 02 мая 2009

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

Если функция сговора была абсолютно надежной, вы просто вызываете ее для каждой пары вершин графа, и вы получаете подграф.

Этот подграф, вероятно, довольно несвязен. Я ожидал бы, что полученный граф будет отключен или очень слабо связан; большие хорошо связанные подграфы будут быстро выпадать из-за нескольких сокращений.

Обратите внимание, что мы можем ограничиться рассмотрением только пар, поскольку функция сговора должна подчиняться (с точки зрения уровня доверия) Collude (A, B, C)

Создание этой глобальной функции сговора - это та часть, которая кажется сложной.

...