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

Il paper dimostra che il problema di determinare se una strategia calcolabile garantisce la vittoria in una data situazione del gioco di carte Yu-Gi-Oh! TCG è indecidibile e, più precisamente, completo per la classe $\Pi^1_1$, estendendo tale risultato a tutte le strategie tramite una riduzione agli ordini ben fondati contabili.

L'essenziale

Immagina di avere un mazzo di carte da gioco, ma invece di essere solo un passatempo, è una macchina capace di pensare, calcolare e risolvere problemi complessi. Questo è il cuore della ricerca presentata nel paper "Deciding Winning Strategies in Yu-Gi-Oh! TCG is Hard" di Nicolsi, Pisciotta e Bresolin.

Ecco una spiegazione semplice, usando metafore quotidiane, di cosa hanno scoperto questi ricercatori.

1. Il Grande Esperimento: Yu-Gi-Oh! come un Cervello

Immagina che il gioco di carte Yu-Gi-Oh! non sia solo un gioco, ma un gigantesco computer fatto di carta.
I ricercatori si sono chiesti: "Se io ti do un piano di gioco (una strategia) e una situazione di gioco specifica, riesci a dire con certezza matematica se quel piano porterà alla vittoria, indipendentemente da cosa fa l'avversario?"

La risposta, secondo loro, è: No. È impossibile saperlo con certezza.

2. La Metafora del Labirinto Infinito

Per capire perché è impossibile, immagina di dover risolvere un labirinto.

• Nel gioco normale: Il labirinto ha un'uscita. Se segui il percorso giusto, vinci.
• In questo studio: Hanno dimostrato che con un mazzo specifico di carte (che hanno costruito e che è legale secondo le regole attuali), un giocatore può trasformare il campo di gioco in un labirinto infinito.

In questo labirinto, il giocatore può:

1. Memorizzare informazioni: Usando le "Conte Magiche" (Spell Counters) su una carta specifica, può scrivere numeri enormi, come se stesse scrivendo su un foglio di carta infinito.
2. Eseguire calcoli: Può far funzionare le carte come se fossero i passaggi di un computer (una Macchina di Turing).
3. Creare un gioco senza fine: Può far sì che il gioco continui all'infinito, simulando un calcolo che forse non finisce mai.

3. Il Problema della "Macchina che non si ferma"

Qui entra in gioco il famoso Problema della Fermata (Halting Problem).
Immagina di avere un robot programmato per fare un compito. Ti chiedi: "Questo robot finirà mai il suo lavoro o rimarrà bloccato per sempre?"
La matematica ci dice che non esiste un modo generale per rispondere a questa domanda prima di far partire il robot. A volte devi solo aspettare e vedere se si ferma, ma non puoi prevederlo con una formula magica.

Gli autori hanno dimostrato che:

• Decidere se una strategia in Yu-Gi-Oh! porta alla vittoria è esattamente come chiedersi se un computer si fermerà o meno.
• Se potessi creare un programma che ti dice sempre "Sì, vincerai" o "No, perderai" per ogni strategia di Yu-Gi-Oh!, allora potresti anche risolvere il problema della fermata dei computer.
• Poiché sappiamo che il problema della fermata è impossibile da risolvere, allora anche il problema della vittoria in Yu-Gi-Oh! è impossibile da risolvere.

4. La "Scatola Nera" e la Complessità

Il paper va oltre e dice che il problema non è solo "difficile", ma appartiene a una categoria di difficoltà matematica chiamata $\Pi^1_1$-completo.
Per usare un'analogia:

• Risolvere un Sudoku è difficile, ma un computer può farlo.
• Risolvere questo problema di Yu-Gi-Oh! è come cercare di prevedere il futuro di un universo intero che cambia mentre lo osservi. È un livello di complessità che va oltre la semplice logica dei computer attuali.

5. Come hanno fatto? (Il Trucco del Mazzo)

Hanno costruito due "mazzi magici" (legali, quindi con carte vere che esistono nel gioco):

1. Il primo mazzo: Permette al primo giocatore di trasformare il gioco in una simulazione di un computer. Se il computer simulato si ferma, il giocatore vince. Se non si ferma, il gioco continua all'infinito.
2. Il secondo mazzo (più avanzato): Permette al secondo giocatore di "scegliere" numeri a caso (come se fosse un generatore di numeri casuali) per interagire con il primo giocatore. Questo rende il problema ancora più complesso, trasformandolo in una sfida contro l'infinito stesso.

In Sintesi: Cosa significa per noi?

Questo studio ci dice che Yu-Gi-Oh! è molto più di un gioco di carte. È un sistema così ricco e complesso che:

• Non esiste un "bot" perfetto: Nessun programma per computer potrà mai essere scritto che ti dice sempre qual è la mossa perfetta per vincere in ogni situazione.
• La strategia è arte, non solo calcolo: Poiché non possiamo calcolare la vittoria perfetta, il gioco rimane un campo di battaglia dove l'intuizione, l'adattamento e l'abilità umana contano più di un algoritmo perfetto.
• È matematicamente "selvaggio": Le regole del gioco, se combinate in certi modi, creano scenari che sfidano la logica matematica stessa.

In poche parole: Vincere a Yu-Gi-Oh! è un compito così complesso che la matematica stessa ci dice che non possiamo mai essere sicuri al 100% se una strategia è vincente, proprio come non possiamo sapere se un computer impazzirà prima di finire il suo lavoro.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del paper "DECIDING WINNING STRATEGIES IN YU-GI-OH! TCG IS HARD" di Orazio Nicolosi, Federico Pisciotta e Lorenzo Bresolin, redatto in italiano.

1. Introduzione e Problema di Ricerca

Il paper si propone di analizzare le proprietà computazionali e logiche del gioco di carte collezionabili Yu-Gi-Oh! TCG (Trading Card Game), un'area finora priva di letteratura accademica formale, a differenza del suo principale concorrente, Magic: The Gathering, che è stato oggetto di studi sulla computabilità (es. [CBH20], [Bid20]).

Il problema centrale indagato è il seguente: È decidibile determinare se una strategia data, partendo da uno stato di gioco specifico, garantisce la vittoria per il giocatore?
A differenza di Magic: The Gathering, dove le interazioni delle carte sono altamente automatizzate, Yu-Gi-Oh! presenta un livello inferiore di automazione nelle risoluzioni degli effetti. Di conseguenza, gli autori riformulano il problema non come la ricerca di una posizione vincente, ma come la verifica di una strategia vincente (una funzione che mappa le configurazioni di gioco alle mosse legali).

2. Metodologia e Ipotesi Fondamentali

Per dimostrare l'indecidibilità e la complessità del problema, gli autori adottano un approccio basato sulla teoria della computabilità e sulla teoria degli insiemi descrittivi, costruendo una riduzione da problemi noti come indecidibili o completi per classi gerarchiche superiori.

Ipotesi di lavoro:

1. Transizione Computabile: Si assume che la funzione che mappa una configurazione legale e una mossa legale alla configurazione risultante sia computabile (Congettura 1). Questo è considerato più plausibile per Yu-Gi-Oh! rispetto a Magic data la semplicità relativa degli effetti delle carte.
2. Vincoli di Gioco: Si assume che in ogni turno un giocatore possa eseguire solo un numero finito di operazioni e che non vi siano limiti di tempo reali sulla durata della partita (permettendo loop infiniti).
3. Costruzione di Mazzo Legale: Per ogni dimostrazione, gli autori presentano mazzi legali (rispettando la lista attuale di carte proibite e limitate) che permettono di raggiungere configurazioni specifiche necessarie per le riduzioni.

3. Costruzione Tecnica Principale

Il cuore della dimostrazione risiede nella capacità di simulare una Macchina di Turing (MT) all'interno del gioco.

• Codifica dello Stato: Gli autori dimostrano che è possibile raggiungere una configurazione legale in cui il numero di "Spell Counters" (gettoni incantesimo) sulla carta Magical Citadel of Endymion codifica lo stato di una Macchina di Turing (contenuto del nastro, posizione della testina, stato corrente).
• Loop di Incremento/Decremento: Vengono descritti due cicli di gioco (loop) legali che permettono al Giocatore 1 di aumentare o diminuire il numero di gettoni in modo arbitrario, simulando le operazioni di scrittura e spostamento della testina della MT.
  • Incremento: Utilizza carte come Bait Doll, Upstart Goblin, Book of Eclipse e Desert Sunlight per riciclare carte e generare gettoni.
  • Decremento: Utilizza Endymion, the Master Magician e Offerings to the Doomed per rimuovere gettoni.
• Simulazione: Il Giocatore 1 segue una strategia computabile che esegue le istruzioni della MT codificata. Se la MT si ferma (halting), il giocatore passa alla fase di attacco per vincere la partita.

4. Risultati Principali

Il paper stabilisce tre risultati fondamentali sulla complessità computazionale del problema di determinare se una strategia è vincente:

A. Indecidibilità (Teorema 1.1)

Il problema di determinare se una strategia computabile è vincente è indecidibile.

• Dimostrazione: Viene effettuata una riduzione many-one dal Problema della Fermata (Halting Problem) ($\Sigma^0_1$-completo) al problema di verifica della strategia.
• Corollario: Non esiste alcun algoritmo informatico in grado di decidere se una strategia data per Yu-Gi-Oh! è vincente.

B. Complessità $\Pi^1_1$-Completa per Strategie Computabili (Teorema 1.3)

Il problema non è solo indecidibile, ma appartiene alla classe di complessità $\Pi^1_1$-completa (completo per la gerarchia analitica al primo livello).

• Metodo: Viene introdotta una variante del mazzo che permette al Giocatore 2 di "scegliere numeri" (aumentando i Life Points in modo controllato tramite un loop specifico con Flint Lock e Morale Boost).
• Riduzione: Si riduce l'insieme NIS (insieme degli indici di macchine di Turing che non ammettono una sequenza infinita di input che producano un output specifico, un insieme $\Pi^1_1$-completo) al problema di verifica della strategia. La strategia del Giocatore 1 deve verificare se la sequenza di scelte dell'avversario corrisponde a una computazione valida; se l'avversario "sbaglia" (o la computazione non termina), il Giocatore 1 vince.

C. Complessità $\Pi^1_1$-Completa per Strategie Generali (Teorema 1.4)

Il risultato si estende anche alle strategie non computabili (strategie arbitrarie, non necessariamente implementabili da un computer).

• Metodo: Utilizzando la teoria degli insiemi descrittivi, gli autori definiscono una riduzione di Wadge dall'insieme WO (insieme degli ordini lineari ben fondati su un dominio numerabile, un classico insieme $\Pi^1_1$-completo) al problema di verifica della strategia.
• Significato: Anche considerando strategie "non calcolabili" (che potrebbero richiedere una memoria o un potere decisionale sovrumano), il problema rimane $\Pi^1_1$-completo.

5. Contributi Chiave e Significato

1. Prima Analisi Formale: Questo lavoro rappresenta il primo studio accademico formale sulle proprietà logiche e computazionali di Yu-Gi-Oh! TCG.
2. Confronto con Magic: The Gathering: Dimostra che, nonostante le differenze meccaniche (Yu-Gi-Oh! ha meno automazione), il gioco possiede la stessa complessità computazionale fondamentale di Magic: The Gathering riguardo alle strategie vincenti.
3. Costruzioni di Deck: Fornisce due mazzi legali dettagliati (uno per la riduzione del problema della fermata e uno per la riduzione $\Pi^1_1$) che dimostrano come le interazioni complesse delle carte esistenti possano essere sfruttate per creare sistemi di calcolo universali all'interno del gioco.
4. Implicazioni Teoriche: Stabilisce che non esiste un "motore di gioco" perfetto o un algoritmo che possa predire l'esito di una partita data una strategia specifica, a meno che non si restringa il dominio a sottoclassi molto limitate di strategie.

Conclusione

Il paper conclude che il problema di determinare se una strategia in Yu-Gi-Oh! TCG è vincente è $\Pi^1_1$-completo. Questo risultato posiziona il gioco tra i sistemi più complessi dal punto di vista computazionale, indicando che la sua analisi strategica completa è al di là delle capacità della computazione classica e richiede strumenti della teoria degli insiemi descrittivi per essere classificata correttamente. Gli autori suggeriscono che tecniche simili potrebbero essere applicate ad altri giochi di carte come Pokémon TCG.