Czy istnieje ograniczenie do gier typu „drzwi i płyta dociskowa”, które nie eksplodują długości rozwiązania?

12

Ten dokument stanowi dowód, że w grze z drzwiami i płytkami dociskowymi trudno jest ustalić, czy awatar (gracza) może dotrzeć do danego miejsca. Dowodzi tego redukcja z TQBF , a długość powstałych rozwiązań zależy wykładniczo od liczby uniwersalnych kwantyfikatorów we wzorze.

Czy istnieje redukcja z maszyny NPSPACE do takiej gry, w której długość rozwiązań gry jest wielomianowo związana z długością ścieżek akceptacji maszyny?

Jeffε
źródło
1
krótki szkic bardziej formalnej definicji „gry z drzwiami i płytkami dociskowymi” [niestety, tak naprawdę nie podany w gazecie w jednym miejscu]. uogólniona gra to nieskończona mapa 2D, którą można przedstawić jako wykres (o dowolnym rozmiarze) łączących spacje / regiony. węzły wykresu to spacje / regiony (equiv, komórki / tunele itp.), krawędzie to drzwi między nimi. płyty dociskowe są przełącznikami zawartymi w przestrzeniach. przełącznik steruje otwieraniem drzwi. drzwi zaczynają się w arbitralnym stanie, może niektóre otwarte, niektóre zamknięte. (itp.) ... wydaje się jednak, że autor rozważa tylko wykresy płaskie.
vzn
ponadto wydaje się, że pytanie jest bliskie lub prawie równoważne z pytaniem, czy długość minimalnej ścieżki rozwiązania (liczona w krawędziach) przez wykres jest wielomianowo lub wykładniczo związana z rozmiarem wykresu / przełączników. ... to z kolei wydaje się być ściśle związane z pytaniem, ile cykli na ścieżce jest niezbędnych, a jeśli nie są ...
dniu

Odpowiedzi:

2

Być może możesz łatwo symulować LBA; pomysł jest następujący:

  • do każdej komórki taśmy LBA dodaj gadżet komórkowy który można wprowadzać tylko od dołu i pozostawiając tylko od góry;solja

  • gadżet posiada drzwiczki wejściowe który symuluje głowicę (tylko jedna C i jest otwarty na każdym etapie);dojadoja

  • Następnie dwa drzwi bit i O I ; Z i jest otwarte, jeśli komórka zawiera zero, O i jest otwarte, jeśli komórka zawiera je;ZjaOjaZjaOja

  • oba bity drzwi prowadzą do podobnej struktury sterowania, która jest utworzona przez kilka jednokierunkowych korytarzy ; korytarz odpowiada stanu LBA, a drzwi z í -tej korytarzu jest otwarty wtedy i tylko wtedy, gdy aktualny stan LBA jest q I ;qjajaqja

  • zgodnie z (być może niedeterministyczną) tabelą przejściową LBA, przejście (otwartego) korytarza zmienia aktualny stan LBA i konfigurację bit-drzwi, zamyka drzwi otwiera C i + 1 lub C i - 1 .dojadoja+1doja-1

Gadżet komórkowy jest naszkicowany na poniższym rysunku.

wprowadź opis zdjęcia tutaj

Można dokonać niedeterministycznych wyborów, dzieląc korytarze w strukturach sterowania na dwa lub więcej pod-korytarzy, jak pokazano na poniższym rysunku.

wprowadź opis zdjęcia tutaj

Uwaga: jeśli płyta może otwierać / zamykać tylko jedne drzwi, możesz dodać konstrukcję pomocniczą z (długimi) jednokierunkowymi korytarzami, które (de) aktywują odrębne drzwi stanu każdej komórki.

Marzio De Biasi
źródło
Jeśli drzwi można otworzyć tylko za pomocą jednego talerza i można je zamknąć tylko za pomocą jednego talerza, możesz użyć gadżetów crossover (które mógłbym opisać), aby korytarze prowadziły tylko do wejścia do żądanej komórki (co usuwa potrzeba drzwi C1), zaimplementuj Z1 i O1 z wieloma różnymi drzwiami, z których każde ma bezpośrednio za sobą płytę zamykającą, a następnie zaimplementuj drzwi q0, ..., q4 jako wiele mini-korytarzy z dwojgiem drzwi przez płytkę, która zamyka jedno z tych dwóch drzwi, oraz płytkę, która zamyka jedną z otwartych par drzwi na qi drugiej [wartości komórki].
Niezależnie od sugestii z mojego poprzedniego komentarza, jeśli LBA jest wtedy niedeterministyczny korytarze jednokierunkowe potrzebowałyby korytarzy podrzędnych, aby wskazać wybór niedeterministyczny.
?? nie jest rozpoznawanie LBA = (N) PSPACE? wydaje się, że bardziej pomocne byłoby sformułowanie odpowiedzi w kategoriach złożoności.
vzn
@RickyDemer: ok, dodałem przykład niedeterministycznego wyboru. Czy używasz metateoretów Viglietty, aby udowodnić złożoność niektórych gier?
Marzio De Biasi,
Czytałem jego metateheorems i zdałem sobie sprawę, że to jedna rzecz, której nie poruszają.
2

Innym szybkim sposobem udowodnienia Metatheorem 2c (twardość PSPACE, gdy drzwi są kontrolowane przez dwie płyty) jest użycie niedeterministycznego szkieletu logiki ograniczeń ( RA Hearn i ED Demaine, niedeterministyczny model ograniczenia logiki obliczeniowej: redukcje i zastosowania ).

W takim przypadku wystarczy użyć poziomej serii pionowych par korytarzy. Stan każdej pary korytarzy reprezentuje kierunek (do wewnątrz / na zewnątrz) krawędzi na oryginalnym wykresie wiązań. Wystarczy symulować gadżet AND i gadżet OR, jak naszkicowano na poniższym rysunku.

wprowadź opis zdjęcia tutaj

Marzio De Biasi
źródło
-5

tego rodzaju badania dotyczące powiązania gier wideo ze złożonością obliczeniową są dość intrygujące, ale są również całkiem nowe, na ogół liczące mniej niż dziesięć lat. Będę się tutaj kłócił, że w obecnych analizach czasami brakuje subtelności [nie widziałem / nie zauważyłem tego, o czym wspomniano w cytowanej pracy lub innych artykułach], a to zdecydowanie utrudnia odpowiedź na zadane pytanie.

aby udowodnić związek z systemem obliczeniowym, trzeba umieć odwzorować system obliczeniowy na grę i odwrotnie. na przykład w wyżej cytowanym artykule Viglietty istnieje koncepcja, że ​​płyty dociskowe i drzwi (tj. drzwi kontrolujące płyty dociskowe) mogą być „jak” QBF. ta analogia jest z pewnością wykonalna, ponieważ ją zmapowali. można użyć QBF do rozwiązania gry za pomocą płyt dociskowych i drzwi.

jednak tutaj jest subtelność. w danej grze układy gry są zasadniczo ustalone. w projektowaniu gier wideo koncepcja różnych układów nazywa się „projektowaniem układu” i nie jest „dana” wszystkim grom. na przykład w przełomowej grze Doom, narzędzia do projektowania poziomów były dostępne na zasadzie open source, tj. udostępnione graczom do użycia. innymi słowy, dowolną konstrukcję poziomu można uznać za część gry. ale w innych grach rozważanych w dokumentach gry wideo w oryginalnej wersji mają ustalone poziomy. dokumenty czasem nie uwzględniają tego wyraźnie.

dlatego istnieje silny argument, że w większości gier bez projektowania poziomów lub losowych układów poziomy są ustalone, co ma duży wpływ na faktyczną złożoność rozwiązania „gry”. tj. czym dokładnie jest „gra”? czy zawiera losowe układy i / lub możliwość projektowania poziomów? czy projektowanie poziomów jest częścią mapowania obliczeniowego? problemy te zostały nieco omówione w bieżących artykułach.

w przeciwieństwie do skrajności dokumentów, można argumentować, że wszystkie rzeczywiste implementacje gier wideo są rozwiązane przez FSM, ponieważ mają skończoną pamięć !

aby istniały prawdziwe odwzorowania obliczeniowe, w zasadzie trzeba uogólnić grę

  • poziomy o dowolnym rozmiarze! dzięki czemu można to odwzorować na TM za pomocą taśm „wejściowych” o dowolnym rozmiarze / nieograniczonym rozmiarze.
  • projektowanie poziomów, które umożliwia tworzenie tych poziomów.

nieco podobny problem z mapowaniem pojawia się w badaniach CA / Cellular Automata, w których istnieją pomysły na stosowanie nieskończonych okresowych wzorców na CA jako „wzorce początkowe” w celu udowodnienia równoważności / kompletności TM.

ogólnie rzecz biorąc, twoje pytanie nie jest ściśle określone, dopóki nie wyjaśnisz lepiej (tj. bardziej formalnie / matematycznie ), co rozumiesz przez „w grze z drzwiami i płytkami dociskowymi” oraz w sposób, który nawet papier nie wydaje się ściśle określony, szczególnie wrt do pomysłów na projektowanie poziomów, nieograniczone poziomy wielkości itp. ale zauważ, że te „gry” z tych cech zdefiniowanych następnie zostały oderwane od rzeczywistych / Rynek gier wideo w bardzo znaczący sposób.

w skrócie, myślę, że jest to interesujące / wartościowe badanie, chociaż zaczyna się jako nieco nieformalne i zasługuje na dalszy rozwój, ale do pewnego stopnia jego formalizacja musi zostać zaostrzona szczególnie w podstawowych definicjach, jeśli ma się dalej rozwijać. musi wprowadzić bardziej rygorystyczne / formalne / przejrzyste rozróżnienie między realizacjami a abstrakcjami .

vzn
źródło
na przykład tutaj jest artykuł na temat Pancernika jako NP zakończony, ale lepiej / formalnie stwierdza / opisuje NP całkowite uogólnienie gry o ograniczonych rozmiarach. Pancerniki jako problem decyzyjny Sevenster, sec2.
vzn
innym przykładem subtelności w uogólnianiu / abstrakcjonowaniu problemu, uogólnienie geometrii 15-łamigłówek może wpłynąć na jej kompletność NP . Uwaga: kwadratowa lub prostokątna siatka może wpływać na wyniki.
vzn
7
Chociaż jest to problem, myślę, że twoje twierdzenie, że jest to porzucone w literaturze, jest bardzo zawyżone. Biorąc pod uwagę istnienie dokumentów takich jak Fraenkel i in. FOCS 1978 na temat złożoności warcabów, Even i Tarjan JACM 1976 na temat Hex oraz Robertson i Munro Util. Matematyka Twoje twierdzenie, że jest to zupełnie nowy obszar z 1978 roku, jest również mocno zawyżone.
David Eppstein,
oczywiście gry ogólnie badane z perspektywy TCS nie są nowe, a gry wideo są takie, jak zaznaczono w tekście.
vzn
1
Mahjong Solitaire : 1994. Saper : 2000. Tetris : 2002. Czy nie liczą się one jako gry wideo, czy używasz długiej dekady ?
Peter Shor,