Redutacja gry permutacyjnej

Jest to powtórzenie wcześniejszego pytania .

Rozważ następującą bezstronną idealną grę informacyjną między dwoma graczami, Alice i Bobem. Gracze otrzymują permutację liczb całkowitych od 1 do n. Jeśli w każdej turze wzrasta bieżąca permutacja, obecny gracz przegrywa, a drugi gracz wygrywa; w przeciwnym razie aktualny gracz usuwa jeden z numerów i gra przechodzi do drugiego gracza. Alice gra pierwsza. Na przykład:

• (1,2,3,4) - Bob z definicji wygrywa natychmiast.

• (4,3,2,1) - Alice wygrywa po trzech turach, bez względu na to, jak ktoś gra.

• (2,4,1,3) - Bob może wygrać w swojej pierwszej turze, bez względu na to, jak gra Alice.

• (1,3,2,4) - Alicja wygrywa natychmiast, usuwając 2 lub 3; w przeciwnym razie Bob może wygrać w swojej pierwszej turze, usuwając 2 lub 3.

• (1,4,3,2) - Alice w końcu wygrywa, jeśli weźmie 1 w swojej pierwszej turze; w przeciwnym razie Bob może wygrać w swojej pierwszej turze, nie usuwając 1.

Czy istnieje algorytm czasu wielomianowego określający, który gracz wygra tę grę na podstawie danej permutacji początkowej, zakładając idealną grę ? Mówiąc bardziej ogólnie, ponieważ jest to standardowa bezstronna gra, każda permutacja ma wartość Sprague – Grundy ; na przykład (1,2,4,3) ma wartość * 1, a (1,3,2) ma wartość * 2. Jak trudno jest obliczyć tę wartość?

Oczywisty algorytm cofania działa w czasie O (n!), Chociaż można go zredukować do $O(2^n poly(n))$ poprzez programowanie dynamiczne.

„Gra permutacyjna” jest izomorficzna do następującej gry:

Rozłączyć się. Gracze na przemian usunąć wierzchołki grafu . Gracz, który wygeneruje całkowicie odłączony wykres (tj. Wykres bez krawędzi), jest zwycięzcą.$G$

Wykres odpowiadający konkretnej permutacji początkowej π ∈ S n zawiera tylko te krawędzie ( i , j ), dla których i - j i π ( i ) - π ( j ) mają przeciwne znaki. Oznacza to, że każda para liczb jest w błędzie$G_{\pi}$$\pi\in S_n$$(i,j)$$i-j$$\pi(i)-\pi(j)$porządek w permutacji jest powiązany z krawędzią. Oczywiście dozwolone ruchy są izomorficzne do tych w grze permutacyjnej (usuń liczbę = usuń węzeł), a warunki wygranej również są izomorficzne (brak par w kolejności malejącej = brak krawędzi).

Widok komplementarny uzyskuje się poprzez rozważenie grania w grę „dualną” na dopełnieniu wykresu , która zawiera te krawędzie ( i , j ), dla których i i j są w prawidłowej kolejności w permutacji. Podwójna gra do rozłączenia to:$G^{c}_\pi = G_{R(\pi)}$$(i,j)$$i$$j$

Na nowo połączyć. Gracze na przemian usunąć wierzchołki grafu . Gracz, który wygeneruje pełny wykres, jest zwycięzcą.$G$

W zależności od konkretnej permutacji jedna z tych gier może wydawać się prostsza niż druga do analizy. Zaletą reprezentacji wykresu jest to, że oczywiste jest, że odłączone elementy wykresu są osobnymi grami, a zatem liczy się na pewne zmniejszenie złożoności. Sprawia również, że symetrie pozycji są bardziej widoczne. Niestety warunki wygranej są niestandardowe ... gra o permutacji zawsze kończy się, zanim wszystkie ruchy zostaną wyczerpane, co nadaje jej charakter niewłaściwej postaci. W szczególności wartości nim nie można obliczyć jako sumy nim (binarny XOR) wartości nim rozłączonych komponentów.

W przypadku Disconnect nietrudno zauważyć, że dla dowolnego wykresu i dowolnego parzystego n gra G ∪ ˉ K n jest równoważna G jest pozbawiona krawędzi, a następnie pierwszy gracz przegrywa natychmiast (obie gry są skończone). W przeciwnym razie pierwszy gracz może wykonać ruch w dowolnym G , a drugi gracz może skopiować swój ruch w drugim (redukując do G ′ + G ′ ∪ ¯ K $G$$n$$G \cup \bar{K}_n$$G$ (gdzie jest bezgranicznym wykresem na n wierzchołkach). Aby to udowodnić, musimy pokazać, że suma rozłączna G + G ∪ ˉ K n to wygrana drugiego gracza. Dowodem jest indukcja na | G | + n . Jeśli $\bar{K}_n$$n$$G + G\cup\bar{K}_n$$|G|+n$$G$$G$$G' + G'\cup \bar{K_n}$ pomocą ); lub, jeśli n ≥ 2 , pierwszy gracz może poruszać się w rozłączonym kawałku, a drugi gracz może zrobić to samo (redukując do G + G ∪ ˉ K n - 2 ).$|G'|=|G|-1$$n\ge 2$$G + G\cup\bar{K}_{n-2}$

To pokazuje, że każdy wykres jest równoważny H ∪ K p , gdzie H jest częścią G bez rozłączonych wierzchołków, a$G$$H \cup K_p$$H$$G$ albo 1 jestparzystościliczby niepołączonych wierzchołków G . Wszystkie gry w klasie równoważności mają tę samą wartość nim, a ponadto relacja równoważności uwzględnia działanie unii: jeśli G ∼ H ∪ K p i G ′ ∼ H ′ ∪ K p ′, to$p=0$$1$$G$$G \sim H \cup K_p$$G' \sim H' \cup K_{p'}$ . Ponadto widać, że gry w [ H ∪ K 0 ] i [ H ∪ K 1 ] mają różne wartości nim, chyba że H jest wykresem zerowym: grając w H + H ∪ K 1 , pierwszy gracz może wziąć izolowane wierzchołek, pozostawiając H + H , a następnie skopiuj ruchy drugiego gracza.$G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$$[H \cup K_0]$$[H \cup K_1]$$H$$H + H \cup K_1$$H+H$

Nie znam żadnych powiązanych wyników dekompozycji dla Reconnect.

Dwa specjalne rodzaje permutacji odpowiadają szczególnie prostym grom sterty.

1. Pierwszy to rosnący , np . 32165487 . Kiedy π przyjmuje tę postać, wykres G π jest połączeniem rozłącznych klik, a gra Rozłącza redukuje się do gry na stosach: gracze naprzemiennie usuwają jedną fasolę ze stosu, aż wszystkie stosy będą miały rozmiar 1 .$32165487$$\pi$$G_{\pi}$$1$
2. Drugi to zstępujący bieg , np . 78456123 . Kiedy π przyjmuje tę postać, wykres G c π jest połączeniem rozłącznych klik, a gra Reconnect sprowadza się do gry na stosach: gracze naprzemiennie usuwają jedną fasolę ze stosu, aż pozostanie tylko jedna sterta .$78456123$$\pi$$G^{c}_{\pi}$

Mała myśl pokazuje, że te dwie różne gry na stosach (możemy je nazwać 1-stertą i 1-stertą , przy pewnym ryzyku pomyłki) są w rzeczywistości same w sobie izomorficzne. Oba mogą być reprezentowane przez grę na schemacie Younga (jak początkowo zaproponował @domotorp), w której gracze naprzemiennie usuwają prawy dolny kwadrat, dopóki nie zostanie tylko jeden rząd. Jest to oczywiście ta sama gra, co 1-sterty, gdy kolumny odpowiadają stosom, i ta sama gra, co 1-sterty, gdy rzędy odpowiadają stosom.

Kluczowym elementem tej gry, który rozciąga się na Rozłącz i Połącz ponownie, jest to, że czas trwania jest powiązany z końcowym stanem gry w prosty sposób. Kiedy nadejdzie Twoja kolej, wygrasz, jeśli w grze pozostanie nieparzysta liczba ruchów, w tym ta, którą zamierzasz wykonać. Ponieważ pojedynczy ruch jest usuwany przy każdym ruchu, oznacza to, że chcesz, aby liczba kwadratów pozostałych na końcu gry miała przeciwną parzystość, którą ma teraz. Co więcej, liczba kwadratów będzie miała taki sam parzystość we wszystkich twoich turach; więc od samego początku wiesz, jaki ma być parytet końcowy. Możemy zadzwonić do dwóch graczy Eve i Otto, w zależności od tego, czy ostateczna liczba musi być parzysta czy nieparzysta, aby wygrać. Ewa zawsze porusza się w stanach z nieparzystą parzystością i wytwarza stany z parzystą parzystością, a Otto jest odwrotnie.

W swojej odpowiedzi @PeterShor podaje pełną analizę One-Heap. Wynik bez powtórzenia dowodu jest następujący:

• Otto lubi stosy i $1$$2$ stosy i może tolerować jedną większą stertę. Wygrywa, jeśli uda mu się stworzyć wszystkie stosy z wyjątkiem jednego , przynajmniej bez udzielenia Eve natychmiastowej wygranej ( 1 , n ) . Optymalną strategią dla Otto jest zawsze pobieranie z drugiej co do wielkości sterty, z wyjątkiem sytuacji, gdy stan to ( 1 , 1 , n > 1 ) , kiedy powinien on wziąć z n . Otto przegra, jeśli na początku będzie za dużo ziaren fasoli.$\le 2$$(1,n)$$(1,1,n>1)$$n$
• Ewa nie lubi kup. Wygrywa, jeśli uda jej się uzyskać wszystkie wielkości sterty ≥ 2 . Optymalną strategią dla Ewy jest zawsze brać od 1- stosu, jeśli taki istnieje, i nigdy nie brać od 2- stosu. Ewa przegra, jeśli na początek będzie za dużo 1- stosów.$1$$\ge 2$$1$$2$$1$

Jak wspomniano, daje to również optymalne strategie dla 1-sterty, chociaż są one nieco trudniejsze do sformułowania (i mogę popełniać błąd w tłumaczeniu pierwotnym na podwójne). W grze 1-Heaps:

• Otto lubi jedno lub dwa duże sterty i może tolerować dowolną liczbę stert. Wygrywa, jeśli uda mu się zebrać wszystkie oprócz dwóch największych stosów 1- stosy, przynajmniej bez udzielenia Eve natychmiastowej wygranej ( 1 , 1 , … , 1 , 2 ) . Optymalną strategią dla Otto jest zawsze pobieranie z trzeciego co do wielkości stosu lub z mniejszego stosu, gdy są tylko dwa stosy.$1$$1$$(1,1,\dots,1,2)$
• Eve nie lubi przerwy między największymi i drugimi co do wielkości stertami. Wygrywa, jeśli uda jej się zrobić dwa największe stosy tego samego rozmiaru. Optymalną strategią dla Ewy jest zawsze brać z największej sterty, jeśli jest wyjątkowa, i nigdy, jeśli są dokładnie dwie największe wielkości.

Jak zauważa @PeterShor, nie jest jasne, w jaki sposób (lub czy) te analizy można rozszerzyć na bardziej ogólne gry Disconnect and Reconnect.

W swojej odpowiedzi domotorp sugeruje przeanalizowanie specjalnego przypadku gry. Ten szczególny przypadek powstaje, gdy permutacja jest serią rosnących sekwencji, z których każda jest większa niż kolejna, na przykład (8,9,5,6,7,4,1,2,3). W tej grze zaczynasz od zbioru stosów kamieni, a gracze na przemian usuwają jeden kamień ze stosu. Gracz, który pozostawia jedną stertę, wygrywa. Powiemy, że ta kupa ma h $i$$h_i$ kamienie w nim, i zakładamy, że są podane w kolejności malejącej. Na przykład dla powyższej permutacji h $h_i$$h_i$są 3,3,2,1. Próbowałem podać analizę tej gry w komentarzach do odpowiedzi domotorp, ale (a) pomyliłem się i (b) nie ma wystarczająco dużo miejsca w komentarzach, aby dać prawdziwy dowód.

Aby przeanalizować tę grę, musimy porównać dwie wielkości: , liczbę hałd zawierających pojedyncze kamienie it = ∑ i ≥ 2 , h i > $s$ ; zauważ, że ignorujemy największą stertę w sumie. Jest to liczba kamieni, które musiałbyś usunąć, aby upewnić się, że wszystkie stosy oprócz jednego zawierają nie więcej niż dwa kamienie. Twierdzimy, że pozycje tracące są następujące:$t=\sum_{i\geq 2, h_i>2\,} h_i -2$

1. Pozycje, w których zawierające nieparzystą liczbę kamieni.$t \leq s-2$

2. Pozycje, w których zawiera parzystą liczbę kamieni.$t \geq s$

Łatwo jest wykazać, że z pozycji przegrywającej musisz przejść do pozycji wygranej, ponieważ może zmieniać się maksymalnie o 1 w każdej turze, a liczba kamieni spada o 1 w każdym ruchu.$t - s$

Aby zakończyć pokazanie, że jest to poprawne, musimy pokazać, że z dowolnej pozycji, która nie znajduje się w kategorii (1) lub (2), pierwszy gracz może jednym ruchem osiągnąć pozycję w kategorii (1) lub (2), lub wygraj bezpośrednio.

Istnieją dwa przypadki:

1. Pozycje, w których zawiera nieparzystą liczbę kamieni. Tutaj, jeśli s > 0 , usuń kamień ze stosu jednym kamieniem. Jeśli pozostała tylko jedna kupa, wygraliśmy. W przeciwnym razie mamy teraz t ≥ s . Jeśli nie ma stosów z jednym kamieniem, usuń kamień ze stosu z co najmniej trzema kamieniami. (Ponieważ liczba kamieni była nieparzysta, jest to możliwe). Ponieważ s = 0 , mamy $t \geq s-1$$s>0$$t \geq s$$s = 0$ .$t \geq s$

2. Pozycje, w których zawierające parzystą liczbę kamieni. Tutaj, jeśli są stosy z co najmniej dwoma kamieniami innymi niż największa hałda, usuń kamień z jednego z nich. Jeśli to stos zawiera trzy lub więcej kamieni, t zmniejsza się o jeden. Jeśli ma dokładnie dwa kamienie, s wzrasta o jeden. Mamy teraz t ≤ s - 2 . Ostatni przypadek ma miejsce, gdy wszystkie hałdy oprócz jednego składają się z pojedynczych kamieni; w takim przypadku łatwo jest sprawdzić, czy wygrywa pierwszy gracz, jeśli jest parzysta liczba kamieni.$t \leq s-1$$t$$s$$t \leq s-2$

Próbowałem uogólnić tę strategię do oryginalnej gry i nie wymyśliłem, jak to zrobić.

$O(2^n n)$

@ Jɛ ff E Zdarzyło się, że (1,4,3,2) ma wartość * 1, a nie * 2, jak sugerowałeś.

Edytuj 5 stycznia: W rzeczywistości gra One Heap opisana poniżej jest szczególnym przypadkiem problemu, tj. Gdy liczby podążają za sobą w określony sposób, tak że pierwsza grupa jest większa niż druga grupa, która jest większa niż trzecia itd. , a liczba w każdej grupie rośnie. Np. 8, 9, 4, 5, 6, 7, 2, 3, 1 jest taką permutacją. Dlatego proponuję najpierw rozwiązać ten szczególny przypadek.

Zastrzeżenie: Nie twierdzę już, że poniższy dowód jest poprawny, patrz np. Komentarz Tsuyoshi, który pokazuje, że usunięcie liczby z permutacji da diagram niemożliwy do uzyskania przez usunięcie kwadratu z diagramu permutacji. Zostawiłem tutaj odpowiedź, aby pokazać, że to podejście nie działa, a ponadto zawiera kolejną prostą grę.

Gra ma bardzo proste inne sformułowanie dzięki Young Tableaux. Jestem pewien, że można go stamtąd przeanalizować jak inne gry i da on liniowy algorytm czasu.

Najpierw zdefiniuj następującą grę na Young Diagrams: Jeśli w każdej turze diagram jest poziomy (wszystkie kwadraty w jednej linii), obecny gracz przegrywa, a drugi gracz wygrywa; w przeciwnym razie obecny gracz usuwa jeden z kwadratów po prawej u dołu i gra przechodzi do drugiego gracza.

Teraz uporządkuj sekwencję liczb w Young Tableaux. Głównym twierdzeniem jest to, że zwycięzca oryginalnej gry jest tym samym zwycięzcą co gra diagramowa rozpoczynająca się od tego kształtu. Aby to zobaczyć, zauważ, że ilekroć gracze usuwają cyfry, diagram nowej sekwencji można uzyskać, usuwając prawy dolny kwadrat diagramu. Co więcej, dowolny taki schemat można uzyskać, usuwając liczbę z odpowiedniego kwadratu w prawym dolnym rogu. Te stwierdzenia wynikają ze standardowej teorii Younga Tableaux.

Chociaż ta gra z diagramami jest dość prosta, w sposób trywialny odpowiada następującej grze, która wydaje się bardziej standardowa:

Gra jednym stosem: gracze otrzymują kilka stosów z kilkoma kamykami w każdym. Jeśli w każdej turze pozostanie tylko jedna kupka, aktualny gracz przegrywa, a drugi gracz wygrywa; w przeciwnym razie aktualny gracz usuwa kamyk ze stosu i gra przechodzi do innego gracza.

Jeśli istnieje proste rozwiązanie gry sterty (i mocno wierzę, że istnieje), otrzymujemy również rozwiązanie oryginalnej gry: Po prostu umieść sekwencję w Young Tableaux i zamień jej schemat w stosy.

Niestety nie wiem, które pozycje na stosie wygrywają / jak określić wartości Sprague – Grundy. Sprawdziłem kilka przypadków ręcznie, a poniżej znajdują się pozycje przegrywające z maksymalnie 6 kamykami:

jedna kupa; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).

Czy ktoś może rozwiązać tę grę?

Edycja: Peter Shor może zobaczyć swoją odpowiedź!