Redutacja gry permutacyjnej

20

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)npoly(n)) poprzez programowanie dynamiczne.

Jeffε
źródło
4
Wydaje mi się, że naiwny algorytm działa w czasie O (2 ^ n⋅poly (n)).
Tsuyoshi Ito
Z twoich przykładów wynika, że ​​Alice zawsze wygrywa, jeśli sekwencja jest malejąca, a Bob zawsze wygrywa, jeśli sekwencja rośnie. Ten problem przypomina mi analizę algorytmów sortowania, które zostały dogłębnie zbadane i pozwalają na użycie szerokiego arsenału narzędzi.
chazisop
1
@chazisop: „Alice zawsze wygrywa, gdy sekwencja jest malejąca”: Tak jest wtedy i tylko wtedy, gdy n jest parzyste.
Tsuyoshi Ito
@ Jɛ ff E w przypadku 3, jak Bob wygrywa w swojej pierwszej turze?
Suresh Venkat
2
@Suresh: W przypadku (2,4,1,3) reprezentacja wykresu jest wykresem liniowym na 4 wierzchołkach (2-1-4-3). Jeśli Alicja usunie węzeł końcowy, pozostawia wykres liniowy na 3 wierzchołkach; Bob wygrywa, usuwając środkowy wierzchołek (więc 3 odpowiada 1, a 2 odpowiada 4). Jeśli Alicja usunie wewnętrzny węzeł, pozostaną dwa połączone wierzchołki i izolowany węzeł; Bob wygrywa, usuwając jeden z dwóch połączonych wierzchołków (więc 1 odpowiada 3 lub 4, a 4 odpowiada 1 lub 2).
mjqxxxx,

Odpowiedzi:

7

„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ą.sol

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łędziesolππS.n(ja,jot)ja-jotπ(ja)-π(jot)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:solπdo=solR(π)(ja,jot)jajot

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

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 nsolnsolK.¯nsol (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 GK.¯nnsol+solK.¯n|sol|+nsolsolsol+solK.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 ).|sol|=|sol|-1n2)sol+solK.¯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, asolH.K.pH.sol 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 Gp=01solsolH.K.psolH.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.solsol(H.H.)K.pp[H.K.0][H.K.1]H.H.+H.K.1H.+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πsolπ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πsolπdo

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 212) 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.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.12)12)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.11(1,1,,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.

mjqxxxx
źródło
2
Myślę, że tego rodzaju gry są wspólnie nazywane „grami z usuwaniem wierzchołków”. Zgadzam się jednak z tobą, że warunek wygranej jest dość niestandardowy, ponieważ odnosi się do globalnej właściwości wykresu zamiast właściwości lokalnych, takich jak stopień wierzchołek.
Tsuyoshi Ito,
4
Skonstruowany wykres nazywa się w literaturze wykresem permutacji ( en.wikipedia.org/wiki/Permutation_graph ). Niektóre właściwości strukturalne mogą pomóc.
Yoshio Okamoto,
1
@Yoshio: To dobra uwaga. Gra permutacyjna jest izomorficzna z grą graficzną, ale początkowe wykresy nie są arbitralne. Więc nawet jeśli ogólna gra graficzna jest trudna do przeanalizowania, możliwe jest, że po ograniczeniu do tej podklasy grafów staje się prostsza.
mjqxxxx,
2
Z drugiej strony bardziej ogólne sformułowanie może być łatwiejsze do udowodnienia. Wiadomo, że odmiany
Jeffε
2
Dodałem pytanie dotyczące tego rodzaju gry specjalnie na math.SE ( math.stackexchange.com/questions/95895/… ). Nawiasem mówiąc, ponieważ wykresy permutacji są wykresami kołowymi, alternatywne sformułowanie jest następujące: Gracze na zmianę usuwają akordy z początkowego zestawu; zwycięzcą zostaje gracz, który pozostawia nieprzecinający się zestaw akordów.
mjqxxxx,
7

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 ijahja kamienie w nim, i zakładamy, że są podane w kolejności malejącej. Na przykład dla powyższej permutacji h ihjahjasą 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 > 2s ; 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=ja2),hja>2)hja-2)

  1. Pozycje, w których zawierające nieparzystą liczbę kamieni.ts-2)

  2. Pozycje, w których zawiera parzystą liczbę kamieni.ts

Ł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.ts

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 tts1s>0tss=0 .ts

  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.ts1tsts2

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

Peter Shor
źródło
1
W mojej odpowiedzi zauważyłem, że rozwiązanie tego specjalnego przypadku rozwiązuje również przypadek specjalny ze zwiększającą się serią malejących przebiegów, grając w pozycji „podwójnej” uzyskanej przez transponowanie diagramu Younga. W szczególności optymalna strategia Eve staje się „wzięcie z największej sterty, chyba że są dokładnie dwie takie wielkości”, a optymalna strategia Otto staje się „zabranie z najmniejszej sterty”.
mjqxxxx
Jestem pewien, że takie podejście doprowadzi do idealnego rozwiązania, ale w tej chwili wciąż istnieje drobny błąd, np. (3,1) nie przegrywa, a (3,1,1) jest. Problem polega na tym, że definicja 2. powinna wykluczać ten przypadek, ponieważ w jednym kroku możemy osiągnąć pozycję jednego sterty. Ale myślę, że to jedyny problem z 2. i mam nadzieję, że nie jest trudno go naprawić.
domotorp
1
Oczywiście na koniec zapomniałem tej części ... Ta gra została rozwiązana!
domotorp
1
Nie jest to kompletna odpowiedź, ale nadal jest warta nagrody.
Jeffε
3

O(2nn)

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

Dmytro Korduban
źródło
Ups, mój błąd. Naprawiono pytanie: g (1,3,2) = mex {g (1,3), g (1,2), g (3,2)} = mex {0, 0, * 1} = * 2.
Jeffε
n10n
@maldini: daje nadzieję, że gra ma jakieś fajne właściwości, które mogą sprawić, że będzie łatwa w obsłudze. Zastanawiam się, co dzieje się z grą uogólnioną na grafy lub grą uogólnioną na idealne wykresy.
Peter Shor,
3

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ź!

domotorp
źródło
1
Czy możesz podać przynajmniej jeden przykład pokazujący, w jaki sposób określona permutacja zamienia się w Młody Tableau i jak ta sama gra (usuwanie liczb do momentu osiągnięcia rosnącej sekwencji) jest rozgrywana na Tableau? W szczególności nie rozumiem, co to znaczy usunąć „jeden z kwadratów w prawym dolnym rogu”.
mjqxxxx
5
Oto kontrprzykład na słabsze twierdzenie, że usunięcie liczby z permutacji odpowiada usunięciu jednej z prawej dolnej komórki z odpowiedniego diagramu Younga (zamiast Young tableau ). Niech n = 5 i rozważmy pozycję określoną przez permutację [4,1,3,5,2] (to znaczy σ (1) = 4, σ (2) = 1 itd.) I usuń 3 z tego. Odpowiedni diagram Younga przed ruchem to 5 = 3 + 1 + 1, ale odpowiedni diagram Younga po ruchu to 4 = 2 + 2, którego nie uzyskuje się po usunięciu jednej komórki z 3 + 1 + 1.
Tsuyoshi Ito,
5
A permutacja [5,4,1,2,3] ma taki sam schemat Younga jak [4,1,3,5,2], ale nie można z niego dotrzeć do schematu Younga 4 = 2 + 2. Gra zależy więc od czegoś więcej niż kształtu Younga.
Peter Shor,
2
Brawo za konstruktywne nieporozumienie!
Jeffε
3
@ Jɛ ff E: Tak, jest to o wiele bardziej przydatne niż dowód na istnienie nieporozumień.
Tsuyoshi Ito