Deciding winning strategies in Yu-Gi-Oh! TCG is hard

Die Autoren zeigen, dass die Frage, ob eine gegebene berechenbare Strategie im Yu-Gi-Oh!-TCG von einem bestimmten Spielzustand aus gewinnt, unentscheidbar und sogar $\Pi^1_1$-vollständig ist, indem sie das Problem auf die Menge der abzählbaren Wohlordnungen reduzieren und dabei legale Decks verwenden.

Das Wesentliche

Titel: Warum man Yu-Gi-Oh! nicht mit einem Computerprogramm lösen kann

Stell dir vor, du hast einen riesigen, unendlichen Spielplatz voller Karten. In diesem Spiel, Yu-Gi-Oh!, versuchen zwei Spieler, sich gegenseitig zu besiegen. Die Autoren dieses wissenschaftlichen Papers haben sich gefragt: Kann ein Computer jemals garantieren, dass eine bestimmte Strategie immer gewinnt?

Die kurze Antwort lautet: Nein. Und das ist nicht nur schwierig, sondern mathematisch unmöglich.

Hier ist die Erklärung, warum das so ist, ohne komplizierte Formeln, sondern mit ein paar einfachen Bildern:

1. Das große Problem: Der unendliche Loop

In vielen Computerspielen gibt es eine klare Grenze: Du hast eine bestimmte Anzahl von Zügen, und das Spiel endet irgendwann. Aber Yu-Gi-Oh! ist anders. Die Autoren haben gezeigt, dass man in Yu-Gi-Oh! eine Situation erschaffen kann, die wie ein unendlicher Zeitmaschinen-Rad funktioniert.

Stell dir vor, du baust ein Riesenrad, das sich immer weiter dreht. Du kannst auf diesem Rad beliebig viele Zahlen speichern (wie auf einem Zettel, den du immer länger machst). Die Autoren haben einen speziellen Stapel Karten (ein "Deck") gebaut, der es einem Spieler erlaubt, diesen Zettel mit Zahlen zu füllen, ohne dass das Spiel jemals aufhört.

2. Der Vergleich mit dem "Halte-Problem"

In der Informatik gibt es ein berühmtes Problem, das Halte-Problem. Stell dir vor, du hast ein Programm und fragst: "Hält dieses Programm irgendwann an, oder läuft es für immer?"
Ein genialer Mathematiker namens Alan Turing hat bewiesen, dass es keinen allgemeinen Weg gibt, das für jedes Programm vorherzusagen. Man kann es nicht berechnen.

Die Autoren von diesem Paper haben Yu-Gi-Oh! so manipuliert, dass das Spiel genau wie ein Computerprogramm funktioniert:

• Die Karten sind die Befehle des Programms.
• Die Lebenspunkte oder Zähler auf dem Spielfeld sind der Speicher (der Zettel mit den Zahlen).
• Der Spieler, der zuerst zieht, ist der Computer, der das Programm ausführt.

Wenn der Spieler eine Strategie hat, die versucht, das Spiel zu gewinnen, ist das im Grunde dasselbe wie zu fragen: "Hält dieses Programm an?" Da wir wissen, dass man das Halte-Problem nicht lösen kann, können wir auch nicht vorhersagen, ob eine Yu-Gi-Oh!-Strategie gewinnt oder nicht.

3. Die Magie der "Flint-Lock-Schleife" (Der Trick)

Um das zu beweisen, haben die Autoren einen speziellen Trick mit Karten namens Flint Lock und Raigeki entwickelt.

• Der Trick: Der zweite Spieler (der Verlierer) kann durch geschicktes Kartenwechseln seine Lebenspunkte immer weiter erhöhen – theoretisch unendlich oft.
• Die Falle: Der erste Spieler kann jederzeit mit einer Karte namens Raigeki (einem Blitz) alles zerstören und das Spiel sofort beenden.

Das ist wie ein Schachspiel, bei dem der Gegner unendlich viele Bauern auf das Brett legen darf, aber du einen Knopf hast, der alles löscht.
Die Frage ist nun: Wann drückt der erste Spieler den Knopf?
Wenn der erste Spieler eine Strategie hat, die immer gewinnt, muss er genau wissen, wann der Gegner aufhört, Lebenspunkte zu sammeln. Aber da der Gegner unendlich lange sammeln kann (wie in einem Programm, das in einer Endlosschleife steckt), kann kein Computer wissen, ob das Spiel jetzt endet oder noch 1000 Jahre weiterläuft.

4. Was bedeutet das für uns?

Die Autoren haben bewiesen, dass die Frage "Ist diese Strategie eine Gewinnstrategie?" so schwer ist, dass sie in eine Kategorie fällt, die Π11-vollständig heißt.
Das klingt nach einem fremden Wort, aber stell es dir so vor:

• Einfache Probleme: "Ist 2+2=4?" (Das kann jeder).
• Schwere Probleme: "Gewinnt dieser Schachzug?" (Das kann ein Computer berechnen).
• Unmögliche Probleme: "Gewinnt diese Yu-Gi-Oh!-Strategie immer, egal was der Gegner macht?" (Das ist wie zu versuchen, die Zukunft vorherzusagen, wenn die Zukunft unendlich viele Möglichkeiten hat).

Fazit

Dieses Papier sagt uns: Yu-Gi-Oh! ist zu komplex für einen perfekten Computer.
Selbst wenn wir einen Supercomputer hätten, der alle Karten kennt, könnte er uns nicht sagen, ob eine bestimmte Spielweise garantiert zum Sieg führt. Das Spiel ist so konstruiert, dass es die Grenzen der Mathematik selbst auslotet. Es ist ein Spiel, in dem die Unendlichkeit der Möglichkeiten die Vorhersagbarkeit zerstört.

Kurz gesagt: Yu-Gi-Oh! ist nicht nur ein Kartenspiel, es ist ein mathematisches Monster, das sich der Berechnung entzieht. Und das macht es (vielleicht) noch spannender für uns Menschen, die wir gerne raten und taktieren, statt alles nur zu berechnen.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Deciding Winning Strategies in Yu-Gi-Oh! TCG is Hard" von Niclosi, Pisciotta und Bresolin auf Deutsch.

1. Problemstellung und Motivation

Das Paper untersucht die Berechenbarkeitstheorie (Computability Theory) im Kontext des Kartenspiels Yu-Gi-Oh! Trading Card Game (TCG). Während das Spiel Magic: The Gathering bereits formal untersucht wurde (insbesondere durch Churchill, Biderman und Herrick [CBH20], die zeigten, dass die Bestimmung optimalen Spiels unentscheidbar ist), fehlte eine solche Analyse für Yu-Gi-Oh!.

Die zentrale Fragestellung lautet:

Kann man entscheiden, ob eine gegebene Strategie in Yu-Gi-Oh! TCG von einem bestimmten Spielzustand aus eine Gewinnstrategie ist?

Im Gegensatz zu Magic: The Gathering, das stark auf Automatisierung und Kettenreaktionen ausgelegt ist, besitzt Yu-Gi-Oh! weniger eingebaute Automatismen. Daher formulieren die Autoren das Problem leicht anders: Statt zu fragen, ob eine Position gewinnbar ist, fragen sie, ob eine gegebene (berechenbare) Strategie garantiert zum Sieg führt.

2. Methodik und Konstruktion

Die Autoren verwenden Methoden der mathematischen Logik und der Berechenbarkeitstheorie, um das Problem zu formalisieren und zu reduzieren.

2.1. Formalisierung

• Konfigurationen ($C$): Ein Spielzustand wird als endlicher String ($\omega^{<\omega}$) codiert, der alle relevanten Informationen enthält (Lebenspunkte, Kartenpositionen, Zähler, bekannte Karten des Gegners etc.).
• Strategien ($S$): Eine Strategie wird als Funktion definiert, die eine Folge von Konfigurationen (den bisherigen Spielverlauf) auf den nächsten legalen Zug abbildet.
  • Zuerst werden berechenbare Strategien betrachtet (die von einem Computerprogramm ausgeführt werden können).
  • Später werden nicht-berechenbare Strategien (allgemeine Strategien) betrachtet.
• Annahmen: Um die Unentscheidbarkeit zu beweisen, treffen die Autoren zwei Annahmen:
  1. Ein Spieler kann pro Zug nur endlich viele Operationen durchführen.
  2. Es gibt keine zeitliche Begrenzung für das Match (unendliche Laufzeit erlaubt).

2.2. Die Turing-Maschinen-Simulation (Der „Deck-Build")

Der Kern der Methode besteht darin, zu zeigen, dass Yu-Gi-Oh! TCG in der Lage ist, die Logik einer Turing-Maschine zu simulieren.

• Speichermedium: Die Anzahl der „Zauberkarten-Zähler" (Spell Counters) auf der Karte Magical Citadel of Endymion dient als Speicher für den Zustand der Turing-Maschine (Bandinhalt, Kopfposition, Zustand).
• Zugriff: Die Autoren konstruieren einen legalen 43-Karten-Deck (später erweitert auf 48 Karten), mit dem Spieler 1 (der erste Spieler) einen spezifischen Startzustand erzwingen kann.
• Mechanismus:
  • Durch eine Schleife aus Karten wie Book of Eclipse, Bait Doll, Upstart Goblin und Desert Sunlight kann Spieler 1 die Zählerzahl beliebig erhöhen.
  • Durch Endymion, the Master Magician und Offerings to the Doomed kann die Zählerzahl verringert werden.
  • Der Gegner wird durch Yata-Garasu daran gehindert, Karten zu ziehen oder neue Züge zu machen, was den Spielverlauf deterministisch für die Simulation macht.

2.3. Erweiterung für $\Pi^1_1$-Vollständigkeit

Um die höhere Komplexität zu beweisen, wird ein zweiter Deck-Entwurf vorgestellt, der es dem Gegner (Spieler 2) erlaubt, eine natürliche Zahl zu „wählen".

• Dies wird durch eine Kombination von Karten wie Flint Lock, Morale Boost und Clara & Rushka, the Ventriloduo erreicht.
• Spieler 2 kann durch wiederholtes Ändern des Ziels einer Ausrüstungskarte seine Lebenspunkte um beliebige Vielfache von 1000 erhöhen.
• Dies simuliert die Eingabe einer unendlichen Folge von Zahlen durch den Gegner, was für die Reduktion auf analytische Hierarchie-Ebenen notwendig ist.

3. Wichtige Ergebnisse und Theoreme

Das Paper liefert vier Hauptergebnisse, die die Komplexität des Problems klassifizieren:

1. Unentscheidbarkeit (Theorem 1.1):
   Das Problem zu entscheiden, ob eine berechenbare Strategie in Yu-Gi-Oh! TCG eine Gewinnstrategie ist, ist unentscheidbar.

   • Beweis: Reduktion des Halting Problems (das Halteproblem für Turing-Maschinen) auf das Gewinnstrategie-Problem. Wenn man entscheiden könnte, ob die Strategie gewinnt, könnte man auch entscheiden, ob eine Turing-Maschine hält.

2. Unmöglichkeit für Algorithmen (Korollar 1.2):
   Es gibt keinen Computeralgorithmus, der für eine gegebene Strategie in Yu-Gi-Oh! TCG bestimmen kann, ob diese garantiert gewinnt.

3. $\Pi^1_1$-Vollständigkeit für berechenbare Strategien (Theorem 1.3):
   Das Problem ist nicht nur unentscheidbar, sondern liegt in der analytischen Hierarchie auf dem Niveau $\Pi^1_1$-vollständig.

   • Beweis: Reduktion der Menge der Indizes $e$, für die keine unendliche Folge existiert, die von der $e$-ten Turing-Maschine generiert wird (eine bekannte $\Pi^1_1$-vollständige Menge), auf das Gewinnstrategie-Problem. Dies zeigt, dass das Problem mindestens so schwer ist wie das Problem, ob eine Turing-Maschine auf allen Eingaben nicht hält.

4. $\Pi^1_1$-Vollständigkeit für allgemeine Strategien (Theorem 1.4):
   Selbst wenn man Strategien betrachtet, die nicht berechenbar sind (d.h. beliebige Funktionen, die nicht von einem Programm ausgeführt werden können), bleibt das Problem $\Pi^1_1$-vollständig.

   • Beweis: Eine Wadge-Reduktion von der Menge der Wohlordnungen (Well-Orders) auf einer abzählbaren Domäne (ein klassisches $\Pi^1_1$-vollständiges Set in der deskriptiven Mengenlehre) auf das Gewinnstrategie-Problem.

4. Signifikanz und Implikationen

• Theoretische Einordnung: Das Paper etabliert Yu-Gi-Oh! TCG als ein System von hoher logischer Komplexität, vergleichbar mit Magic: The Gathering. Es zeigt, dass die Interaktion von Kartenregeln ausreicht, um universelle Berechnungen und komplexe Mengenlehre zu kodieren.
• Unterschied zu Magic: Während Magic oft durch die Komplexität der Ketten und der Automatisierung als „schwieriger" gilt, demonstrieren die Autoren, dass Yu-Gi-Oh! durch geschicktes Deck-Building und das Ausnutzen von Endlosschleifen (Looping) und Zähler-Management dieselbe theoretische Härte erreicht.
• Praktische Relevanz: Die Ergebnisse bedeuten, dass es prinzipiell unmöglich ist, einen perfekten KI-Entscheider für Yu-Gi-Oh! zu bauen, der für jede beliebige Strategie garantieren kann, ob sie gewinnt. Dies gilt selbst für Strategien, die von Computern berechnet werden.
• Offene Fragen: Die Autoren vermuten, dass ähnliche Ergebnisse auch für andere Kartenspiele wie Pokémon TCG gelten könnten, was ein neues Forschungsfeld für die formale Analyse von Brett- und Kartenspielen eröffnet.

Zusammenfassung der technischen Klassifikation

Aspekt	Klassifikation
Problem	Entscheidung, ob eine Strategie $S$ von Zustand $C$ aus gewinnt.
Eingabe	Ein legaler Spielverlauf $C$ und eine Strategie $S$.
Berechenbare Strategien	$\Pi^1_1$-vollständig (Unentscheidbar).
Allgemeine Strategien	$\Pi^1_1$-vollständig (Co-analytisch vollständig).
Reduktionsquelle	Halting Problem (für Unentscheidbarkeit), Wohlordnungen / NIS (für $\Pi^1_1$).
Schlüsselmechanismus	Simulation einer Turing-Maschine mittels Spell Counters und Endlosschleifen.

Das Paper schließt die Lücke in der akademischen Literatur zu Yu-Gi-Oh! TCG und beweist, dass das Spiel aus Sicht der theoretischen Informatik und mathematischen Logik extrem komplex ist.