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 Azaczyna 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 ′ dominuje (gdzie „ B ” dominuje B ”oznacza p A , B ′ ( n ) < p A , B ( n ) dla wszystkich wystarczająco dużych 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.
źródło
Odpowiedzi:
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.
źródło