Gibt es eine Reduzierung auf "Tür- und Druckplatten" -Spiele, bei denen die Lösungslänge nicht explodiert?

12

Dieses Papier gibt einen Beweis dafür, dass es in einem Spiel mit Türen und Druckplatten PSPACE-schwer ist, zu bestimmen, ob der Avatar (des Spielers) einen bestimmten Ort erreichen kann oder nicht. Dies wird durch eine Reduktion von TQBF bewiesen , und die Länge der resultierenden Lösungen hängt exponentiell von der Anzahl der Universalquantifikatoren in der Formel ab.

Gibt es eine Reduzierung von einer NPSPACE-Maschine auf ein solches Spiel, bei dem die Länge der Lösungen des Spiels polynomiell mit der Länge der Akzeptanzpfade der Maschine zusammenhängt?

Jeffε
quelle
1
kurze Skizze eines formelleren Defn von "Spiel mit Türen und Druckplatten" [leider nicht wirklich in der Zeitung an einer Stelle gegeben]. Das verallgemeinerte Spiel ist eine unendliche 2D-Karte, die als Graph (von beliebiger Größe) von Verbindungsräumen / -regionen dargestellt werden kann. Knoten des Graphen sind Räume / Regionen (Äquivalente, Zellen / Tunnel usw.), Kanten sind Türen zwischen ihnen. Die Druckplatten sind Schalter in den Räumen. Ein Schalter steuert eine Türöffnung. Türen beginnen in einem willkürlichen Zustand, manche offen, manche geschlossen. (etc.) ... es scheint jedoch, dass der Autor nur ebene Graphen betrachtet.
vzn
Darüber hinaus scheint die Frage der Frage, ob die Länge des minimalen Pfades einer Lösung (in Kanten gezählt) durch den Graphen polynomiell oder exponentiell mit der Größe des Graphen / der Schalter zusammenhängt, sehr nahe oder nahezu gleichwertig zu sein. .. dies wiederum scheint eng mit der Frage verbunden zu sein, wie viele Zyklen auf dem Weg notwendig sind oder ob sie nicht ...
vzn

Antworten:

2

Vielleicht können Sie eine LBA einfach simulieren. Die Idee ist die folgende:

  • Fügen Sie für jede Zelle des LBA-Bandes ein Zellen-Gadget , das nur von unten eingegeben und nur von oben verlassen werden kann.Gich

  • das Gerät hat eine Eingangstür die die Kopfposition simuliert ( bei jedem Schritt wird nur eine C i geöffnet);CichCich

  • dann gibt es zwei Bittüren und O i ; Z i wird geöffnet, wenn die Zelle eine Null enthält, O i wird geöffnet, wenn die Zelle eine Eins enthält;ZichÖichZichÖich

  • beide Bit Türen führen zu einer ähnlichen Steuerstruktur , die von mehreren Einweg besteht Korridore ; ein Korridor entspricht einem Zustand des LBA, und die Tür des i- ten Korridors wird genau dann geöffnet, wenn der aktuelle Zustand des LBA q i ist ;qichichqich

  • Gemäß der (möglicherweise nicht deterministischen) Übergangstabelle des LBA ändert ein Durchlaufen des (geöffneten) Korridors den aktuellen Zustand des LBA und die Konfiguration der Bittüren, schließt die Tür und öffnet C i + 1 oder C i - 1 .CichCich+1Cich-1

In der folgenden Abbildung ist ein Zellen-Gadget skizziert.

Bildbeschreibung hier eingeben

Nicht deterministische Auswahlmöglichkeiten können realisiert werden, indem die Korridore in den Kontrollstrukturen in zwei oder mehr Unterkorridore aufgeteilt werden, wie in der folgenden Abbildung gezeigt.

Bildbeschreibung hier eingeben

Hinweis: Wenn eine Platte nur eine einzige Tür öffnen / schließen kann, können Sie eine Hilfskonstruktion mit (langen) Einwegkorridoren hinzufügen, die die verschiedenen Zustandstüren jeder Zelle (de) aktiviert.

Marzio De Biasi
quelle
Wenn eine Tür nur von einer einzigen Platte geöffnet und von einer einzigen Platte geschlossen werden kann, können Sie Crossover - Geräte (wie ich es beschreiben könnte) verwenden, um die Korridore nur zum Eingang der gewünschten Zelle führen zu lassen (wodurch die Zelle entfernt wird) Bedarf für die C1-Türen), implementieren Sie Z1 und O1 mit vielen verschiedenen Türen, denen jeweils eine Schließplatte unmittelbar nachgeordnet ist, und implementieren Sie die Türen q0, ..., q4 sowie viele Minikorridore mit jeweils zwei Türen durch eine Platte, die eine dieser beiden Türen schließt, und eine Platte, die eine der beiden offenen Türen auf dem Qi des anderen [Zellenwerts] schließt.
Unabhängig von den Vorschlägen in meinem vorherigen Kommentar, wenn der LBA dann nicht deterministisch ist Die Einwegkorridore würden Unterkorridore benötigen, um die nicht deterministische Wahl anzuzeigen.
?? ist nicht LBA Erkennung = (N) PSPACE? Anscheinend wäre es hilfreicher, wenn die Antwort in Form einer Komplexitätsklasse formuliert würde.
vzn
@ RickyDemer: ok, ich habe ein Beispiel für eine nicht deterministische Wahl hinzugefügt. Verwenden Sie Vigliettas Metatheoreme, um die Komplexität einiger Spiele zu beweisen?
Marzio De Biasi
Ich las seine Metatheoreme und stellte fest, dass dies eine Sache ist, die sie nicht ansprechen.
2

Ein anderer schneller Weg, um das Metatheorem 2c (PSPACE-Härte, wenn die Türen durch zwei Platten gesteuert werden) zu beweisen, ist die Verwendung des Frameworks für nicht deterministische Constraint-Logik ( RA Hearn und ED Demaine, Das Modell für nicht deterministische Constraint-Logik der Berechnung: Reduktionen und Anwendungen ).

In diesem Fall ist es ausreichend, eine horizontale Reihe vertikaler Korridorpaare zu verwenden. Der Zustand jedes Korridorpaares gibt die Richtung (nach innen / außen) einer Kante im ursprünglichen Abhängigkeitsgraphen an. Es reicht aus, das UND-Gadget und das ODER-Gadget wie in der folgenden Abbildung skizziert zu simulieren.

Bildbeschreibung hier eingeben

Marzio De Biasi
quelle
-5

Diese Art der Forschung, Videospiele mit der Komplexität von Computern in Verbindung zu bringen, ist ziemlich faszinierend, aber auch ziemlich neu, im Allgemeinen weniger als ein Jahrzehnt alt. Ich werde hier argumentieren, dass es eine Subtilität gibt, die in den aktuellen Analysen manchmal übersehen wird [habe dies in der zitierten Veröffentlichung oder in anderen Veröffentlichungen bisher nicht gesehen / bemerkt] und die die Beantwortung der angegebenen Frage definitiv erschwert.

Um eine Beziehung zu einem Computersystem zu beweisen, muss man in der Lage sein, das Computersystem auf das Spiel abzubilden und umgekehrt. In der oben zitierten Veröffentlichung von Viglietta gibt es beispielsweise ein Konzept, dass Druckplatten und Türen (dh die Druckplattensteuertüren) "wie" QBFs sein können. Diese Analogie ist zweifellos realisierbar, da sie sie ausgearbeitet hat. Mit einem QBF kann man ein Spiel mit Druckplatten und Türen lösen.

Hier ist jedoch die Subtilität. In einem bestimmten Spiel sind die Layouts des Spiels im Grunde genommen festgelegt. Im Videospiel-Design wird das Konzept verschiedener Layouts als "Layout-Design" bezeichnet und ist nicht bei allen Spielen "gegeben". Zum Beispiel im bahnbrechenden Spiel Doom wurden die Level-Design-Tools Open-Sourcing-fähig gemacht, dh den Spielern zur Verfügung gestellt. Mit anderen Worten: Beliebiges Level-Design kann als Teil des Spiels betrachtet werden. Bei anderen Spielen, die in Zeitungen behandelt werden, haben die ursprünglich gebauten Videospiele feste Level. die Papiere berücksichtigen dies manchmal nicht explizit.

Daher gibt es ein starkes Argument dafür, dass in den meisten Spielen ohne Level-Design oder zufällige Layouts die Levels fest sind, und dies hat einen großen Einfluss auf die tatsächliche Komplexität beim Lösen des "Spiels". dh was genau ist das "Spiel"? Enthält es zufällige Layouts und / oder Level-Design-Möglichkeiten? Ist Level Design Teil der rechnergestützten Zuordnung? Diese Themen werden in aktuellen Veröffentlichungen etwas beschönigt.

Man könnte argumentieren, dass alle realen Videospielimplementierungen von FSMs lösbar sind, weil sie endlichen Speicher haben !

Damit es echte rechnerische Zuordnungen gibt, muss man das Spiel im Grunde verallgemeinern , um es einzubeziehen

  • Ebenen mit beliebiger Größe! Damit kann dies auf TMs mit "Eingabe" -Bändern beliebiger / unbegrenzter Größe abgebildet werden.
  • Level-Design, das die Erstellung dieser Levels ermöglicht.

Ein etwas ähnliches Mapping-Problem tritt in der CA / Cellular Automata-Forschung auf, wo Überlegungen angestellt werden, unendliche periodische Muster auf den CAs als "Startmuster" zu verwenden, um die TM-Äquivalenz / Vollständigkeit zu beweisen.

Daher ist Ihre Frage im Allgemeinen nicht genau definiert, bis Sie besser (dh formeller / mathematischer) klargestellt haben, was Sie unter "in einem Spiel mit Türen und Druckplatten" verstehen und auf eine Weise, die selbst das Papier anscheinend nicht genau definiert Hier finden Sie Ideen zum Level-Design, zu unbegrenzten Größen usw. Beachten Sie jedoch, dass die mit diesen Funktionen definierten "Spiele" dann abstrahiert wurden in sehr bedeutender Weise von den tatsächlichen / realen Videospielen .

Kurz gesagt, ich denke, dies ist eine interessante / lohnende Forschung, auch wenn sie etwas informell beginnt und weitere Fortschritte verdient, aber bis zu einem gewissen Grad muss ihre Formalisierung strenger gemacht werden, insbesondere in grundlegenden Definitionen, wenn sie weiter vorangetrieben werden soll. Es muss eine strengere / formalere / transparentere Unterscheidung zwischen Implementierungen und Abstraktionen geben .

vzn
quelle
Zum Beispiel ist hier ein Artikel über das Schlachtschiff als NP abgeschlossen, der jedoch die NP-vollständige Verallgemeinerung des Spiels mit begrenzter Größe besser / formell angibt / beschreibt. Schlachtschiffe als Entscheidungsproblem von Sevenster, Abschnitt 2.
VZN
Ein weiteres Beispiel für Feinheiten bei der Verallgemeinerung / Abstraktion des Problems ist die Verallgemeinerung der 15-Puzzle-Geometrie, die sich auf die NP-Vollständigkeit auswirken kann . Beachten Sie, dass ein quadratisches oder rechteckiges Gitter die Ergebnisse beeinflussen kann.
vzn
7
Obwohl dies ein Problem ist, denke ich, dass Ihre Behauptung, dass dies in der Literatur beschönigt ist, stark überbewertet ist. Und angesichts der Existenz von Artikeln wie Fraenkel et al., FOCS 1978 über die Komplexität von Checkern, Even und Tarjan JACM 1976 über Hex sowie Robertson und Munro Util. Mathematik. 1978 bei Instant Insanity wird Ihre Behauptung, dass dies ein brandneues Gebiet ist, ebenfalls stark überbewertet.
David Eppstein
Offensichtlich sind Spiele im Allgemeinen, die aus TCS-Sicht untersucht wurden, nicht neu, ihre Videospiele also, wie der Text genau angibt.
vzn
1
Mahjong-Solitaire : 1994. Minesweeper : 2000. Tetris : 2002. Zählen diese nicht als Videospiele oder verwenden Sie ein langes Jahrzehnt ?
Peter Shor