Gra na kilku wykresach

13

Rozważ następującą grę na ukierunkowanym wykresie ważonym G z chipem w pewnym węźle.

Wszystkie węzły G oznaczone są literą A lub B.

Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B).

Początkowo Alice i Bob mają odpowiednio mA i mB dolarów.

Jeśli gracz znajduje się na pozycji przegrywającej (tzn. Bieżąca pozycja żetonu jest oznaczona przeciwną literą), może on przenieść żeton do sąsiedniego węzła. Taki ruch kosztuje kilka dolarów (waga odpowiedniej krawędzi).

Gracz przegrywa, jeśli znajduje się na przegranej pozycji i nie ma pieniędzy, aby to naprawić.

Rozważmy teraz GRA językowa, która składa się ze wszystkich ukierunkowanych ważonych wykresów G (wszystkie wagi są dodatnimi liczbami całkowitymi), początkowej pozycji układu oraz literami Alicji i Boba, które są podane w jednostkowej reprezentacji

tak, że Alice ma zwycięską strategię w tej grze.

GAME język należący do P . Rzeczywiście, obecna pozycja gry jest określona przez pozycję chipa i bieżące stolice Alicji i Boba, więc programowanie dynamiczne działa (tutaj ważne jest, aby początkowe kapitały były podawane w postaci jednoargumentowej).

Teraz rozważ następujące uogólnienie tej gry. Rozważyć kilka skierowanych ważone wykresy G1,Gn w układ na każdym wykresie. Wszystkie węzły wszystkich wykresów są oznaczone A i B. Teraz Bob wygrywa, jeśli wszystkie żetony są oznaczone B, a Alice wygrywa, jeśli co najmniej jeden żeton jest oznaczony A.

Rozważmy wielu języków grze, który składa się ze wszystkich wykresach G1,,Gn początkowe położenie i literami mA i mB (w jednoargumentowy reprezentacji) tak, Alicja wygrywa odpowiedniego gry. Ważne jest, aby wielkie litery były wspólne dla wszystkich grafów, więc nie jest to tylko kilka niezależnych GRA.

Pytanie Jaka jest złożoność języka MULTI-GAMES? (Czy to też należy do P, czy jest jakiś powód, aby sądzić, że ten problem jest trudny?)

UPD1 Neal Young zaproponował wykorzystanie teorii Conwaya. Nie wiem jednak, czy można zastosować tę teorię do kilku gier ze wspólnym kapitałem.

UPD2 Chcę pokazać przykład, który pokazuje, że MULTI-GAME nie jest bardzo prosta. Niech Alice podzieli swój kapitał mA na niektóre n składników mA=a1+a2+an (Ona ma zamiar użyć ai dolary dla i -tej wykresie). Zdefiniuj bi jako minimalnej liczby taki, że w i -ty gry Bob wygrywa, jeśli Alicja i Bob mają ja i b i dolarów odpowiednio. Jeśli b 1 + baibib1+bn>mB (dla niektórych podziałówmA=a1+a2+an ) wtedy Alice wygrywa. Jednak przeciwieństwo nie jest prawdą. Rozważ dwie kopie poniższego wykresu (początkowo układ znajduje się po lewej stronie A): wprowadź opis zdjęcia tutaj

Dla jednego wykresu wygrywa Bob, jeśli mA=0 i mB=2 lub jeśli mA=1 i mB=3 . Jednak w grze z dwiema kopiami tego wykresu Bob przegrywa, jeśli mA=1 i mB=5 . Rzeczywiście, Bob musiał spędzić 4 lub 5 dolarów, aby przesunąć oba chipy do węzła naznaczonym B . Następnie Alice może przenieść co najmniej jeden żeton do węzła oznaczonego literą A. Po tym Bob nie ma pieniędzy, aby zapisać swoją pozycję.

UPD3 Ponieważ pytanie o dowolne wykresy wydaje się trudne, rozważ konkretne wykresy. Oznacz węzły niektórych wykresów Gi jako 1,k . Moje ograniczenie jest następujące: dla każdej pary i<j istnieje krawędź od i do j i nie ma odwrotnej krawędzi. Istnieje również ograniczenie kosztów krawędzi: dla i<j<k krawędź j do k nie jest większa niż od i do k .

Aleksiej Milovanov
źródło
4
co w ruchu MULTI-GAME stanowi ruch? Gracz wykonuje jeden ruch na każdym wykresie? Lub wybiera jeden wykres, aby wprowadzić się? Czy zastanawiałeś się, czy ma tu zastosowanie teoria gier Conwaya (ogrzewanie i chłodzenie)? (Niektóre odniesienia można znaleźć tutaj: en.wikipedia.org/wiki/... )
Neal Young
@Neal Young Gracz wybiera jeden wykres, aby wprowadzić się do środka.
Alexey Milovanov
FWIW, o ile pamiętam, teoria gier Conwaya rozważa, w jaki sposób grać w gry złożone z innych gier w ten sposób (w każdym ruchu gracz wybiera jedną z pod-gier, w które się wprowadza). Nie wiem jednak, jakie znaczenie ma jego teoria, ponieważ ma złożoność obliczeniową.
Neal Young,
1
@NealYoung Dziękuję, ale jak rozumiem, problemem jest to, że gracze mają wspólne stolice dla wszystkich gier. Nie wiem, jak to naprawić w teorii Conwaya ...
Alexey Milovanov,
Czy Alice (Bob) jest zmuszona przesunąć układ, jeśli znajduje się w węźle A (B)? Jakie są warunki wygranej w grze wieloosobowej? Czy B wygrywa również, gdy wszystkie żetony znajdują się w węzłach B, ale A wciąż ma trochę pieniędzy? Mówisz, że A wygrywa, jeśli co najmniej jeden układ znajduje się na A, więc A może po prostu spróbować utrzymać dwa układy w węźle oznaczonym A na „tańszych” dwóch wykresach; jak tylko B przeniesie jeden z dwóch żetonów od węzła A, Alice przyniesie go z powrotem (i zignoruje pozostałe wykresy)
Marzio De Biasi

Odpowiedzi:

2

Ponieważ odpowiedź Stevena Stadnickiego nie wydaje się być zaakceptowana przez pytającego, doszedłem do wniosku, że nadal przydatne może być dostarczenie aktualizacji: mam redukcję z 3SAT do MULTI-GAME. Nie przyjrzałem się uważnie odpowiedzi Stevena ani nie podążyłem za linkiem, który podał, ale na podstawie poniższej redukcji nie zdziwię się, jeśli MULTI-GAME jest rzeczywiście ukończony na PSPACE. Jednak nie zawracam sobie głowy przedłużeniem tego wyniku poza twardość NP.

Instancja 3SAT składa się z klauzul C1,,Cm , przy czym każda klauzula ma postać Ci=Li1Li2Li3 gdzie każda Lik jest jedną ze zmiennych x1,,xn lub negacja jednej ze zmiennych.

Biorąc pod uwagę taką instancję 3SAT, redukcja tworzy instancję MULTI-GAME składającą się z n+1 gier - jednej dla każdej zmiennej i innej gry wykorzystywanej jako ujście nadwyżki kapitału. Najpierw zdefiniujemy strukturę wykresów dla każdej gry, następnie popatrzymy na przykład i omówimy podstawową ideę, a następnie ustalimy, jakie dokładne koszty przypisać do krawędzi, aby utrzymać mocne ograniczenie.

Po pierwsze, zmienny wykres gry Gj dla każdej zmiennej xj :

  1. Utwórz wierzchołek oznaczony xj oznaczonyA (tj. Zwycięski wierzchołek dla Alicji). Chip dlaGj zaczyna się na wierzchołkuxj .
  2. Utwórz wierzchołek oznaczony T i wierzchołek oznaczony F , każdy oznaczony B (tzn. Oba wygrywają pozycje dla Boba). Utwórz skierowane krawędzie od xj do T i F , oba z kosztem 1 .
  3. Dla każdego literału Lik klauzuli Ci , jeśli Lik=xj lub Lik=¬xj , utwórz wierzchołki oznaczone CiTA i CiFA oznaczone A i wierzchołki oznaczone CiTB i CiFB oznaczone B. Dodaj krawędzie (T,CiTA) i(F,CiFA) z kosztami ustawionymi nalik . (Będziemy określićlik później).

    Dodaj krawędzie (CiTA,CiTB) i (CiTA,CiTB) . Jeśli Lik=xj , to ustaw (CiTA,CiTB) na lik1i( C i TA, C i T B ) na l i k . W innym przypadku ( C i(CiTA,CiTB)lik(CiTA,CiTB)koszt T A , C i T B ) nalik orazkoszt(CiTA,CiTB) nalik1 .

Gra w zlew kapitału:

  1. Utwórz wierzchołek oznaczony literą C , oznaczony literą B.
  2. Dla każdego punktu Ci , tworzyć wierzchołek oznaczony CiA oznaczone A, a wierzchołek oznaczony CiB oznaczony B. Tworzenie krawędzi (C,CiA) z kosztami krawędzi ci (ponownie określane poniżej) oraz krawędź (CiA,CiB) również o koszcie krawędzici .

Jest to wiele do zrobienia, więc mam nadzieję, że przykład sprawi, że będzie to trochę łatwiejsze do strawienia. Nasza instancja 3SAT wygląda następująco:

C1=x1x2¬x3

C2=x2x3¬x4

C3=¬x1¬x3x4

Redukcja zamienia to wystąpienie w 4 zmienne wykresy gier i 1 wykres ujścia kapitału. Na poniższych schematach czerwone wierzchołki są oznaczone literą A (tj. Wygrywające pozycje dla Alicji), a cyjanowe wierzchołki są oznaczone literą B (wygrywające pozycje dla Boba).

Wykres dla x1 :

wprowadź opis zdjęcia tutaj

Wykres dla x2 :

wprowadź opis zdjęcia tutaj

x3

wprowadź opis zdjęcia tutaj

x4

wprowadź opis zdjęcia tutaj

Wykres dla ujścia kapitału:

wprowadź opis zdjęcia tutaj

Pomysł jest następujący:

Bob jest zmuszony zrobić pierwszy nn

Alice będzie miała wystarczającą ilość kapitału, aby wykonać dokładnie 4 ruchy, z których każdy będzie musiał mieć wystarczającą ilość kapitału, aby mógł wygrać. Wartości ci a likCi

CiCi=Li1Li2Li3k{1,2,3}Lik=xj¬xjCi?AxjCiA

Ci?ACiTACiFA

CiCili1+li2+li3+ciCi1cilik wartości, a początkowymi literami Alicji i Boba jest upewnienie się, że wspomniany rabat jest decydującym czynnikiem decydującym o tym, czy Alice lub Bob wygra.

b=m+1

lik=2b10+ib2kk{1,2,3}

ci=3b10+b8k=13ib2k

9b10+b8

9b10+b8+n1.

m

Cili1+li2+li3+ci=9b10+b81n

CiCi

Jeśli otwarcie Boba spełnia wszystkie klauzule, możemy argumentować ograniczenia opcji Alice, które wykluczają jakąkolwiek inną możliwość wygranej Alice. Zauważ, że kolejność, w jakiej Alice wykonuje swoje ruchy, jest nieistotna, ponieważ odpowiedzi Boba są wymuszone, a całkowity kapitał, którego będzie potrzebował Bob, aby zareagować na ruchy Alice, nie jest zmieniany przez kolejność ruchów Alice.

  • 5b10
  • 9b10+3b83b7>9b10+2b88b10+2b8+b7
  • 8b10+4b7

b10b89b10+b8CiAb10b8k=13ib2k1

  • lj3Cj3b5
  • lj3li3lj3j>i(i+1)b6lj3j<il(ij)3b6b2b2

li2li1Cilik1


Uwaga do mojej poprzedniej odpowiedzi: z perspektywy czasu jest oczywiste, że dla wariantu MULTI-GAME TABELA zdefiniowanego w komentarzach do tej odpowiedzi, DP w stylu plecaka wystarcza, aby ustalić, który gracz ma strategię wygrywającą. Możesz argumentować, że najlepszą strategią Boba jest zawsze reagowanie na przegrany stan przy danym stole gry przy minimalnej możliwej inwestycji (nie może to odciąć kolejnego ruchu dla Boba, który miałby w przeciwnym razie), a stamtąd zamówienie ruchów Alice nie ma znaczenia. Następnie staje się kwestią wyboru podziału kapitału Alicji między gry, tak aby suma minimalnych wygranych odpowiedzi Boba w stosunku do tych gier przekroczyła jego budżet, który można zmienić jako problem typu plecakowego, który ma DP w czasie wielomianowym do jednolitej reprezentacji kosztów. (Moje ponowne wystąpienie faktycznie „

n

Nie myślałem dużo o twoim specjalnym przypadku z UPD3 . Podejrzewam, że jest to trudne NP, z tego powodu, że moje zmienne gadżety wydają się na pierwszy rzut oka, jakby można je było dostosować do tych ograniczeń, ale prawdopodobnie nie przyjrzę się temu dalej.

gdmclellan
źródło
0

Aktualizacja: prawdopodobnie niepoprawna, na razie pozostawiająca jako dowód na zbadanie alei. Zobacz komentarze.

Aktualizacja 2: zdecydowanie niepoprawna.

G=(V,E)V={1,2,3}E={(1,2),(2,3)} , wierzchołki 1, 2, 3 są oznaczone odpowiednio B, A, B, a wszystkim krawędziom przypisane są koszty 1.

mA=mB=2G1=G2=G3=G , przy czym wszystkie trzy gry rozpoczynają się od wierzchołka 1. Najwyraźniej Alice nie może wygrać tej gry.

M[3,2,2]2u,uv,2vM[2,2u,2v]=BW[3,u,v]=Bu=1u=2M[2,2u,2]=Au=0W[3,u,2]=A

uv


mA,mB,G1,,Gn,

Wstępnie obliczone

W[k,x,y]={Aif Alice wins GAME on Gk with initial funds x for Alice and y for Bob,Botherwise

xmAymB

M[k,x,y]kxmAymBM[k,x,y]=BA

M[1,x,y]=W[1,x,y]

i

M[k+1,x,y]=Bif and only ifvu,W[k+1,u,v]=BandM[k,xu,yv]=B.

M[n,mA,mB]=A

gdmclellan
źródło
Twój algorytm jest nieprawidłowy. Rozważ wykres na zdjęciu w moim poście. Rozważ grę MULTI-GAME z dwoma takimi wykresami. Tutaj W [1,0,2] = W [2,0,2] = B i W [1,1,3] = W [2,1,3] = B. Jednak dla MULTI-GAME z m_A = 1 i m_B = 5 Alice wygrywa
Alexey Milovanov
u
@AlexeyMilovanov ze zmianami w kwantyfikatorach, przez które powinna przejść powtórzenie na przykład. Ale wątpię w to podejście. Wygląda na to, że Bob może wymagać jednej dystrybucji funduszy, która przewyższa wszystkie dystrybucje, jakie Alicja może sobie wyobrazić. To powiedziawszy, nie jestem pewien, czy zostałem przekonany do podstawowej idei tutaj: że ten problem tak naprawdę nie dotyczy gry. Czy jest coś znanego na temat pokrewnego problemu polegającego na tym, że każda instancja GAME jest zastępowana prostą tabelą a la W powyżej?
gdmclellan
Tabela W nie określa zwycięzcy. Nie wiem, czy to prawda w przypadku innego stołu ...
Alexey Milovanov
@AlexeyMilovanov Tabela W z definicji określa zwycięzcę instancji GAME odizolowanych od dowolnego określonego wykresu wejściowego. Nie jestem pewien, dlaczego powiedziałbyś inaczej. Zaktualizowałem jednak odpowiedź za pomocą kontrprzykładu, na wypadek, gdyby istniały jakiekolwiek wątpliwości, że jest ona nieprawidłowa.
gdmclellan
0

[n]n+1n0i+1i0i<n00n[n]n00

Gαβα[i]ββ[j][k]j<kαββ[j][k][k][i]{i{jk}}

Steven Stadnicki
źródło
1
Dowody w pracy wydają się wykorzystywać w grach duże wartości i, j ik. Zauważ, że tutaj można przyjąć, że wszystkie wagi są co najwyżej stolicami graczy, które były reprezentowane w jedności.
Antti Röyskö
@ AnttiRöyskö Będę musiał przyjrzeć się bliżej dowodowi; Wierzę, że wynik na PSPACE-kompletność gier końcowych Go wykorzystuje wynik pracy dyplomowej i zakłada również jednoargumentowe liczenie (ponieważ tam / i / j / k pochodzą z rozmiarów regionów planszy).
Steven Stadnicki
αβ0
αβα[i]>[j]j+1[i][j]
αβn