Liczby (pseudo) losowe

Dzisiaj zajmiemy się jednym z fundamentów całej dziedziny proceduralnej generacji i gier wideo w ogóle – czyli generowaniem liczb. Bez losowych liczb nie byłoby generowanych światów, zdarzeń ani nawet prostego systemu RPG, w którym miecz zadaje 2-3 obrażenia cięte! Tylko czy te liczby są naprawdę losowe? A może ktoś za tym stoi? Załóżcie sobie swoje foliowe czapeczki i rozsiądźcie się wygodnie.

Na wstępie strzelę sobie w stopę – znajomość zagadnienia losowości we współczesnych komputerach nie jest niezbędna; wszystkie znane mi silniki do tworzenia gier oferują wbudowane funkcje do generowania liczb, które trywializują ten proces. Oto przykład losowania liczby z przedziału -10.0 do 10.0 w Godocie:

var my_random_number = rng.randf_range(-10, 10)

Proste, wystarczy ładnie poprosić “daj mi losową liczbę z zakresu x do y”. 

Jednakże znajomość tego JAK te funkcje działają u podstaw pozwoli Wam lepiej zrozumieć zasady proceduralnego tworzenia i odtwarzania elementów w grach. Aby dokładnie zrozumieć specyfikę losowości, musimy sobie tu i teraz ustalić jedną bardzo ważną rzecz. Gotowi? 

We współczesnych komputerach liczby losowe nie istnieją. 

Wiem wiem, szokujące! Daj sobie chwilę na spacerek, meliskę i dojście do siebie po tak szokującej rewelacji. 

W pełni rozumiem, że na pierwszy rzut oka może to wydawać się absurdalne – w końcu w grach RPG gracze zadają losową liczbę obrażeń, gry generują losowe światy i wydarzenia, a nawet po wpisaniu w wyszukiwarkę “generator liczb losowych” otrzymamy dokładnie to o co prosimy:

Szkopuł w tym, że to nie są liczby losowe – tylko pseudolosowe. 

Wyobraź sobie rzut kostką, taki prawdziwy – mimo, że wynik wydaje nam się nie do przewidzenia, gdybyśmy dwukrotnie identycznie rzucili kostką, używając takiej samej siły, ustawienia ręki i kostki – to kostka spadłaby tak samo i otrzymalibyśmy taki sam wynik. W praktyce jest to mało prawdopodobne, ale nie niemożliwe. Na tym właśnie polega pseudolosowość — przy tych samych warunkach początkowych zawsze otrzymujemy ten sam, przewidywalny wynik

W takim razie, czy istnieje coś faktycznie losowego w naszym świecie? Tak, ale daleko wykracza poza tematykę tego bloga – choćby w fizyce kwantowej elektrony zachowują się całkowicie losowo, ponieważ mimo identycznych warunków początkowych potrafią obierać inne ścieżki, bez specjalnego powodu. Swoją drogą, sam Albert Einstein hejtował tę teorię naukową mówiąc, że “Bóg nie gra w kości”. 

“Prawdziwie losowe” są też zjawiska przyrodnicze, takie jak pogoda, szum atmosferyczny czy… lampy lawy, które są wykorzystywane przez firmę Cloudflare do generowania liczb używanych w celach kryptograficznych. Serio!. 

W poprzednim zdaniu celowo napisałem wyrażenie “prawdziwie losowe” w cudzysłowie, ponieważ w przyszłości może okazać się, że je również da się wyliczyć i przewidzieć co wyeliminuje ich prawo do nazywania się losowymi. Jednakże póki w pełni nie rozgryziemy zasad działania fizyki, możemy traktować pewne zjawiska jako losowe – z czego radośnie korzysta strona https://www.random.org/ serwując nam liczby losowe w oparciu o naturalne zjawisko zwane szumem atmosferycznym. Niestety za prawdziwą losowość musimy zapłacić cenę oczekiwania na rezultat, co byłoby niedopuszczalne w przypadku większości gier i symulacji gdzie wynik musimy otrzymać natychmiast.

Wiecie jak losowano liczby zanim komputery przybyły z odsieczą? Ponieważ ludzie nie są zbyt wydajni w wymyślaniu liczb, w 1955 roku opublikowano książkę o tytule “A Million Random Digits with 100,000 Normal Deviates”, która zawiera dokładnie to, czego byśmy się spodziewali – milion liczb losowych. Jakkolwiek absurdalnie teraz to nie wygląda, w latach 50-tych pozycja ta była używana przez naukowców przeprowadzających różne eksperymenty i symulacje.

Nie żartuję – mało tego – reedycję książki można wciąż nabyć na Amazonie: https://www.amazon.com/Million-Random-Digits-Normal-Deviates/dp/0833030477 

---

Wracając do świata cyfrowego, komputer nie jest w stanie sam “wymyślić” losowej liczby. Tak, nawet taki gamingowy z zielonym logo; prosząc o losową liczbę z danego zakresu, komputer tak naprawdę daje nam kolejną liczbę z ciągu liczb, który musi sobie na bieżąco wyliczyć według matematycznych wzorów. Innymi słowy, komputer używa algorytmu do wygenerowania liczb, co samo w sobie wyklucza możliwość otrzymania liczb prawdziwie losowych – w końcu słowo “algorytm” oznacza “krok po kroku”, “według schematu”. No to losowo albo według schematu, wybierz jedno 🙁 

Jak wyglądają takie algorytmy? Nie ma w nich żadnej czarnej magii. Mimo trudnych nazw, takich jak np. Liniowe generatory kongruencyjne (w skrócie LCG – od angielskiej nazwy “Linear congruential generator”) lub Xorshift128+, są dość krótkie i opierają się na operacjach dodawania, mnożenia, reszty z dzielenia. Te bardziej pomysłowe dorzucą jakieś tasowanie cyfr (zamiana miejsc), przesunięcia bitowe (zamiana zer i jedynek o ileś miejsc w prawo lub w lewo) czy kombinacje wszystkich powyższych. Jednak wszystkie są ciągami liczb, które robią szereg operacji na podstawie poprzednio wygenerowanej liczby, po czym zwracają wynik. Na razie wystarczy Ci wiedza, że one istnieją, dla dociekliwych rozwinę temat poszczególnych algorytmów w osobnych artykułach.

Żeby jednak pomóc Ci zrozumieć na czym polega trudność tworzenia takich ciągów, a także dlaczego jest ich wiele i nie ma jednego “najlepszego”, na chwile poudawajmy, że ich nie ma i spróbuję wymyślić swój ciąg liczb losowych, tak jak nasi przodkowie, którzy musieli stworzyć pierwsze generatory. A może by tak…

liczba = (poprzednia_liczba * 7 + 5) % 10

Wygląda czadowo, na pewno jest super! Zaczynając od liczby 1, kolejną bierzemy, mnożymy razy 8, dodajemy 5, a wynikiem będzie reszta dzielenia przez 10 tego co otrzymaliśmy! Zobaczmy, co wygenerował ten wzór:

2, 9, 8, 1, 2, 9, 8, 1, 2, 9, 8, 1, 2, 9, 8, 1, 2, 9, 8, 1

Chyba jednak nie był taki dobry jak mi się wydawało. Widzisz tu jakiś problem? Powtarza się ciągle sekwencja 1, 2, 9, 8. Musimy zatem coś zmienić, aby zwiększyć szanse wystąpienia wszystkich liczb, możliwie jak najbardziej sprawiedliwie. I pewnie spędziłbym tak dobre parę miesięcy, poprawiając go i napotykając się na kolejne błędy których wcześniej nie przewidziałem…

To w pigułce pokazuje problematykę generatorów liczb; sztuka polega na tym, aby tak dobrać wzór i tak pobawić się wynikiem, aby kolejne liczby nie wpadały w żaden przewidywalny ciąg i ich rozkład był równomierny – bez powtarzających się cykli i faworyzowania żadnych liczb, takich jak parzyste, nieparzyste czy pierwsze. Takie tendencje mogą wychodzić nie przy kilku pierwszych liczbach, ale po setkach, tysiącach, milionach, dlatego każdy proponowany algorytm wymaga wnikliwych testów.  Naukowcy od lat doskonalą swoje ciągi i przeprowadzają przeróżne eksperymenty, aby ich generatory spełniały wszystkie wymogi losowości, a także wydajności – dlatego też algorytmów i ich wariacji powstało wiele i nie ma jednego idealnego – każdy generuje liczby pseudolosowe i posiada swój szereg wad i zalet. 

Dobrodziejstwo dostępności takich generatorów sprawia, że nawet nie musicie wiedzieć jakiego algorytmu używacie, ponieważ współczesne silniki do tworzenia gier, takie jak Godot czy Unity, mają wbudowane, optymalne funkcje, które zaspokoją zdecydowaną większość Waszych potrzeb. Tak więc dopóki nie prowadzicie szeroko zakrojonych, skomplikowanych symulacji wymagających miliarda pseudolosowych liczb, możecie być dumni z dotarcia do końca tego artykułu i spać spokojnie wiedząc skąd Baldur’s Gate bierze Wasze nieudane rzuty kostką na zręczność gdy łotrzyk próbuje “pożyczyć” sobie kolejny mieszek ze złotem.