4

ブリッジのゲームは、4 人のプレイヤーにランダムに配布される 52 枚の異なるトランプでプレイされ、各プレイヤーは最終的に 13 枚のカードを持ちます。いわゆる「ディール」です。おおよそ2^96以下のブリッジでお値引き可能です。このドキュメントでは、ランダム取引を生成するプログラムの要件を次のように説明しています。

  1. ソフトウェアは、可能なすべてのブリッジ取引を生成できる必要があります。これは、手動取引でも可能であるためです。
  2. ソフトウェアは、ボード番号、前のハンド、またはその他の状況に影響されることなく、同じ確率ですべての取引を生成する必要があります。
  3. セッションで他のすべての取引を見た後でさえ、取引を予測することは不可能であるべきです。

このドキュメントでは、疑似乱数シーケンスの最初の要素を確認することで、使用されるシードを計算できるようになり、ハッカーがその後の取引を予測できるようになるため、疑似乱数ジェネレーターを使用して取引を生成することはできないと述べています。

さらに、ほとんどの疑似乱数ジェネレーターは 32 ビットのシードを使用するため、これらのジェネレーターは、必要な 2^96 ではなく、せいぜい 2^32 の異なるブリッジ ディールを生成できることになり、いわゆる誕生日のパラドックスに従って、 2^32 取引の平方根の後に同じ取引が行われる可能性があります。

ブリッジ ディール生成アプリケーションの要件を説明するドキュメントの著者は、ランダム ディールを生成するために世界中で使用されているプログラムを作成しました。このプログラムは、人間がキーボードでランダムに入力することを使用して 96 ビット シードを生成します。14 年間、このアプローチに欠陥はありませんでした。

必要なシードを生成するために人間の入力を使用する必要がないルーチンを書きたいと思います。

が来るRNGCryptoServiceProvider。以下のコードを使用してこれを使用し、最初は 1 から 52 の範囲で、次に 1 から 51 の範囲で、1 枚のカードが残るまで乱数を生成しました。

得られたディールのテスト 私は、このコードが同じ確率で可能なあらゆるディールを生み出すことができ、4 人のプレーヤーの 1 人となるカードの確率が 0.25 に等しいことを確信しています。

しかし、RNGCryptoServiceProvider で使用されるシードの強度が不明なため、次のことを考えています。

  1. このコードは、2^96 の異なる取引を生成することができるか、適応することができます。
  2. このコードの次の取引は予測できません。

EDIT この質問で前述した乱数を取得する方法には欠陥がありました。これは、このコードが 2^96 の異なる Bridge 取引を生成できるかどうかという主な質問から気をそらします。乱数ジェネレーターを、Stephen Taub と Shawn Farkas が MSDN マガジンで公開したものに置き換えました。

この Web サイトから取得した、1 ～ 52、1 ～ 51、最大 1 ～ 2 の範囲の暗号的に安全な乱数を生成するために使用されるコード

     /// <summary>
/// Returns a random number within a specified range.
/// </summary>
/// <returns>
/// A 32-bit signed integer greater than or equal to <paramref name="minValue"/> and less than <paramref name="maxValue"/>; that is, the range of return values includes <paramref name="minValue"/> but not <paramref name="maxValue"/>. If <paramref name="minValue"/> equals <paramref name="maxValue"/>, <paramref name="minValue"/> is returned.
/// </returns>
/// <param name="minValue">The inclusive lower bound of the random number returned.</param>
/// <param name="maxValue">The exclusive upper bound of the random number returned. <paramref name="maxValue"/> must be greater than or equal to <paramref name="minValue"/>.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="minValue"/> is greater than <paramref name="maxValue"/>.</exception>
public override Int32 Next(Int32 minValue, Int32 maxValue)
{
    if (minValue > maxValue) throw new ArgumentOutOfRangeException("minValue");
    if (minValue == maxValue) return minValue;
    Int64 diff = maxValue - minValue;

    while (true)
    {
        //The cryptoProvider is of type RNGCryptoServiceProvider.
        cryptoProvider.GetBytes(uint32Buffer); //The uint32Buffer has a size of 4 bytes.
        UInt32 rand = BitConverter.ToUInt32(uint32Buffer, 0);

        Int64 max = (1 + (Int64)UInt32.MaxValue);
        Int64 remainder = max % diff;
        if (rand < max - remainder)
        {
            return (Int32)(minValue + (rand % diff));
        }
    }
}
4

1 に答える 1

5

「真に均一な」乱数ジェネレーター (RNG) を取得したら、次の手順を実行します。

  1. 外部ソースに基づくシードで RNG を初期化します。これは、キーボード入力、プログラムの開始時間、またはその他の多くのものである可能性があります。私の調査によると、RNGCryptoServiceProvider は既にこの部分を行っているようです。

  2. 最も重要なことは、(頻繁に) 間隔を置いて、RNG から数値を引き出すことです。番号を捨てるだけです。重要な部分は、RNG を「循環」させたことです。必要に応じて、間隔をランダムにして予測不可能性を高めることができます。より多くのサイクルがより良いので、私はあなたが行くことができると感じる限り低い最大間隔を選びます.

    • ランダム間隔には 2 つの選択肢があります。(a) より弱い RNG を使用する (実際に使用しています)、(b) それを無視します。スロット マシンでは、ユーザーの入力 (「SPIN」を押す) により、実際の RNG ドローが発生します。十分に速いサイクリング間隔と組み合わせると、十分に予測不可能と見なされます.

  3. (いくらかオプション) すべての数字を連続して描かないでください。次の数字 (または一連の数字) を描画する前に、ランダムな時間待機します (RNG がランダムな回数循環できるようにします)。最初の描画はユーザー入力に基づいている可能性が高いため、それらを一度にすべて描画することができるはずです。それはしかし、傷つけることはできません。

これは、予測不可能な RNG が厳しく規制されている (そしてもちろん必要とされている) ゲーム (ギャンブル) 業界で使用されるプロセスです。(100 の別々のデッキからの) 500 枚のカードを含むドローは、この方法を使用して行われます。通常、使用される RNG は 32 ビット シードを使用し、完全に許容されることに注意してください。

于 2014-09-06T00:37:50.557 に答える