Czy java.util.Random naprawdę jest tak losowy? Jak mogę wygenerować 52! (silnie) możliwe sekwencje?

202

Użyłem, Random (java.util.Random)aby przetasować talię 52 kart. Jest 52! (8.0658175e + 67) możliwości. Jednak dowiedziałem się, że ziarno dla java.util.Randomjest o longwiele mniejsze przy 2 ^ 64 (1.8446744e + 19).

Stąd jestem podejrzliwy, czy java.util.Random to naprawdę tak losowe ; czy jest w stanie wygenerować wszystkie 52! możliwości?

Jeśli nie, jak mogę w sposób niezawodny wygenerować lepszą losową sekwencję, która może wygenerować wszystkie 52! możliwości?

Serj Ardovic
źródło
21
„jak mogę z pewnością wygenerować prawdziwą liczbę losową powyżej 52!” Liczby z Randomnigdy nie są prawdziwymi liczbami losowymi. Jest to PRNG, gdzie P oznacza „pseudo”. Dla prawdziwych liczb losowych potrzebujesz źródła losowości (takiego jak random.org).
TJ Crowder
7
@JimGarrison To nie jest po OP. Mówi o 10 ^ 68 możliwych sekwencjach. Ponieważ każda pseudolosowa sekwencja jest identyfikowana przez jej seed, OP mówi, że może istnieć najwyżej 2 ^ 64 różnych sekwencji.
dasblinkenlight
6
Myślę, że to interesujące pytanie i warto o tym pomyśleć. Ale nie mogę przestać zastanawiać się nad twoim kontekstem problemu: co dokładnie prowadzi do wymagania, aby móc wygenerować wszystkie 52! permutacje? Na przykład w prawdziwym moście możemy tasować talię i rozdawać jedną kartę na raz, ale jest tylko ~ 6e11 różnych rąk, ponieważ wiele różnych kombinacji daje tę samą rękę. Myśląc w drugą stronę, czy potrzebujesz rozwiązania specjalnie dla 52 !, czy potrzebujesz takiego, który uogólnia się, powiedzmy, na dwie talie razem (104! / (2 ** 52) możliwości lub ~ 2e150)?
NPE
9
@NPE - Weźmy na przykład Solitaire (Klondike), 52! jest dokładnie liczbą możliwych rąk.
Serj Ardovic
3
Myślę, że jest to interesująca lektura: superuser.com/a/712583
Dennis_E,

Odpowiedzi:

153

Wybór losowej permutacji wymaga jednocześnie coraz mniej losowości niż sugeruje to pytanie. Pozwól mi wyjaśnić.

Zła wiadomość: potrzeba więcej losowości.

Podstawową wadą twojego podejścia jest to, że stara się wybierać między ~ 2 226 możliwościami, używając 64 bitów entropii (losowego ziarna). Aby rzetelnie wybrać pomiędzy ~ 2226 możliwościami, będziesz musiał znaleźć sposób na wygenerowanie 226 bitów entropii zamiast 64.

Istnieje kilka sposobów generowania losowych bitów: dedykowany sprzęt , instrukcje procesora , interfejsy systemu operacyjnego , usługi online . W twoim pytaniu jest już domniemane założenie, że możesz w jakiś sposób wygenerować 64 bity, więc po prostu zrób to, co zamierzałeś zrobić, tylko cztery razy, i przekaż nadwyżki na cele charytatywne. :)

Dobra wiadomość: potrzeba mniej losowości.

Gdy masz już 226 losowych bitów, resztę można wykonać deterministycznie, a więc właściwości java.util.Randommożna uczynić nieistotnymi . Oto jak.

Powiedzmy, że wygenerowaliśmy wszystkie 52! permutacje (opatrzcie mnie) i posortuj je leksykograficznie.

Aby wybrać jedną z permutacji, potrzebujemy tylko jednej losowej liczby całkowitej między 0i 52!-1. Ta liczba całkowita to nasze 226 bitów entropii. Użyjemy go jako indeksu do naszej posortowanej listy permutacji. Jeśli indeks jest losowo rozmieszczone równomiernie, nie tylko pan zagwarantować, że wszystkie permutacje mogą być wybrane, zostaną one wybrane equiprobably (która jest silniejsza niż gwarancja pytanie jest pytaniem).

Teraz nie musisz generować wszystkich tych permutacji. Możesz go wytworzyć bezpośrednio, biorąc pod uwagę jego losowo wybraną pozycję z naszej hipotetycznej listy posortowanej. Można tego dokonać w czasie O (n 2 ) za pomocą kodu Lehmera [1] (patrz także permutacje numeracji i system liczbowy współczynnika ). N jest tutaj wielkością twojej talii, tj. 52.

Jest to implementacja C w tym StackOverflow odpowiedź . Istnieje kilka zmiennych całkowitych, które przepełniłyby się dla n = 52, ale na szczęście w Javie możesz użyć java.math.BigInteger. Resztę obliczeń można przepisać prawie tak, jak jest:

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] Nie mylić z Lehrerem . :)

NPE
źródło
7
Heh i byłem pewien, że link na końcu to Nowa Matematyka . :-)
TJ Crowder
5
@TJCrowder: Już prawie było! To nieskończenie zróżnicowane rozmaitości Riemanniana, które go zamachały. :-)
NPE
2
Dobrze widzieć ludzi doceniających klasykę. :-)
TJ Crowder
3
Skąd masz losowe 226 bitów w Javie ? Przepraszamy, twój kod nie odpowiada na to pytanie.
Thorsten S.,
5
Nie rozumiem, co masz na myśli, Java Random () również nie zapewni 64 bitów entropii. OP implikuje nieokreślone źródło, które może wygenerować 64 bity, aby zainicjować PRNG. Sensowne jest założenie, że możesz poprosić to samo źródło o 226 bitów.
Przestań krzywdzić Monikę
60

Twoja analiza jest poprawna: zaszczepienie generatora liczb pseudolosowych dowolnym konkretnym ziarnem po tasowaniu musi dać tę samą sekwencję, ograniczając liczbę możliwych permutacji do 2 64 . To twierdzenie jest łatwe do zweryfikowania eksperymentalnego poprzez Collection.shuffledwukrotne wywołanie , przekazanie Randomobiektu zainicjowanego tym samym ziarnem i zaobserwowanie, że dwa losowe losowania są identyczne.

Rozwiązaniem tego jest użycie generatora liczb losowych, który pozwala na większe ziarno. Java zapewnia SecureRandomklasę, którą można zainicjować za pomocą byte[]tablicy o praktycznie nieograniczonym rozmiarze. Następnie można przejść instancję SecureRandomaby Collections.shufflewykonać zadanie:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);
dasblinkenlight
źródło
8
Z pewnością duże ziarno nie gwarantuje, że wszystkie 52! powstałyby możliwości (o co konkretnie chodzi w tym pytaniu)? Jako eksperyment myślowy rozważ patologiczny PRNG, który pobiera dowolnie duże ziarno i generuje nieskończenie długą serię zer. Wydaje się całkiem jasne, że PRNG musi spełniać więcej wymagań niż tylko zebrać wystarczająco duże nasiona.
NPE
2
@SerjArdovic Tak, każdy materiał źródłowy przekazany do obiektu SecureRandom musi być nieprzewidywalny, zgodnie z dokumentacją Java.
dasblinkenlight
10
@NPE Masz rację, chociaż zbyt małe nasiona są gwarancją górnej granicy, wystarczająco duże nasiona nie są gwarantowane na dolnej granicy. Wszystko to polega na usunięciu teoretycznej górnej granicy, dzięki czemu RNG może wygenerować wszystkie 52! kombinacje.
dasblinkenlight
5
@SerjArdovic Najmniejsza wymagana liczba bajtów to 29 (potrzebujesz 226 bitów do przedstawienia 52! Możliwych kombinacji bitów, czyli 28,25 bajtów, więc musimy zaokrąglić w górę). Zauważ, że użycie 29 bajtów materiału źródłowego usuwa teoretyczny górny limit liczby tasowań, które można uzyskać, bez ustalania dolnego limitu (patrz komentarz NPE o gównianym RNG, który pobiera bardzo duże ziarno i generuje sekwencję wszystkich zer).
dasblinkenlight
8
SecureRandomRealizacja będzie niemal na pewno korzystać z podstawowych PRNG. I zależy od okresu tego PRNG (oraz, w mniejszym stopniu, długości stanu), czy jest on w stanie wybierać spośród 52 silnych permutacji. (Należy zauważyć, że dokumentacja mówi, że SecureRandomimplementacja „minimalnie spełnia” określone testy statystyczne i generuje wyniki, które „muszą być kryptograficznie silne”, ale nie nakłada wyraźnego dolnego limitu na długość stanu PRNG ani na jego okres.)
Peter O.
26

Ogólnie rzecz biorąc, generator liczb pseudolosowych (PRNG) nie może wybierać spośród wszystkich permutacji listy 52-elementowej, jeśli jego długość stanu jest mniejsza niż 226 bitów.

java.util.Randomimplementuje algorytm o module 2 48 ; dlatego jego długość stanu wynosi tylko 48 bitów, czyli o wiele mniej niż 226 bitów, o których mówiłem. Będziesz musiał użyć innego PRNG o większej długości stanu - szczególnie takiego z okresem 52 silni lub dłuższym.

Zobacz także „Tasowanie” w moim artykule na temat generatorów liczb losowych .

Ta uwaga jest niezależna od charakteru PRNG; dotyczy to w równym stopniu kryptograficznych, jak i niekryptograficznych programów PRNG (oczywiście niekryptograficzne programy PRNG są nieodpowiednie, gdy dotyczy to bezpieczeństwa informacji).


Chociaż java.security.SecureRandomzezwala na przekazywanie nasion o nieograniczonej długości, SecureRandomimplementacja może wykorzystywać bazowy PRNG (np. „SHA1PRNG” lub „DRBG”). I zależy od okresu tego PRNG (oraz, w mniejszym stopniu, długości stanu), czy jest on w stanie wybierać spośród 52 silnych permutacji. (Zauważ, że definiuję „długość stanu” jako „maksymalny rozmiar nasion, które PRNG może przyjąć, aby zainicjować swój stan bez skracania lub ściskania tego ziarna ”).

Peter O.
źródło
18

Przepraszam z góry, ponieważ jest to trochę trudne do zrozumienia ...

Po pierwsze, wiesz już, że java.util.Randomto wcale nie jest przypadkowe. Generuje sekwencje w całkowicie przewidywalny sposób z nasion. Masz całkowitą rację, ponieważ ponieważ ziarno ma tylko 64 bity, może wygenerować tylko 2 ^ 64 różnych sekwencji. Jeśli miałbyś w jakiś sposób wygenerować 64 prawdziwe losowe bity i użyć ich do wyboru ziarna, nie możesz użyć tego ziarna do losowego wyboru spośród wszystkich 52! możliwe sekwencje z jednakowym prawdopodobieństwem.

Jednak fakt ten nie ma znaczenia, o ile nie zamierzasz wygenerować więcej niż 2 ^ 64 sekwencji, o ile nie ma nic „specjalnego” ani „zauważalnie specjalnego” w sekwencjach 2 ^ 64, które może wygenerować .

Powiedzmy, że miałeś znacznie lepszy PRNG, który używał 1000-bitowych nasion. Wyobraź sobie, że masz dwa sposoby na zainicjowanie go - jeden sposób zainicjowałby go przy użyciu całego ziarna, a jeden sposób skróciłby ziarno do 64 bitów przed jego zainicjowaniem.

Jeśli nie wiesz, który inicjator jest który, to czy mógłbyś napisać test, aby je rozróżnić? Jeśli nie miałeś (aś) szczęścia na tyle, by skończyć inicjowanie złego z tymi samymi 64 bitami dwa razy, odpowiedź brzmi: nie. Nie można było rozróżnić dwóch inicjatorów bez szczegółowej wiedzy o słabościach w konkretnej implementacji PRNG.

Alternatywnie, wyobraź sobie, że Randomklasa miała tablicę 2 ^ 64 sekwencji, które zostały wybrane całkowicie i losowo w pewnym momencie w odległej przeszłości i że ziarno było tylko indeksem do tej tablicy.

Tak więc fakt, że Randomużywa tylko 64 bitów dla jego nasienie, jest rzeczywiście nie koniecznie problem statystycznie, tak długo jak nie ma znaczącej szansa, że będzie korzystać z tego samego materiału siewnego dwukrotnie.

Oczywiście do celów kryptograficznych 64-bitowe ziarno nie jest wystarczające, ponieważ dwukrotne użycie systemu do tego samego zarodka jest wykonalne obliczeniowo.

EDYTOWAĆ:

Powinienem dodać, że pomimo tego, że wszystkie powyższe informacje są poprawne, faktyczna implementacja java.util.Randomnie jest niesamowita. Jeśli piszesz grę karcianą, może użyj MessageDigestinterfejsu API do wygenerowania skrótu SHA-256 "MyGameName"+System.currentTimeMillis()i użyj tych bitów do przetasowania talii. Zgodnie z powyższym argumentem, tak długo, jak użytkownicy naprawdę nie uprawiają hazardu, nie musisz się martwić, że currentTimeMillispowróci on długo. Jeśli użytkownicy naprawdę hazardu, a następnie użyć SecureRandombez nasion.

Matt Timmermans
źródło
6
@ThorstenS, jak możesz napisać dowolny test, który mógłby ustalić, że istnieją kombinacje kart, które nigdy nie mogą się pojawić?
Matt Timmermans,
2
Istnieje kilka zestawów testów liczb losowych, takich jak Diehard z George Marsaglia lub TestU01 z Pierre L'Ecuyer / Richard Simard, które z łatwością znajdują anomalie statystyczne w losowym wyniku. Do sprawdzania kart możesz użyć dwóch kwadratów. Ty decydujesz o kolejności kart. Pierwszy kwadrat pokazuje pozycję pierwszych dwóch kart jako parę xy: pierwszą kartę jako x, a różnicę (!) (-26-25) drugiej karty jako y. Drugi kwadrat pokazuje trzecią i czwartą kartę z (-25-25) w stosunku do drugiej / trzeciej. Spowoduje to natychmiastowe wyświetlenie luk i klastrów w Twojej dystrybucji, jeśli uruchomisz ją na jakiś czas.
Thorsten S.,
4
Cóż, to nie jest test, o którym mówiłeś, że możesz napisać, ale również nie ma zastosowania. Dlaczego zakładasz, że w dystrybucji występują luki i klastry, które ujawnią takie testy? Oznaczałoby to „specyficzną słabość implementacji PRNG”, jak wspomniałem, i nie ma nic wspólnego z liczbą możliwych nasion. Takie testy nie wymagają nawet ponownego uruchomienia generatora. Na początku ostrzegałem, że trudno to zrozumieć.
Matt Timmermans,
3
@ThorstenS. Te pakiety testowe absolutnie nie określą, czy źródłem jest 64-bitowy, zabezpieczony kryptograficznie PRNG, czy prawdziwy RNG. (W końcu testowanie PRNG jest właśnie tym zestawem.) Nawet jeśli znasz algorytm, dobry PRNG uniemożliwia określenie stanu bez brutalnego przeszukiwania przestrzeni stanu.
Sneftel,
1
@ThorstenS .: W prawdziwej talii kart ogromna większość kombinacji nigdy się nie pojawi. Po prostu nie wiesz, które to są. W przypadku pół przyzwoitego PRNG jest tak samo - jeśli możesz przetestować, czy dana sekwencja wyjściowa jest tak długa, jak w PRNG, jest to wada w PRNG. Śmiesznie ogromny stan / okres jak 52! nie jest potrzebne; 128-bit powinno wystarczyć.
R .. GitHub ZATRZYMAJ LÓD
10

Zamierzam zająć się tym trochę inaczej. Masz rację - twoje PRNG nie będzie w stanie trafić wszystkich 52! możliwości.

Pytanie brzmi: jaka jest skala twojej gry karcianej?

Jeśli tworzysz prostą grę w stylu klondike? Zatem zdecydowanie nie potrzebujesz wszystkich 52! możliwości. Zamiast tego spójrz na to w ten sposób: gracz będzie miał 18 quintillion różnych gier. Nawet biorąc pod uwagę „problem urodzinowy”, musieliby rozegrać miliardy rozdań, zanim wpadną na pierwszą zduplikowaną grę.

Jeśli wykonujesz symulację Monte Carlo? Więc prawdopodobnie nic ci nie jest . Być może będziesz musiał poradzić sobie z artefaktami z powodu „P” w PRNG, ale prawdopodobnie nie będziesz mieć problemów po prostu z powodu niskiej przestrzeni początkowej (ponownie, patrzysz na kwintilliony wyjątkowych możliwości). z drugiej strony, jeśli pracujesz z dużą liczbą iteracji, to tak, twoja niska przestrzeń początkowa może być przełomowa.

Jeśli tworzysz grę karcianą dla wielu graczy, szczególnie jeśli na linii są pieniądze? Będziesz musiał trochę popracować nad tym, jak strony pokera online poradziły sobie z tym samym problemem, o który pytasz. Ponieważ chociaż problem niskiej przestrzeni początkowej nie jest zauważalny dla przeciętnego gracza, można ją wykorzystać, jeśli jest warta zainwestowania czasu. (The poker wszyscy przeszli przez fazę, gdzie ich PRNGs były „hacked”, pozwalając ktoś zobaczyć zakryte karty wszystkich innych graczy, po prostu przez dedukcję ziarno od odsłoniętych kart). Jeśli jest to sytuacja, że jesteś w, don „t po prostu znaleźć lepsze PRNG - trzeba traktować je jako poważnie jako problem Crypto.

Kevin
źródło
9

Krótkie rozwiązanie, które zasadniczo jest takie samo jak dasblinkenlight:

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

Collections.shuffle(deck, random);

Nie musisz się martwić o stan wewnętrzny. Długie wyjaśnienie, dlaczego:

Po utworzeniu SecureRandominstancji w ten sposób uzyskuje ona dostęp do generatora liczb losowych specyficznych dla systemu operacyjnego. Jest to albo pula entropii, do której uzyskuje się dostęp do wartości, które zawierają losowe bity (np. Dla timera nanosekundowego precyzja nanosekundowa jest zasadniczo losowa) lub wewnętrzny generator liczb sprzętowych.

Te dane wejściowe (!), Które mogą nadal zawierać fałszywe ślady, są wprowadzane do kryptograficznie silnego skrótu, który usuwa te ślady. Właśnie dlatego te CSPRNG są używane, a nie same w sobie! SecureRandomPosiada licznik, który śledzi liczbę bitów użyto ( getBytes(), getLong()itd.) I napełnia ponownie SecureRandomz entropii bitów, gdy konieczne .

W skrócie: Po prostu zapomnij o zastrzeżeniach i użyj SecureRandomjako prawdziwego generatora liczb losowych.

Thorsten S.
źródło
4

Jeśli uważasz liczbę za zwykłą tablicę bitów (lub bajtów), być może możesz użyć (Bezpiecznych) Random.nextBytesrozwiązań sugerowanych w tym pytaniu Przepełnienie stosu , a następnie zamapować tablicę na new BigInteger(byte[]).

IvanK
źródło
3

Bardzo prostym algorytmem jest zastosowanie SHA-256 do sekwencji liczb całkowitych rosnących od 0 w górę. (W razie potrzeby można dodać sól, aby „uzyskać inną sekwencję”.) Jeśli założymy, że wyjście SHA-256 jest „tak dobre, jak” równomiernie rozłożone liczby całkowite między 0 a 2 256-1, to mamy wystarczającą entropię dla zadanie.

Aby uzyskać permutację z wyjścia SHA256 (wyrażonego jako liczba całkowita), wystarczy po prostu ją zmniejszyć modulo 52, 51, 50 ... jak w tym pseudokodzie:

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
źródło