EIG049 Magic: the Gathering

0:00 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.

0:38 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.

0:58 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.

1:23 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.

1:44 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.

2:02 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.

2:28 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.

2:55 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.

3:17 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.

3:35 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.

3:56 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.

4:17 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.

4:37 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.

4:55 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.

5:18 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.

5:37 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.

5:52 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.

6:10 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.

6:33 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.

7:01 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.

7:18 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.

7:43 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.

8:10 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.

8:30 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.

8:49 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.

9:08 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.

9:28 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.

9:50 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.

10:14 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?

10:34 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.

11:00 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.

11:15 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.

11:33 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.

11:50 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.

12:17 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.

12:39 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.

13:06 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.

13:30 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.

13:52 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.

14:24 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.

14:47 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.

15:06 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.

15:27 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.

15:44 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...

16:07 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.

16:48 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.

17:27 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.

18:06 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.

18:37 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.

19:07 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.

19:34 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.

19:59 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.

20:16 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.

20:37 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.

21:03 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.

21:20 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.

21:40 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.

22:03 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.

22:27 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.

22:54 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.

23:12 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.

23:32 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.

23:51 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.

24:10 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.

24:26 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.

24:54 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.

25:10 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.

25:35 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.

25:50 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.

26:09 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.

26:33 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.

26:55 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.

27:20 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.

27:38 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.

27:54 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.

28:19 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.

28:35 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.

28:55 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.

29:27 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.

29:45 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.

30:07 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.

30:46 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.

31:08 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.

31:26 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.

31:47 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.

32:01 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.

32:31 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.

32:54 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.

33:14 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.

33:36 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.

33:54 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.

34:16 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.

34:41 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.

35:12 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.