Magic: The Gathering ist ein Kartenspiel, bei dem jeder Spieler ein Set von unterschiedlichen Karten hat die im Spielablauf verschiedene Sachen machen. Die grundlegenden Regeln sind im Wesentlichen (wie bei jedem Kartenspiel) sehr simpel: Spiel in deinem Zug eine Karte und wenn auf der was drauf steht, dann mach das.
Die Dinge die auf den Karten stehen sind im Grunde auch nicht sehr komplex. Das wuerde dem Grundgedanken eines (Gesellschafts)Spiels entgegen stehen. Die Komplexitaet liegt in der Interaktion und wenn man nun bestimmte Karten in einer bestimmten Reihenfolge spielt, kann man damit eine Turingmaschine bauen.
Churchill, A., Biderman, S. und Austin Herrick schreiben ueber die Konstruktion einer Turing Maschine aus diesen einfachen Grundbausteinen in ihrem Artikel mit dem passenden Titel „Magic: The Gathering is Turing Complete“ … aber der Reihe nach.
Im Allgemeinen war dies der Konsensus bzgl. normaler, nicht-elektronischer (!) (Gesellschafts)Spiele :
[t]he approach of embedding a Turing machine inside a game directly is generally not considered to be feasible for real-world games […].
Der Grund war, dass …
[…] the unbounded memory required to simulate a Turing machine entirely in a game would be a violation of the very nature of a game.
Darum die obige Beschraenkung auf nicht-elektronische Spiele, denn Minecraft oder Dwarf Fortress haben im Wesentlichen Zugriff zu „unendlichem Speicher“ und da ist es zwar immer noch eine ziemliche Leistung eine Turingmaschine zu bauen, aber es verwundert nicht all zu sehr.
Ein weiterer Grund fuer den bisherigen Konsensus war, dass …
[…] almost every real-world game is trivially decidable, as they produce game trees with only computable paths.
Das kann zwar SEHR komplex (bspw. im Schach) werden, prinzipiell ist das natuerlich richtig. Diese Eigenschaft steht aber einer Turingmaschine entgegen, denn diese ist Turing-vollstaendig. Zur Erinnerung: letzteres bedeutet, dass man ALLE Algorithmen implementieren kann, also auch solche bei den man NICHT entscheiden kann ob die anhalten (oder nicht); was dann ja zum Halteproblem fuehrt.
Der Artikel ist stellenweise lustig zu lesen, denn normalerweise liest man so Sachen wie …
[c]onsider the following situation: both players control Lich, Transcendence, and Laboratory Maniac. One player then casts Menacing Ogre.
… eher nicht in einer wissenschaftlichen Publikation … tihihi.
Aber wie sind die verschiedenen Teile einer Turingmaschine nun konstruiert? Der Speicher ist einfach, das sind einfach nur Karten mit verschiedenen Werten (und Farben, aber ’ne Farbe ist ja auch ein Wert).
Als naechstes braucht man einen Schreib- und Lesekopf und Instruktionen was der (auf dem Speicher) machen soll.
Control instructions in a Turing machine are represented by a table of conditional statements of the form “if the machine is in state s, and the last read cell is symbol k, then do such-and-such.”
Hier nimmt man Karten mit bestimmten Bedingungen …
[m]any Magic cards have triggered abilities which can function like conditional statements.
… und mithilfe wiederum anderer Karte modifiziert man diese Bedingungen gezielt. Letztlich wird dann ein …
Rotlung Reanimator („Whenever Rotlung Reanimator or another Cleric dies, create a 2/2 black Zombie creature token“)
… modifiziert mit …
Artificial Evolution […] „Change the text of target spell or permanent by replacing all instances of one creature type with another […]“
… zu:
Rotlung Reanimator [modifiziert] […] „Whenever Rotlung Reanimator or another Aetherborn dies, create a 2/2 white Sliver creature token“.
Das entspricht dann einer Instruktion wie oben beschrieben; ganz konkret in diesem Fall:
When reading symbol 1 in state A, write symbol 18 and move left.
Symbol 1 ist „Aetherborn“ (A), Symbol 18 ist „Sliver“ (S), „write“ weil Aetherborn mit Sliver ersetzt wird und aus der Farbe der Karte (hier sind die weisz) folgt automatisch, wie sich der Kopf danach bewegen muss.
Das macht man nun mit verschiedenen Karten / Kreaturen und am Ende hat man alle Instruktionen und Teile (man braucht noch mehr als Speicher und Schreib/Lesekopf) die man fuer eine Turingmaschine braucht.
In einem Spielzug fuehrt man dann bspw. eine Aktion aus, die dazu fuehrt, dass gewisse Kreaturen sterben; das triggert die modifizierten Rotlung Reanimators und dann wird eine Instruktion ausgefuehrt.
Nun gibt es Zustaende des „Spielbretts“ (also der Karten die ausliegen), die einem Spieler (prinzipiell) erlauben unendlich viele Zuege hintereinander zu machen … ZACK! Hat man eine Schleife … und die kann prinzipiell unendlich lange laufen … und wenn man das hat, werden die Konsequenzen vorheriger Spielzuege (die ja das Spielbrett in eine gewisse Situation bringen) prinzipiell unverhersagbar … damit hat man keinen Entscheidungsbaum mehr und steht vor dem Halteproblem welches eine Turingmaschine nun mal mit sich bringt.
URST COOL WA!
Um DOOM auf Magic laufen zu lassen, muss man „uebersetzen“ was ein Brettzustand, eine Karte, eine Kombination von Karten usw. usf. denn bedeutet. DAS ist urst kompliziert. Aber dadurch, dass eine Turingmaschine konstruiert werden kann ist Magic Turing vollstaendig und das bedeuet, dass es jedwedes Programm ausfuehren kann und daraus folgt, dass es eine solche Uebersetzung geben muss … Aber die ist bestimmt so involviert, dass die Framerate dieses DOOM bei einem Bild alle zehntausend Jahre liegt oder so … das ist etwas unpraktisch, nicht wahr … Aber um tatsaechliche Durchfuehrbarkeit geht’s mir ja ueberhaupt nicht.
Leave a Reply