Est java.util.Aléatoire vraiment aléatoire? Comment puis-je générer 52! séquences possibles (factorielles)?
J'ai utilisé Random (java.util.Random) pour mélanger un jeu de 52 cartes. Il y en a 52! (8.0658175 e+67) possibilités. Pourtant, j'ai découvert que la graine de java.util.Random est un long, qui est beaucoup plus petit à 2^64 (1.8446744 e+19).
D'ici, je me méfie si java.util.Random est-ce vraiment aléatoire ; est-il réellement capable de générer tous les 52! possibilités?
Sinon, comment puis-je générer de manière fiable une meilleure séquence aléatoire qui peut produire tous les 52! possibilités?
8 answers
Sélectionner une permutation aléatoire nécessite simultanément plus et moins de hasard que ce que votre question implique. Laissez-moi vous expliquer.
Les mauvaises nouvelles: besoin de plus de hasard.
Le défaut fondamental de votre approche est qu'elle essaie de choisir entre ~2226 possibilités en utilisant 64 bits d'entropie (la graine aléatoire). Pour choisir équitablement entre ~2226 possibilités vous allez devoir trouver un moyen de générer 226 bits d'entropie au lieu de 64.
Il existe plusieurs façons de générer des bits aléatoires: matériel dédié, Instructions CPU, Interfaces du système d'exploitation, services en ligne . Il y a déjà une hypothèse implicite dans votre question que vous pouvez en quelque sorte générer 64 bits, alors faites tout ce que vous alliez faire, seulement quatre fois, et donnez les bits excédentaires à la charité. :)
La bonne nouvelle: besoin de moins aléatoire.
Une fois que vous avez ces 226 bits aléatoires, le reste peut être fait de manière déterministe et ainsi les propriétés de java.util.Random peuvent être rendues non pertinentes. Voici comment.
Disons que nous générons tous les 52! permutations (ours avec moi) et les trier lexicographiquement.
Pour choisir l'une des permutations, il suffit d'un seul entier aléatoire entre 0 et 52!-1. Cet entier est nos 226 bits d'entropie. Nous l'utiliserons comme index dans notre liste triée de permutations. Si l'index aléatoire est uniformément distribué, non seulement vous êtes garanti que toutes les permutations puissent être choisies, elles seront choisies équiprobablement (ce qui est une garantie plus forte que ce que la question pose).
Maintenant, vous n'avez pas réellement besoin de générer toutes ces permutations. Vous pouvez en produire un directement, étant donné sa position choisie au hasard dans notre liste triée hypothétique. Cela peut être fait en O (n2) temps en utilisant le Lehmer[1] code (voir aussi permutations de numérotation et nombre factoriadique système). Le n ici est la taille de votre deck, c'est à dire 52.
Il y a une implémentation C dans cette réponse StackOverflow. Il existe plusieurs variables entières qui déborderaient pour n=52, mais heureusement en Java, vous pouvez utiliser java.math.BigInteger. Le reste des calculs peut être transcrit presque tel quel:
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] à ne Pas confondre avec Lehrer. :)
Votre analyse est correcte: ensemencer un générateur de nombres pseudo-aléatoires avec une graine spécifique doit donner la même séquence après un shuffle, limitant le nombre de permutations que vous pourriez obtenir à 264. Cette assertion est facile à vérifier expérimentalement en appelant Collection.shuffle deux fois, en passant un Random objet initialisé avec la même graine, et en observant que les deux shuffles aléatoires sont identiques.
Une solution à cela consiste donc à utiliser un générateur de nombres aléatoires qui permet une graine plus grande. Java fournit SecureRandom classe qui pourrait être initialisée avec byte[] tableau de taille pratiquement illimitée. Vous pouvez ensuite passer une instance de SecureRandom à Collections.shuffle pour terminer la tâche:
byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);
En général, un générateur de nombres pseudo-aléatoires (PRNG) ne peut pas choisir parmi toutes les permutations d'une liste de 52 éléments si sa longueur d'état est inférieure à 226 bits.
java.util.Random implémente un algorithme avec un module de 248; ainsi, sa longueur d'état n'est que de 48 bits, bien moins que les 226 bits auxquels j'ai fait référence. Vous devrez utiliser un autre PRNG avec une longueur d'état plus grande - en particulier, un avec une période de 52 factorielles ou plus.
Voir aussi " Choisir parmi tous Permutations" dans mon article sur les générateurs de nombres aléatoires.
Cette considération est indépendante de la nature du GNR; elle s'applique également aux GNR cryptographiques et non chiffrés (bien sûr, les GNR non chiffrés ne sont pas appropriés lorsque la sécurité de l'information est impliquée).
Bien que java.security.SecureRandom permette de transmettre des graines de longueur illimitée, l'implémentation SecureRandom pourrait utiliser un PRNG sous-jacent (par exemple, "SHA1PRNG" ou "DRBG"). Et cela dépend de ce PRNG période (et dans une moindre mesure, longueur de l'état) s'il est capable de choisir parmi 52 permutations factorielles. (Notez que Je définis la "longueur d'état" comme la "taille maximale de la graine qu'un PRNG peut prendre pour initialiser son état sans raccourcir ou compresser cette graine").
Permettez-moi de m'excuser à l'avance, car c'est un peu difficile à comprendre...
Tout d'Abord, vous savez déjà que java.util.Random n'est pas complètement aléatoire à tous. Il génère des séquences parfaitement prévisible à partir de la graine. Vous avez tout à fait raison de dire que, puisque la graine ne mesure que 64 bits, elle ne peut générer que 2^64 séquences différentes. Si vous deviez en quelque sorte générer 64 bits aléatoires réels et les utiliser pour sélectionner une graine, vous ne pourriez pas utiliser cette graine pour choisir aléatoirement entre tous les des 52! séquences possibles avec une probabilité égale.
Cependant, ce fait est sans conséquencetant que vous n'allez pas réellement générer plus de 2^64 séquences, tant qu'il n'y a rien de "spécial" ou de "sensiblement spécial" sur les 2^64 séquences qu'il peut générer.
Disons que vous aviez un bien meilleur PRNG qui utilisait des graines de 1000 bits. Imaginez que vous aviez deux façons de l'initialiser-une façon de l'initialiser en utilisant la graine entière, et une façon de hacher la graine à 64 bits avant de l'initialiser.
Si vous ne saviez pas quel initialiseur était lequel, pourriez-vous écrire n'importe quel type de test pour les distinguer? À moins que vous n'ayez (pas) la chance de finir par initialiser le mauvais avec le same 64 bits deux fois, alors la réponse est non. Vous ne pouviez pas faire la distinction entre les deux initialiseurs sans une connaissance détaillée de certaines faiblesses dans l'implémentation spécifique de PRNG.
Alternativement, imaginez que la classe Random avait un tableau de 2^64 séquences qui ont été sélectionnées complètement et au hasard à un moment donné dans un passé lointain, et que la graine était juste un index dans ce tableau.
Donc le fait que Random n'utilise que 64 bits pour sa graine est en fait pas nécessairement un problème statistiquement, tant qu'il n'y a pas de chance significative que vous utilisiez la même graine deux fois.
Bien sûr, à des fins cryptographiques, une graine 64 bits n'est tout simplement pas suffisante, car obtenir un système permettant d'utiliser deux fois la même graine est réalisable sur le plan informatique.
MODIFIER:
Je devrais ajouter que, même si tout ce qui précède est correct, que l'implémentation réelle de java.util.Random n'est pas géniale. Si vous écrivez un jeu de cartes, utilisez peut-être l'API MessageDigest pour générer le hachage SHA-256 de "MyGameName"+System.currentTimeMillis(), et utilisez ces bits pour mélanger le jeu. Par l'argument ci-dessus, tant que vos utilisateurs ne jouent pas vraiment, vous n'avez pas à vous inquiéter que currentTimeMillis retourne un long. Si vos utilisateurs sont vraiment jeux d'argent, puis utiliser SecureRandom sans graine.
Je vais prendre un peu d'un point de vue différent à ce sujet. Vous avez raison sur vos hypothèses-votre PRNG ne va pas être en mesure de frapper tous les 52! possibilité.
La question est: quelle est l'échelle de votre jeu de cartes?
Si vous faites un simple jeu de style klondike? Alors vous n'avez certainement pasbesoin de tous les 52! possibilité. Au lieu de cela, regardez-le comme ceci: un joueur aura 18 quintillion distincts jeux. Même en tenant compte du "problème d'anniversaire", ils auraient à jouer des milliards de mains avant de courir dans le premier jeu en double.
Si vous faites une simulation monte-carlo?, Alors vous êtes probablement ok. Vous devrez peut-être faire face à des artefacts en raison du " P " dans PRNG, mais vous n'allez probablement pas rencontrer de problèmes simplement en raison d'un faible espace de graines (encore une fois, vous regardez des quintillions de possibilités uniques.) D'un autre côté, si vous travaillez avec un grand nombre d'itérations, alors, oui, votre faible espace de graine peut-être un deal-breaker.
Si vous faites un jeu de cartes multijoueur, en particulier s'il y a de l'argent en jeu? Ensuite, vous allez avoir besoin de faire quelques recherches sur la façon dont les sites de poker en ligne ont traité le même problème que vous demandez. Parce que bien que le problème du faible espace de graines ne soit pas perceptible pour le joueur moyen, il est exploitable si cela en vaut la peine. (Les sites de poker ont tous traversé une phase où leurs PRNG ont été "piratés", laissant quelqu'un voir les cartes fermées de tous les autres joueurs, simplement en déduisant la graine des cartes exposées.) Si c'est la situation dans laquelle vous vous trouvez, ne trouvez simplement un meilleur PRNG - vous devrez le traiter aussi sérieusement qu'un problème de Crypto.
Solution courte qui est essentiellement la même que dasblinkenlight:
// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();
Collections.shuffle(deck, random);
Vous n'avez pas à vous soucier de l'état interne. Longue explication pourquoi:
Lorsque vous créez une instance SecureRandom de cette façon, elle accède à un système d'exploitation spécifique
vrai générateur de nombres aléatoires. C'est un pool d'entropie, où les valeurs sont
accessible qui contiennent des bits aléatoires (par exemple, pour une minuterie nanoseconde la nanoseconde
la précision est essentiellement aléatoire) ou un nombre de matériel interne générateur.
Cette entrée (!) qui peuvent encore contenir des traces parasites sont introduits dans un
hachage cryptographiquement fort qui supprime ces traces. C'est la raison pour laquelle ces CSPRNG sont utilisés, pas pour créer ces chiffres eux-mêmes! Le SecureRandom a un compteur qui trace le nombre de bits utilisés (getBytes(), getLong() etc.) et remplit le SecureRandom avec des bits d'entropie si nécessaire.
En bref: Oubliez simplement les objections et utilisez SecureRandom comme véritable générateur de nombres aléatoires.
Si vous considérez le nombre comme un tableau de bits (ou d'octets), vous pourriez peut-être utiliser les solutions (sécurisées)Random.nextBytessuggérées dans cette question Stack Overflow, puis mapper le tableau dans un new BigInteger(byte[]).
Un algorithme très simple consiste à appliquer SHA-256 à une séquence d'entiers incrémentant de 0 vers le haut. (Un sel peut être ajouté si vous le souhaitez pour "obtenir une séquence différente".) Si nous supposons que la sortie de SHA-256 est" aussi bonne que " des entiers uniformément distribués entre 0 et 2256 - 1 ensuite, nous avons assez d'entropie pour la tâche.
Pour obtenir une permutation à partir de la sortie de SHA256 (lorsqu'elle est exprimée en entier), il suffit de la réduire modulo 52, 51, 50... comme dans cette pseudo:
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]