Java.util.Random est-il vraiment si aléatoire? Comment puis-je en générer 52! (factorielles) séquences possibles?

J'ai utilisé Random (java.util.Random)pour mélanger un jeu de 52 cartes. Il y en a 52! (8.0658175e + 67) possibilités. Pourtant, j'ai découvert que la graine de java.util.Randomest un long, qui est beaucoup plus petit à 2 ^ 64 (1.8446744e + 19).

À partir d'ici, je me demande si java.util.Random c'est vraiment si aléatoire ; est-il réellement capable de générer 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?

La sélection d'une permutation aléatoire nécessite simultanément plus et moins de caractère aléatoire que ce que votre question implique. Laisse-moi expliquer.

La mauvaise nouvelle: il faut plus de hasard.

Le défaut fondamental de votre approche est qu'elle essaie de choisir entre ~ ²²²⁶ possibilités en utilisant 64 bits d'entropie (la graine aléatoire). Pour choisir équitablement entre ~ ²²²⁶ possibilités, vous devrez 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 OS , services en ligne . Il y a déjà une supposition implicite dans votre question que vous pouvez en quelque sorte générer 64 bits, alors faites simplement ce que vous alliez faire, seulement quatre fois, et donnez les bits excédentaires à une œuvre caritative. :)

La bonne nouvelle: il faut moins de hasard.

Une fois que vous disposez de ces 226 bits aléatoires, le reste peut être effectué de manière déterministe et les propriétés de java.util.Randompeuvent donc être rendues non pertinentes . Voici comment.

Disons que nous générons les 52! permutations (supporter avec moi) et les trier lexicographiquement.

Pour choisir l'une des permutations, tout ce dont nous avons besoin est un seul entier aléatoire entre 0et 52!-1. Cet entier est notre 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 assuré que toutes les permutations peuvent être choisies, elles seront choisies de manière équiprobable (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 temps O (n ² ) en utilisant le code de Lehmer ^[1] (voir également les permutations de numérotation et le système de numérotation factoriadique ). Le n ici est la taille de votre deck, soit 52.

Il y a une implémentation C dans cette réponse StackOverflow . Il existe plusieurs variables entières qui débordent 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: l'ensemencement d'un générateur de nombres pseudo-aléatoires avec n'importe quelle graine spécifique doit produire la même séquence après un mélange, limitant le nombre de permutations que vous pourriez obtenir à 2 ⁶⁴ . Cette assertion est facile à vérifier expérimentalement en appelant Collection.shuffledeux fois, en passant un Randomobjet initialisé avec la même graine et en observant que les deux shuffles aléatoires sont identiques.

Une solution à cela consiste alors à utiliser un générateur de nombres aléatoires qui permet une plus grande graine. Java fournit une SecureRandomclasse qui pourrait être initialisée avec un byte[]tableau de taille pratiquement illimitée. Vous pouvez ensuite passer une instance de SecureRandomà Collections.shufflepour 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.Randomimplémente un algorithme avec un module de 2 ⁴⁸ ; ainsi, sa longueur d'état n'est que de 48 bits, bien moins que les 226 bits dont j'ai parlé. Vous devrez utiliser un autre PRNG avec une plus grande longueur d'état - en particulier, un avec une période de 52 factorielle ou plus.

Voir aussi "Shuffling" dans mon article sur les générateurs de nombres aléatoires .

Cette considération est indépendante de la nature du PRNG; elle s'applique également aux PRNG cryptographiques et non cryptographiques (bien sûr, les PRNG non cryptographiques sont inappropriés lorsque la sécurité de l'information est impliquée).

Bien que des java.security.SecureRandomgraines de longueur illimitée puissent être transmises, la SecureRandommise en œuvre pourrait utiliser un PRNG sous-jacent (par exemple, "SHA1PRNG" ou "DRBG"). Et cela dépend de la période de ce PRNG (et dans une moindre mesure, de la 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 »).

Je m'excuse à l'avance, car c'est un peu difficile à comprendre ...

Tout d'abord, vous savez déjà que ce java.util.Randomn'est pas complètement aléatoire. Il génère des séquences d'une manière parfaitement prévisible à partir de la graine. Vous avez tout à fait raison, puisque la graine ne fait que 64 bits de long, elle ne peut générer que 2 ^ 64 séquences différentes. Si vous deviez en quelque sorte générer 64 vrais bits aléatoires et les utiliser pour sélectionner une graine, vous ne pourriez pas utiliser cette graine pour choisir aléatoirement entre tous les 52! séquences possibles avec une probabilité égale.

Cependant, ce fait est sans conséquence tant 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 "visiblement spécial" dans 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 ayez deux façons de l'initialiser - une façon l'initialiserait en utilisant la graine entière, et une façon hacherait la graine jusqu'à 64 bits avant de l'initialiser.

Si vous ne saviez pas quel initialiseur était lequel, pourriez-vous écrire une sorte de test pour les distinguer? À moins que vous n'ayez (pas) eu la chance de finir par initialiser le mauvais avec le même 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 d'une faiblesse de l'implémentation PRNG spécifique.

Sinon, imaginez que le Random classe 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 n'était qu'un index dans ce tableau.

Le fait de Randomn'utiliser que 64 bits pour sa graine n'est donc pas nécessairement un problème statistiquement, tant qu'il n'y a aucune 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 pour utiliser deux fois la même graine est calculable.

ÉDITER:

Je dois ajouter que, même si tout ce qui précède est correct, la mise en œuvre réelle de java.util.Randomn'est pas géniale. Si vous écrivez un jeu de cartes, utilisez peut-être l' MessageDigestAPI pour générer le hachage SHA-256 "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 soucier du currentTimeMillisretour. Si vos utilisateurs jouent vraiment, utilisez-le SecureRandomsans graine.

Je vais adopter un point de vue différent à ce sujet. Vous avez raison sur vos hypothèses - votre PRNG ne pourra pas toucher les 52! possibilités.

La question est: quelle est l'échelle de votre jeu de cartes?

Si vous créez un jeu simple de style klondike? Alors vous n'avez certainement pas besoin des 52! possibilités. Au lieu de cela, regardez-le comme ceci: un joueur aura 18 quintillions de jeux distincts. Même en tenant compte du `` problème d'anniversaire '', ils devraient jouer des milliards de mains avant de se lancer dans le premier jeu en double.

Si vous faites une simulation de monte-carlo? Alors tu vas probablement bien. 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 espace de graine faible (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 départ pourrait être une rupture.

Si vous faites un jeu de cartes multijoueur, surtout s'il y a de l'argent en jeu? Ensuite, vous devrez faire des recherches sur la façon dont les sites de poker en ligne ont traité le même problème que vous posez. Parce que bien que le problème d'espace de graine faible ne soit pas perceptible par le joueur moyen, il est exploitable s'il vaut l'investissement en temps. (Les sites de poker sont tous passés par 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, don ne trouvez pas 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 celle de 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 SecureRandominstance de cette façon, elle accède à un véritable générateur de nombres aléatoires spécifique au système d'exploitation. Il s'agit soit d'un pool d'entropie où sont accédées des valeurs qui contiennent des bits aléatoires (par exemple, pour un temporisateur de nanosecondes, la précision en nanosecondes est essentiellement aléatoire) ou d'un générateur de nombre de matériel interne.

Cette entrée (!) Qui peut encore contenir des traces parasites est introduite 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 numéros eux-mêmes! Le SecureRandompossède un compteur qui trace le nombre de bits utilisés ( getBytes(), getLong()etc.) et remplit le SecureRandomavec des bits d'entropie si nécessaire .

En bref: oubliez simplement les objections et utilisez-le SecureRandomcomme véritable générateur de nombres aléatoires.

Si vous considérez le nombre comme juste un tableau de bits (ou octets), vous pouvez peut-être utiliser les Random.nextBytessolutions (sécurisées) suggérées dans cette question de dépassement de pile , 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 répartis entre 0 et 2 ²⁵⁶ - 1, alors nous avons suffisamment d'entropie pour la tâche.

Pour obtenir une permutation de la sortie de SHA256 (lorsqu'elle est exprimée sous forme d'entier), il suffit de la réduire modulo 52, 51, 50 ... comme dans ce pseudocode:

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]