Thomas Kahle
Das Sammelkartenspiel Magic: The Gathering entstand 1993 und besteht mittlerweile aus mehr als 27.000 verschiedenen Karten. Die Kombinationsmöglichkeiten sind so groß, dass man im Spiel eine universelle Turingmaschine einbauen kann, die komplett ohne menschliche Interaktion alles berechnen kann, was ein normaler Computer auch berechnen kann. Also kann man z.B. auch eine Magic-Situation aufbauen, sodass die Auswertung des Effekt-Stapels genau dann terminiert, wenn die ZFC-Mengenlehre inkonsitent ist. (Vgl. EIG039).
- Richard Garfield in der Genealogy
- Tasty MTG Podcast
- Comprehensive Magic Rules (pdf)
- Interesting Esoterica Account
- Magic the Gathering is Turing Complete (toothycat.net)
- Informatik für die Moderne Hausfrau Folge 43
- Wizards of the Coast Forum thread mit neuen Ideen.
- 2019 Paper MTG is Turing complete (arXiv)
- MTG is as hard as arithmetic (arXiv)
- FUN2024 Konferenz
Feedback gerne auf Mastodon @Eigenraum@podcasts.social, an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite.
Automatisch generiertes Transkript (nicht geprüft)
Music.
Hallo, willkommen zum Eigenraum-Podcast, Folge Nummer 49.
Das, was ihr da gerade gehört habt, ist eine Melodie, die aus Primzahlen komponiert wurde.
Da könnt ihr ein paar Folgen zurückhören, wie es dazu kam.
Und mein Name ist Thomas Kahle und ich mache hier einen kleinen Mathe-Podcast,
weil ich denke, dass es nicht genug Mathe-Podcasts gibt.
Und ich freue mich sehr, dass ihr entweder zum wiederholten Male oder zum ersten
Mal diese kleine werbefreie, trekkingfreie Indie-Produktion gewählt habt für
euer heutiges Podcast-Erlebnis.
So, ich habe heute wieder ein schönes Thema ausgegraben.
Ich möchte euch nämlich was erzählen über das Sammelkartenspiel Magic the Gathering.
Das kennen vielleicht einige oder viele von euch.
Also das ist ein Sammelkartenspiel. Das bedeutet, man hat ein Kartenspiel,
das zwei Spieler spielen. und die Karten, die die Spieler dabei benutzen,
die stellen sie sich selbst vorher zusammen.
Also die kaufen die sich und dann stellen sie sich eben ihren Kartensatz,
ihr Deck vorher zusammen, bevor es zu so einer Partie geht.
Und formal ist das dann ein zwei-Personen-Nullsummen-stochastisches Kartenspiel
mit unvollständiger Information. Also man weiß nicht, was der Gegner hat,
man weiß nicht, was die nächste Karte ist, die man zieht und gehört damit so
spieltheoretisch zu der gleichen Kategorie wie zum Beispiel Poker.
Und hat eben diese wichtige Eigenschaft, dass man sein eigenes Deck zusammenbaut.
Und das Spiel ist 1993 entwickelt worden von einem Mathematiker namens Richard Garfield.
Und ich habe das Ende der 90er in meiner Jugend auch mal gespielt, ziemlich intensiv.
Und dann letztes Jahr hatte ich es auch noch mal so ein bisschen rausgegraben,
als bei meinem ältesten Sohn in der Schule das Magic Fieber so ein bisschen ausgebrochen ist.
Aber das erfreut sich eigentlich seit mehreren Jahrzehnten, seit 1993 einer
fast ungebrochenen Popularität und wird auch heute noch gespielt.
Und das Interessante ist eben, dass die Karten ...
Immer weiter benutzt werden können. Also auch die ersten Karten aus der ersten
Edition sind spielbar zusammen mit den Karten, die heute neu verkauft werden.
Und trotzdem kommen immer wieder neue Karten raus.
Also es werden immer wieder, es gibt immer wieder neue Editionen,
wo neue Karten mit neuen Möglichkeiten herausgegeben werden.
Dieser Erfinder Richard Garfield, der ist Mathematiker, der ist auch promoviert,
hat in der mathematischen Genealogie den Eintrag Nummer 23.159 und seine Dissertationsschrift
hatte den Titel On the Residue Classes of Combinatorial Families of Numbers,
also ist im Bereich der Kombinatorik anzusiedeln.
Und Doktorvater war Herbert Wilf, auch ein bekannter Kombinatoriker,
der zum Beispiel das Buch Generating Functionology geschrieben hat.
Das ist ein mathematisches Gebiet, was sich Geometry of Numbers nennt,
in dem der recht bekannt ist.
Und Richard Garfield hat auch noch andere Spiele erfunden.
Ich habe mal geschaut, eins habe ich sogar zu Hause. Das heißt King of Tokyo.
Das ist so ein Brettspiel, wo die Spieler so verschiedene Monster sind,
die dann um die Vorherrschaft um Tokio kämpfen.
Also einer ist irgendwie Godzilla und andere ist so ein Riesen-Alien.
Das ist ein ganz witziges Spiel. Aber heute will ich ja eigentlich über Magic reden.
Also die meisten Leute sagen nur Magic. Das Spiel heißt eigentlich Magic the Gathering.
Und die Regeln dieses Spiels sind bis auf kleine Anpassungen und Erweiterungen,
die immer wieder gemacht werden, weil eben die neuen Karten rauskommen,
die dann irgendwie ein paar neue Regeln dazu bringen, sind die bis auf kleine
Anpassungen immer noch die gleichen wie früher.
Es gibt jetzt über 27.000 verschiedene
Magic-Karten, die dieser Verlag mittlerweile rausgebracht hat.
Und die können alle kombiniert werden zu so einem Deck. Und da hat man eben
eine entsprechende Komplexität.
Und alte Karten, also natürlich diesen Sammelkarten-Aspekt, alte Karten sind
manchmal sehr viel wert oder so.
Also wenn man das jetzt mit seinen Kindern spielt, sollte man vielleicht die
besten Karten doch nochmal irgendwie aufheben, bis die Kinder dann wieder Kinder
haben und dann sind die damit der Held oder die Heldin auf dem Schulhof.
Aber, naja, steckt auch eine ganze Menge Kommerz dahinter, also ich will jetzt
hier nicht über irgendwelche Wertzuwächse spekulieren.
Also Eigenraum ist keine Anlageberatung.
Wenn ihr Fehlernsentscheidungen trefft, verlasst euch immer auf eure eigene Analyse oder Profis.
Ich kann nicht empfehlen, mit Magic-Karten zu investieren, euer Erspartes.
Außer vielleicht ein bisschen zu spielen.
Also die zwei Aspekte des Spiels sind immer das Sammeln und dann das eigentliche Spielen.
Und bei dem eigentlichen Spiel spielen eben so zumindest im Turnierspiel zwei
Spieler und die müssen sich dann jeweils für 60 ihrer Karten entscheiden und
sich daraus ein Deck mit 60 Karten zusammenbauen.
Es gibt zwar auch noch so Mehrspielervarianten mit größeren Decks,
aber die Sportart Magic, die sozusagen auf Turnieren gespielt wird,
die sind eben zwei Spieler mit je 60 Karten.
Und das bereiten die dann lange vor, bauen sich ihr Deck zusammen,
dass er so bestimmte Effekte.
Erzielen soll und wenn man spielt, dann fängt man eben an, dass man sich so
ein paar Karten zieht, so sieben Karten und spielt die dann so nach festen Regeln raus.
Man ist dann abwechselnd dran und dann kann man in Karten ausspielen und dann passiert irgendwas.
Manche Karten geben einem dann jede Runde Energie und diese Energie,
die kann man dann wieder benutzen, um andere Zaubersprüche zu machen.
Zum Beispiel kann man sich so Kreaturen zaubern und die kann man dann losschicken
und den Gegner angreifen und dann will man dem irgendwie seine Lebenspunkte
abnehmen, um das Spiel zu gewinnen.
Aber vielleicht hat der andere auch Kreaturen draußen, die verteidigen ihn dann
oder irgendwelche Abwehrzauber und so weiter.
Da will ich jetzt gar nicht so viel drauf eingehen. Ich hoffe,
ihr habt so ein bisschen so eine Idee, wie das Spiel abläuft.
Und ich kann euch aber einen Podcast-Tipp geben an der Stelle.
Wenn ihr da mehr drüber hören wollt oder tiefer einsteigen wollt,
dann hört euch doch mal den Tasty MTG Podcast mit Martin Fischer an. Der ist ganz klasse.
Und da werden auch immer so die neuesten Karten, die rauskommen,
diskutiert und welche Strategie oder Regeländerungen sich daraus ergeben oder so.
Also Empfehlung für den Tasty MTG Podcast.
Und wenn man das mal so ein bisschen spielt, da merkt man ziemlich schnell,
dass es dann immer so ganz spezifische Fragen gibt.
Also bei der Auswertung dieser Effekte, die die ganzen Karten haben.
Kommt man eigentlich ziemlich schnell auf so, ja, fast schon mathematische Fragen.
Also es passieren so Dinge, wie man hat ein Zombie, und ich will den Zombie
wirken, also ich will den jetzt erschaffen, so ein Zombie,
aber da kommt ein Abwehrzauber und ich habe vielleicht einen Abwehrzauber,
der gegen einen Abwehrzauber wirkt und dann gibt es vielleicht noch einen Effekt,
dass jedes Mal, wenn ein Abwehrzauber gegen einen Zombie gezaubert wird,
dann passiert irgendwas, was den Zombie eigentlich stärker macht und man kommt
dann ziemlich schnell in so Fragen, wie man das eigentlich auflöst.
Also wie sozusagen die Kombination dieser verschiedenen Effekte,
die sich dann gegenseitig auslösen, passiert. Zum Beispiel in welcher Reihenfolge.
Und das muss man dann alles eben in den Regeln nachschauen. Also das ist so
das Grundwerk der Regeln für Magic the Gathering, was man eigentlich zum Losspielen
gar nicht so braucht, aber eben für Detailfragen.
Ist schon ein relativ mathematisches Werk, also die offiziellen Regeln,
die das alles festlegen und definieren, in welcher Reihenfolge solche Effekte abzuarbeiten sind.
Es ist ein 300 Seiten PDF, was man dann auf der Webseite des Verlags,
Wizards of the Coast, herunterladen kann.
Und wenn man ein Weilchen spielt, dann kommt man schon öfter in so Situationen,
wo man dann mal was in diesem PDF oder der entsprechenden Webseite dazu nachschauen muss.
So, und wenn irgendwas so kompliziert ist, wie dieses 300 Seiten Regelwerk von
Magic, dann fragt man sich als Mathematikerin vielleicht, wie kompliziert ist
es jetzt eigentlich genau?
Kann man das jetzt irgendwie messen?
Und wie es sich nun fügte, stieß ich kürzlich durch den Mastodon Account Interesting
Esoterica darauf, dass es da so ein Resultat gibt, dass Magic the Gathering
Touring vollständig ist.
Das bedeutet also, Magic the Gathering-Regeln sind genauso kompliziert wie ein
normaler Computer. Also der Computer, vor dem ich jetzt hier gerade sitze.
Und das wird ja normalerweise modelliert durch so eine Turing-Maschine.
Man drückt das immer mit Turing-Maschine aus. Aber wenn ich Turing-Maschine
höre, denke ich einfach immer an Computer, mein Computer, der hier vor mir steht.
Und diesen Interesting Esoterica-Account, den verlinke ich euch auch mal.
Das ist ein super Account, der gräbt immer so interessant esoterisch-mathematische
Dinge aus von vor zehn Jahren oder so.
Also da könnt ihr auf jeden Fall auch folgen.
So, also Touring vollständig. Magic the Gathering ist Touring vollständig.
Was soll das jetzt eigentlich bedeuten?
Das bedeutet, das System der Regeln dieses Spiels kann rechnen wie ein Computer.
Und wenn man untersuchen will, wie ein Computer rechnen kann,
was der berechnen kann und was der nicht berechnen kann, benutzt man eben gern
dieses Modell der Turing-Maschine in der theoretischen Informatik.
Und ich fasse das mal kurz zusammen. Also so eine Turing-Maschine,
die besteht ja üblicherweise aus drei Grundbausteinen, einem Speicher,
wo Informationen gespeichert werden können.
Das ist üblicherweise so ein Band, das besteht aus diskreten Zellen, wie so Speicherzellen.
Und in jeder Zelle kann ein Symbol von einem endlichen Auswahl von Symbolen gespeichert werden.
Also man hat ein endliches Alphabet, sagen wir mal Buchstaben oder auch nur Nullen und Einsen.
Und auf jeder Position kann einer davon gespeichert werden. Und üblicherweise
ist dieses Band unendlich lang in beide Richtungen.
Also mein Computer, der jetzt vor mir steht, hat zwar nur endlich viel Speicher,
aber wenn ein endlicher Algorithmus auf diesem Band rumläuft,
wird er auch nur endlich viele von diesen Speicherzellen lesen können.
Also die Turing-Maschine ist ein bisschen allgemeiner.
Okay, dann hat dieses Ding neben dem Band, dem Speicher, irgendwie so eine Hardware,
so ein Schreib-Lesekopf, der bewegt sich entlang des Bandes,
also der ist immer an einer Stelle dieses Bandes und dort kann er lesen,
was da gerade geschrieben ist auf dem Band,
also an der Stelle, wo er ist, kann das überschreiben,
sich nach links, rechts bewegen und befindet sich in einem Zustand.
Oder den Zustand können wir auch in die Steuerungseinheit verlegen.
Also jetzt gibt es noch eine dritte Zutat, das ist die CPU oder das Programm
oder die Kombination aus beiden.
Und das ist ein sogenannter endlicher Automat, der befindet sich immer in einem
Zustand, so ein interner Programmzustand.
Was mache ich jetzt gerade hier?
Und anhand des Symbols, was er auf dem Band vorfindet, was der Schreiblesekopf
auf dem Band vorfindet und des aktuellen Zustands der Steuerungseinheit wird
definiert, was als nächstes passieren soll.
Und was passieren kann, ist, welches Symbol jetzt auf das Band geschrieben wird,
ob sich der Kopf nach links oder rechts bewegt und ob der interne Zustand geändert werden soll.
Und ja, im Prinzip, außer dass mein Speicher begrenzt ist, ist mein Computer
auch so eine Turing-Maschine. Und eure auch.
Und so eine Turing-Maschine kann alles Mögliche für einen erledigen.
Also das Einfachste oder das Erste, was man sich vielleicht überlegen würde,
ist, wie man mit so einer Turing-Maschine rechnet.
Also da wären dann sozusagen zwei Zahlen, die werden vielleicht schon am Anfang
auf das Band geschrieben und das Programm soll jetzt irgendwie den Kopf so hin und her bewegen,
dass am Ende eine Kodierung von
der Summe auf dem Band steht oder die Ente-Fibonacci-Zahl oder irgendwas,
was man sich eben ausrechnen will.
Und das sind eben diese Grundbausteine, also wenn man rechnen kann,
dann kann man eben auch andere Sachen machen, die ein Computer machen kann und
da will ich jetzt nicht in so viele Details gehen, also es wird alles in der
Informatik untersucht und man kann eben verstehen, dass so eine Turing-Maschine
ein gutes Modell dafür ist, was unser Computer ausrechnen kann.
Und da kann natürlich nicht alles ausrechnen vom Halteproblem,
dem wichtigsten Problem,
das eine Turing-Maschine nicht lösen kann, hatten wir es ja schon zum Beispiel
in Folge 39 über fleißige Biber und das ist eben das Problem,
so eine Turing-Maschine zu konstruieren, die als Eingabe ein Programm enthält,
ein beliebiges anderes Turing-Maschinen-Programm und dann entscheidet,
ob das andere Turing-Maschinen-Programm eine Endlosschleife enthält,
ob das anhält oder nicht.
Und das ist eben unmöglich, so ein Turing-Maschinen-Problem,
was alle anderen Turing-Maschinen-Probleme entscheidet, gibt's nicht.
Und ja, dann kann ich ja meine heutige Folge weiterspicken mit Tipps.
Zum Halteproblem empfehle ich euch mal die Folge 43 vom supercoolen Informatik
für die moderne Hausfrau-Podcast mit Lea Schönberger, in der sie das geschichtlich
ein bisschen auseinander nimmt.
So, dann wisst ihr jetzt alles über Turing-Maschinen und das Halteproblem und
jetzt können wir wieder zu Magic kommen.
Also dieses Ergebnis, Magic ist Turing vollständig, bedeutet also,
dass ich innerhalb dieser komplexen Regeln von Magic so eine Turing-Maschine
simulieren kann, die wiederum alle Computer simulieren kann oder alle anderen Turing-Maschinen.
Also eine sogenannte universelle Turing-Maschine, also einen echten Computer. Also kann ich.
Innerhalb von Magic alle Berechnungen ausführen, die auch mein Computer ausführen kann.
Okay, jetzt sagt ihr vielleicht immer noch, was soll das überhaupt bedeuten innerhalb von Magic?
Und dann habt ihr auch komplett recht, dass man das jetzt so noch nicht verstehen kann.
Jetzt kommen wir also zu Alex Churchill. Alex Churchill ist,
würde ich sagen, der wichtigste Forscher im Bereich Magic-Touring-Vollständigkeit.
Lebt in Großbritannien, in Cambridge.
Und der hat auf einer Webseite namens toothycat.net, was ist eigentlich so eine,
ich würde mal sagen, Manga-Fan-Webseite, hat er seine Forschung zu diesem Thema veröffentlicht.
So Anfang der 10er Jahre, so wie ich das rekonstruieren konnte,
ging das so 2010 bis 2012 los.
Das ist also eine ganz coole Webseite, da findet man so Fan-Manga-Kunst oder
auch Hochzeitsfotos von Alex und so Ergebnisse über Magic-Touring-Vollständigkeit.
Und was der jetzt macht, ist sich zu überlegen, wie kann ich eine Touring-Maschine,
so wie ich sie oben beschrieben habe, in Magic implementieren.
Und als erstes muss man sich überlegen, wie man das Band abbildet.
Also die Turing-Maschine hat ja das Band und das will ich jetzt in irgendwelchen
Spielelementen von Magic abbilden.
Und dann hat er sich entschieden für eine Reihe von Spielsteinen.
Also in Magic gibt es so Spielsteine, die übernehmen irgendwelche Rollen,
also die symbolisieren zum Beispiel Kreaturen.
Und dann hat er sich entschieden, es gibt eine Reihe von Zombiespielsteinen,
die von dem einen Spieler, der eine Spieler heißt Alex, so ein Zufall,
also A wie Alex ist der erste Spieler, und der hat eine Reihe von Zombiespielsteinen
und die repräsentieren das Band rechts von der aktuellen Kopfposition.
Okay? Sollen sie repräsentieren, die einzelnen Positionen. Jetzt gibt's in Magic
nicht sowas wie Nachbarschaft, wer ist neben wem.
Und dieses Band, hat aber ja eine Reihenfolge. Also eins rechts ist was anderes
als zwei rechts von mir, drei rechts von mir, vom Kopf.
Und das implementiert er mit der Lebenskraft, mit den Widerstandspunkten,
die diese Zombies haben.
Also direkt rechts neben im Kopf, der Zombie, der hat einen Widerstandspunkt,
also noch einen Lebenspunkt.
Und der zwei daneben, der hat zwei Widerstandspunkte und so weiter.
Und das sind jetzt erstmal nur endlich viele und später gibt es dann noch einen
Mechanismus, wenn man noch mehr Speicher braucht, dann erzeugt man noch mehr.
Aber wir können jetzt erstmal mit irgendeiner beliebigen, endlichen Anzahl anfangen.
Und dann gibt es noch eine ähnliche Kette von Yeti-Spielsteinen,
die ebenfalls von diesem einen Spieler Alex kontrolliert werden,
die das Band links vom Kopf darstellen.
Okay? Das sind erstmal die diskreten Positionen. Also es gibt diese Zombie-Spielsteine,
die sind im Spiel und es gibt die Yeti-Spielsteine für links vom Kopf. Und...
Jeder Spielstein ist jetzt eine Position von dem Band und der muss jetzt noch
anzeigen, in welchem Zustand der ist, also was da draufgeschrieben ist, welche Farbe.
Es stellt sich raus, dass er 18 Farben braucht und dazu benutzt er weitere Kreaturentypen.
Also in dem Spiel Magic kann so ein Wesen mehrere sogenannte Kreaturentypen
haben, also es kann zum Beispiel gleichzeitig ein Zombie,
ein Zauberer und ein Wassermolch sein und mithilfe dieser weiteren Kreaturentypen,
dass das Ding außer ein Zombie zu sein auch noch ein Wassermolch ist,
kann er eben abspeichern, in welchem Zustand sich dieses Feld des Bandes befindet.
Ja, so und man kann jetzt da einen endlichen Ausschnitt von dem Band eben abbilden,
auch mit den Zuständen, in denen das Band ist.
Jetzt muss man sich überlegen, dieser Schreibkopf, wenn der sich bewegt,
was muss dann passieren?
Dann müssen all diese Kreaturen aktualisiert werden. Wenn er sich zum Beispiel nach rechts bewegt,
dann wird ja der Zombie, der direkt neben dem Schreibkopf ist,
in einen Yeti umgewandelt, weil vorher war er rechts von dem Kopf,
jetzt ist er links davon oder zumindest der, der unter dem Schreibkopf war,
der wird jetzt ein Yeti und der, der rechts vom Schreibkopf war,
der ist jetzt unter dem Schreibkopf und diese, die unter dem Schreibkopf sind,
die gibt es irgendwie nicht.
Und dazu gibt es so Zauberer, die zum Beispiel von allen Zombies je einen Lebenspunkt
entfernen und dann rücken die quasi alle nach links weil ja die Lebenspunkte
ihre Position abbilden.
Okay und so geht es dann immer so weiter,
und der Alex Churchill der beschreibt eben auf seiner toothycat.net Webseite
genau die Mechanik welche Magic Karten oder Effekte oder Regeln jetzt genau
die gewünschten Effekte haben also für die Fans,
damit die jetzt auch was richtig also die Leute, die sich jetzt mit Magic richtig gut auskennen,
Die verstehen jetzt wahrscheinlich von dem, was ich jetzt sage,
mehr als ich, weil ich das jetzt einfach zitiere.
Also ich zitiere jetzt, wie das genau implementiert werden soll.
Wenn die Maschine einen neuen 2-2-Yeti-Spielstein zum Beispiel unter Alex,
dem ersten Spieler, Kontrolle erzeugt, dann werden drei Effekte ausgelöst.
Bobs Noxious Ghoul, Kathy's Aetherflash und Alex' Cazool Warlord.
Und diese kommen in dieser Reihenfolge auf den Stapel. Der Stapel ist so ein
Stapel von Effekten, die der Reihe nach abgearbeitet werden. First in, last out.
Und da es Bobs Zug ist, lösen die sich in umgekehrter Reihenfolge auf und zuerst
wirkt dann dieser Casual Warlord,
das ist eben eine Karte in Magic und der wurde mithilfe von Artificial Evolution
manipuliert und verteilt plus eins plus eins Marken auf alle Yetis unter Alex
Kontrolle und damit sind die einen Schritt weiter vom Sterben entfernt und damit
rücken die sozusagen weiter nach links also es ist der Teil,
wo sich der Kopf nach rechts bewegt,
indem die Yetis je einen Lebenspunkt dazu bekommen.
Und vorher wurde noch ein neuer Yeti erzeugt, der wird jetzt 3-3,
aber dann gibt es wieder einen Effekt, der dem wieder zwei Lebenspunkte entfernt.
Sodass der dann wieder nur noch einen Lebenspunkt hat und sich genau so einfügt,
als direkt links neben dem Kopf liegender Yeti.
Schließlich gibt es noch einen manipulierten Noxious Ghoul, der allen Nicht-Yetis
einen Schadenspunkt zufügt, also den kleinsten Zombie tötet und alle anderen eins nach links bewegt.
Und abhängig von dem weiteren Kreaturentyp, den der gerade gestorbene Zombie
hatte, der bewegt sich ja jetzt unter den Schreibkopf, wird ein entsprechendes Ereignis ausgelöst,
was dann die Logik implementiert, die Logik der Steuereinheit.
Also wäre der neue Spielstein stattdessen ein Zombie gewesen,
dann hätten es eben analoge Karten gegeben, die alles nach rechts bewegen.
Also es ist jetzt sozusagen die Aufgabe für den Alex Churchill gewesen,
die entsprechenden Magic-Karten, die es wirklich gibt, die hat er sich nicht
ausgedacht, sondern er hat die aus den über 20.000 verschiedenen Magic-Karten,
hat er eben die identifiziert, die genau dieses Prinzip mit den Yetis und Zombies
implementieren können.
Und die Stärke und Widerstandskraft dieser Spielstelle, die müssen da alle sorgfältig gewählt werden und.
Also das kann man dann eben auf dieser Webseite nachlesen, wie genau welche
Karten da zusammenwirken, um diese Effekte zu erzielen.
Okay, dann brauchen wir jetzt diesen Steuereinheit und diesen Kopf und das wird
jetzt etwas technisch, also ich kürze das mal ab.
Der Alex Churchill hatte damals eine zweizuständige universelle Turing-Maschine
implementiert, also in der zweizuständigen universellen Turing-Maschine,
die wurde von Rogozin 1996 veröffentlicht,
hat die Steuereinheit nur zwei interne Zustände, die befindet sich immer in
einem Zustand A oder B und dafür braucht man aber 18 verschiedene Farben,
die auf die Bandposition geschrieben werden können.
Und mit diesen Parametern ist es eben möglich, eine universelle Turing-Maschine
zu bauen und damit dann möglich, einen Computer zu emulieren in diesen Magic-Regeln.
Und die 18 Zustände für das Band, die kann er eben durch diese zusätzlichen
Kreaturentypen, die die Zombies und Jedis haben, noch implementieren.
Und die zwei internen Zustände, da hat er jetzt eben so einen Regelsatz,
den er alles mit Karten implementiert, so dass der Kopf dann abhängig von seinem
inneren Zustand, es gibt zwei A oder B,
der Farbe des aktuellen Fells auf dem Band, abgelesen daran.
Was für ein Kreaturentyp gerade gestorben ist.
Also wenn der Kopf sich bewegt, stirbt eine Kreatur, entweder ein Zombie oder
ein Yeti und dann muss eben das Band geschrieben werden, da muss wieder eine
neue Kreatur erzeugt werden und dann der Zustand modifiziert werden.
Und genau genommen benutzt er dafür 43 Kopien des sogenannten Rotlung-Reanimators
und diese sind so verändert, dass sie die Regeln wie folgt kodieren.
Also hier mal ein Beispiel, es gibt zum Beispiel den Faced-Out-Reanimator 16b,
der sagt, immer wenn ein Pegasus stirbt, erzeuge eine Sirene.
Das ist so ein Phasenübergang. Immer wenn ein Pegasus stirbt,
also wenn die Kreatur, die ich gerade gelöscht habe, weil ich auf das Feld gegangen
bin mit meinem Schreibkopf, wenn die den Kreaturentyp Pegasus hatte,
dann erzeuge ich da jetzt eine Sirene.
Die wieder einen anderen, also erändere ich die Farbe auf diesem Feld,
dann schreibe ich etwas aufs Band. Oder ich kann auch einen Zustandsübergang haben.
Faced Out Reanimator 17b sagt, immer wenn eine Ratte stirbt,
wirke Time and Tide, eine bestimmte Magic-Karte, und erzeuge einen Slith.
Und so weiter. Also es gibt eben so ein Regelset, das Programm,
die Steuereinheit implementieren und dann wird immer genau angegeben,
welche Karten dafür irgendwie noch rumliegen müssen, welche Effekte aktiv sein müssen.
Und man kann hier gut die Entsprechung zur Programmierung erkennen.
Also der Typ des neu erzeugten Spielsteins gibt an, in welcher Farbe das Feld
gefärbt werden soll und ob der Kopf sich nach links oder rechts bewegen soll.
Ja, und das Wirken von diesem bestimmten Time-and-Tide-Zauber entspricht eben
einem Zustandswechsel.
Da wechselt der Kopf von einem A-Zustand in den B-Zustand oder zurück.
Dann gibt es da noch so eine Bemerkung, die die Magic-Fans vielleicht verstehen.
Für mich ist es ein bisschen dreös.
Da schreibt der Alex nämlich, natürlich können wir Rotlung Re-Animator nicht
wirklich so manipulieren, dass er sagt, immer wenn ein Pegasus stirbt,
wirke Time and Tide und erzeuge einen Rigger.
Ein Instant als ausgelösten Effekt zu wirken, ist die größte Hürde,
die diese Turing-Maschine überwinden muss.
So, ich gehe jetzt mal nicht weiter in diese Implementierungs-Details.
Jetzt geht es eben darum, wie man diese Zustandsänderung mit Magic-Effekten
aus dem Regelbuch genau implementiert und das könnt ihr euch ja dann mal durchlesen.
Ist natürlich alles verlinkt. Es braucht noch extra Effekte für das Erzeugen neuer Felder vom Band,
das hatten wir ja vorhin schon, weil das eigentliche im Spiel implementierte
Band immer nur ein endlicher Ausschnitt ist und außerdem muss das Anhalten der
Turing-Maschine noch implementiert werden, also ein spezielles Signal,
dass die Turing-Maschine mit ihrer Berechnung fertig ist.
Und das soll passieren, wenn man im Zustand A ist und eine Ratte sieht. Dazu nochmal Alex.
Ich habe entschieden, dass die Maschine das Spiel beenden soll,
auf eine Weise, die das Band intakt lässt, sodass das Ergebnis auch abgelesen werden kann.
Anfangs schien das sehr kompliziert zu sein, aber tatsächlich ist es extrem einfach.
Alle Spieler haben nämlich einen Lebenspunkt und Alex kontrolliert einen Vengeful
Dead, der so manipuliert wurde, dass er sagt, immer wenn Vengeful Dead oder
ein anderer Assassine stirbt, verliert jeder Gegner einen Lebenspunkt.
Der andere stirbt also. Wenn also eine Ratte stirbt, während sich die Maschine
im Zustand A befindet, löst das Reanimator 17A aus,
dessen Effekt tatsächlich lautet, immer wenn eine Ratte stirbt,
erzeuge einen Assassinen, der Assassine kommt ins Spiel, löst sofort Aether
Flash aus, das ihn tötet.
Dies wiederum triggert Vengeful Dead und wenn dieser Trigger verrechnet wird,
verliert jeder Gaggang einen Lebenspunkt, alle außer Alex sterben und das Spiel endet.
Dann kann der finale Zustand des Bandes abgelesen werden.
Also an diesem Absatz seht ihr vielleicht so ein bisschen, was man tun muss,
wenn man Magic the Gathering spielt.
Also man überlegt sich diese Effektketten und dann aus den Karten,
die man auf der Hand hat, konstruiert man so eine Kette von Effekten,
die günstig für einen ist.
Also so gut Magic zu spielen, bedeutet eben interessante oder wirkungsmächtige
Kombinationen aus diesen Effekten zu finden und natürlich dann mit den entsprechenden
Karten zu implementieren, die man gerade in seinem Deck hat.
So, ich hoffe, ihr glaubt mir, dass es möglich ist, die Prinzipien der universellen
Turing-Maschine, also in Magic zu implementieren.
Man darf sich das jetzt aber nicht so vorstellen, dass die beiden Spieler dann
beide mit ihren Decks da sitzen und dann in einem normalen Spiel die Karten
ziehen und dann Entscheidungen treffen oder so.
Genau genommen ist das hier so implementiert, dass die Spieler eigentlich möglichst gar nichts machen.
Alles läuft einfach nach den Regeln des Spiels ab. Also es wird eine Situation
konstruiert, die jetzt in einem normalen Kartenspiel so nicht auftreten würde.
Also in so einem 60er-Deck darf zum Beispiel jede individuelle Karte nur viermal drin sein.
Also kann man nicht 43 von diesen Rotlung-Reanimatoren in seinem Deck haben.
Und zum Beispiel ist da auch gar kein Platz mehr.
Also es wird eine Magic-Situation erzeugt, die im Prinzip plausibel und mit
den Regeln kompatibel ist und einfach nur das Auswerten dieser Situation,
ohne dass die Spieler irgendwas machen, ist die Berechnung.
Nur das Anwenden der Regeln führt die universelle Turing-Maschine aus.
Und da gibt es eben auch noch ein kleines Problem, das Alex auf seiner Seite erwähnt hat, 2012. 12.
Also es wird tatsächlich eine Karte benutzt, in der ein Spieler einen Effekt
auslösen darf, aber nicht muss.
Also auf diesen Karten steht halt auch drauf, wenn du das möchtest,
kannst du das und das haben jetzt, diesen Effekt.
Und für die Analyse, die er damals gemacht hat, ging eben er davon aus, dass Alex das immer tut.
Also wenn er diese Wahl hat, diesen Effekt auszulösen, tut er das.
Und wenn er es nicht tut, dann bricht es halt alles zusammen.
Und das wollte er noch entfernen. Und da hat er damals auf der Webseite aufgerufen,
er würde gern beweisen, dass es möglich ist, Magic-Partien zu konstruieren,
die entweder in einer Endlosschleife hängen oder tatsächlich terminieren.
Und welche der beiden Möglichkeiten eintritt, hängt beispielsweise davon ab,
ob es eine gerade Zahl gibt, die nicht als Summe zweier Primzahlen darstellbar
ist oder von einem anderen ungelösten mathematischen Problem.
Und das ist wieder das, was wir in der Folge 39 mit den fleißigen Bibern hattet,
hört euch die unbedingt nochmal an.
Man kann nämlich die Existenz eines Gegenbeispiels zur Goldbach-Vermutung,
was das hier ja gerade war.
Kodieren als das Halteproblem für eine bestimmte Maschine.
Und dann kann man sich fragen, was ist das für eine Maschine?
Wie viele interne Zustände braucht die? Und so, darum ging es ja eben bei den fleißigen Bibern.
Und die Ankopplung an Magic würde solche Art von Ergebnissen jetzt auch für Magic ermöglichen.
Also in der Version 5 seiner Turing-Maschine hat Spieler A immer noch die Möglichkeit,
etwas abzulehnen von diesen Optionen.
Und das war eben so ein kleiner Schönheitsfehler.
Und er fragt sich eben, ob es möglich ist, eine Magic-Turing-Maschine zu bauen,
bei der kein Spieler jemals irgendeine Option erhält, sondern die komplett automatisch abläuft.
Und er rief dann so ein bisschen auf, also wenn ihr einen Weg findet oder ich
einen Weg finde, dann werde ich euch in den Foren von Wizards of the Coast im
Magic Forum da schreiben oder wir machen das per E-Mail aus.
Und ihr braucht jetzt noch nicht zum Keyboard greifen, weil ihr denkt, ihr könnt das lösen.
Das Problem ist natürlich mittlerweile gelöst und es wurde tatsächlich in diesem
Wizards of the Coast Forum die entscheidende Idee entwickelt,
um dieses das Problem zu lösen und wirklich eine vollständige,
allein ohne Wahlmöglichkeit ablaufende Turing-Maschine zu implementieren.
Aber ich wollte euch trotzdem das Original vorstellen, denn in der Mathematik
gehen wir immer gern auf die Originalreferenzen rein.
Und ich denke, ohne diese ganze grundlegende Arbeit von Alex Churchill wäre
das auch alles nicht möglich gewesen.
So, jetzt fragt ihr euch natürlich, solche bahnbrechenden Forschungsergebnisse,
müssen die nicht irgendwie veröffentlicht werden?
Also gut, sie sind ja irgendwie veröffentlicht in einem sehr länglichen Thread
im Magic the Gathering Forum bei Wizards of the Coast und auf ToothyCat.net,
aber eben jetzt nicht so ganz mit Peer Review, wie man es jetzt aus den üblichen
mathematischen Veröffentlichungen kennt oder informatischen veröffentlichen.
Und tatsächlich hat sich ein Team gefunden, bestehend aus eben Alex Churchill
und dann noch Stella Biedermann von der Georgia Tech University in Atlanta und
Austin Herrick von der University of Pennsylvania, die das komplett formalisiert haben.
Verlinke ich euch den Link auf das Archive. Also das ist wirklich ein klasse Paper.
Also die Introduction davon, die kann man sehr gern mal lesen.
Und es hat auch so richtig goldene Referenzen. Also die greifen auch nochmal
so die Historie der spieltheoretischen Komplexitätsforschung,
möchte ich es mal nennen, auf.
Also es gibt da zum Beispiel, zitiert, Resultate, dass Videospiele wie zum Beispiel Super Smash Bros.
Melee und Mario Kart unentscheidbare Verallgemeinerungen haben.
Also den Referenzen könnt ihr da auf jeden Fall auch allen mal folgen.
Und ihr Theorem 1 ist eben Determining the outcome of a game of magic,
the gathering in which all remaining moves are forced is undecidable.
Also, es ist unentscheidbar, auf einer Turing-Maschine nicht berechenbar,
ob, wenn ein Magic the Gathering-Spiel in einem Zustand ist,
in dem nie mehr ein Spieler eine Entscheidung treffen muss, wo also alles ab
jetzt durch Anwendung der Regeln abläuft, wer dann gewinnt. Das ist unentscheidbar.
Das ist zum Beispiel ein ganz starker Kontrast zu Spielen wie Schach.
Schach hat nur einen endlichen Spielbaum. Beim Schach ist es trivial zu entscheiden,
ob in einer Spielposition ein Spieler eine Gewinnstrategie hat.
Und mit trivial meine ich, es ist trivial zu beweisen, dass das möglich ist.
Es gibt einen endlichen Algorithmus, den Spielbaum zu durchsuchen.
Also natürlich ist es nicht trivial, Schach zu spielen oder die Strategie zu
berechnen, das ist alles riesengroß.
Aber aus computertheoretischer Sicht ist, weil Schach ein endliches Spiel ist, das trivial.
Und bei Magic hat man eben die gesamte
Unendlichkeit der Turing-Maschinen-Komplexität innerhalb eines Zugs.
Also die Spieler kommen gar nicht wieder dran.
Dieses ganze, wir ziehen Karten, wir treffen eine Entscheidung,
was spiele ich, welche meiner Länder tappe ich, das spielt alles überhaupt keine
Rolle für diese Untersuchung.
Für diese Untersuchung wird eben eine Situation konstruiert und dann laufen
nur noch die Effekte ab, die die Regeln vorschreiben, bevor jemals ein Spieler
wieder dran ist und eine Entscheidung treffen sollte.
So, zum Glück hört diese Forschung aber auch nie auf. Man würde denken,
okay, jetzt ist das Problem gelöst, aber wie es in der Mathematik immer ist
oder in der theoretischen Informatik, wenn man ein Problem gelöst hat,
eröffnen sich zwei neue und so gibt es auch in diesem Paper zwei Conjectures,
an denen ihr noch arbeiten könnt.
Conjecture 1, die Funktion, die einen Zustand des Spiels nimmt und einen legalen
Zug und dann den nächsten Zustand des Spiels Magic bestimmt,
ist berechenbar. Also das ist unbekannt.
Und Conjecture 2, die ist vielleicht etwas überraschender oder vielfältiger.
In der Conjecture 1 habe ich gesagt, es muss ein legaler Zug vorgeschlagen werden
und Conjecture 2 beschäftigt sich damit.
Conjecture 2 sagt nämlich, es gibt gar keinen Algorithmus.
Der sagen kann, ob ein Zug legal ist.
Also es ist unentscheidbar mit einer Turing-Maschine, ob ein Zug,
den ich jetzt mache, eine Entscheidung, die ich treffe, sich an die Regeln hält.
Okay, ich lasse das jetzt mal so stehen. Das war der Stand ungefähr 2019.
Das ist dann da noch so ein bisschen weitergegangen. Die Stella Biedermann hat
auch noch ein Paper geschrieben, Magic the Gathering is as hard as arithmetic.
Verlinke ich euch, das war ungefähr 2000. Und jetzt 2024 ist das jüngste Ergebnis
aus der Magic-Komplexitätstheoretischen Forschung, was ich euch noch berichten kann.
Da hat Alex Churchill sich mit einem anderen Mathematiker Howe Chonying zusammengeschlossen
und sie haben ihr Paper geschrieben, A Programming Language Embedded in Magic the Gathering.
Da geht es darum, dass diese Turing-Maschine natürlich sehr schwer zu steuern ist.
Also es gibt einen sehr komplexen Aufbau, um sehr einfache Probleme nur zu lösen.
Also wenn ihr selbst auf einer Turing-Maschine einfach mal die Summe von zwei
Zahlen berechnen wollt, dann wisst ihr ja schon, wie kompliziert das ist.
Aber mit Magic jetzt die Turing-Maschine zu implementieren, macht das Ganze
ja nicht einfacher, sondern noch viel, viel komplizierter.
Und was ist die Lösung in der praktischen
Informatik? Ist natürlich Programmiersprachen zu machen und Compiler.
Und sie beginnen jetzt eben das Programm, dort eine Programmiersprache in Magic
einzubetten, um die Programmierung der Magic-Turing-Maschine einfacher zu machen.
Und das haben sie veröffentlicht, ihre Arbeit bei einer Konferenz.
Es ist ja in der Informatik eher so, dass viele wichtige Ergebnisse auf Konferenzen
präsentiert werden, während die Mathematik mehr aufs Journale setzt.
Aber in der Informatik sind Konferenzen sehr wichtig. Und so ist ihr Ergebnis,
glaube ich, auf der wichtigsten Konferenz für diese Art von Forschung erschienen,
nämlich auf der 12th International Conference on Fun with Algorithms, kurz FUN 2024.
Die fand auf Sardinien statt, verlinke ich euch natürlich. Und ich vermute,
ich war nicht da und ich bedauere es auch, ich vermute, das war wirklich eine
sehr schöne Konferenz, sehr spaßig und sehr inspirierend.
Und ich will euch nur ein paar Titel sagen von Beiträgen, die in den Konferenz-Proceedings
erschienen sind. Oder könnt ihr dann nochmal ein bisschen nachlesen und selbst
entscheiden, ob die Konferenz auch wirklich fun war.
Also diese Titel sind zum Beispiel Peace Pace Heart 2D Super Mario Games 13
Doors oder Tetris is Not Competitive oder Achieving the Highest Possible Elo
Rating oder Eating Ice Cream with a Colander oder Snake in Optimal Space and Time.
Also für die Fans des Retro-Gamings, für die Fans der Komplexitätstheorie,
für jeden ist da was dabei.
Also, in diesem Sinne wünsche ich euch viel Spaß am Gerät, viel Spaß bei Magic,
bleibt neugierig und habt weiter Fun with Algorithms. Bis bald.