Ist java.util.Random wirklich so zufällig? Wie kann ich 52 generieren! (faktorielle) mögliche Sequenzen?

202

Ich habe Random (java.util.Random)ein Kartenspiel mit 52 Karten gemischt. Es gibt 52! (8.0658175e + 67) Möglichkeiten. Ich habe jedoch herausgefunden, dass der Keim für a java.util.Randomist long, der mit 2 ^ 64 (1.8446744e + 19) viel kleiner ist.

Von hier aus bin ich misstrauisch, ob java.util.Random das wirklich so zufällig ist ; ist es tatsächlich in der Lage, alle 52 zu erzeugen! Möglichkeiten?

Wenn nicht, wie kann ich zuverlässig eine bessere Zufallssequenz erzeugen, die alle 52 erzeugen kann! Möglichkeiten?

Serj Ardovic
quelle
21
"Wie kann ich sicher eine echte Zufallszahl über 52 erzeugen !" Die Zahlen von Randomsind niemals echte Zufallszahlen. Es ist ein PRNG, wobei P für "Pseudo" steht. Für echte Zufallszahlen benötigen Sie eine Zufallsquelle (z. B. random.org).
TJ Crowder
7
@ JimGarrison Das ist nicht das, wonach OP sucht. Er spricht über 10 ^ 68 mögliche Sequenzen. Da jede Pseudozufallssequenz durch ihren Startwert identifiziert wird, sagt OP, dass es höchstens 2 ^ 64 verschiedene Sequenzen geben könnte.
Dasblinkenlight
6
Ich denke, es ist eine interessante Frage und es lohnt sich darüber nachzudenken. Aber ich kann nicht anders, als mich über Ihren Problemkontext zu wundern: Was genau dazu führt, dass alle 52 generiert werden müssen! Permutationen? Zum Beispiel können wir in der realen Brücke das Deck mischen und jeweils eine Karte austeilen, es gibt jedoch nur ~ 6e11 verschiedene Hände, da viele verschiedene Permutationen zu derselben Hand führen. Wenn Sie in die andere Richtung denken, benötigen Sie eine Lösung speziell für 52! Oder eine Lösung, die sich beispielsweise auf zwei Decks verallgemeinert (104! / (2 ** 52) Möglichkeiten oder ~ 2e150)?
NPE
9
@NPE - Nehmen Sie zum Beispiel Solitaire (Klondike), 52! ist genau die Anzahl der möglichen Hände ..
Serj Ardovic
3
Ich denke , das ist eine interessante Lektüre: superuser.com/a/712583
Dennis_E

Antworten:

153

Die Auswahl einer zufälligen Permutation erfordert gleichzeitig mehr und weniger Zufälligkeit als Ihre Frage impliziert. Lassen Sie mich erklären.

Die schlechte Nachricht: brauche mehr Zufälligkeit.

Der grundlegende Fehler in Ihrem Ansatz besteht darin, dass versucht wird, mit 64 Bit Entropie (dem zufälligen Keim) zwischen ~ 2 226 Möglichkeiten zu wählen . Um fair zwischen ~ 2 226 Möglichkeiten zu wählen , müssen Sie einen Weg finden, 226 Entropiebits anstelle von 64 zu erzeugen.

Es gibt verschiedene Möglichkeiten, zufällige Bits zu generieren: dedizierte Hardware , CPU-Anweisungen , Betriebssystemschnittstellen , Onlinedienste . Es gibt bereits eine implizite Annahme in Ihrer Frage, dass Sie irgendwie 64 Bit generieren können. Tun Sie also nur vier Mal, was Sie tun wollten, und spenden Sie die überschüssigen Bits für wohltätige Zwecke. :) :)

Die gute Nachricht: brauche weniger Zufälligkeit.

Sobald Sie diese 226 zufälligen Bits haben, kann der Rest deterministisch erledigt werden, sodass die Eigenschaften von java.util.Randomirrelevant werden können . Hier ist, wie.

Nehmen wir an, wir generieren alle 52! Permutationen (tragen Sie mit mir) und sortieren Sie sie lexikographisch.

Um eine der Permutationen auszuwählen, benötigen wir lediglich eine einzelne zufällige Ganzzahl zwischen 0und 52!-1. Diese ganze Zahl ist unsere 226 Entropiebits. Wir werden es als Index für unsere sortierte Liste von Permutationen verwenden. Wenn der Zufallsindex gleichmäßig verteilt ist, ist nicht nur garantiert, dass alle Permutationen ausgewählt werden können, sondern sie werden auch gleich wahrscheinlich ausgewählt (was eine stärkere Garantie ist als das, was die Frage stellt).

Jetzt müssen Sie nicht mehr alle diese Permutationen generieren. Sie können eine direkt erstellen, wenn Sie die zufällig ausgewählte Position in unserer hypothetischen sortierten Liste angeben. Dies kann in O (n 2 ) -Zeit mit dem Lehmer [1] -Code erfolgen (siehe auch Nummerierungspermutationen und faktoriadisches Zahlensystem ). Das n hier ist die Größe Ihres Decks, dh 52.

Diese StackOverflow-Antwort enthält eine C-Implementierung . Es gibt dort mehrere ganzzahlige Variablen, die für n = 52 überlaufen würden, aber zum Glück können Sie sie in Java verwenden java.math.BigInteger. Der Rest der Berechnungen kann fast so wie sie sind transkribiert werden:

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

[1] Nicht zu verwechseln mit Lehrer . :) :)

NPE
quelle
7
Heh, und ich war mir sicher, dass der Link am Ende New Math sein würde . :-)
TJ Crowder
5
@TJCrowder: Es war fast! Es waren die unendlich differenzierbaren Riemannschen Mannigfaltigkeiten, die es schwangen. :-)
NPE
2
Gut zu sehen, dass die Leute die Klassiker schätzen. :-)
TJ Crowder
3
Woher bekommen Sie die zufälligen 226 Bits in Java ? Entschuldigung, Ihr Code beantwortet das nicht.
Thorsten S.
5
Ich verstehe nicht, was Sie meinen, Java Random () liefert auch keine 64-Bit-Entropie. Das OP impliziert eine nicht spezifizierte Quelle, die 64 Bit erzeugen kann, um das PRNG zu setzen. Es ist sinnvoll anzunehmen, dass Sie dieselbe Quelle nach 226 Bit fragen können.
Hör auf, Monica
60

Ihre Analyse ist korrekt: Das Seeding eines Pseudozufallszahlengenerators mit einem bestimmten Seed muss nach einem Shuffle dieselbe Sequenz ergeben, wodurch die Anzahl der Permutationen, die Sie erhalten können, auf 2 64 begrenzt wird . Diese Behauptung lässt sich leicht experimentell überprüfen, indem Sie Collection.shufflezweimal aufrufen , ein Randommit demselben Startwert initialisiertes Objekt übergeben und feststellen, dass die beiden zufälligen Mischvorgänge identisch sind.

Eine Lösung hierfür ist die Verwendung eines Zufallszahlengenerators, der einen größeren Startwert ermöglicht. Java bietet eine SecureRandomKlasse, die mit einem byte[]Array von praktisch unbegrenzter Größe initialisiert werden kann. Sie können dann eine Instanz von übergeben SecureRandom, Collections.shuffleum die Aufgabe abzuschließen:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);
dasblinkenlight
quelle
8
Sicherlich ist ein großer Samen keine Garantie dafür, dass alle 52! Möglichkeiten entstehen würden (worum geht es in dieser Frage speziell)? Betrachten Sie als Gedankenexperiment ein pathologisches PRNG, das einen beliebig großen Keim nimmt und eine unendlich lange Reihe von Nullen erzeugt. Es scheint ziemlich klar zu sein, dass das PRNG mehr Anforderungen erfüllen muss, als nur ein ausreichend großes Saatgut zu nehmen.
NPE
2
@SerjArdovic Ja, jedes an ein SecureRandom-Objekt übergebene Seed-Material muss gemäß der Java-Dokumentation unvorhersehbar sein.
Dasblinkenlight
10
@NPE Sie haben Recht, obwohl ein zu kleiner Samen eine Garantie für die Obergrenze ist, ist ein ausreichend großer Samen keine Garantie für die Untergrenze. Dies alles ist das Entfernen einer theoretischen Obergrenze, die es dem RNG ermöglicht, alle 52 zu generieren! Kombinationen.
Dasblinkenlight
5
@SerjArdovic Die kleinste Anzahl von Bytes, die dafür benötigt wird, ist 29 (Sie benötigen 226 Bits, um 52 mögliche Bitkombinationen darzustellen, was 28,25 Bytes entspricht, also müssen wir es aufrunden). Beachten Sie, dass durch die Verwendung von 29 Byte Seed-Material die theoretische Obergrenze für die Anzahl der möglichen Shuffles aufgehoben wird, ohne die Untergrenze festzulegen (siehe NPEs Kommentar zu einem beschissenen RNG, das einen sehr großen Seed nimmt und eine Folge aller Nullen erzeugt).
Dasblinkenlight
8
Die SecureRandomImplementierung wird mit ziemlicher Sicherheit ein zugrunde liegendes PRNG verwenden. Und es hängt von der Periode dieses PRNG (und in geringerem Maße von der Zustandslänge) ab, ob es in der Lage ist, aus 52 faktoriellen Permutationen zu wählen. (Beachten Sie, dass in der Dokumentation angegeben ist, dass die SecureRandomImplementierung bestimmten statistischen Tests "nur minimal entspricht" und Ausgaben generiert, die "kryptografisch stark sein müssen", jedoch keine explizite Untergrenze für die Zustandslänge oder den Zeitraum des zugrunde liegenden PRNG festlegen.)
Peter O.
26

Im Allgemeinen kann ein Pseudozufallszahlengenerator (PRNG) nicht aus allen Permutationen einer Liste mit 52 Elementen auswählen, wenn seine Zustandslänge weniger als 226 Bit beträgt.

java.util.Randomimplementiert einen Algorithmus mit einem Modul von 2 48 ; Somit beträgt seine Zustandslänge nur 48 Bit, also viel weniger als die 226 Bits, auf die ich mich bezog. Sie müssen ein anderes PRNG mit einer größeren Zustandslänge verwenden - insbesondere eines mit einer Periode von 52 Fakultäten oder mehr.

Siehe auch "Mischen" in meinem Artikel über Zufallszahlengeneratoren .

Diese Überlegung ist unabhängig von der Art des PRNG; Dies gilt gleichermaßen für kryptografische und nicht verschlüsselte PRNGs (natürlich sind nicht verschlüsselte PRNGs unangemessen, wenn es um Informationssicherheit geht).


Obwohl java.security.SecureRandomdie Übergabe von Seeds unbegrenzter Länge möglich ist, könnte die SecureRandomImplementierung ein zugrunde liegendes PRNG verwenden (z. B. "SHA1PRNG" oder "DRBG"). Und es hängt von der Periode dieses PRNG (und in geringerem Maße von der Zustandslänge) ab, ob es in der Lage ist, aus 52 faktoriellen Permutationen zu wählen. (Beachten Sie, dass ich "Zustandslänge" als die "maximale Größe des Seeds definiere, die ein PRNG verwenden kann, um seinen Zustand zu initialisieren, ohne diesen Seed zu verkürzen oder zu komprimieren ").

Peter O.
quelle
18

Lassen Sie mich im Voraus entschuldigen, denn das ist etwas schwer zu verstehen ...

Zunächst einmal wissen Sie das bereits java.util.Random nicht völlig zufällig ist. Es erzeugt Sequenzen auf perfekt vorhersehbare Weise aus dem Samen. Sie haben völlig Recht, dass der Startwert, da er nur 64 Bit lang ist, nur 2 ^ 64 verschiedene Sequenzen erzeugen kann. Wenn Sie irgendwie 64 echte Zufallsbits generieren und damit einen Startwert auswählen würden, könnten Sie diesen Startwert nicht verwenden, um zufällig zwischen allen 52 zu wählen ! mögliche Sequenzen mit gleicher Wahrscheinlichkeit.

Diese Tatsache ist jedoch ohne Bedeutung , solange Sie nicht mehr als 2 ^ 64 Sequenzen generieren, solange die 2 ^ 64 Sequenzen, die sie generieren können , nichts "Besonderes" oder "merklich Besonderes" enthalten .

Nehmen wir an, Sie hatten ein viel besseres PRNG, das 1000-Bit-Samen verwendete. Stellen Sie sich vor, Sie hätten zwei Möglichkeiten, es zu initialisieren: Eine Möglichkeit würde es mit dem gesamten Seed initialisieren und eine Möglichkeit würde den Seed vor der Initialisierung auf 64 Bit reduzieren.

Wenn Sie nicht wüssten, welcher Initialisierer welcher ist, können Sie einen Test schreiben, um sie zu unterscheiden? Es sei denn, Sie hatten das (Un-) Glück, den schlechten mit demselben zu initialisieren 64 Bit zweimal zu , lautet die Antwort nein. Sie konnten nicht zwischen den beiden Initialisierern unterscheiden, ohne detaillierte Kenntnisse über einige Schwachstellen in der spezifischen PRNG-Implementierung zu haben.

Alternativ stellen Sie sich vor, dass die Random Klasse ein Array von 2 ^ 64 Sequenzen hatte, die zu einem bestimmten Zeitpunkt in der fernen Vergangenheit vollständig und zufällig ausgewählt wurden, und dass der Startwert nur ein Index in diesem Array war.

Die Tatsache, dass Randomnur 64 Bit für den Startwert verwendet werden, ist also nicht der Fall statistisch gesehen unbedingt ein Problem, solange keine signifikante Wahrscheinlichkeit besteht, dass Sie denselben Startwert zweimal verwenden.

Für kryptografische Zwecke reicht ein 64-Bit-Startwert natürlich nicht aus, da es rechnerisch möglich ist, ein System dazu zu bringen, denselben Startwert zweimal zu verwenden.

BEARBEITEN:

Ich sollte hinzufügen, dass, obwohl alle oben genannten Punkte korrekt sind, die tatsächliche Implementierung von java.util.Randomnicht fantastisch ist. Wenn Sie ein Kartenspiel schreiben, verwenden Sie möglicherweise die MessageDigestAPI, um den SHA-256-Hash von zu generieren "MyGameName"+System.currentTimeMillis(), und verwenden Sie diese Bits, um das Deck zu mischen. Mit dem obigen Argument müssen Sie sich keine Sorgen machen, solange Ihre Benutzer nicht wirklich spielen currentTimeMillis. Wenn Ihre Benutzer sind wirklich Glücksspiel, dann verwenden SecureRandomohne Samen.

Matt Timmermans
quelle
6
@ThorstenS, wie könnten Sie irgendeine Art von Test schreiben, der feststellen könnte, dass es Kartenkombinationen gibt, die niemals auftauchen können?
Matt Timmermans
2
Es gibt mehrere Zufallszahlen-Testsuiten wie Diehard von George Marsaglia oder TestU01 von Pierre L'Ecuyer / Richard Simard, die statistische Anomalien in der Zufallsausgabe leicht finden. Für die Kartenprüfung können Sie zwei Quadrate verwenden. Sie bestimmen die Kartenreihenfolge. Das erste Quadrat zeigt die Position der ersten beiden Karten als xy-Paar: Die erste Karte als x und die Differenz (!) Position (-26-25) der zweiten Karte als y. Das zweite Quadrat zeigt die 3. und 4. Karte mit (-25-25) relativ zum 2./3. Dies zeigt sofort Lücken und Cluster in Ihrer Distribution an, wenn Sie sie eine Zeit lang ausführen.
Thorsten S.
4
Nun, das ist nicht der Test, von dem Sie sagten, Sie könnten schreiben, aber er trifft auch nicht zu. Warum nehmen Sie an, dass es Lücken und Cluster in der Verteilung gibt, die solche Tests aufdecken würden? Dies würde, wie bereits erwähnt, eine "spezifische Schwäche in der PRNG-Implementierung" bedeuten und hat überhaupt nichts mit der Anzahl möglicher Samen zu tun. Für solche Tests müssen Sie den Generator nicht einmal neu säen. Ich habe am Anfang gewarnt, dass dies schwer zu verstehen ist.
Matt Timmermans
3
@ThorstenS. Diese Testsuiten bestimmen absolut nicht , ob es sich bei Ihrer Quelle um ein kryptografisch sicheres 64-Bit-Seed-PRNG oder ein echtes RNG handelt. (Das Testen von PRNGs ist schließlich das Ziel dieser Suiten.) Selbst wenn Sie den verwendeten Algorithmus kennen, macht es ein gutes PRNG unmöglich, den Zustand ohne eine Brute-Force-Suche im Zustandsraum zu bestimmen.
Sneftel
1
@ThorstenS.: In einem echten Kartenspiel wird die überwiegende Mehrheit der Kombinationen niemals auftauchen. Sie wissen einfach nicht, welche das sind. Für ein halbwegs anständiges PRNG ist es dasselbe - wenn Sie testen können, ob eine bestimmte so lange Ausgabesequenz in ihrem Bild enthalten ist, ist dies ein Fehler im PRNG. Lächerlich großer Staat / Periode wie 52! wird nicht gebraucht; 128-Bit sollte ausreichen.
R .. GitHub STOP HELPING ICE
10

Ich werde das etwas anders angehen. Sie haben Recht mit Ihren Annahmen - Ihr PRNG wird nicht in der Lage sein, alle 52 zu treffen! Möglichkeiten.

Die Frage ist: Wie groß ist Ihr Kartenspiel?

Wenn Sie ein einfaches Spiel im Klondike-Stil machen? Dann brauchen Sie definitiv nicht alle 52! Möglichkeiten. Betrachten Sie es stattdessen so: Ein Spieler hat 18 Billionen verschiedene Spiele. Selbst wenn sie das "Geburtstagsproblem" berücksichtigen würden, müssten sie Milliarden von Händen spielen, bevor sie auf das erste doppelte Spiel stoßen würden.

Wenn Sie eine Monte-Carlo-Simulation durchführen? Dann bist du wahrscheinlich okay. Möglicherweise müssen Sie sich mit Artefakten aufgrund des 'P' in PRNG befassen, aber Sie werden wahrscheinlich nicht einfach aufgrund eines geringen Startraums auf Probleme stoßen (auch hier sehen Sie sich Billionen einzigartiger Möglichkeiten an.) Kehrseite: Wenn Sie mit einer großen Anzahl von Iterationen arbeiten, ist Ihr geringer Startplatz möglicherweise ein Deal-Breaker.

Wenn Sie ein Multiplayer-Kartenspiel machen, besonders wenn Geld auf dem Spiel steht? Dann müssen Sie ein bisschen googeln, wie die Online-Pokerseiten mit dem gleichen Problem umgegangen sind, nach dem Sie gefragt haben. Denn während das Problem des geringen Startplatzes für den durchschnittlichen Spieler nicht auffällt , ist es ausnutzbar, wenn sich die Zeitinvestition lohnt. (Die Pokerseiten haben alle eine Phase durchlaufen, in der ihre PRNGs "gehackt" wurden, sodass jemand die Hole Cards aller anderen Spieler sehen konnte, indem er einfach den Samen von den exponierten Karten ableitete.) Wenn dies die Situation ist, in der Sie sich befinden, ziehen Sie an ‚t einfach eine bessere PRNG finden - Sie müssen es so ernst wie ein Crypto Problem zu behandeln.

Kevin
quelle
9

Kurze Lösung, die im Wesentlichen der von dasblinkenlight entspricht:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

Sie müssen sich keine Sorgen um den internen Zustand machen. Lange Erklärung warum:

Wenn Sie eine SecureRandomInstanz auf diese Weise erstellen , greift sie auf einen betriebssystemspezifischen Generator für echte Zufallszahlen zu. Dies ist entweder ein Entropiepool, in dem auf Werte zugegriffen wird, die zufällige Bits enthalten (z. B. für einen Nanosekunden-Timer ist die Nanosekundengenauigkeit im Wesentlichen zufällig), oder ein interner Hardware-Zahlengenerator.

Diese Eingabe (!), Die möglicherweise noch falsche Spuren enthält, wird in einen kryptografisch starken Hash eingespeist, der diese Spuren entfernt. Aus diesem Grund werden diese CSPRNGs verwendet, nicht um diese Nummern selbst zu erstellen! Das SecureRandomhat einen Zähler, der verfolgt , wie viele Bits verwendet wurden ( getBytes(), getLong()etc.) und füllt die SecureRandommit Entropie - Bits , wenn notwendig .

Kurzum: Vergessen Sie einfach Einwände und verwenden Sie sie SecureRandomals echten Zufallszahlengenerator.

Thorsten S.
quelle
4

Wenn Sie die Zahl nur als Array von Bits (oder Bytes) betrachten, können Sie möglicherweise Random.nextBytesdie in dieser Frage zum Stapelüberlauf vorgeschlagenen (sicheren) Lösungen verwenden und das Array dann einem zuordnen new BigInteger(byte[]).

IvanK
quelle
3

Ein sehr einfacher Algorithmus besteht darin, SHA-256 auf eine Folge von Ganzzahlen anzuwenden, die von 0 aufwärts inkrementiert werden. (Ein Salz kann angehängt werden, wenn dies gewünscht wird, um "eine andere Sequenz zu erhalten".) Wenn wir annehmen, dass die Ausgabe von SHA-256 "so gut wie" gleichmäßig verteilte ganze Zahlen zwischen 0 und 2 256 - 1 ist, haben wir genug Entropie für die Aufgabe.

Um eine Permutation von der Ausgabe von SHA256 zu erhalten (ausgedrückt als Ganzzahl), muss sie einfach modulo 52, 51, 50 ... wie in diesem Pseudocode reduziert werden:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]
Artelius
quelle