10

1,000 万人のプレイヤーがいるオンライン ポーカー サイトの共謀検出のアルゴリズムの複雑さを説明する最良の方法は何ですか?

仮定します（これらの仮定は大きな違いを生むとは思わないので、無視してかまいませんが、明確にするために）：

  • サイトの登録ユーザー数が 10,000,000 であること。
  • これらのプレイヤーが合計 50 億回のハンドをプレイしたこと。
  • 提供される唯一の情報は、サイトの「マスターハンド履歴データベース」であり、すべてのプレーヤーのホールカードと各ハンドの賭けアクションが含まれています.
  • 言い換えれば、IP アドレスを調べたり、異常なレーキ/利益パターンを探したりするなどの近道をすることはできません。
  • ちょうど N 人 (N は 2 から 10 の間) のプレーヤーのグループを渡すと、グループ内のすべてのプレーヤーが共謀した場合に TRUE を返す関数が与えられたと仮定します。すべてのプレイヤーではなく一部のプレイヤーが共謀者である場合、関数は FALSE を返します。TRUE の戻り値は、(たとえば) 75% の信頼度で作成されます。

あなたの仕事は、共謀したすべてのプレイヤーの完全なリストと、彼が共謀したプレイヤーの完全なリストを作成することです。最近、この問題が NP 困難であると説明されているのを耳にしましたが、これは正確ですか? 単に「難しい」ものを「NP」または「NP-hard」と呼ぶことがあります。

ありがとう！

4

4 に答える 4

4

私がすぐに目にする力ずくのアプローチは次のとおりです。

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);
    }
  }
}

2 より大きい引数カウントで haveColluded を呼び出す意味がわかりません。これは、偽陰性が発生する可能性があるためです。関数のコストがどれくらいかにもよると思いますが。しかし、上記の結果は、haveColluded (n はプレーヤーの数) への O(n^2) 呼び出しになります。関数自体は O(m) のように見えます。ここで、m は一緒にプレイしたゲームの数です。したがって、このアルゴリズムはO(n^3) を十分に下回っているように見えます。NP 困難であるためには、「H にチューリング還元可能な多項式時間である NP 完全問題 L が存在する場合にのみ、問題 H が NP 困難であることを証明する必要があります [...] 言い換えれば、L はHのオラクルを備えたオラクルマシンによって多項式時間で解決されます。」( http://en.wikipedia.org/wiki/NP-hard）。私は NP 完全問題 (例: 3-SAT、巡回セールスマン問題など) を研究しましたが、それをどのように証明するのかわかりません。しかし、やはり、クリークの問題と疑わしいほど似ているようです。

于 2009-04-26T11:49:32.150 に答える
3

NP 困難なクリーク検出のように見えます。一方、クリークのサイズはここ (10) に制限されているため、ブルート フォースは最悪でも n^10 です。

編集:ここでの重要な問題は、共謀関数のプロパティが何であるかです。2 人の小さなセット (たとえば 5 人) のプレーヤーで関数を呼び出すことによって、共謀している 10 人のプレーヤーを常に検出できますか?

于 2009-04-27T07:23:54.557 に答える
1

あなたのモデルの下で、あなたが説明することはかなり簡単でなければなりません。暗黙のグラフが表示されます（頂点はプレーヤーであり、エッジは一緒にゲームをプレイしたことに対応します）。そのグラフのサブグラフが必要です。

共謀関数が完全に信頼できる場合は、グラフ内の頂点のすべてのペアでそれを呼び出すだけで、サブグラフが得られます。

そのサブグラフはおそらくかなり切り離されています。結果のグラフは切断されているか、非常に弱く接続されていると思います。大きく接続されたサブグラフは、いくつかの最小カットを実行することですぐに削除されます。

共謀関数は（信頼水準の観点から）Collude（A、B、C）<Collude（A、B）に従う必要があるため、ペアのみを表示するように制限できることに注意してください。

このグローバルコリュージョン関数の構築は難しいと思われる部分です。

于 2009-05-02T02:25:30.613 に答える
1

これを 2 つのステップに分けます。

  1. 50 億以上のポーカー ハンドを反復して、各ハンドのプレイを調べます。それぞれのアルゴリズムをアルゴリズム Aと呼びましょう。頂点がプレーヤーを表し、重み付けされた無向エッジが 2 人のプレーヤー間の共謀の信頼度を表す共謀グラフを作成します。プレーヤー X がプレーヤー Y と共謀しているという疑いでアルゴリズム Aがトリガーされると、共謀グラフの加重エッジ XY に何らかの値が追加されます。プレイされたハンドが進行するにつれて、エッジの重みが時間の経過とともに蓄積されます。あるしきい値に達すると、エッジは X と Y の間の共謀を表します。

  2. 次に、N 個のプレーヤーの頂点のリストがすべて共謀したかどうかを判断する関数は、N 個の頂点を含むサブグラフが完全に接続されていることを確認することです (つまり、すべてのノードが、サブグラフ内の他のすべてのノードに対する結託のしきい値よりも大きなエッジの重みを持っていることを意味します)。 ）。IIRC、これを O(n*lg(n) ) と判断します。

于 2010-01-07T01:23:33.263 に答える