Gibt es eine Verallgemeinerung des GO-Spiels, von dem bekannt ist, dass es Turing vollständig ist?

Gibt es eine Verallgemeinerung des GO-Spiels, von dem bekannt ist, dass es Turing vollständig ist?

Wenn nein, haben Sie einige Vorschläge zu vernünftigen (Verallgemeinerungs-) Regeln, mit denen versucht werden kann, zu beweisen, dass Turing vollständig ist? Das Offensichtliche ist, dass das Spiel auf einem unendlichen Brett (positiver Quadrant) gespielt werden muss. Aber was ist mit den Bedingungen im Spiel und am Ende des Spiels?

Verwandte: Rengo Kriegspiel, eine Teamvariante von Go mit verbundenen Augen, wird als unentscheidbar vermutet.

http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel

Robert Hearns These (und das entsprechende Buch mit Erik Demaine) diskutieren dieses Problem. Sie beweisen andere Probleme, die durch "TEAM COMPUTATION GAME" unentscheidbar sind, das direkt aus der Akzeptanz der Turing-Maschine bei leerer Eingabe reduziert wird (siehe Satz 24 auf Seite 70 der Arbeit). Es scheint mir also, dass eine solche Reduzierung bedeuten würde, dass Rengo Kriegspiel vollständig ist.

Andererseits besagt ihre Diskussion, dass diese Reduzierung sehr schwierig wäre (siehe Seite 123). Obwohl dies ein potenzieller Weg ist, scheint es, dass er zuvor untersucht wurde.

Dies ist ein Aufbau meines Kommentars mit der Idee, Shishos (Leitern) als Berechnungen zu verwenden. Es ist lediglich ein Versuch, ein auf Go basierendes Berechnungsmodell anzugeben, für das es sinnvoll ist, zu fragen, ob es Turing-vollständig ist.

Wir beginnen damit, ein leistungsfähiges, aber nicht Turing-vollständiges Berechnungsmodell zu reparieren, das immer anhält, zum Beispiel einige typisierte Kalküle oder primitive rekursive Funktionen. Dies ist der "betrügerische" Teil, da wir ein externes Berechnungsmodell verwenden, aber es ist ein schwächeres. Hoffentlich ist es das Go-Spiel, das die Lücke füllt und es Turing-vollständig macht.$\lambda$

Wir betrachten einen unendlichen Goban, der mit . Jetzt kann die anfängliche Konfiguration des Gobans unendlich sein und wird durch einen Algorithmus aus unserem Formalismus gegeben: Bei gegebenen Koordinaten sagt der Algorithmus, ob der Schnittpunkt leer, von einem schwarzen Stein besetzt oder besetzt ist von einem weißen Stein. Wir legen eine maximale Größe der Gruppen in der Anfangskonfiguration fest. Dies bedeutet, dass wir bei einer bestimmten Position immer die Gruppe, die sie besetzt, und die Anzahl der Freiheiten berechnen oder auf "ungültige Konfiguration" antworten können. ( i , j ) ( i , j ) $\mathbb Z\times\mathbb Z$$(i,j)$$(i,j)$$N$

Wir befestigen auch einen markierten Stein (sagen wir schwarz) an der Koordinate . Eine Erstkonfiguration ist gültig, wenn die Gruppe des markierten Steins zu Beginn zwei Freiheiten hat.$(0,0)$

Jetzt können wir diese Konfiguration des Gobans als die anfängliche Konfiguration einer nicht deterministischen Maschine betrachten, bei der ein Übergang darin besteht, einen weißen Stein in einer der beiden Freiheiten der markierten Gruppe zu spielen. Bei jedem Schritt antwortet Schwarz automatisch in der anderen Freiheit.

Der Lauf endet wenn

• Die markierte Gruppe wird erfasst. In diesem Fall wird die Eingabe akzeptiert
• Die markierte Gruppe erwirbt mehr als Freiheiten. In diesem Fall wird die Eingabe abgelehnt.$2$

Der Lauf kann auch für immer weitergehen ...

Bei nicht deterministischen Turing-Maschinen wird die Eingabe akzeptiert, wenn ein akzeptierender Lauf vorliegt.

Dank der Existenz des gebundenen (das ein Parameter des gesamten Modells ist) ist es einfach, diese Maschine mit einem nicht deterministischen TM zu simulieren .$N$

Vermutung : Für groß genug ist (wahrscheinlich nicht mehr als , um die erforderlichen Geräte zu erhalten), ist dieses Modell Turing-vollständig.$N$$10$

Hier sind einige Beweise / Analysen / Ergebnisse, die sich auf Ihre Vermutung stützen, dass eine Go-Verallgemeinerung unentscheidbar sein könnte (auch bekannt als "Turing Complete"). Zumindest scheint es keinen bekannten oder allgemein akzeptierten Fall zu geben, und eine Suche liefert mehr Ergebnisse auf der Idee, dass seine ("natürlichen"?) Verallgemeinerungen entscheidbar sind. Die in diesem Aufsatz berücksichtigte Verallgemeinerung ist PSpace vollständig. Es gibt jedoch keine "konsistenten" oder "unvermeidlichen" Möglichkeiten, Spiele zu verallgemeinern, und es ist denkbar, dass jemand eine Variante entwickelt, die nicht zu entscheiden ist.

Tatsächlich können die meisten nicht trivialen Spiele wahrscheinlich auf irgendeine Weise modifiziert oder verallgemeinert werden, um unentscheidbare Varianten zu haben. (Ein berühmtes einfaches Spiel / Beispiel in dieser Richtung, das von Conway als "unentscheidbar" erwiesen wurde, ist das Leben .) Die folgenden Referenzen verweisen auch auf viele andere Referenzen.

Ein anderer Gedanke könnte sein, dass kein Spiel unentscheidbar sein kann, wenn es gewinnbar ist, dh Unentscheidbarkeit wirkt der Idee entgegen, dass Spiele mit einem Gewinner in einer endlichen Anzahl von Zügen enden. Mit anderen Worten, vielleicht werden Spiele besser / natürlicher analysiert als innerhalb der (entscheidbaren) Komplexitätshierarchie, wie dies normalerweise der Fall ist.

• GO ist PSpace schwer , von Reyzin, über das Ergebnis von Lichtenstein, Sipser
• GO ist PSpace hart von Lichetenstein, Sipser
• Go-Endspiele sind PSPACE-hart , Wolfe

In meiner Patentanmeldung - Komplette Sätze von Spielkomponenten mit Wahrsagungselementen- Ich beschreibe Varianten für Spielregeln (einschließlich Spiele, die auf einem 19x19 Go-Brett gespielt werden), die Spielen wie Schach und Go ein gewisses Maß an Komplexität verleihen, sodass Brettpositionen linear begrenzte Automaten für einen beliebig langen Zeitraum simulieren können. Wie in den obigen Kommentaren erwähnt, würde Go on a Infinite Board einige Schwierigkeiten bei der Bestimmung eines Spielgewinners mit sich bringen, da es sich im Gegensatz zu Schach um ein Spiel mit einem territorialen Ziel handelt. Aus meiner Anwendung: "Viele andere Ausführungsformen von Turing-Komplettspielen sind möglich, aber ich werde nur zwei weitere kurze beschreibende Beispiele geben, um einige andere Möglichkeiten zur Anpassung von Spielen als Turing-Komplettvarianten zu veranschaulichen und dann die Auswirkungen zu diskutieren. Spiele wie Gomoku (SCARNE, S. 537) und Go (SCARNE, S. 533-7), die auf einem 19 × 19-Raster mit zwei verschiedenen Farben von Stücken gespielt werden, sind ebenfalls Kandidaten für Turing-Komplettvarianten mit Wahrsagungselementen. Bei diesen Spielen wird Rogozhins (2,18) UTM verwendet. Dies ist auch die von Churchill (2012) verwendete UTM, wie in den Referenzen des Standes der Technik zitiert. Um eine Spielvariante dieses Typs zu erstellen, verwenden wir Münzen für unsere Spielsteine. Bereiten Sie sich darauf vor, die gewählte Spielvariante zu spielen, indem Sie große Mengen von zwei verschiedenen Münzen - zum Beispiel Pennys und Groschen - basierend auf dem Datum auf der Vorderseite in Stapel sortieren. In diesem Fall werden Datumsangaben auf den Münzen im Rahmen der UTM-Anweisungen als Ersatz für Farben verwendet. In den zuvor beschriebenen Ausführungsformen wurden Farben für UTM-Anweisungen verwendet, aber diese Ausführungsform zeigt, dass ein anderes Attribut der Spielkomponenten, in diesem Fall eine Zahl, könnte genutzt werden. Im allgemeinsten Fall werde ich auf dieses Potenzial für das Ersetzen eines anderen Attributs der Spielkomponenten anstelle von Farben als Verwendung einer Teilmenge der Menge von Spielkomponenten verweisen. Jeder Spieler sollte mit 19 Stapeln von 19 seiner gewählten Münze beginnen. Jeder Stapel von Pennys und Groschen sollte nur Münzen mit demselben Datum enthalten - sagen wir zum Beispiel 19 Pennys von 1991, 19 Groschen von 1991, 19 Pennies von 1992 usw. bis 19 Groschen von 2009. Eine Münze darf nur sein Wird in der linken Spalte des Bretts gespielt, wenn es ein Datum von 1991 hat. Für die nächste Spalte rechts ist eine Münze mit dem Datum 1992 usw. bis 2009 in der rechten Spalte erforderlich. Spielen Sie wie gewohnt Go oder Gomoku, mit Ausnahme dieser Regel, welche Stücke wo gespielt werden dürfen. Wenn die (2, 18) UTM wird basierend auf vorgewählten Spielkriterien (auf ähnliche Weise wie in anderen Ausführungsformen beschrieben) initiiert. Der UTM-Lese- / Schreibkopf liest eine Heads-Up-Münze als Zustand 1 und eine Heads-Down-Münze als Zustand 2 Eine Münze mit dem Datum 1991 wird von der UTM als A-Münze betrachtet, 1992 = B, 1993 = C usw., wobei das Jahr 2000 übersprungen wird. Münzen werden gemäß den UTM-Anweisungen durch andere mit unterschiedlichen Daten ersetzt. In Bezug auf Wahrsagungselemente gibt es 360 Grad im Tierkreis und 360 Kreuzungen, die die zentrale Kreuzung auf einem Go-Brett umgeben, so dass Sabian-Symbole (ROCHE) eine offensichtliche Übereinstimmung sind. Weitere Wahrsagungsaspekte eines Go-Bretts und -Spiels finden Sie unter "Die religiösen Dimensionen von Go" (SCHNEIDER). "Go-Spielszenarien, in denen eine vorab vereinbarte UTM-Analyse einer Brettposition nützlich sein kann, umfassen Bretter mitTriple Kos und Boards mit langen Ko-Kämpfen .

Lohnt sich der Kompromiss zwischen dem Hinzufügen zusätzlicher Komplexität in Regeln, um die Vollständigkeit von Turing für Tabletop-Spiele einzuführen? Wahrscheinlich hängt die Antwort auf diese Frage vom Spiel und den Spielern ab, aber Magic: the Gathering ist ein Beispiel dafür, dass die Antwort auf diese Frage zumindest in einigen Fällen wahrscheinlich Ja lautet.