Autor Wątek: Gospodarka losowością - schemat  (Przeczytany 2433 razy)

Offline Szmer

  • Użytkownik

# Marzec 21, 2014, 19:56:40
Technologie: używam do komunikacji serwer-klient biblioteki Socket.io we frameworku Sails na Node.js (czyli JavaScript), gra to leaderofnation.com (ogłaszałem się kiedyś na tym forum), ale to wszystko raczej drugorzędne, bo mam problem ogólny.

Gra to RTS i właściwie jedyną chwilą, kiedy wchodzi czynnik losowy, są bitwy. Bitwy toczą się technicznie w turach, obliczanych co jakąś sekundę czy coś koło tego. Moje motywacje:
1. Chcę mieć jakieś możliwości walki z ewentualnym czitowaniem.
2. Najchętniej przerzuciłbym generowanie pseudolosowych z serwera na klienta.

I widziałbym to tak:
1. Kiedy klient (klienci) potrzebują pseudolosówek, wysyła do serwera wiadomość przez socket z tyloma liczbami, ilu potrzebuje ORAZ numerem bitwy, np. (dwie potrzebne liczby):
socket.emit("rand", [3 /* numer bitwy = regionu, gdzie toczy się bitwa */,Math.random(), Math.random()])2. a) Serwer w wiadomości zwrotnej przesyła klientowi żądaną liczbę liczb. Jeżeli gracz bije się akurat z AI, serwer w praktyce odbija wiadomość klienta. Jeżeli zaś walczy dwóch lub więcej graczy, serwer decyduje, który zestaw rozesłać jednocześnie wszystkim na podstawie jakiegoś prostego mechanicznego algorytmu (choćby i na zmianę/po kolei).
b) Jednocześnie wszystkie liczby wygenerowane i przysłane przez klienta są zrzucane (tymczasowo) do bazy.
3. Każdy klient oblicza wynik danej tury bitwy na podstawie nie własnych liczb, ale tych przysłanych z serwera. Ponieważ algorytmy obliczania strat bitewnych są stałe, wszędzie wychodzi to samo. (Wyniki - tzn. liczba jednostek padłych w boju - też są raportowane do centrali, ale to całkiem inna opowieść).

Otóż po zakończeniu sesji (rozgrywki) serwer obliczałby na podstawie wszystkich pseudolosówek gracza jakiś "współczynnik losowości" (myślę, że przy 50 czy 100 liczbach na sesję ma to już sens). Dopiero ten współczynnik trafiałby do bazy danych na stałe i mógł być jakoś wykorzystywany. Czy znacie jakiś gotowy algorytm sprawdzający podobieństwo zestawu liczb do rozkładu losowego? Może nawet ktoś to zaimplementował w JS? Jeszcze gdyby był mało obciążający komputacyjnie, byłoby bosko.

I w ogóle, co sądzicie o moim podejściu? Słabości? Punkty zaczepienia dla cziterów? (Rozumiem, że moja gra zapewne nie będzie na tyle popularna, żeby ktoś aż oszukiwał, ale teoretycznie chyba też to jest ciekawe :D ).

Aha, i temat "prawdziwej losowości" średnio mnie interesuje w tym kontekście :P

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

  • +2
# Marzec 21, 2014, 20:59:18
Cytuj
I w ogóle, co sądzicie o moim podejściu?
Po co w ogóle klient generuje te losowe liczby? Generuj je na serwerze i będzie spokój.

Offline Xender

  • Użytkownik

# Marzec 22, 2014, 23:24:20
Może nawet ktoś to zaimplementował w JS? Jeszcze gdyby był mało obciążający komputacyjnie
0. "Obliczeniowo". Kalka całkowicie bezpodstawna i błędna.
1. JS (język interpretowalny) i minimalizacja obciążenia obliczeniowego? Sprzeczne założenia.

Generalnie cała logika, która ma wpływ na wynik, powinna być liczona na serwerze. Ale nie ma też potrzeby wysyłać do klienta liczb pseudolosowych z serwera - wystarczy upewnić się, że algorytm jest ten sam i zsynchronizować seedy.
Chociaż wtedy potencjalny wektor ataku wygląda tak, że atakujący może podejrzeć, jakie liczby wygeneruje serwer np. dla innego gracza. Na to można by szukać rozwiązania (seed generatora per gracz i jeden dla rzeczy "systemowych"?), ale...

Po co serwer w ogóle ma wysyłać klientom pseudolosówki? Niech liczy logikę na podstawie swojego generatora i śle klientom tylko już coś znaczące zmiany - czyli np. "jednostka X traci Y HP".

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Marzec 23, 2014, 00:06:43
Cytuj
Chociaż wtedy potencjalny wektor ataku wygląda tak, że atakujący może podejrzeć, jakie liczby wygeneruje serwer np. dla innego gracza.
To znaczy mniej więcej tyle, że masz słaby generator liczb losowych. Wystarczy użyć generatora o długim wektorze stanu (np. Mersenne Twister) i w razie czego ewentualnie jeszcze część z tego stanu reseedować co jakiś czas (np. na podstawie systemowej liczby mikrosekund).

Cytuj
Po co serwer w ogóle ma wysyłać klientom pseudolosówki? Niech liczy logikę na podstawie swojego generatora i śle klientom tylko już coś znaczące zmiany - czyli np. "jednostka X traci Y HP".
Po to, żeby nie musiał liczyć logiki. Jeżeli liczby losowe będziesz generował na serwerze, to odpada manipulacja losowością (przy każdej próbie czeka Cię desync).

Offline Xender

  • Użytkownik

# Marzec 23, 2014, 10:03:01
To znaczy mniej więcej tyle, że masz słaby generator liczb losowych. Wystarczy użyć generatora o długim wektorze stanu (np. Mersenne Twister) i w razie czego ewentualnie jeszcze część z tego stanu reseedować co jakiś czas (np. na podstawie systemowej liczby mikrosekund).
Przecież to dotyczy sytuacji, gdy serwer explicite synchronizuje seed z klientem. To kwestia założenia, a nie implementacji.

Po to, żeby nie musiał liczyć logiki. Jeżeli liczby losowe będziesz generował na serwerze, to odpada manipulacja losowością (przy każdej próbie czeka Cię desync).
Żeby który nie musiał liczyć logiki? Tak czy inaczej powinien liczyć ją serwer, chyba że masz pomysł na kryptograficzne sprawdzenie na serwerze, że klient wyliczył ją poprawnie (a to scenariusz chyba z kosmosu).

A skoro serwer ma już liczyć logikę jako zabezpieczenie przed cheatami, to może wysłać klientom gotowy wynik. No chyba, że przesłanie pół-gotowego wyniku i doliczenie na kliencie pozwoli znacząco zmniejszyć bandwidth.

Offline deadeye

  • Użytkownik

  • +1
# Marzec 23, 2014, 10:55:09
1. JS (język interpretowalny)
Cały JS Node i większość przeglądarek kompilują JS do kodu natywnego.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Marzec 23, 2014, 12:26:45
Cytuj
Żeby który nie musiał liczyć logiki? Tak czy inaczej powinien liczyć ją serwer, chyba że masz pomysł na kryptograficzne sprawdzenie na serwerze, że klient wyliczył ją poprawnie (a to scenariusz chyba z kosmosu).
Wystarczy że wszyscy klienci liczą logikę i sprawdzają, czy któryś się nie rozsynchronizował.

Offline Szmer

  • Użytkownik

# Marzec 23, 2014, 13:05:21
Przepraszam, że tak późno, byłem zajęty.

Do wszystkich, którzy radzą mi przerzucić wszystko na serwer - wezmę pod uwagę argumenty, ale serwer będzie najpewniej mocno obciążony AI. Dlatego chcę go jak najbardziej odchudzić.

Cytat: Xender
0. "Obliczeniowo". Kalka całkowicie bezpodstawna i błędna.
Łoo, jakie zagłębie puryzmu :) Computo, computare znaczy po łacinie "zrachować, obliczyć", więc chyba wolno używać tego jako synonimu.

Cytat: Xender
1. JS (język interpretowalny) i minimalizacja obciążenia obliczeniowego? Sprzeczne założenia.
Śmiem się nie zgodzić. Przy stosunkowo wolnym języku rzeczy proste i tak powinny obliczać się szybciej (choć na pewno wolniej niż przy szybszym języku). Poza tym na Node.js i na moim frameworku chyba nie do końca taki interpretowany. Z tego co się zorientowałem, kod kontrolerów jest przynajmniej trzymany w cache.
O, zresztą deadeye zwrócił na to uwagę.

Cytat: Krzysiek K.
Ale nie ma też potrzeby wysyłać do klienta liczb pseudolosowych z serwera - wystarczy upewnić się, że algorytm jest ten sam i zsynchronizować seedy.
No właśnie mi się nie chce za bardzo wychodzić poza proste Math.random(). Chcę ten projekt doprowadzić w miarę szybko do używalności. Nie zależy mi też (to ogólnie) na rozwiązaniach idealnych, tylko w miarę trudnych do zepsucia.

Co do szczegółów waszych propozycji, muszę przemyśleć, doszukać i może się jeszcze odniosę.
« Ostatnia zmiana: Marzec 23, 2014, 13:08:41 wysłana przez Szmer »

Offline castro12321

  • Użytkownik

# Marzec 23, 2014, 16:42:46
serwer będzie najpewniej mocno obciążony AI. Dlatego chcę go jak najbardziej odchudzić.

Jeżeli będzie obciążony AI, to znaczy, że reszta gry nie będzie.
Zamiast wymyślać jakieś rozwiązania z kosmosu, proponowałbym obliczać wszystko na serwerze tak jak wyżej padły propozycje.

Nie wiem jak wygląda logika gry, ale chyba nie jest okropnie skomplikowana, więc zamiast ją komplikowaćoptymalizować zajmij się optymalizacją AI.
Lepiej zoptymalizować AI z 90% wykonania do 80, niż logikę z 10% do 9. ;)
« Ostatnia zmiana: Marzec 23, 2014, 18:08:32 wysłana przez castro12321 »

Offline Szmer

  • Użytkownik

# Marzec 23, 2014, 19:22:37
Ech, no niby słuszna uwaga (to do castro). Ale z kolei z AI chcę sobie poszaleć, bo planuję wykorzystać okazję (gra online, system rozgrywek - łatwa definicja sukcesu) i zrobić system samouczący się. Może o tym później na forum napiszę.

Bo ponownym zbadaniu sprawy skłaniam się ku wykorzystaniu Mersenne Twistera (gotowej implementacji) po stronie klienta z rozsyłaniem ziarna przez serwer. Pojawia się z kolei problem, kiedy to ziarno rozsyłać, bo z założenia nowy gracz może dołączyć do pokoju (wziąć państwo kierowane przez AI) w dowolnym momencie. Łatwo o rozsynchronizowanie się. Z kolei generowanie nowego ziarna co turę, czyli jak mówiłem co sekundę, wygląda na trochę głupi pomysł - to już równie dobrze można by wysyłać gołe pseudolosówki. Pewnie zrobię tak, że będzie oddzielne ziarno dla każdej bitwy. Nawet można by to wygodnie przechowywać, bo bitwy to obiekty.

Offline Xender

  • Użytkownik

# Marzec 23, 2014, 20:54:29
Łoo, jakie zagłębie puryzmu :) Computo, computare znaczy po łacinie "zrachować, obliczyć", więc chyba wolno używać tego jako synonimu.
"Zagłębie" od razu... Potworek "komputacyjnie" ma po prostu bardzo dobry, poprawny polski odpowiednik. W IT jest bardzo dużo pojęć, których lepiej nie tłumaczyć i użyć słowa angielskiego lub kalki, ale to zdecydowanie nie jest jednym z nich.