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.Random
ist 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?
java
random
permutation
random-seed
java.util.random
Serj Ardovic
quelle
quelle
Random
sind 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).Antworten:
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.Random
irrelevant 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
0
und52!-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:[1] Nicht zu verwechseln mit Lehrer . :) :)
quelle
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.shuffle
zweimal aufrufen , einRandom
mit 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
SecureRandom
Klasse, die mit einembyte[]
Array von praktisch unbegrenzter Größe initialisiert werden kann. Sie können dann eine Instanz von übergebenSecureRandom
,Collections.shuffle
um die Aufgabe abzuschließen:quelle
SecureRandom
Implementierung 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 dieSecureRandom
Implementierung 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.)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.Random
implementiert 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.SecureRandom
die Übergabe von Seeds unbegrenzter Länge möglich ist, könnte dieSecureRandom
Implementierung 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 ").quelle
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
Random
nur 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.Random
nicht fantastisch ist. Wenn Sie ein Kartenspiel schreiben, verwenden Sie möglicherweise dieMessageDigest
API, 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 spielencurrentTimeMillis
. Wenn Ihre Benutzer sind wirklich Glücksspiel, dann verwendenSecureRandom
ohne Samen.quelle
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.
quelle
Kurze Lösung, die im Wesentlichen der von dasblinkenlight entspricht:
Sie müssen sich keine Sorgen um den internen Zustand machen. Lange Erklärung warum:
Wenn Sie eine
SecureRandom
Instanz 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
SecureRandom
hat einen Zähler, der verfolgt , wie viele Bits verwendet wurden (getBytes()
,getLong()
etc.) und füllt dieSecureRandom
mit Entropie - Bits , wenn notwendig .Kurzum: Vergessen Sie einfach Einwände und verwenden Sie sie
SecureRandom
als echten Zufallszahlengenerator.quelle
Wenn Sie die Zahl nur als Array von Bits (oder Bytes) betrachten, können Sie möglicherweise
Random.nextBytes
die in dieser Frage zum Stapelüberlauf vorgeschlagenen (sicheren) Lösungen verwenden und das Array dann einem zuordnennew BigInteger(byte[])
.quelle
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:
quelle