8.14 — Generowanie liczb losowych za pomocą Mersenne Twister

W poprzednim lekcja 8.13 — Wprowadzenie do generowania liczb losowych, przedstawiliśmy koncepcję generowania liczb losowych i omówiliśmy, w jaki sposób algorytmy PRNG są zwykle używane do symulacji losowości programów.

W tej lekcji przyjrzymy się, jak generować liczby losowe w programach. Aby uzyskać dostęp do jakichkolwiek funkcji randomizacji w C++, dołączamy <random> nagłówek standardowej biblioteki.

Generowanie liczb losowych w C++ za pomocą Mersenne Twister

Mersenne Twister PRNG, oprócz świetnej nazwy, jest prawdopodobnie najpopularniejszym PRNG we wszystkich językach programowania. Chociaż jest nieco stary jak na dzisiejsze standardy, generalnie zapewnia wysokiej jakości wyniki i ma przyzwoitą wydajność. Biblioteka losowa obsługuje dwa typy Mersenne Twister:

• mt19937 to Mersenne Twister generujący 32-bitowe liczby całkowite bez znaku
• mt19937_64 to Mersenne Twister generujące 64-bitowe liczby całkowite bez znaku

Korzystanie z Mersenne Twister jest proste:

#include <iostream>
#include <random> // for std::mt19937

int main()
{
	std::mt19937 mt{}; // Instantiate a 32-bit Mersenne Twister

	// Print a bunch of random numbers
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << mt() << '\t'; // generate a random number

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

	return 0;
}

Daje to wynik:

3499211612      581869302       3890346734      3586334585      545404204
4161255391      3922919429      949333985       2715962298      1323567403
418932835       2350294565      1196140740      809094426       2348838239
4264392720      4112460519      4279768804      4144164697      4156218106
676943009       3117454609      4168664243      4213834039      4111000746
471852626       2084672536      3427838553      3437178460      1275731771
609397212       20544909        1811450929      483031418       3933054126
2747762695      3402504553      3772830893      4120988587      2163214728

Najpierw dołączamy nagłówek <random>, ponieważ tam właśnie znajdują się wszystkie możliwości liczb losowych. Następnie tworzymy instancję 32-bitowego silnika Mersenne Twister za pomocą instrukcji std::mt19937 mt. Następnie za każdym razem, gdy chcemy wygenerować losową 32-bitową liczbę całkowitą bez znaku, wywołujemy mt().

Rzut kostką za pomocą Mersenne Twister

32-bitowy PRNG wygeneruje losowe liczby od 0 do 4 294 967 295, ale nie zawsze chcemy w tym przypadku liczb zasięg. Jeśli nasz program symulował grę planszową lub grę w kości, prawdopodobnie chcielibyśmy symulować rzut 6-ścienną kostką, generując losowe liczby od 1 do 6. Jeśli nasz program był przygodą w lochach, a gracz miał miecz, który zadał potworom od 7 do 11 obrażeń, to chcielibyśmy generować losowe liczby od 7 do 11 za każdym razem, gdy gracz uderzył potwora.

Niestety, PRNGs nie mogę tego zrobić. Mogą generować tylko liczby wykorzystujące pełny zakres. Potrzebujemy sposobu na przekształcenie liczby wyprowadzanej z naszego PRNG na wartość z mniejszego zakresu, jaki chcemy (z równym prawdopodobieństwem wystąpienia każdej wartości). Chociaż moglibyśmy sami napisać funkcję, która by to robiła, zrobienie tego w sposób zapewniający nieobciążone wyniki nie jest trywialne.

Na szczęście biblioteka losowa może nam w tym pomóc w postaci rozkładów liczb losowych. A losowym rozkładem liczb konwertuje wynik PRNG na inny rozkład liczb.

Biblioteka losowa zawiera wiele losowych rozkładów liczb, z których większości nigdy nie użyjesz, chyba że przeprowadzisz jakąś analizę statystyczną. Istnieje jednak jeden losowy rozkład liczb, który jest niezwykle przydatny: a równomierny rozkład to losowy rozkład liczb, który daje wyniki pomiędzy dwiema liczbami X i Y (włącznie) z równym prawdopodobieństwem.

Oto program podobny do powyższego, wykorzystujący rozkład równomierny do symulacji rzutu 6-ścienną kostką:

#include <iostream>
#include <random> // for std::mt19937 and std::uniform_int_distribution

int main()
{
	std::mt19937 mt{};

	// Create a reusable random number generator that generates uniform numbers between 1 and 6
	std::uniform_int_distribution die6{ 1, 6 }; // for C++14, use std::uniform_int_distribution<> die6{ 1, 6 };

	// Print a bunch of random numbers
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // generate a roll of the die here

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

	return 0;
}

Daje to wynik:

3       1       3       6       5       2       6       6       1       2
2       6       1       1       6       1       4       5       2       5
6       2       6       2       1       3       5       4       5       6
1       4       2       3       1       2       2       6       2       1

W tym przykładzie są tylko dwie godne uwagi różnice w porównaniu z poprzednim. Po pierwsze, stworzyliśmy zmienną o rozkładzie równomiernym (nazwaną die6) do generowania liczb od 1 do 6. Po drugie, zamiast wywoływać mt() w celu wygenerowania 32-bitowych liczb losowych w postaci liczb całkowitych bez znaku, teraz wywołujemy die6(mt) w celu wygenerowania wartości z zakresu od 1 do 6.

Powyższy program nie jest tak losowy, jak się wydaje

Chociaż wyniki naszego powyższego przykładu rzucania kośćmi są dość losowe, program ma poważną wadę. Uruchom program 3 razy i sprawdź, czy potrafisz zrozumieć, co to jest. Śmiało, poczekamy.

Jeopardy music

Jeśli uruchomisz program kilka razy, zauważysz, że za każdym razem wypisuje te same liczby! Chociaż każda liczba w sekwencji jest losowa w stosunku do poprzedniej, cała sekwencja wcale nie jest losowa! Każde uruchomienie naszego programu daje dokładnie ten sam wynik.

Wyobraźmy sobie, że piszesz grę hi-lo, w której użytkownik ma 10 prób odgadnięcia losowo wybranej liczby, a komputer informuje użytkownika, czy jego wynik jest za wysoki, czy za niski. Jeśli komputer za każdym razem wybierze tę samą liczbę losową, gra nie będzie interesująca po pierwszym uruchomieniu. Przyjrzyjmy się zatem bliżej, dlaczego tak się dzieje i jak możemy temu zaradzić.

W poprzedniej lekcji (8.13 — Wprowadzenie do generowania liczb losowych), omówiliśmy, że każda liczba w sekwencji PRNG jest deterministyczna. I że stan PRNG jest inicjowany na podstawie wartości początkowej. Tak więc, biorąc pod uwagę dowolny początkowy numer początkowy, PRNG zawsze wygeneruje w rezultacie tę samą sekwencję liczb z tego ziarna.

Ponieważ inicjujemy wartość naszego Mersenne Twister, jest on inicjowany tym samym ziarnem za każdym razem, gdy program jest uruchamiany. A ponieważ ziarno jest takie samo, generowane liczby losowe również są takie same.

Aby cała nasza sekwencja była losowo losowana przy każdym uruchomieniu programu, musimy wybrać ziarno, które nie jest stałą liczbą. Pierwszą odpowiedzią, która prawdopodobnie przychodzi na myśl, jest to, że potrzebujemy losowej liczby dla naszego materiału siewnego! To dobry pomysł, ale jeśli potrzebujemy liczby losowej do wygenerowania liczb losowych, to mamy do czynienia z paragrafem 22. Okazuje się, że tak naprawdę nie potrzebujemy, aby nasze ziarno było liczbą losową — wystarczy, że wybierzemy coś, co będzie się zmieniać przy każdym uruchomieniu programu. Następnie możemy użyć naszego PRNG do wygenerowania z tego ziarna unikalnej sekwencji liczb pseudolosowych.

Są w tym celu powszechnie stosowane dwie metody:

• Użyj zegara systemowego
• Użyj losowego urządzenia systemowego

Zainicjowanie za pomocą zegara systemowego

Jaka jest jedna rzecz, która różni się za każdym razem, gdy uruchamiasz program? Jeśli nie uda ci się uruchomić programu dwa razy dokładnie w tym samym momencie, odpowiedź jest taka, że ​​bieżący czas jest inny. Dlatego też, jeśli jako wartość początkową wykorzystamy bieżący czas, wówczas nasz program przy każdym uruchomieniu będzie generował inny zestaw liczb losowych. C i C++ mają długą historię inicjowania PRNG przy użyciu bieżącego czasu (przy użyciu funkcji std::time() ), więc prawdopodobnie zobaczysz to w wielu istniejących kodach.

Na szczęście C++ posiada bibliotekę chrono zawierającą różne zegary, których możemy użyć do wygenerowania wartości początkowej. Aby zminimalizować ryzyko, że dwie wartości czasu będą identyczne, jeśli program będzie wykonywany szybko po sobie, chcemy zastosować miarę czasu, która zmienia się tak szybko, jak to możliwe. W tym celu zapytamy zegar, ile czasu minęło od najwcześniejszego momentu, jaki może zmierzyć. Czas ten mierzony jest w „taktach”, czyli bardzo małej jednostce czasu (zwykle nanosekundach, ale może to być milisekunda).

#include <iostream>
#include <random> // for std::mt19937
#include <chrono> // for std::chrono

int main()
{
	// Seed our Mersenne Twister using steady_clock
	std::mt19937 mt{ static_cast<std::mt19937::result_type>(
		std::chrono::steady_clock::now().time_since_epoch().count()
		) };

	// Create a reusable random number generator that generates uniform numbers between 1 and 6
	std::uniform_int_distribution die6{ 1, 6 }; // for C++14, use std::uniform_int_distribution<> die6{ 1, 6 };

	// Print a bunch of random numbers
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // generate a roll of the die here

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

	return 0;
}

Powyższy program zawiera tylko dwie zmiany w stosunku do poprzedniego. Po pierwsze, dołączamy <chrono>, który daje nam dostęp do zegara. Po drugie, używamy bieżącego czasu zegara jako wartości początkowej dla naszego Mersenne Twister.

Wyniki generowane przez ten program powinny teraz być inne przy każdym uruchomieniu, co można zweryfikować eksperymentalnie, uruchamiając go kilka razy.

Wadą tego podejścia jest to, że jeśli program zostanie uruchomiony kilka razy z rzędu w krótkich odstępach czasu, nasiona wygenerowane dla każdego uruchomienia nie będą się zbytnio różnić, co może mieć wpływ na jakość losowych wyników ze statystycznego punktu widzenia. W przypadku normalnych programów nie ma to znaczenia, ale w przypadku programów wymagających wysokiej jakości niezależnych wyników ta metoda inicjowania może być niewystarczająca.

Zainicjowanie losowym urządzeniem

Biblioteka losowa zawiera typ o nazwie std::random_device który jest PRNG zdefiniowanym w implementacji. Zwykle unikamy możliwości zdefiniowanych w ramach implementacji, ponieważ nie dają one gwarancji jakości ani przenośności, ale jest to jeden z wyjątków. Zwykle std::random_device poprosi system operacyjny o liczbę pseudolosową (sposób, w jaki to zrobi, zależy od systemu operacyjnego).

#include <iostream>
#include <random> // for std::mt19937 and std::random_device

int main()
{
	std::mt19937 mt{ std::random_device{}() };

	// Create a reusable random number generator that generates uniform numbers between 1 and 6
	std::uniform_int_distribution die6{ 1, 6 }; // for C++14, use std::uniform_int_distribution<> die6{ 1, 6 };

	// Print a bunch of random numbers
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // generate a roll of the die here

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

	return 0;
}

W powyższym programie zaszczepiamy naszego Mersenne Twister jedną losową liczbą wygenerowaną z tymczasowej instancji std::random_device. Jeśli uruchomisz ten program wiele razy, powinien on również dawać za każdym razem inne wyniki.

Jeden potencjalny problem z std::random_device: nie jest wymagane, aby był on niedeterministyczny, co oznacza, możew niektórych systemach generować tę samą sekwencję przy każdym uruchomieniu programu, a właśnie tego staramy się uniknąć. Wystąpił błąd w MinGW (naprawiony w GCC 9.2), który mógł zrobić dokładnie to, czyniąc std::random_device bezużytecznym.

Jednak najnowsze wersje najpopularniejszych kompilatorów (GCC/MinGW, Clang, Visual Studio) obsługują prawidłowe implementacje std::random_device.

unsigned int getRandomDeviceValue()
{
   std::random_device rd{}; // create a value initialized std::random_device object
   return rd(); // return the result of operator() to the caller
}

Wysyłaj PRNG tylko raz

Wiele PRNG można ponownie inicjować po początkowym inicjowaniu. Zasadniczo powoduje to ponowną inicjalizację stanu generatora liczb losowych, powodując generowanie wyników począwszy od nowego stanu początkowego. Generalnie należy unikać ponownego wysyłania, chyba że masz ku temu konkretny powód, ponieważ może to spowodować, że wyniki będą mniej losowe lub w ogóle nie będą losowe.

Oto przykład typowego błędu popełnianego przez nowych programistów:

#include <iostream>
#include <random>

int getCard()
{
    std::mt19937 mt{ std::random_device{}() }; // this gets created and seeded every time the function is called
    std::uniform_int_distribution card{ 1, 52 };
    return card(mt);
}

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

    return 0;
}

W getCard() funkcja, generator liczb losowych jest tworzony i uruchamiany za każdym razem, gdy funkcja jest wywoływana. Jest to w najlepszym przypadku nieefektywne i prawdopodobnie spowoduje słabe losowe wyniki.

Problemy z Mersenne Twister i niedosiewem

Stan wewnętrzny Mersenne Twister wymaga 19937 bitów (2493 bajtów), co stanowi 624 wartości 32-bitowe lub 312 wartości 64-bitowych. W rezultacie std::mt19937 przydziela 624 liczby całkowite, podczas gdy std::mt19937_64 przydziela 312 liczb całkowitych.

W powyższych przykładach, gdzie zaszczepiamy nasze std::mt19937 z zegara lub std::random_device, naszym ziarnem jest tylko pojedyncza liczba całkowita. Oznacza to, że zasadniczo inicjujemy 624 liczby całkowite przy użyciu pojedynczej liczby całkowitej, co znacznie osłabia działanie Mersenne Twister PRNG. Biblioteka Random robi wszystko, co w jej mocy, aby wypełnić pozostałe 623 wartości „losowymi” danymi… ale nie może zdziałać cuda. Niedostatecznie obsadzony PRNG może generować wyniki, które są nieoptymalne w przypadku zastosowań wymagających najwyższej jakości wyników. Na przykład, dodanie std::mt19937 pojedynczej wartości 32-bitowej nigdy nie wygeneruje liczby 42 jako pierwszego wyniku.

Jak więc to naprawić? Począwszy od C++ 20, nie ma łatwego sposobu. Mamy jednak pewne sugestie.

Najpierw porozmawiajmy o std::seed_seq (co oznacza „sekwencję nasion”). Na poprzedniej lekcji wspomnieliśmy, że idealnie byłoby, gdyby nasze dane początkowe miały tyle bitów, ile jest stan naszego PRNG, w przeciwnym razie nasz PRNG byłby niedostateczny. Jednak w wielu przypadkach (zwłaszcza gdy nasz PRNG ma duży stan) nie będziemy mieli tak wielu bitów losowych danych początkowych.

std::seed_seq to typ, który został zaprojektowany, aby w tym pomóc. Możemy przekazać mu tyle losowych wartości, ile mamy, a następnie wygeneruje tyle dodatkowych, obiektywnych wartości początkowych, ile potrzeba do zainicjowania stanu PRNG. Jeśli zainicjujesz std::seed_seq pojedynczą wartością (np. z std::random_device), a następnie zainicjujesz Mersenne Twister obiektem std::seed_seq , std::seed_seq wygeneruje 623 wartości dodatkowych danych początkowych. Nie doda to losowości, ale da nam lepszą mieszankę bitów 0 i 1. Im jednak więcej losowych danych będziemy w stanie dostarczyć std::seed_seq, tym lepszą robotę dla nas wykona. Zatem najłatwiejszym pomysłem jest po prostu użycie std::random_device w celu uzyskania std::seed_seq więcej danych do pracy. Jeśli zainicjujemy std::seed_seq 8 wartościami z std::random_device zamiast 1, wówczas pozostałe wartości wygenerowane przez std::seed_seq powinny być znacznie lepsze:

#include <iostream>
#include <random>

int main()
{
	std::random_device rd{};
	std::seed_seq ss{ rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd() }; // get 8 integers of random numbers from std::random_device for our seed
	std::mt19937 mt{ ss }; // initialize our Mersenne Twister with the std::seed_seq

	// Create a reusable random number generator that generates uniform numbers between 1 and 6
	std::uniform_int_distribution die6{ 1, 6 }; // for C++14, use std::uniform_int_distribution<> die6{ 1, 6 };

	// Print a bunch of random numbers
	for (int count{ 1 }; count <= 40; ++count)
	{
		std::cout << die6(mt) << '\t'; // generate a roll of the die here

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

	return 0;
}

To całkiem proste, więc nie ma powodu, aby nie robić tego przynajmniej.

Możesz także użyć innych „losowych” danych wejściowych do std::seed_seq. Pokazaliśmy już, jak uzyskać wartość z zegara, więc możesz łatwo to wrzucić. Inne rzeczy, które są czasami używane, to bieżący identyfikator wątku, adres poszczególnych funkcji, identyfikator użytkownika, identyfikator procesu itp. Wykonanie tego wykracza poza zakres tego artykułu, ale ten artykuł zawiera pewien kontekst i łącze do randutils.hpp który to implementuje.

Alternatywna ścieżka to użyj innego PRNG z mniejszym stanem. Wiele dobrych PRNG używa 64 lub 128 bitów stanu, które można łatwo zainicjować za pomocą std::seed_seq wypełnienia 8 wywołaniami std::random_device.

Rozgrzewka PRNG

Gdy PRNG otrzymuje nasiona złej jakości (lub są niedosiane), początkowe wyniki PRNG mogą nie być wysokiej jakości. Z tego powodu niektóre PRNG korzystają z „rozgrzewki”, która jest techniką, w której odrzuca się pierwsze N ​​wyników wygenerowanych z PRNG. Pozwala to na pomieszanie stanu wewnętrznego PRNG w taki sposób, że późniejsze wyniki powinny być wyższej jakości. Zwykle odrzuca się kilkaset do kilku tysięcy wyników początkowych. Im dłuższy okres PRNG, tym więcej początkowych wyników należy odrzucić.

Klasa seed_seq Inicjalizacja używana przez std::mt19937 przeprowadza rozgrzewkę, więc nie musimy jawnie rozgrzewać std::mt19937 obiekty.

Liczby losowe w wielu funkcjach lub plikach (Random.h)

Ta treść została przeniesiona do 8.15 -- Globalne liczby losowe (Random.h).

Programy debugujące, które używaj liczb losowych

Debugowanie programów korzystających z liczb losowych może być trudne, ponieważ przy każdym uruchomieniu mogą one zachowywać się inaczej. W takim przypadku błędne zachowanie może się zdarzyć lub nie. Może to spowodować stratę dużej ilości czasu. Podczas debugowania warto upewnić się, że program za każdym razem wykonuje się w ten sam (niepoprawny) sposób. W ten sposób możesz uruchomić program tyle razy, ile potrzeba, aby określić, gdzie występuje błąd.

Z tego powodu podczas debugowania przydatną techniką jest zaszczepienie PRNG określoną stałą wartością (np. 5), która powoduje wystąpienie błędnego zachowania. Jeśli dane ziarno nie powoduje, że Twój program wyświetla błąd, zwiększaj wartość ziarna, aż znajdziesz takie, które to powoduje. Dzięki temu program będzie generował za każdym razem te same wyniki, co ułatwi debugowanie. Po znalezieniu błędu możesz użyć zwykłej metody rozmieszczania, aby ponownie rozpocząć generowanie losowych wyników.

Losowe często zadawane pytania