Czy można obliczyć lub matematycznie udowodnić, czy gra jest zrównoważona / sprawiedliwa?


40

To pytanie nie dotyczy gier wideo, ale ogólnie gier. Wczoraj poszedłem na targi gier planszowych i zadałem sobie pytanie, czy istnieje sposób na obliczenie uczciwości gry. Pewnie, niektóre z nich wymagają sporej części szczęścia, ale można obliczyć, czy jakaś postać jest obezwładniona. Zwłaszcza w grach fabularnych i grach karcianych. Jak na przykład twórcy „Magic: The Gathering” mogą upewnić się, że nie ma „jednej karty, która pokonałaby wszystkie”, biorąc pod uwagę imponującą liczbę dostępnych kart?


2
Na marginesie, istnieją gry, w których gra wyłącznie w celu wygrania sprawia, że ​​gra jest mniej przyjemna dla wszystkich . Dawno, dawno temu jest jednym z takich szczególnie godnych uwagi przykładów, ale ogólnie cała „społeczna” kategoria gier jest ich pełna.
Martin Sojka

3
Twórcy MtG przeprowadzają wiele testów, a nawet jeśli to nie pomaga (czasem są kombinacje pozwalające wygrać w pierwszej turze) , banują karty z turniejów (ostrzeżenie, TVTropes).
liori

1
Uruchom szereg symulacji / zbierz dane. W ten sposób równoważą się w StarCraft 2 ... Mierzą, które jednostki są najczęściej używane, a która rasa wygrywa najwięcej. Gromadzenie danych jest kluczem do złożonych gier, a statystyki są tak samo dobre jak matematyka. Jeszcze lepiej, powiedziałbym, ponieważ uchwycisz również efekty psychologiczne. Właśnie dlatego nie ma tak wielu matematyków grających w pokera, jak można się spodziewać.
Per Alexandersson,

Niektóre z najlepszych niemieckich gier planszowych są opracowywane przez matematyków (np. Reiner Knizia ), którzy specjalizują się w teorii gier, i to pokazuje. Szczególnie gry Knizii są wyjątkowo dobrze wyważone.
Konrad Rudolph,

Do tej pory twórcy MTG często ponieśli porażkę i wypuścili karty, które okazały się znacznie obezwładnione (często z powodu interakcji z innymi kartami, których nie brali pod uwagę), więc musieli zostać zbanowani w oficjalnej grze turniejowej.
Philipp

Odpowiedzi:


34

Tak, jest to teoretycznie możliwe - to dobra część teorii gier, która dotyczy tego tematu.

Jest to jednak rzadko praktyczne , a nawet wtedy głównie dla gier, które nie wymagają randomisera (Chess, Reversi, Go i tak dalej). Kombinatoryczna eksplozja zapewnia, że ​​teoretyczny czas potrzebny na takie dowody dla bardziej złożonych gier, takich jak Magic the Gathering, może łatwo być o kilka rzędów wielkości dłuższy niż obecny wiek wszechświata.

Ostatecznie, w przypadku każdej nietrywialnej gry prawdopodobnie będziesz musiał porzucić pojęcie dowodzenia równowagi lub uczciwości gry i zamiast tego stosować kombinację zdrowego rozsądku, instynktów projektantów, ponownego użycia systemu gry i testów.


11
Dodaj do tego, że gra, która została udowodniona jako uczciwa, niekoniecznie jest postrzegana przez graczy jako uczciwa. I to percepcja jest naprawdę ważna przez większość czasu.
Nevermind

4
Również ani Chess, ani Go nie zostały „udowodnione” jako uczciwe. W szachach nie wiadomo, czy biały gracz ma przewagę. W Go różne kraje mają różne komi , więc Go nie może być uczciwy w co najwyżej we wszystkich oprócz jednego.
BlueRaja - Danny Pflughoeft

4
@BlueRaja: Teoria gier absolutnie daje nam narzędzia do analizy uczciwości w grach, np. Równowagę Nasha. Jeśli wypłaty są równe, gra jest sprawiedliwa. Jeśli wypłaty są nierówne, gra jest niesprawiedliwa. Problem polega na tym, że nie wszystkie gry mają unikalną równowagę Nasha, a najciekawsze gry nie mają obliczeniowej, nawet jeśli mają taką (i to prawdopodobnie z definicji „interesującej”). Ale teoria gier absolutnie obejmuje tę domenę.

5
W rzeczywistości nawet jeśli gra jest całkowicie losowa, można udowodnić, że jest uczciwa. Na przykład rzuć monetą: wygrywam głowy, wygrywasz ogony. Matematyczna definicja uczciwości to E (ProfitOrLoss) = 0 w długim okresie. Joe Wreschnig powyżej ma najdokładniejszy komentarz tutaj.
kfmfe04

1
@ BlueRaja-DannyPflughoeft: ponownie różni Komi w Go: Pamiętaj, że punktacja również jest nieco inna, więc porównanie ma sens tylko przy rozważaniu obu efektów.
Pieter Geerkens,

5

Krótka odpowiedź: każda gra ze skończoną, nawet jeśli nieokreśloną liczbą dostępnych ruchów, ma skończoną liczbę możliwych gier. Każda gra o skończonej „złożoności drzewa gry” może teoretycznie przeanalizować wszystkie możliwe gry, aby ustalić, czy liczba gier, w których wygrałby każdy gracz, jest równa.

Mówiąc wprost: jeśli Gracz 1 wygra dokładnie połowę wszystkich możliwych gier, gra jest zrównoważona. Jeśli nie jest to prawdą, gra jest stronnicza w stosunku do jednego gracza lub drugiego.

Jednak ta prosta zasada może być całkiem niewykonalna w praktyce. Go, na przykład, ma złożoność drzewa gry rzędu 10 ^ 170 możliwych gier, więcej niż liczbę atomów uważanych za istniejące w znanym wszechświecie. Uważa się, że niemożliwe jest skompilowanie wyczerpującego drzewa gry. Jednak biblioteka gier, w które gra się i nagrywa, jest liczona w milionach, i sugeruje, że gra ma „przewagę w pierwszym ruchu” (którą zwykle łagodzi 1,5 punktu „komi” przyznanego Białemu).

Przeciwnie, nawet biorąc pod uwagę dużą złożoność drzewa gry, wszystkie gry M, N, K (plansza o szerokości M, wysokości N, w której celem gracza jest utworzenie rzędu K elementów poprzez umieszczenie i nigdy przenoszenie / usuwanie ich) są rozwiązane, ponieważ istnieje skrót; całe „gałęzie” drzewa gry można zidentyfikować jako zawsze powodujące przegraną jednego lub drugiego gracza. Pozostałe gałęzie są zgodne ze wzorem, który można zidentyfikować. Kółko i krzyżyk jest oczywistym przykładem; oprócz tego, że możliwe jest tylko 300 000 możliwych gier, jest tylko 16, w których jeden gracz lub drugi nie wykonuje ruchu, który oczywiście pozwoli drugiemu graczowi wygrać w następnym ruchu. Drzewo gry zaczyna się od małych i staje się mniejsze, gdy weźmie się pod uwagę gry, które gracze mogą stworzyć.

W grach z elementem szczęścia złożoność drzewa gry jest zawyżona ponad liczbę decyzji dostępnych dla każdego gracza. Ponieważ w grze nie ma już „doskonałej informacji”, podobnie jak w szachach, warcabach, Go, Othello itp., Gracz, który grał doskonale, podając znane informacje, wciąż przegrywa z grą element losowy. Te gry nie mają „rozwiązania”; jednak zwykle istnieje jeszcze skończone drzewo gry, więc teoretycznie gry można nadal analizować wyczerpująco. Nadal nie jest to zazwyczaj możliwe; zamiast tego gry z prawdopodobieństwem są analizowane w sposób probabilistyczny w celu zidentyfikowania strategii „najlepszego zakładu”, a jeśli strategie te faworyzują gracza, który ich używa, niezależnie od strategii stosowanej przez innego gracza (w tym tę samą strategię),

Zasadniczo obowiązuje następująca zasada: jeśli konstrukcja gry z natury prowadzi do nierówności w jednym lub więcej z poniższych elementów, gra ma tendencję do:

  • Liczba całkowitych ruchów dla każdego gracza
  • Liczba dostępnych ruchów w danym momencie, które pozwolą co najmniej jednemu ruchowi tego gracza
  • Początkowa siła sił graczy
  • Dostęp do skończonych zasobów lub obszarów o określonym znaczeniu strategicznym

Teraz projekt gry może wprowadzać jedną nierówność, ale próbować zrekompensować inną. Lub projekt gry może dopuszczać losowość w obszarach, które mogą powodować stronniczość, co oznacza, że ​​jedna gra może być stronnicza, podczas gdy inna jest bardziej sprawiedliwa (gry z losowymi planszami mogą to wykazywać). W takich przypadkach tylko analiza empiryczna gier między graczami o mniej więcej równej sile w dłuższej perspektywie może wykazać jakiekolwiek uprzedzenie.

Więcej dyskusji na temat stronniczości w grach planszowych można znaleźć na forach http://www.geekdo.com ; odbyło się kilka dyskusji na temat wykazanego uprzedzenia w grach oraz ogólnie, jak uniknąć tego uprzedzenia w rozwoju gier.


3

Wydaje mi się, że nie ma gotowego wzoru matematycznego, który oceniałby uczciwość gry ze względu na to, że każda gra jest tak inna i złożona.

Nie można tak naprawdę porównywać różnych parametrów gry i tworzyć pewnego rodzaju oceny siły tego, jak dobra jest postać (chyba że gra jest bardzo prosta), ponieważ wszystkie one wpływają na twoją rozgrywkę w różny sposób i zależą od tego, jak są zaimplementowane (np. Jak możesz oceniasz, jak siła odnosi się do witalności? Jak przypisujesz wartość liczbową specjalnemu atakowi postaci?).

Musisz przetestować swoją grę. Wiele . Zagraj w grę samodzielnie i spraw, aby inni w nią grali, i przechowuj wyniki bitwy / gry w pliku, aby tworzyć statystyki i oceniać, jak często wygrywają określone postacie, w jakich okolicznościach itp. Następnie upewnij się, że wprowadziłeś jakiś sposób sprawdzania powtórek lub przeanalizuj rozgrywkę, aby zobaczyć, dlaczego taka postać jest obezwładniona i odpowiednio zastosuj zmiany.

Naprawdę nie masz innej opcji niż testowanie. To jeden z powodów, dla których istnieją bety (np. Starcraft2 jako beta dał Blizzardowi możliwość zrównoważenia 3 wyścigów w oparciu o wyniki gry).

Podsumowując, zagraj w swoją grę i spraw, aby inni w nią grali (rozpoczęcie wersji beta jest opcją). Sprawdź, dlaczego gra jest niezrównoważona poprzez powtórki lub automatyczną analizę, i zmień to, co należy odpowiednio zmienić. To jedyny sposób, aby zbliżyć się do uczciwości.


1
+1 za przetestowanie gry . Testy beta są ważne w grach wideo i grach planszowych, im więcej osób testuje Twoją grę, tym większe prawdopodobieństwo, że ktoś znajdzie tę zepsutą kartę lub zaklęcie, które rujnuje wszystko.
thedaian

2
Do kogo głosował, dlaczego?
Jesse Emond,

1
Testowanie jest na miejscu. Wprowadzić nową kartę? Przeprowadź go przez wielkoskalową symulację losowych talii, aby zobaczyć, jak często była częścią zwycięskiej talii. Jeśli większość wygranych gier była związana z nową kartą, należy ją stonować i spróbować ponownie.
waterwizard11

2

Aby udowodnić, że gra jest zrównoważona lub sprawiedliwa, musisz najpierw określić, co oznacza zrównoważona lub uczciwa. Są to raczej niejasne terminy, które mogą obejmować szereg rzeczy, na przykład często przyjmuje się, że „równowaga” gry oznacza:

  • każda z kilku różnych stron ma taką samą szansę na wygraną
  • postęp w grze staje się coraz trudniejszy
  • decyzje podejmowane w grze oferują identyczne wskaźniki kosztów / wypłat w niektórych / większości / wszystkich przypadkach

I tak dalej.

Ogólnie jestem fanem matematycznie udowadniających takie rzeczy, ale aby udowodnić coś za pomocą logiki lub testów, najpierw musisz to jasno zdefiniować. Niektóre aspekty równowagi są łatwe do przetestowania za pomocą matematyki, jeśli potrafisz poprawnie zrozumieć zasady gry. Inni są znacznie trudniej osądzać bez przeprowadzania testów empirycznych. Główny problem polega na tym, że większość projektantów gier nie do końca rozumie mechanikę swojej gry, ponieważ zazwyczaj łączą reguły gry w otaczającą symulację, a ta ostatnia jest bardzo trudna do dokładnego modelowania.


1

Teoretycznie jest to możliwe, ale w przypadku większości gier jest niezwykle trudne, więc można je uznać za niemożliwe.

Jedno podejście: Konwertuj grę do normalnej postaci. Gra w normalnej formie to zestaw strategii dla każdego gracza i funkcji, który mówi, jak dobry jest wynik przy danej kombinacji wyborów. Czynnik losowy można modelować jako innego gracza.

Następnie możemy szukać strategii dominujących / zdominowanych (rzeczy, które ZAWSZE należy robić i rzeczy, których NIGDY nie należy robić). Gra jest co najmniej interesująca, jeśli nie zawiera dominujących strategii.

Następnie możemy spojrzeć na to, co każdy gracz może sobie zagwarantować. dla każdego „MOJEGO” wyboru, spójrz na najgorszy możliwy wynik i wybierz wybór, który ma to, co najlepsze.

Jeśli różni się bardzo między graczami, w grze jest coś zgniłego.

Są inne rzeczy, na które warto zwrócić uwagę (dominująca strategia mieszana (wybieranie każdego wyboru z pewną dozą prawdopodobieństwa), równowaga Nash (kombinacje, które gdy wszyscy gracze wiedzą, że zrobią inni, są lokalnie najlepsze dla wszystkich)).

Ale pierwszy krok jest bardzo skomplikowany dla większości gier, więc zwykle nie jest tak przydatny. Ale można go użyć, jeśli uda się oderwać skomplikowane szczegóły / zastąpić strategie rozpoznawalnymi zestawami strategii (np. Początkowe zlecenia budowania) i uzyskać statystyczną aproksymację z faktycznie granych gier i może powiedzieć coś o problemach w grze. Myślę, że coś takiego jak ten blizard robi z SC.

Inną formą gry jest gra, w której gracze na zmianę wiedzą o wszystkim, co robią (szachy). Tam możesz spróbować wyszukać strategię dominującą, przeszukując stanowe drzewo gry (i zwykle jest to OGROMNE, więc znowu zbyt skomplikowane w użyciu). Wiele gier nie ma całkowitej wiedzy i to bardzo komplikuje sytuację.

Inne podejście, spójrz na rzeczy w grze i spróbuj je porównać.

Inne podejście: do walki drużynowej (szczególnie z dużą liczbą uczestników) możesz spróbować użyć siły w symulacji siły (nigdy jej nie użyłem i wymaga to dużej matematyki (równań różniczkowych) i ciężkiej pracy, aby przekształcić grę w model aproprytowy).

Więc mój wniosek, wiele rzeczy można zrobić, aby zrównoważyć podsystemy gry, a kiedy gra się kończy (i podczas betatestu), wiele można zrobić, analizując wyniki, ale jeśli nie zrobisz tego samego, prawie niemożliwe jest udowodnienie, że gra jest zrównoważona .

PS: Możesz zamaskować identyczność, zamieniając jeden atrybut na wielokrotność, które razem można wykorzystać do obliczenia atrybutu początkowego, i czyniąc wszystko znacznie bardziej losowym, aby gracze nie widzieli tej identyczności (

Strzeż się, że łatwo popełnisz błąd (np. Szybkie małe ataki vs. duże wolne ataki), ponieważ 18 rzutów przez d6 -18 daje wyniki 0-90, 10 rzutów przez d10-10 daje wyniki 0-90 1 rzut przez d91-1 daje wyniki 0–90, ale wszystkie mają różne rozkłady.

PS2: Pewien mądry człowiek powiedział, że rzeczywista równowaga nie jest ważna, równowaga postrzegana jest.


Dominująca koncepcja strategii jest bardzo ważna. Istnienie dominującej strategii w każdej sytuacji pociąga za sobą nieodłączną niesprawiedliwość, chociaż zwykle powoduje to po prostu nadmiarowość w projekcie, a nie problem równowagi jako takiej. Ale projektant musi być w stanie unikać dominujących strategii, aby każdy element miał szansę na jasny cel.
Kylotan

Jednej rzeczy zapomniałem: istnienie dominującej strategii nie musi stanowić problemu, o ile jej realizacja jest naprawdę trudna, nawet jeśli gracz WIEDZIE. Uproszczony przykład, strzelanie w głowę jest strategią dominującą w FPS, ale wielu graczy wybiera środek ciężkości, ponieważ jest łatwiejszy do trafienia, ale optymalny bot zawsze wybierałby strzał w głowę.
user470365 22.10.11

1

Wiele dobrych odpowiedzi na temat uzyskania poprawnej matematycznie odpowiedzi, ale spróbuję pod innym kątem: jeśli twój kod na to pozwala, możesz symulować bardzo dużą liczbę gier, a następnie sprawdzić, czy istnieje strategia (lub strategie), które wygrywać zbyt często.

Być może znasz symulacje Monte-Carlo lub algorytmy genetyczne. Pomysł tutaj był związany. Aby zagrać w grę, musisz mieć AI i kilka kluczowych pomiarów. Często pozwalasz sobie na AI w dużym turnieju, z różnymi zmiennymi początkowymi i mierzysz wyniki.

Zawsze chciałem spróbować takiego podejścia do zrównoważenia klas / broni, to byłaby niezła frajda.


1

Z perspektywy teorii obliczeń wydaje się, że odpowiedź na to pytanie nie jest w ogóle możliwa . Zadaje pytanie o właściwość programu i może mieć zastosowanie twierdzenie Rice'a . Zakładam, że gra odnosi się do programu napisanego w języku Turing Complete , takim jak c ++. Zakładam również, że aby obliczyć lub udowodnić, że gra jest uczciwa, oznacza to, że istnieje program c ++, który czyta program c ++ (program do gry) i kończy się w skończonym czasie dla wszystkich możliwych danych wejściowych , z tylko dwoma wyjściami, uczciwymi lub niesprawiedliwe.

Szybkie wyszukiwanie pokazuje, że można mieć deterministyczną, ale nierozstrzygalną grę, patrz slajd 7 tutaj i International Journal of Game Theory: Niektóre nierozstrzygnięte określone gry:

„Maszyny komputerowe wykorzystujące algorytmy grają w gry, a nawet uczą się w nie grać. Jednak nieodłączne właściwości skończoności algorytmów nakładają ograniczenia na możliwości grania w maszyny. M. Rabin zilustrował to ograniczenie w 1957 r., Konstruując dwuosobową grę typu wygrana-przegrana z rozsądnymi regułami, ale bez obliczalnych strategii wygranych ”.

Ludzki mózg jest najwyraźniej „potężniejszy” niż komputery, ponieważ możemy zdobywać i stosować wiedzę z przeszłości, a czasem wydaje się, że zaprzeczamy wynikom takim jak problem Halting , znajdując nieskończone pętle w programach. Jednak sposób, w jaki to robimy, nie jest dobrze znany i nie może być zapisany precyzyjnie i jednoznacznie w algorytmie.


0

Naprawdę chciałem skomentować odpowiedź Martina Sojki, ale nie mam reputacji. Ma rację, że teoria gry obejmuje obliczanie rzetelności gry (na przykład otwarte pytanie, czy w grze w szachy, w której zarówno biały, jak i czarny grali idealnie, czy byłby remis).

W przypadku MtG może być bardzo niemożliwe, aby obliczyć, czy jest to uczciwe, ale nikt nie udowodnił matematycznie, że obliczenia byłyby niemożliwe.

Można w prosty sposób udowodnić, że jest sprawiedliwy - jeśli los jest pierwszy, a wszyscy grają według tych samych zasad, to jest sprawiedliwy. Może się zdarzyć, że ten, kto pójdzie pierwszy, zawsze wygrywa, ale jeśli kto pójdzie pierwszy, jest sprawiedliwy, gra jest sprawiedliwa.


Usuń 109 znaków, a przekonwertuję to na komentarz.
Jesse Dorsey

-2

Co należy rozumieć przez „sprawiedliwy” jest niejasne, pozwól mi wyjaśnić:

Rozważ grę Rock-paper-cissors (http://en.wikipedia.org/wiki/Rock-paper-scissors): według ciebie to sprawiedliwe, tak sądzę (według mnie również).

Rozważmy teraz grę: kamień-papier-nożyce-studnia, w której studnia bije kamień i papier, a studnia przegrywa z papierem. Niezrównoważony, prawda? Studnia wydaje się dość obezwładniona: bije dwie bronie i przegrywa z jedną.

Można jednak powiedzieć, że wcale nie jest on obezwładniony: ponieważ jeśli wiesz, że twój przeciwnik chętniej skorzysta ze studni, ponieważ bije dwie bronie, możesz po prostu działać częściej, wybierając papier.

Istnieje więc odpowiedź na potencjalnie dobrze obezwładnione: po prostu częściej wybieraj papier. Ale wtedy wiesz, że twój przeciwnik może to wiedzieć i może dość często korzystać z papieru, więc uważasz, że powinieneś częściej używać nożyczek. Itd. Naprawdę nie obezwładniony, po prostu inna gra z różnymi zasadami.

Poleciłbym przeczytać o teorii gier, a zwłaszcza o grach z niedokładnymi informacjami (http://en.wikipedia.org/wiki/Game_theory).


5
Bez względu na to, jaką kombinację przedmiotów się bierze, każdy wariant Rock-Paper-Scissors jest oczywiście sprawiedliwy, ponieważ obaj gracze są równi. W większości gier planszowych jeden gracz porusza się pierwszy.
Random832

-1. Niezależnie od tego, czy jest to uczciwe, czy nie, może być znane lub nieznane (a jeśli nieznane, możliwe do poznania lub niemożliwe do poznania), ale teoria gier daje nam wiele narzędzi do zdefiniowania „sprawiedliwego” bez niejasności.

Jak, na przykład, twórcy „The Gathering” mogą upewnić się, że nie ma „jednej karty, która pokonałaby ich wszystkich” -> Próbowałem podkreślić to zdanie i pokazać autorowi, że jego koncepcja „uczciwości” nie jest dobrze. W przeciwnym razie, na przykład, w grze takiej jak Magia, ludzie zwykle nie mają takich samych kart jak ich przeciwnik, więc nawet jeśli ludzie zaczynają w tym samym czasie (właściwie nie wiem), może to nie być uczciwe. I gra w analogię Rock-Paper-Cissors może nie jest najlepsza do rozważenia, ale wyjaśnia mój punkt widzenia.
JohnCastle

@JohnCastle To nie jest miejsce do dyskusji na temat oceny uczciwości OP, ponieważ byłaby to dyskusja i nie jest to forum dyskusyjne (w tym celu użyj czatu). Wyjątkiem jest sytuacja, gdy Twój post odpowiada na pytanie i omawia koncepcję uczciwości PO jako część tego.
doppelgreener

@JathanathanHobbs, jak możesz udowodnić uczciwość, jeśli nie jest poprawnie zdefiniowana? To prawda, że ​​mój post nie jest tak naprawdę odpowiedzią - nie powinienem zdawać sobie sprawy, że powinienem był zamieścić go pod postem głównym, ale uważam, że ważne jest określenie uczciwości przed udzieleniem odpowiedzi na pytanie.
JohnCastle
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.