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

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?

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;$G_i$

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

• 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;$Z_i$$O_i$$Z_i$$O_i$

• 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 ;$q_i$$i$$q_i$

• 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 .$C_i$$C_{i+1}$$C_{i-1}$

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

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.

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.

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.

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 .