Magic: The Gathering è ufficialmente il gioco più complesso del mondo

Un'immagine dei pacchetti di carte da gioco di Magic: The Gathering Nathan Rupert

Magic: The Gathering è un gioco di carte in cui i maghi lanciano incantesimi, evocano creature e sfruttano oggetti magici per sconfiggere i loro avversari.

Nel gioco, due o più giocatori assemblano ciascuno un mazzo di 60 carte con poteri variabili. Scelgono questi mazzi da un pool di circa 20.000 carte create durante l'evoluzione del gioco. Sebbene simile ai giochi di ruolo fantasy come Dungeons and Dragons, ha molte più carte e regole più complesse rispetto ad altri giochi di carte.

E questo solleva una domanda interessante: tra i giochi del mondo reale (quelli a cui le persone giocano effettivamente, al contrario di quelli ipotetici che di solito considerano i teorici dei giochi), dove cade in complessità Magic?

Oggi riceviamo una risposta grazie al lavoro di Alex Churchill, ricercatore indipendente e designer di giochi da tavolo a Cambridge, Regno Unito; Stella Biderman al Georgia Institute of Technology; e Austin Herrick all'Università della Pennsylvania.

Il suo team ha misurato per la prima volta la complessità computazionale del gioco codificandolo in un modo che può essere giocato da un computer o da una macchina di Turing. Questa costruzione lo stabilisce Magia: The Gathering è il gioco del mondo reale più complesso dal punto di vista computazionale conosciuto in letteratura, dicono.

Innanzitutto, un po' di background. Un compito importante nell'informatica è determinare se un problema può essere risolto in linea di principio. Ad esempio, decidere se due numeri sono primi relativamente (in altre parole, se il loro massimo comun divisore è maggiore di 1) è un compito che può essere svolto in un numero finito di passaggi ben definiti e quindi è calcolabile.

In una normale partita a scacchi, anche decidere se il bianco ha una strategia vincente è calcolabile. Il processo prevede il test di ogni possibile sequenza di mosse per vedere se il bianco può forzare una vittoria.

Ma mentre entrambi questi problemi sono calcolabili, le risorse necessarie per risolverli sono molto diverse.

È qui che entra in gioco la nozione di complessità computazionale. Questa è una classifica basata sulle risorse necessarie per risolvere i problemi.

In questo caso, decidere se due numeri sono primi tra loro può essere risolto in un numero di passaggi proporzionale a una funzione polinomiale dei numeri in ingresso. Se l'input è X , il termine più importante in una funzione polinomiale è della forma Cxn , dove C e n sono costanti. Questo rientra in una classe nota come P , dove P sta per tempo polinomiale.

Al contrario, il problema degli scacchi deve essere risolto con la forza bruta e il numero di passaggi che ciò richiede aumenta in proporzione a una funzione esponenziale dell'input. Se l'input è X , il termine più importante in una funzione esponenziale è della forma Cnx , dove C e n sono costanti. E come X aumenta, questo diventa più grande molto più velocemente di Cxn . Quindi questo rientra in una categoria di maggiore complessità chiamata EXP, o tempo esponenziale.

Oltre a questo, ci sono varie altre categorie di varia complessità e persino problemi per i quali non esistono algoritmi per risolverli. Questi sono chiamati non calcolabili.

Capire in quale categoria rientrano i giochi di classe di complessità è una faccenda complicata. La maggior parte dei giochi del mondo reale ha limiti finiti alla loro complessità, come le dimensioni di un tabellone di gioco. E questo rende molti di loro banali dal punto di vista della complessità. La maggior parte delle ricerche sulla teoria algoritmica dei giochi dei giochi del mondo reale ha principalmente esaminato le generalizzazioni dei giochi comunemente giocati piuttosto che le versioni dei giochi del mondo reale, affermano Churchill e co.

Quindi solo pochi giochi del mondo reale sono noti per avere una complessità non banale. Questi includono Dots-and-Boxes, Jenga e Tetris. Crediamo che nessun gioco del mondo reale sia noto per essere più difficile di NP prima di questo lavoro, afferma Churchill e co.

Il nuovo lavoro mostra che Magic: the Gathering è significativamente più complesso. Il metodo è semplice in linea di principio. Churchill e compagni iniziano traducendo i poteri e le proprietà di ogni carta in una serie di passaggi che possono essere codificati.

Quindi svolgono una partita tra due giocatori in cui il gioco si svolge in una macchina di Turing. E infine mostrano che determinare se un giocatore ha una strategia vincente equivale al famoso problema dell'arresto in informatica.

Questo è il problema di decidere se un programma per computer con un input specifico terminerà l'esecuzione o continuerà per sempre. Nel 1936 Alan Turing dimostrò che nessun algoritmo può determinare la risposta. In altre parole, il problema non è calcolabile.

Quindi il risultato chiave di Churchill e co è che determinare l'esito di una partita di Magic non è calcolabile. Questo è il primo risultato che mostra che esiste un gioco nel mondo reale per il quale determinare la strategia vincente non è calcolabile, dicono.

Questo è un lavoro interessante che solleva importanti questioni fondamentali per la teoria dei giochi. Ad esempio, Churchill e colleghi affermano che la principale teoria formale dei giochi presuppone che qualsiasi gioco debba essere calcolabile. Magia: The Gathering non si adatta alle ipotesi comunemente fatte dagli informatici durante la modellazione dei giochi, dicono.

Ciò suggerisce che gli informatici devono ripensare le loro idee sui giochi, in particolare se sperano di produrre una teoria computazionale unificata dei giochi. Chiaramente, la magia rappresenta una mosca nell'unguento incantato per quanto riguarda questo.

Rif: arxiv.org/abs/1904.09828 : Magic: The Gathering Is Turing Complete

nascondere