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

Question

J'ai été en utilisant Random (java.util.Random) de mélanger un jeu de 52 cartes. Il y a 52! (8.0658175 e+67) possibilités. Pourtant, j'ai trouvé que la graine de la java.util.Random est long, qui est de beaucoup inférieur à 2^64 (1.8446744 e+19).

À partir d'ici, je me méfie si java.util.Random est vraiment aléatoire; est-il réellement capable de générer tous les 52! possibilités?

Si non, comment puis-je générer de manière fiable une meilleure séquence aléatoire qui peut produire tous les 52! possibilités?

Answer 1

La sélection d'une permutation aléatoire nécessite aussi de plus en plus et moins aléatoire que ce que votre question implique. Laissez-moi vous expliquer.

La mauvaise nouvelle: besoin de plus de hasard.

La faille fondamentale dans votre approche est qu'il essaye de choisir entre ~2²²⁶ possibilités à l'aide de 64 bits d'entropie (aléatoire). Assez choisir entre ~2²²⁶ possibilités que vous allez avoir à 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 du PROCESSEUR, OS des interfaces, des 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, donc il suffit de faire ce que vous alliez faire, seulement quatre fois, et de donner de l'excès de bits à la charité. :)

La bonne nouvelle: besoin de moins aléatoire.

Une fois que vous avez ceux 226 bits aléatoires, le reste peut être fait de façon déterministe et donc les propriétés de l' java.util.Random peut être fait hors de propos. Voici comment.

Disons que nous générons tous les 52! permutations (ours avec moi) et les trier de manière lexicographique.

Pour choisir l'une des permutations tous nous avons besoin est un simple entier aléatoire compris entre 0 et 52!-1. Cet entier est notre 226 bits d'entropie. Nous allons l'utiliser comme un index dans notre liste triée des permutations. Si le hasard de l'indice est distribuée de manière uniforme, non seulement sont vous garanti que toutes les permutations peuvent être choisis, ils seront choisis equiprobably (qui est un renforcement de la garantie que ce qui est demandé).

Maintenant, vous n'avez pas réellement besoin de générer toutes ces permutations. Vous pouvez produire directement un, compte tenu de sa choisies au hasard position dans notre hypothétique liste triée. Cela peut être fait en O(n²) de temps à l'aide de la Lehmer^[1] code (voir également la numérotation des permutations et factoriadic numéro de système). Le n ici est la taille de votre deck, c'est à dire 52.

Il y a un C mise en œuvre dans ce StackOverflow réponse. Il y a plusieurs variables de type entier là que serait débordement pour n=52, mais heureusement, en Java, vous pouvez utiliser java.math.BigInteger. Le reste des calculs peut être transcrit presque-est:

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. :)

Answer 2

Votre analyse est correcte: le semis d'un générateur de nombres pseudo aléatoires avec des semences doit donner le même séquence après un shuffle, limiter le nombre de permutations que l'on pourrait obtenir à 2⁶⁴. Cette affirmation est facile à vérifier expérimentalement en appelant Collection.shuffle deux fois, le passage d'un Random objet initialisé avec la même semence, et en observant que les deux aléatoire shuffle sont identiques.

Une solution à ce, alors, est d'utiliser un générateur de nombre aléatoire qui permet un plus grand semences. Java fournit SecureRandom classe qui pourrait être initialisé avec byte[] tableau quasi-illimité de taille. Vous pouvez ensuite passer une instance de SecureRandom de Collections.shuffle pour terminer la tâche:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

Answer 3

En général, un générateur de nombres pseudo-aléatoires (PRNG) ne peut pas choisir parmi toutes les permutations de 52 de l'élément de liste si son état longueur est inférieure 226 bits.

java.util.Random implémente un algorithme avec un module de 2⁴⁸; ainsi, son état longueur n'est que de 48 bits, donc beaucoup moins que le 226 bits que j'ai évoqué. Vous aurez besoin d'utiliser un autre GÉNÉRATEUR avec un plus grand état longueur — plus précisément, l'un avec une période de 52 factorielle ou plus.

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

Cette considération est indépendante de la nature du GÉNÉRATEUR; il s'applique également à la cryptographie et de noncryptographic PRNGs (bien sûr, noncryptographic PRNGs sont inappropriées à chaque fois que la sécurité de l'information est impliqué).

---

Bien qu' java.security.SecureRandom permet de graines de longueur illimitée à être passé de, de la SecureRandom mise en œuvre pourrait utiliser un sous-jacente PRNG (par exemple, "SHA1PRNG" ou "DRBG"). Et il dépend du GÉNÉRATEUR de période (et dans une moindre mesure, de l'état de la longueur), qu'il est capable de choisir parmi 52 factorielle des permutations. (Notez que je définir "l'état longueur" "maximum de la taille de la graine d'un PRNG pouvez prendre pour initialiser son état sans raccourcissement ou la compression de la graine").

Answer 4

Permettez-moi de m'excuser à l'avance, parce que c'est un peu difficile à comprendre...

Tout d'abord, vous savez déjà qu' 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 totalement raison que, depuis la semence est seulement 64 bits, il ne peut que générer des 2^64 séquences différentes. Si vous étiez en quelque sorte à générer 64 réel de bits aléatoires et les utiliser pour sélectionner une graine, vous ne pourriez pas utiliser que des semences de choisir au hasard entre tous les 52! séquences possibles avec la même probabilité.

Toutefois, ce fait est sans conséquence, tant que vous n'êtes en fait pas va générer plus de 2^64 séquences, tant qu'il n'y a rien de "spécial" ou "nettement spécial" sur la 2^64 séquences qu'il peut générer.

Disons que vous avez eu une bien meilleure PRNG que utilisés 1000 bits graines. Imaginez que vous avez deux façons d'initialiser -- l'une de l'initialiser à l'aide de la graine entière, et l'une de hachage de la graine vers le bas à 64 bits avant de l'initialiser.

Si vous ne savez pas qui l'initialiseur était qui, pourriez-vous écrire toute sorte de test pour les distinguer? Sauf si vous avez été (de l'onu)la chance pour la fin de l'initialisation du mal avec la même 64 bits deux fois, alors la réponse est non. Vous ne pouvait pas distinguer entre les deux initialiseurs sans une connaissance détaillée de certaines faiblesses dans le PRNG mise en œuvre.

Sinon, imaginez que l' Random classe un tableau de 2^64 séquences qui ont été sélectionnés sont complètement aléatoires et à un certain moment dans le passé lointain, et que la semence a été juste un indice dans ce tableau.

Donc le fait qu' Random utilise uniquement 64 bits pour sa graine est en fait pas nécessairement un problème statistiquement, tant qu'il n'y a pas grande chance que vous allez utiliser les mêmes graines deux fois.

Bien sûr, pour cryptographique , un 64 bits de semences est tout simplement pas suffisant, car l'obtention d'un système à l'utilisation de la même semence deux fois calcul est possible.

EDIT:

Je dois ajouter que, même si tous les ci-dessus est correcte, que la mise en œuvre effective de l' java.util.Random n'est pas génial. Si vous écrivez une carte de jeu, peut-être utiliser l' MessageDigest API pour générer le hachage SHA-256 de "MyGameName"+System.currentTimeMillis(), et d'utiliser ces bits à battre les cartes. Par l'argument ci-dessus, aussi longtemps que vos utilisateurs ne sont pas vraiment des jeux de hasard, vous n'avez pas à vous inquiéter currentTimeMillis renvoie une longue. Si vos utilisateurs sont vraiment les jeux de hasard, puis utilisez SecureRandom avec pas de postérité.

Answer 5

Je vais prendre un peu d'un autre angle sur cette. Vous êtes à droite sur votre hypothèses - votre PRNG ne va pas être en mesure de frapper tous les 52! les possibilités.

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

Si vous êtes un simple klondike style de jeu? Alors vous avez certainement n'avez pas besoin de tous les 52! les possibilités. Au lieu de cela, regardez-le comme ceci: un joueur aura 18 quintillion différents jeux. Même en tenant compte de l'Anniversaire de Problème", qu'ils auraient à jouer à des milliards de mains avant qu'ils ne courrais dans la première double jeu.

Si vous réalisez une simulation monte-carlo? Alors vous êtes probablement d'accord. Vous pourriez avoir à traiter avec des artefacts dus à la 'P' dans PRNG, mais vous n'allez probablement pas à rencontrer des problèmes, simplement à cause d'un peu de graines de l'espace (encore une fois, vous êtes à la recherche à quintillions de possibilités uniques.) Sur le revers de la médaille, si vous travaillez avec un grand nombre d'itérations, alors, oui, votre peu de graines de l'espace peut être un deal-breaker.

Si vous faites un multijoueur jeu de cartes, en particulier si il ya de l'argent sur la ligne? Ensuite, vous allez avoir besoin de faire quelques recherches sur google sur la façon dont les sites de poker en ligne géré le même problème que vous vous posez sur. Parce que tout le peu de graines question de l'espace n'est pas perceptible pour le joueur moyen, il est exploitable si il vaut le temps de l'investissement. (Les sites de poker tous passés par une phase où leur PRNGs "piratage", permettre à quelqu'un de voir les cartes des autres joueurs, tout simplement par le retrait de la graine de cartes exposées.) Si c'est la situation où vous êtes, ne pas simplement de trouver un meilleur PRNG - vous aurez besoin de traiter avec autant de sérieux qu'un Crypto problème.