Peer-to-peer bezkonkurencyjne konkurencyjne gry losowe? [Zamknięte]


15

Zastanawiam się - czy kiedykolwiek powstały jakieś gry:

  • peer-to-peer bez jednego peera wyznaczonego jako host
  • konkurencyjny (brak współpracy, gracze grają przeciwko sobie)
  • możliwe do udowodnienia (nie ma możliwości oszukiwania żadnego gracza)
  • Nie udzielaj graczom więcej informacji niż potrzebują (na przykład nie ujawniaj tajemnic innych graczy nawet działającym aplikacjom)

Przykładem takiej gry może być gra w pokera, w której każdy gracz i jego gry będą mogli poznać tylko swoją rękę, ale nie ręce innych graczy bez polegania na tym, że którykolwiek z nich jest gospodarzem gry. Wiem, że istnieje kilka gier, które są możliwe do udowodnienia, ale wszystko, co wiem, istnieje w konfiguracji serwer-klient.


1
„peer-to-peer” i „nie ma możliwości oszukiwania żadnego gracza” - To niemożliwe.
Kikaimaru,

7
@Kikaimaru Mylisz się.
sam hocevar

@ Kikaimaru Właściwie mam pewne pojęcie, jak to może działać, ale chciałbym najpierw zapytać, zanim spróbuję wymyślić koło (ok, w tym przypadku może samolot).
ThePiachu

2
Bardzo wątpię, aby istniała metoda, która zapobiegałaby oszukiwaniu na poziomie, w jakim robi to klient-serwer. Gracze mogą na przykład wiedzieć, że inni gracze oszukują i przestają grać - bez żadnego kodu (lub możesz po prostu zatrzymać grę), ale czy to „nie ma możliwości oszukiwania”?
Kikaimaru,

@Kikaimaru Jeśli protokół wymusza poprawność, próba oszustwa jest taka sama, jak w ogóle nie gra - jeśli jest więcej niż dwóch graczy, inni gracze mogą nadal grać, a próba oszustwa zostanie zignorowana, podobnie jak nieprawidłowy pakiet IP być.
sam hocevar,

Odpowiedzi:


19

Nie wiem, czy takie gry zostały utworzone, ale na pewno zostały teoretyczne. Opublikowano kilka artykułów na ten temat. Możesz zbadać schematy zobowiązań, które wyjaśniają, w jaki sposób dwie niezgadzające się ze sobą strony mogą rzucić monetą, będąc fizycznie oddalone (patrz także ten artykuł z 1981 r .: Przerzucanie monet przez telefon ).

Jednym z bardzo dokładnych artykułów jest na przykład Cheat-Proof Peer-to-Peer Trading Card Games :

Proponujemy odporny na oszustwa protokół peer-to-peer do wdrażania internetowych gier karcianych. Rozbijamy działania wspólne dla wszystkich TCG i wyjaśniamy, w jaki sposób można je wykonać między dwoma graczami bez potrzeby sędziego zewnętrznego (co zwykle wymaga bezstronnego serwera). W każdej akcji graczowi albo uniemożliwia się oszustwo, albo jeśli oszukuje, przeciwnik będzie w stanie udowodnić, że to zrobił . Podsumowujemy, pokazując, w jaki sposób te metody są bezpieczne i jak można je mieszać z innymi stylami gier komputerowych i innymi grami peer-to-peer.

Również Cheat-Proof Playout dla scentralizowanej i peer-to-peer gier :

Proponujemy protokół, który ma udowodnione gwarancje przeciwdziałania oszustwom, jest możliwy do udowodnienia, bezpieczny i żywy , ale ponosi karę za wydajność. Następnie opracowujemy rozszerzoną wersję tego protokołu, zwaną synchronizacją asynchroniczną, która pozwala uniknąć kary, jest pozbawiona serwera, oferuje sprawdzalne gwarancje przeciwdziałania oszustwom, jest niezawodna w przypadku utraty pakietów i zapewnia znacznie zwiększoną wydajność komunikacji. Technika ta ma zastosowanie do typowych funkcji gry, a także technik klastrowania i opartych na komórkach w przypadku gier wieloosobowych. W szczególności zapewniamy protokół zerowej wiedzy, dzięki czemu gracze znajdują się w określonym przedziale, a poza tym nie mają pojęcia o odległości. Nasze twierdzenia dotyczące wydajności są poparte analizą wykorzystującą symulację opartą na rzeczywistych śladach gry.


1
Zobacz także stronę Mental Poker na Wikipedii - en.wikipedia.org/wiki/Mental_poker . Na forum Bitcoin odbyła się dyskusja na temat potencjalnych zastosowań tego bitcointalk.org/index.php?topic=1487.0
liamzebedee

Świetny link @liamzebedee. Ten artykuł ma właściwie dokładny algorytm, dzięki któremu poker działa dobrze w sieci peer-to-peer.
captncraig

4

Chociaż nie jest to gra losowa, tworzę grę AIR, która jest zbliżona do twoich wymagań.

  1. Opracowany przy użyciu protokołu multiemisji Flash RTMFP. Żaden klient nie jest uważany za hosta.
  2. System konkurencji oparty na fizyce.
  3. Weryfikuje dane wejściowe przeciwnika i dyskwalifikuje grę na podstawie nieprawidłowych danych.
  4. Nie przesyła niektórych informacji fizycznych z powodów związanych z przepustowością / opóźnieniami (spowodowało to również wyłączenie niektórych metod oszukiwania).

Należy jednak pamiętać ...

Uważam „brak możliwości ... oszukiwania” za fałszywe oświadczenie. Jeśli nie kontrolujesz wszystkich aspektów (sprzętu i oprogramowania), oszustwo jest możliwe.

Chociaż nie jest to gra, myślę, że sieć Bitcoin jest doskonałym przykładem tego, czego szukasz.

Edytować

Rozbuduję trochę twoje główne pytanie.

Po pierwsze, nie widzę żadnej gry wymagającej „możliwych do udowodnienia” warunków bez pewnego poziomu autorytatywnych wymagań. Od tablic wyników po mikropłatności, scentralizowane systemy i uprawnienia idą w parze.

Po drugie, najlepszą przykładową grą, jaką mogę wymyślić, są wczesne gry Pokemon. Chociaż logistyka wewnętrznej sieci mogła nie być peer-to-peer, jest zgodna z tą samą zasadą.

Wreszcie, platformy mobilne są specjalnie przystosowane do gier peer-to-peer. Uważam, że w tej dziedzinie bardzo brakuje, dlatego właśnie opracowuję linię gier peer-to-peer.


Tak, mogę mieć trochę doświadczenia z Bitcoinem ... bitcoin.stackexchange.com/users/323/thepiachu ;)
ThePiachu

1

Kilka elementów, które mogą pomóc, w zależności od przypadków użycia:

Jeśli potrzebujesz uzyskać równoczesny wkład od użytkowników bez możliwości przedwczesnego wykorzystania informacji na ich korzyść, możesz skorzystać ze schematu zobowiązań. Zasadniczo jest to:

  1. Obaj gracze zapewniają skrót akcji, którą chcą podjąć.
  2. Po tym, jak obaj podadzą swoje zobowiązanie, obaj mogą podać swoje działania w postaci zwykłego tekstu.
  3. Zwykły tekst można porównać do skrótów, aby sprawdzić, czy nikt nie zmienił odpowiedzi po zapoznaniu się z działaniem drugiej osoby.

Można to wykorzystać do różnych rzeczy, w tym do wspólnej liczby losowej (obie zapewniają liczbę całkowitą poprzez zobowiązania i xor razem po udostępnieniu, aby uzyskać wspólną wartość).

Nie jest to jednak wystarczające w przypadku gry takiej jak poker, ponieważ wymaga, aby karty były znane tylko jednej osobie, przy jednoczesnym dalszym losowaniu ze wspólnej talii. Wikipedia ma dość dobry algorytm wspólnego tasowania za pomocą schematu, w którym obaj gracze szyfrują każdą kartę indywidualnie wiele razy. To powoduje sytuację, w której do odszyfrowania dowolnej karty wymagane są 2 klucze, a obaj gracze mają 1. W artykule wspomniano o problemach z wydajnością, ale nie sądzę, aby AES lub podobny był zbyt drogi w skali wymaganej dla pokera 2-osobowego.

Gdybym projektował algorytm, kazałbym graczom obliczyć losową wartość na początku gry, aby użyć jej jako zalążka dla wszystkich pozostałych operacji i udostępnić skrót tej wartości. W ten sposób mogą dzielić się tą wartością po grze i możesz sprawdzić, czy postępowali zgodnie z protokołem, bez shenaniganów.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.