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

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?

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.

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.

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.

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.

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.

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.

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.

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.

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).