Rozważmy teraz kluczowe pytania obliczeniowe związane z pojęciami omówionymi powyżej. Najpierw rozważymy czyste strategie, w których randomizacja nie jest dozwolona. Jeśli gracze mają tylko skończoną liczbę możliwych wyborów, do znalezienia równowagi można użyć wyczerpującego wyszukiwania: iteruj przez każdy możliwy profil strategii i sprawdź, czy jakikolwiek gracz ma korzystne odchylenie od tego profilu; jeśli nie, to jest to równowaga Nasha w czystych strategiach. Strategie dominujące i równowagi strategii dominującej można obliczyć za pomocą podobnych algorytmów. Niestety, liczba możliwych profili strategii dla n graczy, z których każdy ma m możliwych działań, jest mn, co oznacza, że jest niewykonalna dla wyczerpujących poszukiwań. Alternatywnym podejściem, które sprawdza się w niektórych grach, jest najlepsza odpowiedź krótkowzroczna (znana również jako najlepsza odpowiedź iterowana): zacznij od losowego wyboru profilu strategii; następnie, jeśli jakiś gracz nie rozgrywa swojego optymalnego wyboru, biorąc pod uwagę wybory innych, odwróć jego wybór na optymalny i powtórz proces. Proces będzie zbieżny, jeśli doprowadzi do profilu strategii, w którym każdy gracz dokonuje optymalnego wyboru, biorąc pod uwagę wybory innych – innymi słowy, równowagi Nasha. W przypadku niektórych gier najlepsza odpowiedź krótkowzroczności nie jest zbieżna, ale w przypadku niektórych ważnych klas gier jest gwarantowana. Obliczanie równowag strategii mieszanej jest algorytmicznie znacznie bardziej skomplikowane. Aby uprościć sprawę, skupimy się na metodach dla gier o sumie zerowej i krótko skomentujemy ich rozszerzenie na inne gry na końcu tej sekcji. W 1928 roku von Neumann opracował metodę znajdowania optymalnej strategii mieszanej dla dwóch graczy o sumie zerowej – gier, w których wypłaty zawsze sumują się do zera. Oczywiście Morra jest taką grą. Dla dwóch graczy, suma zerowa .W grach wiemy, że wypłaty są równe i przeciwne, więc musimy wziąć pod uwagę wypłaty tylko jednego gracza, który będzie maksymalizatorem (tak jak w rozdziale 6). Dla Morry wybieramy parzystego gracza E jako maksymalizatora, więc możemy zdefiniować macierz wypłat wartościami UE(e,o) – wypłata dla E, jeśli E robi e, a O robi o. (Dla wygody nazywamy gracza E „jej”, a O „nim”). Metoda von Neumanna nazywana jest techniką maksyminową i działa w następujący sposób:
- Załóżmy, że zmieniamy zasady w następujący sposób: najpierw E wybiera swoją strategię i ujawnia ją O. Następnie O wybiera swoją strategię, znając strategię E. Na koniec oceniamy oczekiwaną wypłatę gry na podstawie wybranych strategii. W ten sposób otrzymujemy grę polegającą na składaniu tur, do której możemy zastosować standardowy algorytm minimaksów. Załóżmy, że daje to wynikUE,O. Najwyraźniej ta gra faworyzuje O, więc prawdziwa użyteczność U oryginalnej gry (z punktu widzenia E) to przynajmniej UE,O. Na przykład, jeśli przyjrzymy się czystym strategiom, drzewo gry minimax ma pierwiastek równy -3 (patrz rysunek (a)),
więc wiemy, że U ≥ -3.
- Załóżmy teraz, że zmieniamy zasady, aby zmusić O do ujawnienia swojej strategii jako pierwszego, a następnie E. Następnie minimalną wartością tej gry jest UO,E, a ponieważ ta gra faworyzuje E, wiemy, że U jest co najwyżej UO,E. W przypadku czystych strategii wartość wynosi +2 , więc wiemy, że U ≤ +2.
Łącząc te dwa argumenty, widzimy, że prawdziwa użyteczność U rozwiązania oryginalnej gry musi spełniać UE,O ≤ U ≤ UO,E lub w tym przypadku -3 ≤ U ≤ +2.
Aby określić wartość U, musimy skierować naszą analizę do strategii mieszanych. Po pierwsze, zwróć uwagę na następujące: gdy pierwszy gracz ujawni strategię, drugi gracz może równie dobrze J wybrać czystą strategię. Powód jest prosty: jeśli drugi gracz gra mieszaną strategią, [p:one; (1- p):two], jego oczekiwana użyteczność jest kombinacją liniową (p · Uone +(1- p) · Utwo) użyteczności czystych strategii Uone i Utwo. Ta liniowa kombinacja nigdy nie może być lepsza niż lepsza Uone i Utwo, więc drugi gracz może po prostu wybrać lepszą. Mając to na uwadze, drzewa minimaksowe mogą być traktowane jako mające nieskończenie wiele gałęzi u nasady, co odpowiada nieskończenie wielu mieszanym strategiom, które może wybrać pierwszy gracz. Każda z nich prowadzi do węzła z dwiema gałęziami odpowiadającymi czystym strategiom dla drugiego gracza. Możemy zobrazować te nieskończone drzewa w sposób skończony, mając jeden „sparametryzowany” wybór u nasady:
• Jeśli E wybierze pierwszy, sytuacja jest taka, jak pokazano na rysunku (c).
E wybiera strategię [p:one; (1- p):two] na początku, a następnie O wybiera czystą strategię (a więc ruch) o wartości p. Jeśli O wybierze jeden, oczekiwana wypłata (do E) wynosi 2p-3(1-p)=5p-3; jeśli O wybierze dwa, oczekiwana wypłata wynosi -3p+4(1-p)=4-7p. Możemy narysować te dwie korzyści jako linie proste na wykresie, gdzie p waha się od 0 do 1 na osi x, jak pokazano na rysunku (e).
O, minimalizator zawsze wybierze dolną z dwóch linii, jak pokazano grubymi liniami na rysunku. Dlatego najlepsze, co E może zrobić u podstawy, to wybrać p tak, aby znajdował się w punkcie przecięcia, czyli gdzie
5p-3 = 4-7p => p = 7/12:
Użyteczność dla E w tym momencie to UE,O= -1/12.
• Jeśli O porusza się jako pierwszy, sytuacja jest taka jak na rysunku (d)
O wybiera strategię [q:one; (1-q):two] na początku, a następnie E wybiera ruch mający wartość q. Wypłaty wynoszą 2q-3(1-q)=5q-3 i -3q+4(1-q)=4-7q.2 Ponownie, rysunek (f) pokazuje, że najlepsze O może zrobić u nasady wybierz punkt przecięcia: 5q-3 = 4-7q => q = 7/12:
Użyteczność dla E w tym momencie wynosi UO,E = -1/12.
Teraz wiemy, że prawdziwa użyteczność oryginalnej gry leży między -1/12 a -1/12; czyli dokładnie -1/12! (Konkluzja jest taka, że lepiej być O niż E, jeśli grasz w tę grę.) Co więcej, prawdziwą użyteczność osiąga się dzięki strategii mieszanej [7/12:one;5/12:dwa], którą należy grać przez obu graczy. Ta strategia nazywa się maksymalną równowagą gry i jest równowagą Nasha. Należy zauważyć, że każda strategia składowa w mieszanej strategii równowagowej ma taką samą oczekiwaną użyteczność. W tym przypadku zarówno jedna, jak i dwie mają taką samą oczekiwaną użyteczność, -1/12, jak sama strategia mieszana. Nasz wynik dla Morry z dwoma palcami jest przykładem ogólnego wyniku von Neumanna: każda dwuosobowa gra o sumie zerowej ma maksymalną równowagę, gdy dopuszczasz strategie mieszane. J Co więcej, każda równowaga Nasha w grze o sumie zerowej jest maksymą dla obu graczy. Gracz, który przyjmuje strategię maksyminową, ma dwie gwarancje: po pierwsze, żadna inna strategia nie poradzi sobie lepiej z przeciwnikiem, który gra dobrze (chociaż niektóre inne strategie mogą być lepsze w wykorzystywaniu przeciwnika, który popełnia irracjonalne błędy). Po drugie, gracz nadal radzi sobie równie dobrze, nawet jeśli strategia zostanie ujawniona przeciwnikowi. Ogólny algorytm znajdowania równowag maksyminowych w grach o sumie zerowej jest nieco bardziej skomplikowany niż mogłyby sugerować rysunki 17.2 (e) i (f). Gdy istnieje n możliwych działań, strategia mieszana to punkt w przestrzeni n-wymiarowej, a linie stają się hiperpłaszczyznami. Możliwe jest również, że niektóre czyste strategie dla drugiego gracza będą zdominowane przez innych, tak że nie będą one optymalne w stosunku do żadnej strategii dla pierwszego gracza. Po usunięciu wszystkich takich strategii (co może być konieczne wielokrotnie), optymalnym wyborem u podstawy jest najwyższy (lub najniższy) punkt przecięcia pozostałych hiperpłaszczyzn. Znalezienie tego wyboru jest przykładem problemu programowania liniowego: maksymalizacji funkcji celu podlegającej ograniczeniom liniowym. Takie problemy można rozwiązać standardowymi technikami w wielomianu czasu w liczbie akcji (i liczbie bitów użytych do określenia funkcji nagrody, jeśli chcesz uzyskać informacje techniczne). Pozostaje pytanie, co właściwie powinien zrobić racjonalny agent, grając w pojedynczą grę w Morrę? Racjonalny podmiot wyprowadzi fakt, że [7/12:one;5/12:two] jest strategią maksymalnej równowagi i założy, że jest to wzajemna wiedza z racjonalnym przeciwnikiem. Agent może użyć 12-ściennej kości lub generatora liczb losowych, aby wybrać losowo zgodnie z tą mieszaną strategią, w którym to przypadku oczekiwana wypłata wyniesie -1/12 dla E. Albo agent może po prostu zdecydować się na zagranie jednego lub dwóch . W obu przypadkach oczekiwana wypłata pozostaje -1/12 dla E. Co ciekawe, jednostronne wybranie konkretnego działania nie szkodzi oczekiwanej wypłacie, ale umożliwienie drugiemu agentowi poznania, że podjął taką jednostronną decyzję, ma wpływ na oczekiwaną wypłatę. ponieważ wtedy przeciwnik może odpowiednio dostosować strategię. Znalezienie równowagi w grach o sumie niezerowej jest nieco bardziej skomplikowane. Ogólne podejście składa się z dwóch kroków: (1) Wymień wszystkie możliwe podzbiory działań, które mogą tworzyć mieszane strategie. Na przykład najpierw wypróbuj wszystkie profile strategii, w których każdy gracz używa jednej akcji, następnie te, w których każdy gracz używa jednej lub dwóch akcji i tak dalej. Jest to wykładnicza liczba akcji, a więc dotyczy tylko stosunkowo małych gier. (2) Dla każdego profilu strategii wymienionego w (1) sprawdź, czy jest to równowaga. Odbywa się to poprzez rozwiązanie zestawu równań i nierówności, które są podobne do tych używanych w przypadku o sumie zerowej. Dla dwóch graczy równania te są liniowe i można je rozwiązać za pomocą podstawowych technik programowania liniowego, ale dla trzech lub więcej graczy są one nieliniowe i mogą być bardzo trudne do rozwiązania.