単純なシャッフルに関する現実世界の問題

Question

私は、ポーカー関連のトピックを通じてプログラミングの概念を初心者に教えることを目的とした記事を多数書いています。現在、シャッフルをテーマに取り組んでいます。

として Jeff Atwood氏がCodingHorror.comで指摘, 1 つの単純なシャッフル方法 (配列を反復処理し、各カードを配列内の他の場所にあるランダムなカードと交換する) では、順列の不均一な分布が作成されます。実際のアプリケーションでは、 クヌース・フィッシャー＝イェーツのシャッフル より均一なランダム性を実現します。しかし、私は、コード作成者にとってあまりフレンドリーではないアルゴリズムを使用して、プログラミングの概念の説明を行き詰まらせたくないのです。

これは次のような疑問につながります。あなたが 52 枚のカード デッキの単純なシャッフルを使用していることをブラックハットが知ったら、どれほどの利点があるでしょうか?限りなく小さくなりそうです。

Answer 1

実際のオンライン ギャンブル サイトで使用されるポーカー プログラムを作成しているわけではありません。人にプログラムの仕方を教える場合、誰かがプログラムで不正行為をする能力は大したことではありません。

これは現実世界の貧弱なモデルであるというメモを残して（セキュリティ上の欠陥の可能性があると言及されています）、そのまま教えを続けてください。

Answer 2

knuth shuffle は、naive shuffle と比べて重要な変更はありません。デッキ全体のどこかではなく、デッキの残りの（シャッフルされていない）セクションにある任意のカードと交換するだけです。選ばれなかった残りのカードから順番に次のカードを繰り返し選ぶと考えると、これもかなり直感的です。

個人的には、適切なアルゴリズムがそれほど複雑ではない (そして視覚化しやすい!) のに、貧弱なアルゴリズムを生徒に教えるのは悪いアプローチだと思います。

Answer 3

この利点は非常に重要であることがわかります。 この記事をチェックしてください

問題の一部はアルゴリズムの欠陥にありますが、もう 1 つはコンピュータから「乱数」を取得できるという前提にあります。

Answer 4

シャッフルのシンプルで公平なアルゴリズムは、デッキ内の各カードにランダムな浮動小数点数 (たとえば、0 から 1 の間) を割り当て、割り当てられた番号でデッキを並べ替えることです。

これは実際、何かが直感的であるからといって、この場合は単純なシャッフルであるからといって、それが正しいとは限らないことを生徒が理解するのに最適な例です。

Answer 5

主観的。

限りなく小さくなりそうです。

同意する。

Answer 6

余談ですが、こんなことがありました。 ITtoolbox のブログ投稿 シャッフルをシミュレートする場合に興味深いかもしれないシャッフルについて。

あなたの質問については、52 あると考えてください。ジェフの 3 カードデッキの例のように、物事がどこに着地するかに役割を果たす可能性のあるデッキ構成から始めることができますが、過剰に表示されている 1 が各スロットに 1 回ずつ出現することに注意してください。また、どこに利点があるかが明らかになるまでに数千の例が必要だと言っていることにも注目してください。しかし、あるデッキの場合、まったく同じ最初のデッキで再び始める可能性は低いですよね。配られたカードを一番下に置いてシャッフルするのですが、これは繰り返される可能性は低いと思います。