Ten sam seed,
inna gra,
a oczywista poprawka pogarsza sprawę.

Wszystko tutaj pochodzi z jednego projektu: symulacji zarządzania, w której kampania trwa około 1100 dni gry, każdy dzień losuje dziesiątki wyników, a całość musi wczytać się z pliku zapisu i toczyć dalej tak, jakby nic się nie stało. Na tym siedzą 1624 testy automatyczne, a spora ich część sprawdza dokładne liczby.

Piszę to dlatego, że wyniki wyszukiwania na ten problem to głównie ludzie, którym radzi się wywołać Random.InitState, czyli porada na zupełnie inny problem. Ustawienie ziarna decyduje o tym, gdzie strumień się zaczyna. Prawie każdy błąd determinizmu, jaki miałem, dotyczył tego, co dzieje się ze strumieniem później.

Trzy generatory, trzy różne obietnice

W projekcie Unity masz w zasięgu ręki trzy oczywiste generatory i każdy obiecuje co innego. Wybranie jednego z przyzwyczajenia jest początkiem tej historii.

Trzeci wiersz wart jest przypisu: Unity.Mathematics.Random to całkowicie dobra odpowiedź, a nawet dostarcza pomocnik CreateFromIndex, czyli drugi wzorzec z tego artykułu z oficjalnym wsparciem. Jeśli już masz ten pakiet, używaj go. Reszta poradnika dotyczy rozumowania, a ono jest takie samo w obu przypadkach.

Problemem nie jest zapisywanie. Problemem jest współdzielenie.

Obiegowa opinia mówi, że UnityEngine.Random nie da się uczynić deterministycznym. To nie całkiem prawda, a precyzja ma tu znaczenie, bo wskazuje właściwą naprawę. Dokumentacja Unity mówi wprost, że stan da się zapisać i odtworzyć, i opisuje generator jako inicjowany statycznie ziarnem o wysokiej entropii z systemu operacyjnego, po czym zostaje on „w całości pod kontrolą skryptów”.

Da się go więc utrwalić. Czego się nie da, to go posiadać. Ta sama dokumentacja mówi równie wprost dlaczego: to klasa statyczna, więc jej stan jest globalnie współdzielony. Twoja symulacja jest jednym z wielu czytelników. System cząsteczek, wtyczka, narzędzie edytora, kawałek interfejsu losujący wariant animacji bezczynności — każde z nich czerpie z tej samej sekwencji, a każde pobranie przesuwa wszystko, co następuje po nim.

Ziarno, które po cichu przestaje znaczyć to samo

Odruch po przeczytaniu powyższego to przesiadka na System.Random, który jest instancyjny, a więc nie współdzielony. To usuwa jeden problem i wprowadza cichszy, i tej części bym nie zgadł: zasiany System.Random nie ma obietnicy, że zawsze da tę samą sekwencję.

Dokumentacja Microsoftu, w sekcji pokazującej, jak uzyskać tę samą sekwencję wartości losowych, niesie taką uwagę: przykład „może dawać różne sekwencje liczb losowych uruchomiony na różnych wersjach .NET”. Algorytm jest tam opisany jako zmodyfikowany generator subtraktywny, a taki opis to udokumentowanie implementacji, nie gwarancja na nią.

Dla szumu rozgrywki to bez znaczenia. Robi się kosztowne w chwili, gdy liczba musi coś przetrwać:

• plik zapisu napisany w jednej wersji silnika i otwarty w następnej;
• dzienny albo tygodniowy przebieg na wspólnym ziarnie, który dwóch graczy ma przeżyć identycznie;
• test regresji sprawdzający dokładną wartość, który ma oblewać tylko wtedy, gdy coś zepsułeś.

Żadne z tego się nie zapowiada. Aktualizacja środowiska, która zmienia sekwencję, daje build, który się kompiluje, uruchamia, nic nie loguje i jest subtelnie inną grą.

Czterdzieści linijek wartych posiadania

Prowadzi to do mało efektownego wniosku: jeśli wynik ma być stabilny między wersjami i maszynami, generator należy do twojego repozytorium, gdzie nic go nie zmieni bez commita. Mój to xorshift32 z jednym słowem stanu i to jest całość:

Trzy rzeczy ważą tu więcej niż sam algorytm. Stan to jeden uint, więc utrwalenie go jest pojedynczym polem, a nie ćwiczeniem z serializacji. Zero jest zabezpieczone w dwóch miejscach, w konstruktorze i w setterze, bo xorshift jest w zerze pochłaniający: podaj mu zero, a będzie zwracał zera w nieskończoność. To nie mój spryt — własny pakiet matematyczny Unity dokumentuje tę samą regułę dla swojej struktury, że ziarno musi być niezerowe. I algorytm jest teraz twój, więc aktualizacja Unity nie renegocjuje go za ciebie.

Na tym siedzą wygody, z których symulacja faktycznie korzysta: NextDouble, zakres całkowity, NextChance(p) oraz NextGaussian metodą Boxa–Mullera, żeby przebieg treningu lądował blisko swojej prognozy, a nie dokładnie na niej. Wszystkie są tylko odczytami tego samego słowa stanu, i o to chodzi: jedna rzecz do zapisania.

Dwa rodzaje losowości, które nie są wymienne

Posiadanie generatora nie mówi jeszcze, ile ich mieć. Tu spędziłem najwięcej czasu, a odpowiedź nie brzmi „po jednym na system”. Brzmi tak, że symulacje zawierają dwa różne rodzaje losowości, a każdy ma własny właściwy kształt.

Pierwszy rodzaj jest sekwencyjny. Postępuje z czasem, a kolejność losowań jest częścią znaczenia. Kolejka kandydatów do pracy napływających przez tygodnie jest sekwencyjna: każde losowanie zależy od tego, jak daleko zaszła kampania. Ten rodzaj potrzebuje strumienia z zapisywanym słowem stanu, żeby wczytanie wznawiało sekwencję w środku, a nie zaczynało ją od nowa.

Drugi rodzaj jest adresowany współrzędną i to jego najczęściej brakuje w projektach. Niektóre wartości wcale nie są sekwencją. Są właściwością rzeczy: składem kadry w konkurencyjnej firmie, inwestorem, który zjawia się konkretnego dnia, charakterem laboratorium numer cztery. Tego nie trzeba pamiętać, bo da się to przeliczyć. Zbuduj generator z samej współrzędnej, a ta sama współrzędna odbuduje te same wartości na zawsze:

Komentarz nad tą metodą w moim repozytorium nazywa kontrakt, którego ona dotrzymuje: „Deterministyczne względem laboratorium i ziarna kampanii, więc ta sama firma ma tych samych ludzi za każdym otwarciem, a dwie kampanie na tym samym ziarnie się zgadzają.”

Funkcja mieszająca ma tu znaczenie, bo współrzędna w stylu seed ^ labId jest fatalnym ziarnem: sąsiednie laboratoria dawałyby widocznie spokrewnione składy. Potrzebna jest lawina, żeby jeden zmieniony bit zmieniał wszystko:

Zwróć uwagę na argument salt. To on pozwala dwóm niezwiązanym pytaniom o to samo laboratorium tego samego dnia — czy dziś coś wyda, czy podkupi komuś człowieka — dostać niezależne odpowiedzi, bez tego żeby którekolwiek wiedziało o istnieniu drugiego.

Metoda, którą napisałem, udokumentowałem i nigdy nie wywołałem

Gdy podsystem potrzebuje własnego strumienia, oczywistym ruchem jest odgałęzienie go od rodzica. Wylosuj liczbę, użyj jej jako ziarna potomka, podaj potomka dalej. To ładne API i je napisałem:

Przeczytaj implementację obok jej własnego komentarza. Obiecuje pozwolić podsystemowi losować bez przesuwania strumienia rodzica, a pierwsze, co robi, to wywołuje NextUInt(), co przesuwa strumień rodzica.

To nie literówka, to kształt samego pomysłu. Nie da się wyprowadzić ziarna potomka z generatora rodzica bez posunięcia rodzica, bo posuwanie się jest tym, w jaki sposób generator cokolwiek produkuje. Akt izolowania podsystemu sam jest losowaniem, a izolacja kosztuje dokładnie to, co miała kupić.

W przypadku, na którym naprawdę ci zależy, jest gorzej. Jeśli odgałęzienie jest warunkowe — podsystem budzi się dopiero, gdy gracz coś odblokuje, albo w dniu pierwszego uruchomienia funkcji — to czy w ogóle się odgałęziłeś zależy od przebiegu kampanii, a strumień rodzica jest już inny u dwóch graczy, którzy zrobili co innego. Czyli dokładnie ta klasa błędu, przed którą odgałęzienie miało chronić.

Znalazłem to, dając systemowi rekrutacji własny strumień, a to, co mówi tam kod, jest najjaśniejszym zdaniem na ten temat w całym repozytorium:

Fork() jest więc nadal w pliku, wkompilowany w każdy build, i wywołany dokładnie zero razy. Oba problemy, dla których powstał, miały lepsze odpowiedzi: stałe ziarno z własnym zapisywanym słowem stanu dla przypadku sekwencyjnego i zmieszana współrzędna dla całej reszty.

Mam nawyk znajdowania u siebie takich funkcji: napisanych, przetestowanych, nieosiągalnych dla nikogo. Według mojego własnego licznika to szesnasta. Różnica polega na tym, że ta metoda nie jest nieosiągalna przez zapomnienie. Jest nieosiągalna, bo podłączenie jej byłoby błędem, a komentarz trzy pliki dalej wyjaśnia dlaczego. To jest ten rodzaj martwego kodu, który warto zostawić — pod warunkiem że powód leży zapisany obok.

Cztery testy, które czynią to prawdziwym

Nic z powyższego nie jest nic warte jako intencja. Determinizm to własność, która psuje się po cichu, więc trzeba go asercjonować. Te cztery faktycznie wyłapały regresje i są na tyle tanie, że nie ma wymówki, żeby ich nie mieć.

Raz: to samo ziarno daje tę samą kampanię. Najkrótsze możliwe sformułowanie całej idei i pierwsza rzecz, która pęka, gdy ktoś doda losowanie w złym miejscu.

Dwa: strumień przeżywa podróż w obie strony przez plik zapisu. Posuń go, zapisz, wczytaj i sprawdź zarówno stan, jak i następną wartość z niego. Sprawdzanie samego stanu przeoczy odtwarzanie, które zapisuje pole, ale nigdy nie dochodzi do generatora:

Trzy: cała kampania odtwarza się pod skryptowanym graczem. Ten zarabia na swój czas wykonania. Bot gra 1100 dni gry dwa razy na tym samym ziarnie, a oba przebiegi muszą zgodzić się co do gotówki, zdolności i liczby wydanych modeli. Wyłapuje to, czego testy jednostkowe nie widzą, bo trybem awarii jest tu narastające rozjeżdżanie się, a nie pojedyncza zła wartość:

Cztery: systemy adresowane współrzędną zgadzają się same ze sobą. Poproś dwa razy o to samo pole rywali, ten sam skład kadry, ten sam harmonogram inwestorów, z dwóch osobno zbudowanych kampanii na jednym ziarnie, i porównaj. To pilnuje wzorca z poprzedniej sekcji, gdzie nie ma zapisanego stanu, który wyłapałby pomyłkę.

Czego to nie naprawia

Poradnik o determinizmie, który nie podaje swoich granic, coś ci sprzedaje. Wszystko powyżej daje powtarzalną sekwencję liczb. To nie to samo co powtarzalna gra, a różnica ma znaczenie:

• Zmiennoprzecinkowe między platformami. Ta sama arytmetyka na typie double może różnić się między procesorami, kompilatorami i celami kompilacji. Jeśli twoja symulacja ma zgadzać się co do bitu na różnych maszynach, to osobny i znacznie trudniejszy problem niż generator.
• Fizyka. Domyślna fizyka Unity nie jest deterministyczną symulacją lockstep, a zasianie generatora nic w tej sprawie nie robi.
• Kolejność w kolekcjach. Iterowanie słownika albo zbioru i losowanie na każdym elemencie rozjedzie się nawet przy idealnym generatorze, bo kolejność nie jest obiecana. To gryzie znacznie częściej niż zmiennoprzecinkowe.
• Czas i liczba klatek. Cokolwiek czyta Time.deltaTime, a potem losuje, uczyniło liczbę klatek wejściem do symulacji.

W symulacji turowej, krokowanej dniami jak moja, pierwsze dwa w zasadzie nie występują i dlatego ten poradnik jest o generatorze. Trzeciego pilnowałbym: łatwo napisać go przez przypadek, a psuje się dokładnie tak samo, więc jeśli przebieg rozjeżdża się po zrobieniu wszystkiego powyżej, zajrzyj najpierw w to, co iterowałeś, a nie w to, co losowałeś.

Kształt odpowiedzi w czterech punktach

Jeśli nie zabierasz stąd nic innego:

• Miej własny generator. Czterdzieści linijek w twoim repozytorium bije zależność, której algorytm jest szczegółem implementacji.
• Zapytaj, czy wartość jest sekwencyjna, czy adresowana współrzędną, zanim dasz jej strumień. Większość tego, co w symulacji wygląda na losowe, da się przeliczyć, a przeliczane dane nie mogą się rozjechać.
• Nigdy nie wyprowadzaj strumienia potomnego ze strumienia rodzica. Wyprowadź go z tożsamości — stałej, współrzędnej, soli — żeby był niezależny od tego, co rodzic zrobił.
• Zasercjonuj to testem, który odtwarza długi przebieg dwa razy. Determinizm, którego nie testujesz, to determinizm, który miałeś kiedyś.

Pytania, które ludzie zadają