Jak możliwe są gry deterministyczne w obliczu zmiennoprzecinkowego niedeterminizmu?

Aby stworzyć grę podobną do sieci RTS, widziałem tutaj wiele odpowiedzi sugerujących, że gra jest całkowicie deterministyczna; musisz tylko przenieść do siebie działania użytkowników i opóźnić to, co się trochę wyświetla, aby „zablokować” dane wejściowe wszystkich osób przed renderowaniem następnej klatki. Wówczas rzeczy takie jak pozycja jednostki, zdrowie itp. Nie muszą być stale aktualizowane przez sieć, ponieważ symulacja każdego gracza będzie dokładnie taka sama. Słyszałem również to samo, co sugerowałem przy tworzeniu powtórek.

Jednak skoro obliczenia zmiennoprzecinkowe nie są deterministyczne między maszynami, a nawet między różnymi kompilacjami tego samego programu na tej samej maszynie, czy to naprawdę jest możliwe do zrobienia? Jak zapobiegamy temu, by fakt ten powodował niewielkie różnice między graczami (lub powtórkami), które falują w trakcie gry ?

Słyszałem, jak niektórzy ludzie sugerują całkowite unikanie liczb zmiennoprzecinkowych i użycie intdo przedstawienia ilorazu ułamka, ale nie wydaje mi się to praktyczne - co jeśli na przykład muszę wziąć cosinus kąta? Czy naprawdę muszę przepisać całą bibliotekę matematyczną?

Zauważ, że interesuje mnie głównie C #, który, o ile mogę powiedzieć, ma dokładnie takie same problemy jak C ++ w tym zakresie.

Czy zmiennoprzecinkowe są deterministyczne?

Czytałem dużo na ten temat kilka lat temu, kiedy chciałem napisać RTS przy użyciu tej samej architektury lockstep, co ty.

Moje wnioski dotyczące sprzętowych zmiennoprzecinkowych były następujące:

• Ten sam natywny kod zestawu jest najprawdopodobniej deterministyczny, pod warunkiem, że zachowujesz ostrożność przy ustawianiu flag zmiennoprzecinkowych i ustawieniach kompilatora.
• Był jeden projekt RTS o otwartym kodzie źródłowym, który twierdził, że otrzymali deterministyczne kompilacje C / C ++ w różnych kompilatorach za pomocą biblioteki opakowań. Nie zweryfikowałem tego roszczenia. (Jeśli dobrze pamiętam, chodziło o STREFLOPbibliotekę)
• JIT .net ma sporo swobody. W szczególności dozwolone jest stosowanie większej dokładności niż wymaga. Używa również różnych zestawów instrukcji na x86 i AMD64 (myślę, że na x86 używa x87, AMD64 używa niektórych instrukcji SSE, których zachowanie różni się dla denormów).
• Złożone instrukcje (w tym funkcja trygonometryczna, wykładnicze, logarytmy) są szczególnie problematyczne.

Doszedłem do wniosku, że niemożliwe jest deterministyczne użycie wbudowanych typów zmiennoprzecinkowych w .net.

Możliwe obejścia

Potrzebowałem więc obejść. Przemyślałem:

1. Implementuj FixedPoint32w C #. Chociaż nie jest to zbyt trudne (mam w połowie zakończoną implementację), bardzo mały zakres wartości sprawia, że ​​korzystanie z niego jest denerwujące. Przez cały czas musisz uważać, aby nie przepełnić ani nie stracić zbyt dużej precyzji. W końcu uznałem, że nie jest to łatwiejsze niż bezpośrednie użycie liczb całkowitych.
2. Implementuj FixedPoint64w C #. Trudno mi było to zrobić. W przypadku niektórych operacji przydatne byłyby pośrednie liczby całkowite 128-bitowe. Ale .net nie oferuje takiego typu.
3. Użyj natywnego kodu do operacji matematycznych, który jest deterministyczny na jednej platformie. Powoduje narzut wywołania połączenia delegowanego przy każdej operacji matematycznej. Traci zdolność do biegania na różnych platformach.
4. Użyj Decimal. Ale jest powolny, zajmuje dużo pamięci i łatwo rzuca wyjątki (dzielenie przez 0, przepełnienia). Jest to bardzo przydatne do celów finansowych, ale nie nadaje się do gier.
5. Zaimplementuj niestandardowy 32-bitowy zmiennoprzecinkowy. Na początku wydawało się to dość trudne. Brak wewnętrznej funkcji BitScanReverse powoduje kilka niedogodności podczas jej wdrażania.

My SoftFloat

Zainspirowany postem na StackOverflow , właśnie zacząłem implementować 32-bitowe zmiennoprzecinkowe oprogramowanie i wyniki są obiecujące.

• Reprezentacja pamięci jest binarnie zgodna ze zmiennoprzecinkowymi elementami IEEE, dzięki czemu mogę ponownie interpretować rzutowanie podczas wysyłania ich do kodu graficznego.
• Obsługuje SubNormy, nieskończoności i NaNy.
• Dokładne wyniki nie są identyczne z wynikami IEEE, ale zwykle nie ma to znaczenia dla gier. W tego rodzaju kodzie znaczenie ma tylko to, że wynik jest taki sam dla wszystkich użytkowników, a nie, że jest dokładny do ostatniej cyfry.
• Wydajność jest przyzwoita. Trywialny test wykazał, że może on wykonać około 75MFLOPS w porównaniu z 220-260MFLOPS z floatdodawaniem / mnożeniem (pojedynczy wątek na 2,66 GHz i3). Jeśli ktoś ma dobre wzorce zmiennoprzecinkowe dla .net, proszę o przesłanie ich do mnie, ponieważ mój obecny test jest bardzo podstawowy.
• Zaokrąglanie można poprawić. Obecnie obcina się, co z grubsza odpowiada zaokrągleniu do zera.
• To wciąż bardzo niekompletne. Obecnie brakuje podziału, rzutów i skomplikowanych operacji matematycznych.

Jeśli ktoś chce wesprzeć testy lub ulepszyć kod, skontaktuj się ze mną lub wyślij prośbę o ściągnięcie na github. https://github.com/CodesInChaos/SoftFloat

Inne źródła nieokreśloności

Istnieją również inne źródła nieokreśloności w .net.

• iteracja nad a Dictionary<TKey,TValue>lub HashSet<T>zwraca elementy w nieokreślonej kolejności.
• object.GetHashCode() różni się w zależności od biegu.
• Implementacja wbudowanej Randomklasy jest nieokreślona, ​​użyj własnej.
• Wielowątkowość z naiwnym blokowaniem prowadzi do zmiany kolejności i różnych wyników. Bądź bardzo ostrożny, aby używać wątków poprawnie.
• Kiedy WeakReferences tracą, ich cel jest nieokreślony, ponieważ GC może działać w dowolnym momencie.

Odpowiedź na to pytanie pochodzi z zamieszczonego linku. W szczególności powinieneś przeczytać cytat z Gas Powered Games:

Pracuję w Gas Powered Games i mogę powiedzieć z pierwszej ręki, że matematyka zmiennoprzecinkowa jest deterministyczna. Potrzebujesz tylko tego samego zestawu instrukcji i kompilatora, a procesor użytkownika jest zgodny ze standardem IEEE754, który obejmuje wszystkich naszych klientów PC i 360. Silnik, który obsługuje DemiGod, Supreme Commander 1 i 2, opiera się na standardzie IEEE754. Nie wspominając już chyba o wszystkich innych grach RTS peer to peer dostępnych na rynku.

A potem poniżej jest to:

Jeśli przechowujesz powtórki jako dane wejściowe kontrolera, nie można ich odtwarzać na komputerach z różnymi architekturami procesorów, kompilatorami lub ustawieniami optymalizacji. W MotoGP oznaczało to, że nie mogliśmy udostępniać zapisanych powtórek między Xbox i PC.

Gra deterministyczna będzie deterministyczna tylko przy użyciu identycznie skompilowanych plików i uruchomiona w systemach zgodnych ze standardami IEEE. Zsynchronizowane symulacje lub powtórki sieciowe między platformami nie będą możliwe.

Używaj arytmetyki punktów stałych. Lub wybierz autorytatywny serwer i od czasu do czasu synchronizuj stan gry - tak właśnie robi MMORTS. (Przynajmniej Elements of War działa w ten sposób. Jest napisane również w języku C #). W ten sposób błędy nie mają szans na kumulację.

Edycja: Link do stałej klasy punktu (Kupujący strzeż się! - Nie użyłem go ...)

Zawsze możesz polegać na arytmetyki stałych punktów . Ktoś (robiąc rts, nie mniej) wykonał już nogę przy przepełnieniu stosu .

Zapłacisz karę za wydajność, ale może to stanowić problem, ponieważ .net nie będzie tutaj szczególnie wydajny, ponieważ nie będzie korzystał z instrukcji SIMD. Reper!

Uwaga: Wygląda na to, że ktoś w firmie Intel ma rozwiązanie umożliwiające korzystanie z biblioteki operacji podstawowych Intel Performance z c #. Może to pomóc wektoryzacji kodu stałego punktu, aby zrekompensować wolniejszą wydajność.

Pracowałem nad wieloma dużymi tytułami.

Krótka odpowiedź: jest to możliwe, jeśli jesteś szalenie rygorystyczny, ale prawdopodobnie nie warto. O ile nie masz ustalonej architektury (czytaj: konsola), jest wybredna, krucha i zawiera wiele drugorzędnych problemów, takich jak późne dołączenie.

Jeśli przeczytasz niektóre z wymienionych artykułów, zauważysz, że chociaż możesz ustawić tryb procesora, istnieją dziwne przypadki, na przykład gdy sterownik drukarki przełącza tryb procesora, ponieważ był w tej samej przestrzeni adresowej. Miałem przypadek, w którym aplikacja była zablokowana ramką na urządzeniu zewnętrznym, ale wadliwy komponent powodował dławienie procesora z powodu ciepła i raportował inaczej rano i po południu, co spowodowało, że po lunchu stała się inną maszyną.

Te różnice między platformami dotyczą krzemu, a nie oprogramowania, więc odpowiedź na twoje pytanie dotyczy również C #. Instrukcje takie jak fused multiply-add (FMA) vs ADD + MUL zmieniają wynik, ponieważ zaokrągla wewnętrznie tylko raz zamiast dwa razy. C daje większą kontrolę, aby zmusić procesor do robienia tego, co chcesz, po prostu wykluczając operacje takie jak FMA, aby uczynić rzeczy „standardowymi” - ale kosztem szybkości. Rzeczywistości wydają się najbardziej podatne na różnice. W ramach jednego projektu musiałem wykopać 150-letnią księgę tabel acos, aby uzyskać wartości do porównania w celu ustalenia, który procesor był „właściwy”. Wiele procesorów korzysta z aproksymacji wielomianowych dla funkcji wyzwalania, ale nie zawsze z tymi samymi współczynnikami.

Moja rekomendacja:

Niezależnie od tego, czy wybierasz blokowanie liczb całkowitych, czy synchronizację, postępuj z podstawową mechaniką gry osobno od prezentacji. Spraw, aby gra była dokładna, ale nie martw się o dokładność w warstwie prezentacji. Pamiętaj także, że nie musisz wysyłać wszystkich danych o sieci w sieci z tą samą liczbą klatek na sekundę. Możesz ustawić priorytety swoich wiadomości. Jeśli twoja symulacja jest dopasowana w 99,999%, nie będziesz musiał transmitować tak często, aby pozostać sparowanym. (Pomijając zapobieganie oszustwom.)

Jest ładny artykuł na temat silnika Source, który wyjaśnia jedną z metod synchronizacji: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Pamiętaj, że jeśli jesteś zainteresowany późnym dołączeniem, będziesz musiał ugryźć kulę i zsynchronizować.

Zauważ, że interesuje mnie głównie C #, który, o ile mogę powiedzieć, ma dokładnie takie same problemy jak C ++ w tym zakresie.

Tak, C # ma takie same problemy jak C ++. Ale ma też o wiele więcej.

Weźmy na przykład to zdanie Shawna Hawgravesa:

Jeśli przechowujesz powtórki jako dane wejściowe kontrolera, nie można ich odtwarzać na komputerach z różnymi architekturami procesorów, kompilatorami lub ustawieniami optymalizacji.

Jest „wystarczająco łatwy”, aby mieć pewność, że dzieje się tak w C ++. W języku C # będzie to jednak o wiele trudniejsze. To dzięki JIT.

Jak myślisz, co by się stało, gdyby interpreter uruchomił kod zinterpretowany raz, ale potem JIT zrobiłby to za drugim razem? A może interpretuje to dwukrotnie na czyimś komputerze, ale potem JIT?

JIT nie jest deterministyczny, ponieważ masz nad nim bardzo małą kontrolę. Jest to jedna z rzeczy, które rezygnujesz z korzystania z CLR.

I niech Bóg ci pomoże, jeśli jedna osoba używa .NET 4.0 do uruchomienia twojej gry, podczas gdy inna osoba używa Mono CLR (oczywiście używając bibliotek .NET). Nawet .NET 4.0 vs. .NET 5.0 może być inny. Potrzebujesz po prostu większej kontroli nad szczegółami platformy niskiego poziomu, aby zagwarantować tego rodzaju rzeczy.

Powinieneś być w stanie uciec od matematyki o stałym punkcie. Ale to jest o tym.

Po napisaniu tej odpowiedzi zdałem sobie sprawę, że tak naprawdę nie odpowiada ona na pytanie, które dotyczy konkretnie niedeterminizmu zmiennoprzecinkowego. Ale może i tak mu to pomoże, jeśli zamierza stworzyć grę sieciową w ten sposób.

Wraz z udostępnianiem danych wejściowych, które transmitujesz do wszystkich graczy, bardzo przydatne może być utworzenie i nadanie sumy kontrolnej ważnego stanu gry, takiej jak pozycja gracza, zdrowie itp. Podczas przetwarzania danych wejściowych upewnij się, że sumy kontrolne stanu gry dla wszyscy zdalni gracze są zsynchronizowani. Gwarantujesz, że masz problemy z synchronizacją (OOS) do naprawienia, a to ułatwi to - wcześniej zauważysz, że coś poszło nie tak (co pomoże ci zrozumieć kroki odtwarzania) i powinieneś być w stanie dodać więcej stan gry loguje się podejrzany kod, aby umożliwić przechwytywanie wszystkiego, co powoduje OOS.

Wydaje mi się, że pomysł z bloga, który jest nadal powiązany, wymaga okresowej synchronizacji, aby był wykonalny - widziałem wystarczająco dużo błędów w sieciowych grach RTS, które nie przyjmują takiego podejścia.

Sieci są stratne, powolne, mają opóźnienia, a nawet mogą zanieczyszczać dane. „Determinacja zmiennoprzecinkowa”, (co brzmi dość buzzworystycznie, by wzbudzić we mnie sceptycyzm) jest najmniejszym z twoich zmartwień w rzeczywistości ... szczególnie, jeśli zastosujesz określony czas. ze zmiennymi krokami czasowymi będziesz musiał interpolować między stałymi krokami czasowymi, aby uniknąć również problemów z determinizmem. Myślę, że zwykle to rozumie się przez niedeterministyczne zachowanie „zmiennoprzecinkowe” - tyle, że zmienne stopnie czasu powodują, że integracje się rozchodzą - nie ma to nic wspólnego z bibliotekami matematycznymi lub funkcjami niskiego poziomu.

Kluczem jest jednak synchronizacja.

Sprawiasz, że są deterministyczne. Dla świetnego przykładu zobacz Prezentację GDC Dungeon Siege, w jaki sposób sprawiły, że lokalizacje w świecie można połączyć w sieć.

Pamiętaj też, że determinizm dotyczy również zdarzeń „losowych”!