Ist Magic: the Gathering Turing abgeschlossen?

Ich bin mir bewusst, dass dies eine sehr spezielle Frage ist, und ich bezweifle, dass sie von jedem beantwortet wird, der mit den Regeln der Magie noch nicht vertraut ist. Cross-posted zu Draw3Cards . Hier sind die umfassenden Regeln für das Spiel Magic: the Gathering . In dieser Frage finden Sie eine Liste aller Magic Cards. Meine Frage ist - ist das Spiel Turing Complete?

Weitere Details finden Sie im Beitrag unter Draw3Cards .

Alex Churchill (@AlexC) hat eine Lösung veröffentlicht, die keine Zusammenarbeit zwischen den Spielern erfordert, sondern die vollständige Ausführung einer universellen Turing-Maschine mit zwei Zuständen und 18 Bandsymbolen modelliert. Weitere Informationen finden Sie unter https://www.toothycat.net/~hologram/Turing/ [ archive ].

Ok, ich habe eine Lösung, die das Mana-Brand-Problem vermeidet, auf das ich gestoßen bin. Dies ist eine Art Hack, da ich davon ausgehen muss, dass die Spieler bestimmte Länder identifizieren können, was meines Erachtens in den Regeln nicht behandelt wird. In der Praxis ist dies der Fall, da sie in einer Reihe angeordnet werden können, die auf der Reihenfolge basiert, in der sie gespielt werden.

Zuerst die vollständige Beschreibung des Problems von der Draw3Cards-Site:

Eine positive Antwort würde sich aus folgenden Komponenten zusammensetzen:

1. Eine berechenbare Funktion fM von Turing Machines zu bestellten Magic Decks (wo die Reihenfolge der Bibliothek wichtig ist)
2. Zwei gut definierte deterministische und berechenbare Strategien, um Magic zu spielen (die nicht vom Deck abhängen). Nennen wir sie Strategie TS (Turing Strategy) und Strategie IS (Input Strategy).
3. Eine berechenbare Methode, um eine beliebige Folge von Nullen und Einsen als Magic Input-Deck zu codieren. Ein solcher Weg wäre, die Gödel-Nummer der Saite zu nehmen und so viele Inseln wie möglich in das Input-Deck zu legen.

Die zusätzliche Bedingung, die erfüllt sein sollte, ist folgende: Betrachten wir bei gegebenen Turing Machines TM das Ergebnis des Magic-Spiels zwischen der Strategie TS, die mit Deck fM (TM) spielt, und der Strategie TI, die mit Deck fI (I) spielt, wenn sich die Bibliotheken befinden wird vor Spielbeginn nicht gemischt. Dieses Spiel sollte nur dann vom ersten Spieler gewonnen werden, wenn TM (I) = wahr ist.

Also hier ist die Idee. Wir haben 2 Spieler, A und B. B wird die Eingabe liefern, während A direkt eine Turing-Maschine implementiert. Die Decks bestehen fast ausschließlich aus Land, aber auch aus der Edelstein-Array- Karte, um das Mana zu löschen. A wird drei Arten von Land haben: Inseln, Berge und Wälder. Die Grundidee besteht darin, mit abgegriffenem Land eine 1 und mit nicht abgegriffenem Land eine 0 darzustellen. Inseln werden verwendet, um den Zustand des Bandes darzustellen, Berge, um die aktuelle Position entlang des Bandes zu indizieren, und Wälder, um den internen Zustand von 24 darzustellen Zustand 2 Symbol Turing Maschine (Ich glaube, es gibt eine universelle wegen Rogozhin).

$2^5 = 32 > 24$$2^{m+1}$

$2^5 = 32 > 24$$2^{m+1}$

Strategie: A und B spielen jeweils ein Land in der Reihenfolge, in der sie gezogen wurden. Wenn jeder 4 Wälder gezeichnet hat, spielt er Edelsteinartefakt. Hinweis A geht zuerst und hat bereits eine Insel, wenn B zieht, und spielt seine erste Eingabekarte aus.

A und B setzen einfach ihre Karten in der richtigen Reihenfolge fort, bis B ihre Ebenen und Sümpfe erschöpft hat und ihre erste Insel spielt. Bei seinem nächsten Versuch tippe ich A für alles auf seine i-te Insel, wenn es sich bei Input Land um einen Sumpf handelte. A initialisiert seine Turingmaschine, indem er auf seinen ersten Wald und Berg tippt. Wenn er eine ungerade Anzahl von Karten getappt hat, tippt er auf seinen zusätzlichen Wald und verwendet all dieses Mana, um dem Edelstein-Array Marker hinzuzufügen. Ab hier läuft das Spiel wie folgt ab: B verwendet ihren Zug, um einfach den Zustand des Manas von A widerzuspiegeln. B tippt sein i-tes Eingabeland an, wenn A's i-tes Island angetippt wird. In ähnlicher Weise tippt B auf seinen i-ten Wald (Berg), wenn A auf seinen i-ten Wald (Berg) tippt. Da A immer eine gerade Anzahl von Karten abgibt, gilt dies auch für B, und das Mana wird verwendet, um dem Edelstein-Array Token hinzuzufügen.

In der Runde von A wird das gesamte Mana von A erschöpft, sodass A den Zustand des Manas von B betrachtet und den Zustand des Manas von A in der vorherigen Runde darstellt. A wendet die Übergangsregel gemäß der Universalmaschine (24,2) auf den Zustand von B an, um seinen neuen Zustand zu erhalten.

Das Spiel wird auf diese Weise fortgesetzt, bis die Drehmaschine anhält. Zu diesem Zeitpunkt versetzt A seine Berge in den reservierten "fertigen" Zustand (den vollständig unbenutzten Zustand). Wenn die Turing-Maschine in einem akzeptierenden Zustand anhält, kopiert B den Zustand der Berge von A, tippt jedoch das gesamte verbleibende Land ab, ohne die Edelstein-Anordnung zu verwenden, und beginnt so den Selbstmordprozess durch Mana-Verbrennung. Wenn die Berge von B am Zug von A "fertig" sind und das gesamte andere Land von B erschlossen wird, tut A einfach nichts (beachte, dass sich seine Berge automatisch im "fertig" -Zustand befinden). Wenn die Berge von A fertig sind, aber nichts anderes erschlossen ist, setzt B den Selbstmord durch Mana-Verbrennung fort. Dies wird wiederholt, bis B tot ist.

Wenn der Computer jedoch im Ablehnungszustand endet, lässt B alle seine Karten ungenutzt. Wenn alle Karten von B nicht getappt sind, tippt A alle seine Karten ab und beginnt den gleichen Selbstmordprozess durch Mana-Verbrennung. Wenn alle Karten von A, die keine Bergkarten sind, getappt sind und die Berge nicht getappt sind, lässt B alle ihre Karten ungetappt. Dies führt dazu, dass A den Mana-Selbstmord fortsetzt, bis er das Spiel verliert.

Dies sollte die in der Frage gestellten Kriterien erfüllen, und wenn diese Reihenfolge zulässig ist, glaube ich, dass das Spiel im in der Frage beschriebenen Sinne vollständig ist.

Alex Churchill, Stella Biderman und Austin Herrick haben dieses Papier veröffentlicht, das zeigt, dass Magic Turing Complete ist

Abstract — Magic: The Gathering ist ein beliebtes und bekanntermaßen kompliziertes Sammelkartenspiel über magische Kämpfe. In diesem Artikel zeigen wir, dass ein optimales Spiel in der realen Magie mindestens so schwierig ist wie das Halteproblem, indem ein seit einem Jahrzehnt offenes Problem gelöst wird [1] [10]. Dazu präsentieren wir eine Methode zum Einbetten einer beliebigen Turing-Maschine in ein Magiespiel, sodass der erste Spieler das Spiel garantiert gewinnt, wenn die Turing-Maschine anhält. Unser Ergebnis bezieht sich auf die Art und Weise, wie echte Magie gespielt wird, wie sie mit turniergerechten Decks in Standardgröße erzielt werden kann und beruht nicht auf Stochastizität oder verborgenen Informationen. Unser Ergebnis ist auch insofern höchst ungewöhnlich, als alle Züge beider Spieler in die Konstruktion gezwungen werden. Dies zeigt, dass es nicht zu entscheiden ist, wer ein Spiel gewinnt, in dem keiner der Spieler eine nicht triviale Entscheidung für den Rest des Spiels trifft. Wir schließen mit einer Diskussion der Implikationen für eine einheitliche rechnergestützte Spieltheorie und Anmerkungen zur Spielbarkeit eines solchen Bretts in einem Turnierumfeld.