logic - 論理/確率の質問：バッグからのピッキング

Question

可能なピースのバッグがあるボードゲームをコーディングしています。毎ターン、プレイヤーは特定のルールに従ってランダムに選択されたピースをバッグから取り出します。

私の実装では、最初にバッグを1人以上のプレーヤーのプールに分割する方が簡単な場合があります。これらのプールはランダムに選択されますが、今ではさまざまなプレイヤーがさまざまなバッグから選んでいます。これは違いますか？

1人のプレイヤーのバッグがなくなると、一般的な備蓄からさらに多くのプレイヤーがランダムにシャッフルされます。

Answer 1

限り：

• 「プール」バッグへのパーティションはランダムです
• 特定のプールバッグへのプレーヤーの割り当てはランダムです
• ゲームは、プレイヤーによって描かれたアイテムがバッグから効果的に取り除かれるようなものです（現在のゲームの期間中、バッグまたは他のバッグに戻されることはありません）
• プレイヤーはバッグの内容を認識していません

2つのアプローチ（1つの大きな共通バッグを使用する「オリジナル」、プレーヤーごとに1つのプールバッグを使用する「変更」）は、確率に関して同等です。

一部のプレイヤーのバッグが空になると、ゲームの終わりに向かって少しトリッキーになります。まだプレイ中のアイテムの100％から選ぶのが最も公平なので、どちらのバッグから選ぶか、[もちろん]そのバッグから1つのアイテムを選ぶ必要があります。

この問題は、確率が状況について持っている知識の量に関連しているという、確率の興味深い特性を示しています。たとえば、ゲームのホストは、プレーヤーXに割り当てられた「プール」バッグに文字「A」（スクラブルについて考える）が含まれていないことをよく知っているかもしれませんが、プレーヤーの誰もこれを知らない限り（そしてプールバッグへのパーティションは完全にランダムでした）、ゲームは公平なままであり、プレーヤー「X」は、次に文字が描かれたときにおそらく「A」を打つ可能性が、残りのすべての文字と同じであると想定する必要があります。彼/彼女に利用可能でした。

編集：
両方の手順が完全に同等であるという主張の数学的妥当性にもかかわらず、知覚はチャンス要素を含むゲームの重要な要素です（特にゲームに金銭的要素も含まれている場合）。この公平性を理解していないプレイヤーの怒りを避けるために、元の手順に固執することができます...

Answer 2

ゲームのルールにもよりますが、@ mjvは正しいですが、最初のランダムな除算は確率に影響しません。これは、n人のプレイヤーが裏向きのデッキから順番にカードを引くゲームに似ています。デッキの最初のシャッフルは、各プレイヤーのカードの「バッグ」へのランダムな分割です。

ただし、抽選のたびにアイテムを交換する場合は、バッグが1つであるか多数であるかは重要です。1つのバッグで、特定のアイテムは最終的に同じ確率ですべてのプレイヤーによって描かれます。多くのバッグがある場合、そのアイテムは、最初にバッグを入れたプレーヤーだけが描くことができます。

ソフトウェアレベルにポップアップし、ゲームで1つのバッグが必要な場合は、そのようにプログラミングすることをお勧めします。n個のバッグよりも難しくはなく、新しいゲームが年。

Answer 3

私の直感では、物事のランダムなコレクションをより小さなランダムなサブセットに分割しても、同様にランダムなままであることがわかります...プレーヤーが大きなプールから選択するか小さなプールから選択するかは問題ではありません (つまり、自分自身を大きなプールにフィードします)。

ゲームの場合、ランダムな私見で十分です！

Answer 4

セキュリティがどれほど重要かにもよりますが、大丈夫かもしれません（お金が関係している場合（あなたまたは彼ら）はそうしないでください）。無知なプレーヤーの観点からすると、ランダム性が低くなるかどうかは完全にはわかりません.

a) 彼らが無知であることを当てにしないでください。あなたのプログラムがクラックされて、彼らはどの部分が登場するかを知るでしょう。

b) 脆弱性を持ち込まないようにバッグを埋めるのは非常に難しいでしょう。たとえば、ランダムに 1 つを選択して最初のバケットに入れ、それを取り出し、2 番目のバケットに対して同じことを行うという単純なアルゴリズムを考えてみましょう。N個のピース​​がある場合、最初のプレーヤーが特定のピースを選ぶ確率は1/N、2番目のプレーヤーは1/(N-1)、3番目のプレーヤーは1/(N-3)、すぐ。プレーヤーは、他のプレーヤーが特定のピースを保持している可能性を把握するために、既にプレイされたピースを分析できます。

次のアルゴリズムの方がうまくいくと思いますが、ほとんどの人は、新しいアルゴリズムを初めて思いついたときに確率を間違えます。これを使用しないでください。私が話したセキュリティの脆弱性をカバーする可能性があることを理解してください。

1. N 個の注文アイテムのリストを作成し、P 人のプレーヤーをインスタンス化する
2. プレイヤーごとにアイテムの 1/P をランダムに (置き換えて) マークします。
3. N 個のアイテムがすべてマークされ、各プレイヤーが同じ数のアイテムがマークされるまで、これを繰り返します (注: N と P によっては、生きているよりもはるかに長くかかる場合があります)。
4. 適切なアイテムをプレイヤーのバケツに置き、ランダムに並べ替えます (場所交換アルゴリズムは使用しないでください)。

それでも、エクスプロイトからバケツに何が入っているかを誰かが把握する脆弱性が残っている可能性があります. 組み合わせプールに固執します。本当にランダムに選択するのはまだ難しいですが、それはあなたの人生を楽にします.

編集：トーンがぎこちなく聞こえることは知っています。これを文脈から外して読んで、これらのアルゴリズムのいくつかを試す可能性のある人々のために、私はほとんどすべての太字を含めました. 私は本当にあなたがうまくいくことを願っています:-)

編集2：さらに検討すると、順番に選ぶことの問題は、最初にプレイヤーが交代することに帰着する可能性があると思います. それがすでにルールに含まれている場合、それは問題ではないかもしれません。