8.13 — Wprowadzenie do generowania liczb losowych

Możliwość generowania liczb losowych może być przydatna w niektórych rodzajach programów, szczególnie w grach, programach do modelowania statystycznego i aplikacjach kryptograficznych, które wymagają szyfrowania i deszyfrowania rzeczy. Weźmy na przykład gry – gdyby nie zdarzenia losowe, potwory zawsze atakowałyby cię w ten sam sposób, zawsze znajdowałbyś ten sam skarb, układ lochów nigdy by się nie zmienił itd… a to nie oznaczałoby dobrej gry.

W prawdziwym życiu często tworzymy losowość, na przykład rzucając monetą, kostką lub tasując talię kart. Zdarzenia te nie są w rzeczywistości losowe, ale obejmują tak wiele zmiennych fizycznych (np. grawitację, tarcie, opór powietrza, pęd itp.), że prawie niemożliwe jest ich przewidzenie lub kontrolowanie i (chyba że jesteś magiem) dają wyniki, które są ze wszech miar losowe.

Komputery nie są jednak zaprojektowane do wykorzystywania zmiennych fizycznych — nie mogą rzucać monetą, kostką ani tasować prawdziwych kart. Nowoczesne komputery żyją w kontrolowanym świecie elektrycznym, w którym wszystko jest binarne (0 lub 1) i nie ma miejsca pomiędzy. Komputery ze swej natury są zaprojektowane tak, aby generować wyniki jak najbardziej przewidywalne. Kiedy każesz komputerowi obliczyć 2 + 2, zawsze chcesz, aby odpowiedź brzmiała 4. Czasami nie 3 lub 5.

W rezultacie komputery na ogół nie są w stanie generować naprawdę losowych liczb (przynajmniej za pomocą oprogramowania). Zamiast tego nowoczesne programy zazwyczaj symulują losowość za pomocą algorytmu.

W tej lekcji omówimy wiele teorii dotyczących generowania liczb losowych w programach i wprowadzimy pewną terminologię, której będziemy używać w przyszłych lekcjach.

Algorytmy i stan

Najpierw omińmy pojęcia algorytmów i stanów.

An algorytm to skończona sekwencja instrukcji, którą można wykonać, aby rozwiązać jakiś problem lub uzyskać użyteczny wynik.

Załóżmy na przykład, że twój szef daje ci mały plik tekstowy zawierający kilka nieposortowanych nazw (po jednej w każdym wierszu) i prosi o posortowanie listy. Ponieważ lista jest niewielka i nie spodziewasz się, że będziesz to robić często, decydujesz się posortować ją ręcznie. Istnieje wiele sposobów sortowania listy, ale możesz zrobić coś takiego:

• Utwórz nową pustą listę do przechowywania posortowanych wyników
• Przeskanuj listę nieposortowanych nazw, aby znaleźć nazwę, która jest pierwsza w kolejności alfabetycznej
• Wytnij tę nazwę z nieposortowanej listy i wklej ją na dole posortowanej listy
• Powtarzaj poprzednie dwa kroki, aż nie będzie już żadnych więcej nazw na nieposortowanej liście

Powyższy zestaw kroków opisuje algorytm sortowania (przy użyciu języka naturalnego). Algorytmy z natury nadają się do wielokrotnego użytku — jeśli szef poprosi Cię jutro o posortowanie kolejnej listy, możesz po prostu zastosować ten sam algorytm do nowej listy.

Ponieważ komputery mogą wykonywać instrukcje i manipulować danymi znacznie szybciej niż my, algorytmy są często pisane przy użyciu języków programowania, co pozwala nam automatyzować zadania. W C++ algorytmy są zazwyczaj implementowane jako funkcje wielokrotnego użytku.

Oto prosty algorytm generowania sekwencji liczb, w której każda kolejna liczba jest zwiększana o 1:

#include <iostream>

int plusOne()
{
    static int s_state { 3 }; // only initialized the first time this function is called

    // Generate the next number

    ++s_state;      // first we modify the state
    return s_state; // then we use the new state to generate the next number in the sequence
}

int main()
{
    std::cout << plusOne() << '\n';
    std::cout << plusOne() << '\n';
    std::cout << plusOne() << '\n';

    return 0;
}

Wypisuje:

4
5
6

Ten algorytm jest całkiem prosty. Za pierwszym razem wywołanie plusOne(), s_state jest inicjalizowane wartością 3. Następnie generowany i zwracany jest kolejny numer w sekwencji wyjściowej.

Algorytm jest uważany za stanowy jeśli zachowuje pewne informacje podczas połączeń. I odwrotnie, algorytm bezstanowy algorytm, który nie przechowuje żadnych informacji (i przy każdym wywołaniu musi otrzymać wszystkie informacje potrzebne do pracy). Nasza plusOne() funkcja jest stanowa, ponieważ używa zmiennej statycznej s_state do przechowywania ostatniego wygenerowanego numeru. W zastosowaniu do algorytmów termin stan odnosi się do bieżących wartości przechowywanych w zmiennych stanowych (tych zachowywanych podczas wywołań).

Aby wygenerować kolejny numer w sekwencji, nasz algorytm wykorzystuje dwuetapowy proces:

• Najpierw bieżący stan (zainicjowany od wartości początkowej lub zachowany z poprzedniego wywołania) jest modyfikowany w celu utworzenia nowego stanu.
• Następnie następna liczba w sekwencja jest generowana z nowego stanu.

Nasz algorytm jest brany pod uwagę deterministyczny, co oznacza, że dla danego wejścia (wartość podana dla start) zawsze wygeneruje tę samą sekwencję wyjściową.

Generatory liczb pseudolosowych (PRNG)

W celu symulacji losowości programy zazwyczaj używają generatora liczb pseudolosowych. A Generator liczb pseudolosowych (PRNG) to algorytm generujący ciąg liczb, którego właściwości symulują ciąg liczb losowych.

Napisanie podstawowego algorytmu PRNG jest łatwe. Oto krótki przykład PRNG, który generuje 100 16-bitowych liczb pseudolosowych:

#include <iostream>

// For illustrative purposes only, don't use this
unsigned int LCG16() // our PRNG
{
    static unsigned int s_state{ 0 }; // only initialized the first time this function is called

    // Generate the next number

    // We modify the state using large constants and intentional overflow to make it hard
    // for someone to casually determine what the next number in the sequence will be.

    s_state = 8253729 * s_state + 2396403; // first we modify the state
    return s_state % 32768; // then we use the new state to generate the next number in the sequence
}

int main()
{
    // Print 100 random numbers
    for (int count{ 1 }; count <= 100; ++count)
    {
        std::cout << LCG16() << '\t';

        // If we've printed 10 numbers, start a new row
        if (count % 10 == 0)
            std::cout << '\n';
    }

    return 0;
}

Wynik tego programu jest następujący:

4339	838	25337	15372	6783	2642	6021	19992	14859	26462	
25105	13860	28567	6762	17053	29744	15139	9078	14633	2108	
7343	642	17845	29256	5179	14222	26689	12884	8647	17050	
8397	18528	17747	9126	28505	13420	32479	23218	21477	30328	
20075	26558	20081	3716	13303	19146	24317	31888	12163	982	
1417	16540	16655	4834	16917	23208	26779	30702	5281	19124	
9767	13050	32045	4288	31155	17414	31673	11468	25407	11026	
4165	7896	25291	26654	15057	26340	30807	31530	31581	1264	
9187	25654	20969	30972	25967	9026	15989	17160	15611	14414	
16641	25364	10887	9050	22925	22816	11795	25702	2073	9516	

Każda liczba wydaje się dość losowa w stosunku do poprzedniej.

Zauważ, jak LCG16() jest podobny do naszego plusOne() przykładu powyżej! Stan jest początkowo ustawiony na wartość 0. Następnie, aby wygenerować następną liczbę w sekwencji wyjściowej, bieżący stan jest modyfikowany (poprzez zastosowanie pewnych operacji matematycznych) w celu utworzenia nowego stanu, a następna liczba w sekwencji jest generowana na podstawie tego nowego stanu.

Jak się okazuje, ten konkretny algorytm nie jest zbyt dobry jako generator liczb losowych (zwróć uwagę, że każdy wynik zmienia się pomiędzy parzystymi i nieparzystymi – to nie jest zbyt losowe!). Jednak większość PRNG działa podobnie do LCG16() -- po prostu zazwyczaj używa większej liczby zmiennych stanu i bardziej złożonych operacji matematycznych w celu wygenerowania wyników lepszej jakości.

Zakładanie PRNG

Sekwencja „liczb losowych” generowana przez PRNG nie jest wcale przypadkowa. Podobnie jak nasz plusOne() funkcji LCG16() jest również deterministyczny. Biorąc pod uwagę pewną wartość stanu początkowego (taką jak 0), PRNG będzie generować za każdym razem tę samą sekwencję liczb. Jeśli uruchomisz powyższy program 3 razy, zobaczysz, że za każdym razem generuje tę samą sekwencję wartości.

Aby wygenerować różne sekwencje wyjściowe, należy zmienić stan początkowy PRNG. Wartość (lub zbiór wartości) używana do ustawienia stanu początkowego PRNG nazywana jest w skrócie a losowym ziarnem (lub nasionem ). Kiedy stan początkowy PRNG został ustawiony przy użyciu wartości początkowej, mówimy, że został zadane.

Wartość początkowa jest zazwyczaj dostarczana przez program przy użyciu PRNG. Oto przykładowy program, który żąda od użytkownika wartości początkowej, a następnie generuje 10 liczb losowych przy użyciu tej wartości początkowej (przy użyciu naszej funkcji LCG16() ).

#include <iostream>

unsigned int g_state{ 0 };

void seedPRNG(unsigned int seed)
{
    g_state = seed;
}

// For illustrative purposes only, don't use this
unsigned int LCG16() // our PRNG
{
    // We modify the state using large constants and intentional overflow to make it hard
    // for someone to casually determine what the next number in the sequence will be.

    g_state = 8253729 * g_state + 2396403; // first we modify the state
    return g_state % 32768; // then we use the new state to generate the next number in the sequence
}

void print10()
{
    // Print 10 random numbers
    for (int count{ 1 }; count <= 10; ++count)
    {
        std::cout << LCG16() << '\t';
    }   

    std::cout << '\n';
}

int main()
{
    unsigned int x {};
    std::cout << "Enter a seed value: ";
    std::cin >> x;

    seedPRNG(x); // seed our PRNG
    print10();   // generate 10 random values

    return 0;
}

Oto 3 przykładowe przebiegi z tego:

Enter a seed value: 7
10458	3853	16032	17299	10726	32153	19116	7455	242	549	

Enter a seed value: 7
10458	3853	16032	17299	10726	32153	19116	7455	242	549	

Enter a seed value: 9876
24071	18138	27917	23712	8595	18406	23449	26796	31519	7922	

Zauważ, że gdy podamy tę samą wartość początkową, otrzymamy tę samą sekwencję wyjściową. Jeśli podamy inną wartość początkową, otrzymamy inną sekwencję wyjściową.

Jakość początkowa i niedosiew

Jeśli chcemy, aby program generował różne liczby losowe przy każdym uruchomieniu, to potrzebujemy jakiegoś sposobu na zmianę wartości początkowej przy każdym uruchomieniu programu. Proszenie użytkownika o podanie wartości początkowej nie jest dobrym rozwiązaniem, ponieważ za każdym razem może po prostu wprowadzić tę samą wartość. Program naprawdę potrzebuje jakiegoś sposobu na wygenerowanie losowej wartości początkowej przy każdym uruchomieniu. Niestety nie możemy użyć PRNG do wygenerowania losowego materiału siewnego, ponieważ potrzebujemy losowego materiału siewnego do wygenerowania liczb losowych. Zamiast tego zazwyczaj będziemy używać algorytmu generowania nasion, który ma na celu wygenerowanie wartości początkowych. Omówimy (i zaimplementujemy) takie algorytmy w następnej lekcji.

Teoretyczna maksymalna liczba unikalnych sekwencji, które PRNG może wygenerować, jest określona przez liczbę bitów w stanie PRNG. Na przykład PRNG ze 128 bitami stanu może teoretycznie wygenerować do 2^128 (340 282 366 920 938 463 463 374 607 431 768 211 456) unikalnych sekwencji wyjściowych. To dużo!

Jednak to, która sekwencja wyjściowa zostanie w rzeczywistości wygenerowana, zależy od stanu początkowego PRNG, który jest określony przez ziarno. Dlatego też, praktycznie rzecz biorąc, liczba unikalnych sekwencji wyjściowych, które PRNG może w rzeczywistości wygenerować, jest ograniczona przez liczbę unikalnych wartości początkowych, które może zapewnić program korzystający z PRNG. Na przykład, jeśli określony algorytm generowania nasion może wygenerować tylko 4 różne wartości początkowe, wówczas PRNG będzie w stanie wygenerować co najwyżej 4 różne sekwencje wyjściowe.

Jeśli PRNG nie ma wystarczającej liczby bitów wysokiej jakości danych początkowych, mówimy, że jest to zasiane. Niedostatecznie obsadzony PRNG może zacząć dawać losowe wyniki, których jakość jest w jakiś sposób obniżona — a im poważniejsze niedosianie, tym bardziej ucierpi jakość wyników.

Na przykład niedostatecznie obsadzony PRNG może wykazywać którykolwiek z następujących problemów:

• Losowe sekwencje generowane przez kolejne przebiegi mogą mieć ze sobą wysoką korelację.
• Podczas generowania N-tej liczby losowej niektóre wartości nigdy nie będą mogły zostać wygenerowane. Na przykład Twister Mersenne'a, który jest niedosiany w określony sposób, nigdy nie wygeneruje wartości 7 lub 13 jako pierwszego wyniku.
• Ktoś może być w stanie odgadnąć ziarno na podstawie początkowej wytworzonej wartości losowej (lub kilku pierwszych wartości losowych). To umożliwiłoby im następnie wygenerowanie wszystkich przyszłych liczb losowych, które zostaną wygenerowane przez generator. Może to pozwolić im na oszukanie lub oszukanie systemu.

Programiści, którzy nie są zaznajomieni z właściwymi praktykami inicjowania, często będą próbować zainicjować PRNG przy użyciu pojedynczej wartości 32-bitowej lub 64-bitowej (niestety, projekt standardowej biblioteki Random w C++ nieumyślnie do tego zachęca). Ogólnie rzecz biorąc, spowoduje to znaczne niedopełnienie PRNG.

Zapełnienie PRNG 64 bajtami wysokiej jakości danych początkowych (mniej, jeśli stan PRNG jest mniejszy) jest zazwyczaj wystarczająco dobre, aby ułatwić generowanie 8-bajtowych wartości losowych do zastosowań niewrażliwych (np. nie do symulacji statystycznych ani kryptografii).

Co wyróżnia dobry PRNG? (odczyt opcjonalny)

Aby być dobrym PRNG, PRNG musi wykazywać szereg właściwości:

• PRNG powinien generować każdą liczbę z w przybliżeniu tym samym prawdopodobieństwem.

Nazywa się to równomiernością dystrybucji. Jeśli niektóre liczby są generowane częściej niż inne, wynik programu korzystającego z PRNG będzie stronniczy! Aby sprawdzić równomierność rozkładu, możemy skorzystać z histogramu. Histogram to wykres pokazujący, ile razy została wygenerowana każda liczba. Ponieważ nasze histogramy są tekstowe, użyjemy symbolu * do przedstawienia każdorazowego wygenerowania danej liczby.

Rozważmy PRNG, który generuje liczby od 1 do 6. Jeśli wygenerujemy 36 liczb, PRNG z równomiernością rozkładu powinien wygenerować histogram wyglądający mniej więcej tak:

1|******
2|******
3|******
4|******
5|******
6|******

PRNG, który jest w jakiś sposób stronniczy, wygeneruje histogram nierówny, np. to:

1|***
2|******
3|******
4|******
5|******
6|*********

lub to:

1|****
2|********
3|******
4|********
5|******
6|****

a może nawet to:

1|*******
2|********
3|*******
4|********
5|
6|******

Powiedzmy, że próbujesz napisać generator losowych przedmiotów dla gry. Kiedy potwór zostaje zabity, twój kod generuje losową liczbę od 1 do 6, a jeśli wynikiem jest 6, potwór upuści rzadki przedmiot zamiast zwykłego. Można się spodziewać, że prawdopodobieństwo takiego zdarzenia wynosi 1 do 6. Jeśli jednak bazowy PRNG nie jest jednolity i generuje o wiele więcej 6 niż powinno (jak drugi histogram powyżej), twoi gracze otrzymają więcej rzadkich przedmiotów, niż zamierzałeś, co prawdopodobnie trywializuje trudność twojej gry lub zaburza ekonomię gry.

Znalezienie algorytmów PRNG, które dają jednolite wyniki, jest trudne.

• Metoda, za pomocą której generowana jest kolejna liczba w sekwencji, nie powinna być przewidywalne.

Rozważmy na przykład następujący algorytm PRNG: return ++num. Ten PRNG jest doskonale jednolity, ale jest również całkowicie przewidywalny - i niezbyt przydatny jako ciąg liczb losowych!

Nawet ciągi liczb, które wydają się losowe dla oka (takie jak wynik LCG16() powyżej) mogą być banalnie przewidywalne dla kogoś, kto jest zmotywowany. Badając zaledwie kilka liczb wygenerowanych z powyższej funkcji LCG16() , można określić, które stałe są używane (8253729 i 2396403) do modyfikacji stanu. Gdy już to wiemy, obliczenie wszystkich przyszłych liczb, które zostaną wygenerowane na podstawie tego PRNG, stanie się trywialne.

Wyobraź sobie teraz, że prowadzisz witrynę bukmacherską, w której użytkownicy mogą obstawiać 100 $. Twoja witryna generuje następnie losową liczbę z zakresu od 0 do 32767. Jeśli liczba jest większa niż 20000, klient wygrywa, a Ty zwracasz podwójną stawkę. W przeciwnym razie przegrają, a ty zachowasz zakład. Ponieważ klient wygrywa tylko 12767/32767 (39%) przypadków, Twoja witryna powinna zarobić mnóstwo pieniędzy, prawda? Jeśli jednak klienci są w stanie określić, które liczby zostaną wygenerowane jako następne, mogą strategicznie obstawiać zakłady, aby zawsze (lub zwykle) wygrywały. Gratulacje, teraz możesz ogłosić upadłość!

• PRNG powinien mieć dobry rozkład wymiarowy liczb.

Oznacza to, że PRNG powinien losowo zwracać liczby z całego zakresu możliwych wyników. Na przykład PRNG powinien generować małe liczby, średnie liczby, wysokie liczby, liczby parzyste i liczby nieparzyste pozornie losowo.

PRNG, który zwrócił wszystkie małe liczby, wówczas wszystkie wysokie liczby mogą być jednolite i nieprzewidywalne, ale nadal będzie prowadzić do stronniczych wyników, szczególnie jeśli liczba liczb losowych, których faktycznie używasz, jest niewielka.

• PRNG powinien mieć wysoki okres dla wszystkich nasion

Wszystkie PRNG mają charakter okresowy, co oznacza, że w pewnym momencie sekwencja wygenerowanych liczb zacznie się powtarzać. Długość sekwencji, zanim PRNG zacznie się powtarzać, jest znana jako okresem.

Na przykład tutaj jest pierwszych 100 liczb wygenerowanych z PRNG ze słabą okresowością:

112	9	130	97	64	31	152	119	86	53	
20	141	108	75	42	9	130	97	64	31	
152	119	86	53	20	141	108	75	42	9	
130	97	64	31	152	119	86	53	20	141	
108	75	42	9	130	97	64	31	152	119	
86	53	20	141	108	75	42	9	130	97	
64	31	152	119	86	53	20	141	108	75	
42	9	130	97	64	31	152	119	86	53	
20	141	108	75	42	9	130	97	64	31	
152	119	86	53	20	141	108	75	42	9

Zauważysz, że wygenerowano 9 jako drugą liczbę, ponownie jako 16-tą liczbę, a następnie co 14 liczb. Ten PRNG utknął, generując wielokrotnie następującą sekwencję: 9-130-97-64-31-152-119-86-53-20-141-108-75-42-(powtórz).

Dzieje się tak, ponieważ PRNG są deterministyczne. Gdy stan PRNG będzie identyczny ze stanem poprzednim, PRNG zacznie generować tę samą sekwencję wyników, którą wytwarzał wcześniej – co spowoduje pętlę.

Dobry PRNG powinien mieć długi okres dla uniknąć liczb początkowych. Zaprojektowanie algorytmu spełniającego tę właściwość może być niezwykle trudne — wiele PRNG ma długie okresy tylko dla niektórych nasion, a innych nie. Jeśli zdarzy się, że użytkownik wybierze ziarno, którego wynikiem będzie stan o krótkim okresie, PRNG nie wykona dobrej roboty, jeśli potrzebnych jest wiele liczb losowych.

• PRNG powinien być wydajny

Większość PRNG ma rozmiar stanu mniejszy niż 4096 bajtów, więc całkowite wykorzystanie pamięci zazwyczaj nie stanowi problemu. Jednakże im większy stan wewnętrzny, tym większe prawdopodobieństwo, że PRNG będzie niedostatecznie zaszczepiony i tym wolniejsze będzie początkowe zaszczepianie (ponieważ jest więcej stanu do zainicjowania).

Po drugie, aby wygenerować następną liczbę w sekwencji, PRNG musi pomieszać swój stan wewnętrzny, stosując różne operacje matematyczne. Ile czasu to zajmuje, może się znacznie różnić w zależności od PRNG, a także architektury (niektóre PRNG działają lepiej w określonych architekturach niż inne). Nie ma to znaczenia, jeśli generujesz liczby losowe tylko okresowo, ale może mieć ogromny wpływ, jeśli potrzebujesz dużej losowości.

Istnieje wiele różnych rodzajów algorytmów PRNG

Na przestrzeni lat opracowano wiele różnych rodzajów algorytmów PRNG (Wikipedia ma dobrą listę tutaj). Każdy algorytm PRNG ma mocne i słabe strony, które mogą sprawić, że będzie mniej lub bardziej odpowiedni dla konkretnej aplikacji, dlatego ważny jest wybór odpowiedniego algorytmu dla Twojej aplikacji.

Wiele PRNG jest obecnie uważanych za stosunkowo słabe według współczesnych standardów — i nie ma powodu, aby używać PRNG, który nie działa dobrze, skoro jest równie łatwy w użyciu.

Randomizacja w C++

Możliwości randomizacji w C++ są dostępne poprzez <random> nagłówek biblioteki standardowej. W bibliotece losowej dostępnych jest 6 rodzin PRNG (od C++20):

Nie ma powodu używać knuth_b, default_random_engine lub rand() (który jest generatorem liczb losowych dostarczonym w celu zapewnienia zgodności z C).

Począwszy od C++20, algorytm Mersenne Twister jest jedynym PRNG dostarczanym z C++, który ma zarówno przyzwoitą wydajność, jak i jakość.

Więc powinniśmy użyć Mersenne Twister, prawda?

Prawdopodobnie. Do większości zastosowań Mersenne Twister jest w porządku, zarówno pod względem wydajności, jak i jakości.

Warto jednak zauważyć, że jak na współczesne standardy PRNG, Mersenne Twister jest nieco przestarzały. Największym problemem Mersenne Twister jest to, że jego wyniki można przewidzieć po zobaczeniu 624 wygenerowanych liczb, co sprawia, że nie nadaje się on do żadnej aplikacji wymagającej nieprzewidywalności.

Jeśli tworzysz aplikację, która wymaga najwyższej jakości losowych wyników (np. symulacji statystycznej), najszybszych wyników lub takich, w których ważna jest nieprzewidywalność (np. kryptografia), będziesz musiał skorzystać z pomocy strony trzeciej biblioteka.

Popularne wybory w chwili pisania tego tekstu:

• Klasa Rodzina Xoshiro i Wyrand dla niekryptograficznych PRNG.
• Klasa Rodzina Chacha dla kryptograficznych (nieprzewidywalnych) PRNG.

OK, teraz, gdy twoje oczy prawdopodobnie są krwawienie, to wystarczy teorii. Porozmawiajmy o tym, jak faktycznie generować liczby losowe za pomocą Mersenne Twister w C++.