Czy istnieje prosta gra o asymetrycznej złożoności?

Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch wygrywającym, jeśli pozycja nadal wygrywa po rozegraniu go.) Aby rozróżnić, wywołam dawną KOMPLEKSOWOŚĆ POZYCJI, a drugą MOKĄ KOMPLEKSOWOŚĆ.

Łatwo zauważyć, że jeśli MOVE-COMPLEXITY jest w lub , to i POZYCJA-COMPLEXITY - możemy obliczyć optymalne ruchy i sprawdzić, kto wygra na końcu. (Naprawdę nie zastanawiałem się, co się stanie, jeśli MOVE-COMPLEXITY jest w , prawdopodobnie POSITION-COMPLEXITY jest w czymś w rodzaju ). Istnieją jednak fikcyjne przykłady, gdy MOVE-COMPLEXITY jest trywialny, a POZYCJA -WSPÓŁPRACA jest arbitralnie trudna - podobnie jak (niezbyt interesująca) gra polegająca na sprawdzaniu wyniku działania algorytmu, w której gracze wykonują kolejne kroki, mając tylko jeden ruch. Trochę dygresowałem, moje główne pytanie jest następujące. $P$ $PSPACE$ $NP$ $P^{NP}$

Czy istnieje naturalna gra, w której MOVE-COMPLEXITY dwóch graczy jest inna?

Na przykład gra, w której pierwszy gracz wybiera wartości zmiennych CNF (która może nie mieć rozwiązania), podczas gdy drugi gracz próbuje rozwiązać zagadkę SOKO-BAN (która może nie mieć rozwiązania), jest taki przykład.

cc.complexity-theory np board-games pspace

— domotorp
źródło

Naprawdę podoba mi się to pytanie.

— Tayfun Pay

Nie wiem, czy gra QBF spełnia twój warunek, jeden gracz jest graczem egzystencjalnym, inny jest graczem uniwersalnym. Wiele gier ma podobną formę. Myślę, że jeśli nie ma zależności między graczami, to gra nie jest grą dla dwóch graczy, ale jeśli istnieje zależność między nimi, to (niejasno mówiąc) istnieją pewne interpretacje podobne do stylu QBF.

— Saeed,

Jest to uwaga poboczna, ale większość naturalnych gier (w sensie rozgrywanych w prawdziwym świecie, takich jak szachy, gra, ...) nie kończy się po wielomianowej liczbie ruchów, ale raczej wykładniczo (w najgorszym przypadku). Czy masz jakiś szczególny powód, aby dodać to ograniczenie, oprócz uzyskania wielomianowej relacji między MOVE-COMPLEXITY a POZYCJA-COMPLEXITY?

— Denis,

Być może uda się stworzyć rodzinę przykładów relaksujących warunki wygranej jednego z dwóch graczy: na przykład mecz szachowy, w którym biały wygrywa ze standardowym matem i czarny wygrywa z matowym lub schwyta białą królową. Innym przykładem może być GG z czerwono-niebieskimi węzłami, a jeden z dwóch graczy może wygrać nie tylko w standardowy sposób, ale także zbierając pewną liczbę czerwonych węzłów. Zastanowię się więcej nad możliwymi formalizacjami podobnych przykładów.

— Marzio De Biasi,

Jeśli gra nie ma remisów (i rozsądnie ograniczona liczba możliwych ruchów na turę), czy następujący fakt oznacza, że odpowiedź brzmi „nie”? Ruch wygrywa wtedy i tylko wtedy, gdy żadna odpowiedź przeciwnika na niego nie wygrywa.

— usul

Odpowiedzi:

Być może dość naturalna gra to:

Gracz 1 jest umieszczony w środku labiryntu i musi dotrzeć do wyjścia, aby wygrać.

Gracz 2 znajduje się w tym samym labiryncie i musi zebrać zestaw „komponentów”, aby zbudować kontroler radiowy, który pozwoli mu zamknąć wyjście (i wygrać).

Decyzja o kolejnym ruchu ze zwycięskiej pozycji jest łatwa dla Gracza 1: wystarczy podążać najkrótszą ścieżką od jego aktualnej pozycji i wyjścia; ale może to być bardzo trudne dla Gracza 2.
Rzeczywiście, jeśli (pozostałe) komponenty kontrolera radiowego znajdują się na wierzchołkach wykresu siatki węzłów (załóżmy, że Gracz 2 jest sam na sąsiednim wierzchołku) i odległość między Graczem 1 a wyjście jest dokładnie , a następnie musi znaleźć ścieżkę hamiltonowską, aby się ruszyć. $n$ $n$

Aby uczynić grę bardziej „interaktywną”, możemy również dodać kilka dodatkowych akcji do Gracza 2, które mogą spowodować jedynie spowolnienie wielomianowe w obliczeniach następnego ruchu dla Gracza 1; na przykład pozwalając mu blokować stałą liczbę korytarzy labiryntu.

— Marzio De Biasi
źródło

Dzięki twoim ograniczeniom mamy również silniejszą zależność odwrotną: jeśli POZYCJA-KOMPLEKSOWOŚĆ należy do klasy , to i tak MOŻLIWOŚĆ KOMPLEKSOWA, ponieważ wystarczy przetestować skończoną liczbę dostępnych ruchów. (Zakładałem, że „skończony” miałeś na myśli „stały”, jeśli jest arbitralny, wówczas złożoność może się zmienić). $C$

Wystarczy spojrzeć na niektóre naturalne gry, w których POZYCJA-KOMPLEKSOWOŚĆ jest asymetryczna. Zawsze będziemy potrzebować pewnej asymetrii między graczami, aby stworzyć takie sytuacje, ale mam nadzieję, że będzie to jak najbardziej naturalne.

Moim zdaniem gry z częściową obserwacją są tego dobrym przykładem: rozgrywane są na skończonej arenie, a jeden gracz zawsze zna aktualny wierzchołek, podczas gdy drugi tylko wie, w której grupie jest obecny wierzchołek (są one arbitralnie grupowane razem). Najbardziej klasycznym przykładem tego są gry z parzystością, w których liczba ruchów jest nieskończona. Tam złożoność POZYCJI jest kompletna WYŁĄCZNIE dla częściowego gracza w porównaniu do liniowego / kwadratowego / NP coNP dla pełnego gracza, w zależności od złożoności warunków wygranej. Zobacz tutaj odniesienie na ten temat. $\cap$

Myślę, że z tego możemy zaprojektować grę rozgrywaną w skończonym czasie, w której jeden gracz ma częściową obserwację, a drugi pełną obserwację, a złożoność POZYCJA i złożoność RUCHU są bardzo różne. Naturalną próbą jest podzielenie wierzchołków na i i ustawienie warunku wygranej na „zagraj ruchy , Gracz wygrywa, jeśli zakończymy partycję ”. $P_1$ $P_2$ $p(n)$ $i$ $P_i$

— Denis
źródło

Twierdziłbym, że jest mało prawdopodobne, aby „skończony” znaczył tutaj „stały”.

— Kyle

W rzeczywistości w tak zwanych grach Picker-Chooser lub Chooser-Picker łatwo jest skonstruować przykłady, dla których najlepszą strategią jednego gracza jest prosta strategia parowania, podczas gdy drugi musi rozwiązać 3-SAT na dowolnym określonym wcześniej CNF, to jest problem NP-zupełny.

Powiedzmy, że gry Picker-Chooser to gra asymetryczna na hiperrafacie H = (V, E): Picker wybiera dwa niezaznaczone elementy V, a następnie Selectr bierze jeden z nich i zwraca drugi do Picker. Wybieracz wygrywa, jeśli otrzymuje wszystkie elementy litery A od E. Teraz, biorąc pod uwagę formułę CNF F od 3-SAT, V jest zbiorem literałów, a E realizuje jakiś gadżet. Podsumowując, Picker musi zawsze oferować x_i i x_i negację na wszystkich etapach (w przeciwnym razie natychmiast traci), podczas gdy wybór selektora jest dowolnym wejściem 0-1 dla dowolnego x_i, a on wygrywa, spełniając F.

Zobacz szczegóły w: A. Csernenszky, R. Martin i A. Pluhár, O złożoności gier pozycyjnych selektor-zbieracz. Liczby całkowite 11 (2011).

lub na stronie : http://www.inf.u-szeged.hu/~pluhar/complexity_2011.pdf

— Andras Pluhar
źródło