Guida

Magic the Gathering è il gioco più complesso in assoluto

2.3.2020

Traduzione: tradotto automaticamente

Sorpresa per i teorici dei giochi algoritmici: non avrebbero mai sognato che un gioco potesse essere così complesso. Tuttavia, la "magia" a volte può sopraffare i computer, come dimostra una recente ricerca.

Chi si trovava a Las Vegas nel settembre 2018 poteva facilmente sentirsi trasportato nella popolare serie televisiva "The Big Bang Theory": In una stanza, 24 uomini adulti si stavano sfidando con carte da gioco fantasy colorate che raffiguravano creature magiche e incantesimi. In realtà si trattava del campionato mondiale annuale di "Magic: The Gathering", in cui i giocatori si sfidano per aggiudicarsi un montepremi complessivo di 300.000 dollari.

Nel frattempo, il campionato mondiale di "Magic: The Gathering" si è concluso.

Nel frattempo, il gioco di carte ha affascinato molte persone anche dal punto di vista scientifico, poiché sembra che stia ribaltando le convinzioni decennali dei teorici del gioco: A quanto pare Magic, con le sue numerose carte, le sue regole complicate e le sue strategie ingegnose, rappresenta una sfida per i computer più di quanto gli informatici pensassero.

Il principale interesse dei teorici dei giochi algoritmici è quello di calcolare strategie vincenti per i giochi in corso. Più è difficile per un computer prevedere l'esito di un gioco, più gli informatici classificano un gioco complesso. La magia sembra distinguersi in modo particolare rispetto agli altri giochi: Come il ricercatore indipendente Alex Churchill di Cambridge, nel Regno Unito, ha pubblicato insieme a Stella Biderman del Georgia Institute of Technology di Atlanta e Austin Herrick dell'Università della Pennsylvania di Filadelfia in un articolo pubblicato sul server di documenti preprint ArXiv lavoro, non è sempre possibile prevedere l'esito di un duello di Magic, rendendolo il più complesso di tutti i giochi conosciuti fino ad oggi.

Per distinguere i giochi di Magic da quelli di altri giochi, è stato necessario un lavoro di ricerca.

Per distinguere i diversi livelli di difficoltà, gli informatici teorici classificano i problemi in cosiddette classi di complessità. Il fattore decisivo è il tempo di cui un computer ha bisogno - se è in grado di farlo - per risolvere un compito. Ad esempio, se vuoi scomporre un numero nei suoi fattori primi, il tempo di calcolo necessario aumenta esponenzialmente con le sue dimensioni. L'operazione opposta, cioè la moltiplicazione di due fattori primi, è molto più semplice: secondo le ultime indagini, il tempo di calcolo aumenta con n log(n), dove n è la lunghezza dei due fattori.

Per i numeri estremamente grandi, non esiste quindi un modo efficiente per scomporli nei loro fattori primi, mentre è molto facile verificare il risultato. Tali problemi sono noti in informatica come problemi NP.

Lo schema può essere utilizzato anche per la scomposizione in fattori primi.

Lo schema può essere utilizzato anche per valutare la complessità di un gioco. Ad esempio, durante una partita di scacchi che sta per finire, un computer può calcolare se e come il colore bianco può ancora vincere. Tutto ciò che deve fare è passare in rassegna tutte le mosse possibili. Può sembrare piuttosto complicato, ma il tavolo da gioco limitato significa che un computer può completare questo compito in poco tempo. Poiché la maggior parte dei giochi reali (cioè quelli a cui le persone giocano davvero e che non sono stati costruiti artificialmente) non sono molto complessi, gli scienziati informatici non se ne sono mai interessati. Infatti, in passato gli esperti avevano ipotizzato che non esistesse alcun gioco reale la cui complessità raggiungesse la classe NP.

Sorpresa per i teorici dei giochi

Come hanno dimostrato Churchill e i suoi due colleghi, però, questo è il caso di Magic. E sospettano addirittura che il gioco di carte collezionabili possa essere ancora più complesso. Per giungere a queste conclusioni, i ricercatori hanno utilizzato un concetto comune nell'informatica teorica: la cosiddetta macchina di Turing. Questo modello di computer, introdotto nel 1936 dallo scienziato britannico Alan Turing, simula il modo in cui funzionano i computer classici.

Consiste in un nastro diviso in singoli campi e in una testina che legge i campi e li descrive se necessario. La macchina può spostare il nastro a sinistra o a destra per raggiungere i campi desiderati. Rappresenta quindi ciò che i matematici chiamano una funzione: Converte numeri in altri numeri secondo una regola specifica e non ambigua. Un tipico estratto di un programma per una macchina di Turing, ad esempio, recita: "Se la macchina si trova nello stato 3 e il campo contiene il numero 0, allora sovrascrivilo con un 1, passa allo stato 5 e sposta 4 campi a destra."

Una domanda classica nella discussione sulle macchine di Turing è se una macchina raggiunge mai la fine del calcolo di un problema o se continua a girare all'infinito. Già nel 1936, Turing dimostrò che non c'è modo di rispondere a questa domanda in generale per tutti i possibili algoritmi.
Churchill e i suoi collaboratori hanno dimostrato che la macchina di Turing non è in grado di risolvere i problemi.
Churchill e il suo team sono ora riusciti a dimostrare che la questione dell'esito di un duello di Magic corrisponde al problema dell'halting: ciò significa che esistono situazioni di gioco in cui un computer non può calcolare chi vincerà.

Gli scienziati sono arrivati a questo sorprendente risultato dimostrando che Magic: The Gathering ha le stesse funzioni di una macchina di Turing, cioè è "Turing-completo", come dicono gli esperti. In altre parole, Magic può essere utilizzato per simulare una macchina di Turing e viceversa.
A questo scopo, Churchill e The Gathering hanno dimostrato che Magic: The Gathering ha le stesse funzioni di una macchina di Turing.
A tal fine, Churchill, Biderman e Herrick hanno costruito una situazione di partenza speciale tra due giocatori di Magic e hanno identificato le mosse possibili con le funzioni essenziali di una macchina di Turing: leggere, scrivere e spostare il nastro. Di conseguenza, il gioco ha tutte le proprietà del modello teorico del computer e può essere analizzato con gli strumenti dell'informatica teorica.

Un gioco come un computer

La scelta della giusta situazione di gioco per Magic: The Gathering si è rivelata comunque difficile. Da un lato, doveva contenere elementi di gioco abbastanza complicati da simulare una macchina di Turing, ma dall'altro doveva rimanere abbastanza semplice da permettere al giocatore di avere una visione d'insieme delle mosse possibili. Dopo tutto, esistono più di 20.000 carte Magic diverse, ognuna delle quali ha una funzione diversa. Inoltre, alcune di esse contengono azioni volontarie che danno al giocatore una libertà strategica difficile da simulare. Churchill e i suoi colleghi hanno quindi incluso solo carte che hanno un effetto chiaro. Nella situazione di gioco da loro creata - che può certamente verificarsi in un torneo realistico - ci sono quindi solo mosse forzate; i giocatori non hanno alcuna libertà di scelta.

Prima di iniziare una partita di Magic, un giocatore seleziona 60 carte dalla sua collezione: questa selezione dall'enorme pool di carte disponibili e le conseguenti possibilità di combinazione portano alla straordinaria complessità del gioco. Una volta effettuata la selezione, il giocatore mescola accuratamente le carte e ne prende sette in mano. Le carte rimanenti formano il loro mazzo di carte.

Le carte comprendono creature che attaccano l'avversario, incantesimi e artefatti. All'inizio di ogni turno viene pescata una carta. Se un giocatore deve prendere una carta da un mazzo di carte vuoto, perde. In caso contrario, puoi sconfiggere il tuo avversario riducendo i suoi punti vita a zero o meno con degli attacchi mirati.

Nel gioco ideato da Churchill e dai suoi colleghi, Alice e Bob competono l'uno contro l'altro. Bob si trova in una situazione in cui non ha carte in mano e la sua pila è vuota, quindi è sull'orlo della sconfitta. Tuttavia, controlla tutte le creature sul tavolo. Alice può quindi provare ad attaccare le creature di Bob solo con le carte del suo mazzo.

Questa situazione iniziale permette ai ricercatori di identificare il gioco con una macchina di Turing. In questo modello, le creature sul tavolo corrispondono alla banda: c'è una creatura su ogni casella, con i suoi valori di potenza e durezza che indicano quanto danno fa e quanto può sopportare. Anche la magia ha cinque diversi colori "magici" che caratterizzano una carta. Nel gioco ideato da Churchill e dai suoi colleghi, le creature bianche o verdi appaiono con gli stessi valori di forza e resistenza (ad esempio 2/2 o 3/3).

Nello stato iniziale, le creature sono di colore bianco e verde.

Nello stato iniziale, il nastro è disposto in modo che la testina di lettura poggi sulla creatura più debole (2/2); a destra di essa ci sono tutte le creature bianche in ordine di forza e, allo stesso modo, tutte le creature verdi a sinistra. Una creatura bianca con i valori 5/5 si trova quindi nel terzo spazio a destra della testa. Il tipo di creatura è indicato da un simbolo sul quadrato.

Macchina di Turing per Magic: The Gathering | Gli spazi sul nastro corrispondono alle creature verdi (a sinistra) e bianche (a destra) di Bob. La distanza dalla testa della Macchina di Turing (in giallo) corrisponde ai valori di forza e resistenza della rispettiva creatura (valori numerici superiori). Le lettere simboleggiano il tipo di creatura.
Fonte: Spektrum der Wissenschaft

Le varie funzioni della macchina di Turing vengono avviate giocando le carte di Alice: Per spostare il nastro a destra o a sinistra, Alice deve giocare una carta che infligge danni a tutte le creature di un certo colore. Ma cosa succede se una creatura muore durante il processo? Churchill e i suoi colleghi hanno previsto questa eventualità: una delle carte di Bob è il Moderlungen Reviver, che sostituisce una creatura morta con una nuova dello stesso colore. Questo spiega anche il modo in cui la testa della Macchina di Turing legge e riscrive un campo: Alice uccide una creatura e Bob la rianima.

Cruciale per l'intero processo è la carta "Evoluzione Artificiale", che permette a un giocatore di cambiare le azioni di altre carte. Ad esempio, mentre il Resuscitatore di Polmoni di Moda resuscita solo chierici come zombie, l'Evoluzione Artificiale ti permette di sostituire lo zombie con qualsiasi altra creatura. Secondo Churchill, è proprio questa capacità a caratterizzare Magic: The Gathering: "Affinché un gioco abbia la stessa complessità di Magic, un giocatore deve essere in grado di controllarlo o programmarlo durante la partita nel modo in cui l'Evoluzione Artificiale lo consente", ha detto.

Con questa selezione di carte, il gioco tra Alice e Bob ha tutte le capacità di una macchina di Turing. "Se scegli il tuo problema matematico preferito, puoi creare una situazione di gioco magica che calcola questo problema scegliendo le carte giuste", spiega Stella Biderman, coautrice dell'articolo. Tuttavia, questo richiede molto tempo: Prima bisogna tradurre il compito nel linguaggio di una macchina di Turing, che è già piuttosto complicato, e poi trovare la giusta selezione e disposizione delle carte magiche che corrisponde al problema. Tuttavia, una volta trovata la giusta situazione di partenza, non devi fare altro che lasciare che Alice e Bob inizino a giocare; le loro mosse forzate corrispondono poi alle singole fasi di calcolo. Non appena la partita tra i due è terminata, è possibile leggere la soluzione del problema.
Churchill e i suoi collaboratori sono riusciti a trovare una soluzione.
Churchill e il suo team hanno progettato il gioco in modo tale che Bob non possa vincere. Pertanto, la macchina di Turing si ferma solo quando Alice vince, altrimenti continua a funzionare per sempre. Situazioni del genere possono verificarsi nei veri giochi di Magic. Esiste persino una regola secondo la quale una partita termina con un pareggio se le mosse vengono ripetute più volte.
In totale sono tre le situazioni che si possono verificare.
In totale, nel gioco tra Alice e Bob possono verificarsi tre situazioni: Le carte corrispondono a un problema che una macchina di Turing può risolvere, come ad esempio il compito di calcolare "2 + 2". In questo caso, Alice vincerà la partita. D'altra parte, il gioco potrebbe rappresentare un problema irrisolvibile, come "calcolare il numero naturale x per il quale x2 = 2". Poiché tale numero non esiste, la macchina di Turing continuerà a girare all'infinito, quindi il gioco finirà con un pareggio. Tuttavia, esiste anche una terza possibilità: le carte potrebbero rappresentare qualcosa che non si sa se può essere risolto o meno. Un esempio potrebbe essere "Calcola una coppia di gemelli primi (cioè due numeri primi con una differenza di 2) che siano maggiori di 10500.000". Poiché i matematici non sanno ancora se esistano gemelli primi di queste dimensioni, è anche incerto se la macchina di Turing sarà mai valida.

Problemi matematici in Magic: The Gathering | Ci sono tre tipi di problemi matematici che possono sorgere in un duello di Magic, come costruito dagli scienziati. In alto: un problema risolvibile, la macchina di Turing si ferma e Alice vince. Centro: Il problema è irrisolvibile, la macchina di Turing continua a funzionare all'infinito e la partita di Magic termina con un pareggio. In basso: Non è chiaro se esista una soluzione, non si sa se la macchina di Turing reggerà mai e quindi anche l'esito del gioco è incerto.
Fonte: Spektrum der Wissenschaft

Se un computer vuole prevedere l'esito del gioco tra Alice e Bob, deve risolvere il problema dell'arresto delle macchine di Turing. Per molte situazioni, come nei primi due esempi citati, questo non è un problema. Tuttavia, ci sono anche giochi in cui l'esito non è chiaro, come nell'ultimo caso. In generale, quindi, nessun algoritmo può prevedere come, se e quando finirà la partita tra Alice e Bob in un determinato duello, anche se ogni mossa di entrambi i giocatori è forzata. L'esito della partita dipende quindi solo dalle creature che Bob controlla all'inizio e dall'ordine in cui Alice pesca le sue carte.

I ricercatori sono riusciti a dimostrare che la situazione di gioco da loro immaginata può effettivamente verificarsi in un duello realistico e non è solo un costrutto artificiale. Inoltre, ipotizzano che altre situazioni di gioco possano portare a vicoli ciechi simili. Pertanto, il gioco raggiunge almeno il livello di complessità NP, scrivono gli autori. Tuttavia, per verificare se è forse ancora più complesso, è necessario adottare un approccio diverso.

Ciò non toglie che il gioco raggiunga almeno il livello di complessità NP, scrivono gli autori.

Comunque, il risultato rimane sorprendente dal punto di vista della teoria dei giochi, anche se potrebbe essere meno sorprendente per i giocatori di Magic: alcuni di loro si sono a lungo vantati di aver padroneggiato un gioco estremamente complicato. Ora possono ufficialmente affermare di giocare al gioco più complesso del mondo.

Provalo subito

Spettro della scienza

Siamo partner di Spektrum der Wissenschaft e vogliamo rendere più accessibili le informazioni scientifiche. Ti piacciono gli articoli di Spektrum? Allora segui Spektrum der Wissenschaft o abbonati alla rivista e sostieni il giornalismo scientifico.

[[small:]]

A 25 persone piace questo articolo

Spektrum der Wissenschaft

Wissenschaft aus erster Hand

dirdjaja@spektrum.de

Gli esperti della scienza e della ricerca riferiscono sulle ultime scoperte nei loro campi – competenti, autentiche e comprensibili.

Giocattoli

Segui gli argomenti e ricevi gli aggiornamenti settimanali relativi ai tuoi interessi.

Guida

Soluzioni pratiche per le domande di tutti i giorni su tecnologia, trucchi per la casa e molto altro.

Visualizza tutti

Potrebbero interessarti anche questi articoli

Guida
10 giochi da tavolo e di carte che devi assolutamente avere
di Alessandro Grieco
Guida
Dai giochi d'azione a quelli strategici: 5 giochi per tutta la famiglia
di Michael Restin
Guida
Cinque giochi veloci con le carte Jass
di Ramon Schneider

9 commenti

later

Cerca

Magic the Gathering è il gioco più complesso in assoluto

Sorpresa per i teorici dei giochi

Un gioco come un computer

Provalo subito

Spettro della scienza

Potrebbero interessarti anche questi articoli

10 giochi da tavolo e di carte che devi assolutamente avere

Dai giochi d'azione a quelli strategici: 5 giochi per tutta la famiglia

Cinque giochi veloci con le carte Jass

9 commenti

Top 10 categorie

Vai direttamente a

9 commenti

Galaxus Offerta del giorno