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

Deze paper bewijst dat het bepalen van een winnende strategie in Yu-Gi-Oh! TCG een onbeslisbaar probleem is dat zelfs $\Pi^1_1$-compleet is, wat betekent dat het minstens zo moeilijk is als het Halting-probleem en dat het zelfs de complexiteit van het bepalen van tellbare welordeningen overtreft.

De kern

Yu-Gi-Oh! is onmogelijk te winnen (of te voorspellen): Een simpele uitleg

Stel je voor dat je een enorme, ingewikkelde puzzel hebt: het kaartspel Yu-Gi-Oh!. Iedereen denkt dat als je maar goed genoeg bent, je altijd kunt winnen of verliezen. Maar een groep wiskundigen heeft bewezen dat dit niet waar is. Ze tonen aan dat het onmogelijk is om met een computerprogramma te bepalen of een bepaalde strategie in Yu-Gi-Oh! gegarandeerd tot winst leidt.

Hier is hoe ze dat deden, vertaald naar alledaagse taal:

1. Het grote idee: Het spel als een supercomputer

In de wiskunde bestaat er een beroemd probleem: het "Halting Problem" (het Stop-probleem). Dit gaat over het voorspellen of een computerprogramma ooit stopt of voor altijd blijft draaien. Wiskundigen hebben bewezen dat je dit nooit voor elke mogelijke situatie kunt voorspellen.

De auteurs van dit paper zeggen: "Wat als we Yu-Gi-Oh! gebruiken als die computer?"

Ze hebben een manier bedacht om een specifiek kaartspel-arrangement te bouwen (een "deck") dat precies doet wat een computer doet.

• De "Tape" (Geheugen): In plaats van papier en potlood, gebruiken ze de toverkracht-punten (Spell Counters) op een kaart genaamd Magical Citadel of Endymion. Elke keer dat je een kaart speelt, tel je op of haal je af. Dit is het geheugen van de computer.
• De "Programmeur": De speler die begint (Speler 1) volgt een strikt stappenplan. Dit stappenplan is zo slim dat het de instructies van elke willekeurige computer kan nabootsen.

2. De "Time Travel" van de kaarten

Om dit te laten werken, gebruiken ze een paar magische kaarten die het spel een beetje "breken" (maar op een legale manier volgens de regels).

• Onbeperkt herhalen: Ze gebruiken kaarten die het spel in een lus kunnen brengen. Stel je voor dat je een knop hebt die je oneindig vaak kunt indrukken, elke keer met een klein beetje energie (punten) erbij.
• De tegenstander als knop: In een nog complexere versie van hun experiment, laten ze de tegenstander (Speler 2) een getal kiezen door hun levenspunten te verhogen. Het is alsof de tegenstander een willekeurig getal in een computer typt, en de eerste speler moet daarop reageren.

3. Waarom is dit een probleem?

Stel je voor dat je een computerprogramma schrijft dat zegt: "Als ik deze strategie speel, win ik altijd."
De wiskundigen zeggen: "Nee, dat kun je niet weten."

Waarom? Omdat de strategie in Yu-Gi-Oh! zo complex kan worden, dat het precies hetzelfde is als proberen te voorspellen of een computerprogramma ooit stopt.

• Als de "computer" (het kaartspel) stopt, betekent dit dat Speler 1 wint.
• Als de "computer" blijft draaien, blijft het spel oneindig doorgaan (of Speler 1 verliest).

Omdat wiskundigen al bewezen hebben dat je nooit kunt weten of een computerprogramma stopt (het is een onoplosbaar raadsel), kunnen ze ook nooit weten of een Yu-Gi-Oh! strategie altijd wint.

4. De "Onmogelijke" conclusie

De paper komt tot drie belangrijke conclusies:

1. Geen computer kan dit oplossen: Er bestaat geen software die je kunt zeggen: "Hier is mijn deck en mijn strategie, win ik hiermee?" Het antwoord is onmogelijk te geven.
2. Het is nog moeilijker dan wiskunde: Het probleem is niet alleen onoplosbaar, maar het zit in een heel hoog niveau van wiskundige moeilijkheidsgraad (Π11-compleet). Dit betekent dat het zelfs moeilijker is dan de meeste andere onoplosbare problemen die we kennen.
3. Het geldt voor iedereen: Of je nu een simpele computerstrategie gebruikt of een super-slimme, niet-berekenbare strategie, het blijft onmogelijk om te garanderen dat je wint.

De Metafoor: De Oneindige Labyrint

Stel je voor dat Yu-Gi-Oh! een labyrint is.

• In een normaal spel loop je door het labyrint en probeer je de uitgang te vinden.
• De auteurs hebben bewezen dat je een labyrint kunt bouwen dat exact zo groot en complex is als een heel universum aan computerberekeningen.
• Als je vraagt: "Is er een pad dat altijd naar de uitgang leidt?", is het antwoord: "Dat kunnen we niet weten, omdat het pad misschien oneindig doorgaat in een cirkel die we niet kunnen doorzien."

Kortom

Dit paper is een wiskundig bewijs dat Yu-Gi-Oh! niet alleen een leuk spelletje is, maar een systeem dat logisch onvoorspelbaar is. Je kunt niet zeggen dat een bepaalde manier van spelen "perfect" is, omdat de regels van het spel toestaan dat het spel oneindig doorgaat op manieren die geen computer ooit kan doorrekenen.

Het is alsof je zegt: "Ik heb een strategie die altijd wint." De wiskunde zegt dan: "Dat kunnen we nooit bewijzen, en misschien is het zelfs onmogelijk."

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Deciding Winning Strategies in Yu-Gi-Oh! TCG is Hard" van Orazio Nicolosi, Federico Pisciotta en Lorenzo Bresolin, geschreven in het Nederlands.

Titel: Het Bepalen van Winststrategieën in Yu-Gi-Oh! TCG is Moeilijk (Onbeslisbaar)

1. Probleemstelling

Het artikel onderzoekt de computationele complexiteit van het bepalen of een gegeven strategie in het Yu-Gi-Oh! Trading Card Game (TCG) een winnende strategie is.

• Context: Hoewel er al significant onderzoek is gedaan naar de onbeslisbaarheid van Magic: The Gathering (waarbij het vinden van een optimale zet onmogelijk is voor een algoritme), ontbreekt er formeel academisch onderzoek naar de computationele eigenschappen van Yu-Gi-Oh! TCG.
• De Vraag: Kan men algoritmisch bepalen of een specifieke strategie, die start vanuit een bepaalde speltoestand, gegarandeerd leidt tot overwinning, ongeacht de zetten van de tegenstander?
• Aannames: De auteurs nemen aan dat er geen tijdsbeperkingen zijn op de duur van een match en dat een speler per beurt slechts een eindig aantal operaties mag uitvoeren. Ze veronderstellen ook dat de spelregels "transition-computable" zijn (de overgang van de ene speltoestand naar de volgende is berekenbaar).

2. Methodologie en Constructie

De auteurs bewijzen hun stellingen door het spel Yu-Gi-Oh! TCG te gebruiken als een platform om Turing-machines te simuleren. Ze tonen aan dat het spel in staat is om willekeurige hoeveelheden informatie op te slaan en complexe berekeningen uit te voeren.

• De "Board" Constructie:
  De auteurs presenteren twee specifieke, legale decks (volgens de huidige verboden/beperkte lijst) die een speler (Speler 1) kan gebruiken om een specifieke speltoestand te bereiken.

  • Configuratie: Speler 1 controleert een veld met specifieke kaarten (zoals Magical Citadel of Endymion, Temple of the Kings, Yata-Garasu, etc.) die het mogelijk maken om de speltoestand te manipuleren zonder dat de tegenstander kan reageren of kaarten kan trekken.
  • Informatie-opslag: Het aantal "Spell Counters" op de kaart Magical Citadel of Endymion fungeert als het werkgeheugen (tape) van een Turing-machine.
  • Loop-mechanismen: Door specifieke kaartencombinaties (zoals Bait Doll, Upstart Goblin, Book of Eclipse en Desert Sunlight) kan Speler 1 een lus creëren die het aantal Spell Counters willekeurig kan verhogen of verlagen. Dit simuleert het lezen en schrijven op de tape van een Turing-machine.

• Reductie van het Halting Problem:

  • De auteurs reduceren het klassieke Halting Problem (het probleem om te bepalen of een Turing-machine stopt) tot het probleem van het bepalen van een winnende strategie.
  • Ze definiëren een strategie $S_e$ die de berekening van de $e$-de Turing-machine simuleert. Als de machine stopt, wint Speler 1 direct. Als de machine niet stopt, blijft het spel doorgaan.
  • Omdat het Halting Problem onbeslisbaar is, moet het bepalen of deze strategie winnend is, ook onbeslisbaar zijn.

• Uitbreiding naar Complexere Complexiteitsklassen:

  • Voor het bewijs van $\Pi^1_1$-compleetheid (zie hieronder) introduceren ze een meer flexibele constructie waarbij Speler 2 (de tegenstander) in staat wordt gesteld om getallen te "kiezen" (door Life Points te verhogen via een specifieke kaartcombinatie met Flint Lock en Morale Boost). Dit stelt Speler 1 in staat om een strategie te definiëren die reageert op deze keuzes, wat essentieel is voor het modelleren van kwantificering over oneindige reeksen.

3. Belangrijkste Resultaten en Stellingen

Het artikel levert drie fundamentele stellingen op:

1. Stelling 1.1 (Onbeslisbaarheid voor berekenbare strategieën):
   Het bepalen of een berekenbare strategie (een strategie die door een computerprogramma kan worden uitgevoerd) winnend is in Yu-Gi-Oh! TCG, is een onbeslisbaar probleem.

   • Corollary: Er bestaat geen computerprogramma dat kan beslissen of een gegeven strategie winnend is.

2. Stelling 1.3 (Complexiteit voor berekenbare strategieën):
   Het probleem is niet alleen onbeslisbaar, maar valt precies in de complexiteitsklasse $\Pi^1_1$-compleet (in de lichtgrijze analytische hiërarchie).

   • Dit betekent dat het probleem minstens zo moeilijk is als het bepalen van eigenschappen van verzamelingen die gedefinieerd worden door universele kwantificering over reële getallen (of oneindige reeksen). De auteurs bewijzen dit door een reductie van een bekende $\Pi^1_1$-complete verzameling (de verzameling van indices van Turing-machines die geen oneindige tegenstootreeks hebben) naar het Yu-Gi-Oh! probleem.

3. Stelling 1.4 (Complexiteit voor niet-berekenbare strategieën):
   Zelfs als men de beperking tot "berekenbare" strategieën verwijdert en alle mogelijke strategieën (inclusief niet-berekenbare) beschouwt, blijft het probleem $\Pi^1_1$-compleet.

   • Dit wordt bewezen via een Wadge-reductie vanuit de verzameling van goed-geordende lijnordeningen (well-orders) op een aftelbaar domein.

4. Bijdragen aan de Literatuur

• Formele Analyse: Dit is het eerste academische werk dat de computationele logica van Yu-Gi-Oh! TCG formeel analyseert.
• Vergelijking met Magic: The Gathering: Het artikel toont aan dat Yu-Gi-Oh! TCG, ondanks het gebrek aan de extreme automatisering van sommige Magic-kaarten, even complex is wat betreft de onbeslisbaarheid van winnende strategieën.
• Technische Innovatie: De auteurs tonen aan hoe men met bestaande, legale kaarten (zonder hacks of verboden kaarten) een Turing-machine kan simuleren en hoe men de spelregels kan manipuleren om willekeurige berekeningen en interacties met de tegenstander mogelijk te maken.

5. Significance en Implicaties

• Theoretische Informatica: Het resultaat bevestigt dat kaartspellen met complexe interacties en geheugenmechanismen fundamenteel onoplosbaar kunnen zijn voor algoritmen. Het plaatst Yu-Gi-Oh! TCG in dezelfde categorie als Magic: The Gathering en andere complexe systemen wat betreft de grenzen van berekenbaarheid.
• Speltheorie: Het onderstreept dat het vinden van een "perfecte" strategie in dit spel theoretisch onmogelijk is. Er is geen algoritme dat voor elke mogelijke speltoestand en strategie kan garanderen of deze winnend is.
• Toekomstig Onderzoek: De auteurs suggereren dat hun technieken waarschijnlijk ook van toepassing zijn op andere kaartspellen zoals Pokémon TCG, wat suggereert dat onbeslisbaarheid een gemeenschappelijk kenmerk kan zijn van complexe trading card games.

Conclusie:
Het artikel concludeert dat het probleem van het bepalen van een winnende strategie in Yu-Gi-Oh! TCG fundamenteel onoplosbaar is voor computers en dat de wiskundige complexiteit ervan de hoogste niveaus van de analytische hiërarchie bereikt ($\Pi^1_1$-compleet). Dit betekent dat er geen algoritme bestaat dat dit probleem voor alle mogelijke situaties kan oplossen.