Obliczeniowa wersja równowagi Nasha?

Zastanawiam się, czy istnieje obliczeniowa wersja koncepcji równowagi Nasha, coś podobnego do tego.

Wyobraź sobie jakąś idealną grę informacyjną dla dwóch graczy, która jest rozgrywana na planszy , i która jest złożona w tym sensie, że optymalna gra jest trudna WYGODNIE. Załóżmy również dla uproszczenia, że ​​losowanie nie jest możliwe. Wyobraź sobie parę ( A , B ) losowych wielomianowych maszyn Turinga grających przeciwko sobie. Dla każdego n , niech p A , B ( n ) będzie prawdopodobieństwem, że A pokona B w kolejności n . (Dla konkretności, powiedzmy, że $n\times n$$(A, B)$$n$$p_{A,B}(n)$$A$$B$$n$$A$zaczyna grać z prawdopodobieństwem 0,5.) Myślę, że fajnie byłoby, gdyby można było udowodnić istnienie pary z właściwością, że żadna randomizowana maszyna Turinga A ′ w czasie wielomianowym nie dominuje A (gdzie „ A ” dominuje A ”oznacza p A ′ , B ( n ) > p A , B ( n ) dla wszystkich wystarczająco dużych n ) i podobnie nie ma losowej wielomianowej maszyny Turinga B $(A,B)$$A'$ $A$$A'$$A$$p_{A',B}(n) > p_{A,B}(n)$$n$$B'$dominuje (gdzie „ B ” dominuje B ”oznacza p A , B ′ ( n ) < p A , B ( n ) dla wszystkich wystarczająco dużych n ).$B$$B'$$B$$p_{A,B'}(n) < p_{A,B}(n)$$n$

Podejrzewam, że to jakoś zbyt wiele, na co można liczyć, ale czy jest jakaś nadzieja na coś takiego, być może dla ograniczonej klasy gier?

Jedną z motywów tego pytania jest to, że szukam sposobu na sformalizowanie poglądu, że dana pozycja szachowa jest „korzystna dla białych”. Klasycznie pozycja to albo wygrana dla Białych, albo nie. Jednak gracze w szachy, zarówno ludzcy, jak i komputerowi, intuicyjnie rozumieją, co oznacza dla Białej przewagę. Wydaje się, że ma to coś wspólnego z prawdopodobieństwem wygranej białych, biorąc pod uwagę, że gracze są obliczeniowo ograniczeni i muszą zgadywać, co zrobić najlepiej. W przypadku konkretnej pary randomizowanych algorytmów można oczywiście mówić o prawdopodobieństwie wygranej przez White, ale zastanawiam się, czy w pewnym sensie może istnieć kanoniczny para obliczeniowo ograniczonych graczy, których prawdopodobieństwa wygranej dają wartość dla pozycji, która zależy tylko od samej gry, a nie od osobliwości graczy.

Nie potrafię wymyślić żadnej łatwej, całkowicie eleganckiej / satysfakcjonującej odpowiedzi na to pytanie, szczególnie dlatego, że końcową wypłatę tak trudno jest obliczyć; jednak moje myśli są zbyt długie, aby opublikować je jako komentarz.

Najlepszy pomysł, jaki mam: w przypadku szachów spróbuj oszacować prawdopodobieństwo wygranej białych na podstawie materialnej przewagi białych (tj. Dodatkowych pionków, rycerzy itp.) Dla danej pozycji, losowo wybierając pozycje z dokładnie taką samą kwotą -konfiguracja materiału. Być może w przypadku „szachów z wieloma wieżami” moglibyśmy powiedzieć: „Jak prawdopodobne jest, że White wygra z 8 wieżami do 17 wież Blacków?”. Być może prawdopodobieństwo to wynosi 4%; aby to obliczyć, musielibyśmy zbadać (powiedzmy) 1000 różnych losowo wygenerowanych pozycji szachowych, które mają 8 białych wież i 17 czarnych wież, a następnie spojrzeć przed siebie (powiedzmy) 10 ruchów głęboko w każdym przypadku i zobaczyć, jaka jest nowa konfiguracja materiału . Następnie weź oczekiwane szanse na podstawie konfiguracji materiału na końcu,

Oczywiście konieczne byłoby znalezienie konfiguracji materiału dla każdej odpowiedniej możliwości ( M , N ) M białych wież do N czarnych wież ... prawdopodobnie zaczynając od najniższej uporządkowanej pary ( M = 1, N = 1) i pracując stamtąd

Jeśli chodzi o pierwotną pozycję, nie korzystaj tylko z uzyskanych statystyk (tj. Jeśli pierwotna pozycja ma wieżę ( M = 6, N = 7), nie zakładaj tylko, że białe mają 25% szans na wygraną, ponieważ to przewidywane szanse na zwycięstwo dla (6,7); zamiast tego, ponieważ możesz być bardziej precyzyjny, spójrz 10 ruchów jak zwykle z tą tylko jedną pozycją i znajdź każdą możliwą pozycję końcową. Następnie znajdź właściwą ścieżkę (która wymaga optymalnej gry po obu stronach) do konfiguracji o głębokości 10 ruchów i wybierz oczekiwane szanse tej ścieżki jako oczekiwane szanse na pierwotną pozycję.

Myślę, że ten proces można wykonać w czasie wielomianowym. Przyglądanie się k ruchów głębokich dla ustalonego k w szachach jest wielomianowe pod względem wielkości planszy, a całkowita liczba białych i czarnych wież jest wyrażona w jednostkowej (w pewnym sensie), ponieważ liczba ta musi być mniejsza niż rozmiar planszy.

Jeśli wydaje się to skomplikowane i trudne do wyjaśnienia, to dlatego, że tak jest. Bardziej zwięzłe podsumowanie tego, co opisuję, to: Użyj rekurencji i podstawowych statystyk, aby obliczyć szanse na zwycięstwo dla białych, biorąc pod uwagę M białych wież i N czarnych wież. Następnie użyj tych wartości, aby spojrzeć głęboko w k i sprawdzić szanse, że biały wygra na pierwotnej pozycji.

Komentarz końcowy: Myślę, że ten problem jest także interesujący w przypadku gier niekompletnych, takich jak Kółko i krzyżyk, które według Wikipedii jest kompletne z PSPACE. Ponadto uważam, że proces taki jak ten, który opisałem powyżej, może być również tam przydatny, chociaż oczywiście niemożliwe byłoby uzyskanie „materialnej” przewagi w kółko i krzyżyk; musiałaby istnieć inna podstawa do oceny wyższości pozycji X lub O.