Più di un semplice gioco di carte, Magic fornisce una bizzarra occasione per costruire un prototipo di macchina di Turing
La cosiddetta ‘macchina di Turing’ è l’archetipo di ogni calcolatore esistente, un meccanismo astratto ideato dal matematico inglese Alan Turing che ha gettato le basi dell’informatica moderna. Magic: the gathering, invece, è l’archetipo dei giochi di carte collezionabili, ideato all’inizio degli anni ’90 del secolo scorso da Richard Garfield e distribuito ininterrottamente fino ad oggi. Un articolo datato aprile 2019 svela una curiosa connessione tra i due.
Alan Turing e il problema della decidibilità
Alan Turing è stato sicuramente uno dei più brillanti studiosi del secolo scorso: nato a Londra nel 1912, lavorò in Inghilterra come matematico, logico e crittografo e morì tristemente nel 1954 in seguito a un travagliato periodo dovuto alla castrazione chimica, pena inflittagli per reato di omosessualità. Le umiliazioni subite da Turing, unite ai problemi fisici che la castrazione comportò, generarono in lui uno stato di depressione che per alcuni studiosi fu alla base della scelta di suicidarsi. Cionondimeno si distinse in vita per la genialità delle sue idee e per alcune sue bizzarrie (si dice che legasse la propria tazza personale a un calorifero perché nessun altro la usasse). Sicuramente oggi, grazie al film del 2014 The imitation game con Benedict Cumberbatch, la sua fama è legata strettamente al lavoro svolto nella Seconda Guerra Mondiale per decifrare i codici tedeschi criptati con il sistema Enigma, ma la macchina Bomba da lui perfezionata è solo uno dei tanti successi che lo consacrarono come uno dei padri dell’informatica. Nel 1936, infatti, a due anni dalla laurea conseguita con il massimo dei voti, il giovane matematico pubblicò un articolo in cui descriveva per la prima volta quella che oggi conosciamo come macchina di Turing e che al tempo era un espediente astratto per risolvere un problema diverso. In quegli anni ferveva l’interesse per lo studio dei fondamenti della matematica, ovvero le basi di logica e filosofia su cui essa si fonda, e facevano scalpore le sfide lanciate da David Hilbert (1862-1943). Questo matematico tedesco, infatti, aveva proposto una lista di 23 problemi allora irrisolti, passati alla storia come ‘Problemi di Hilbert’, nonché una serie di altre questioni come l’Entscheidungsproblem (in italiano: problema della decisione). Fu proprio sulla decidibilità che lavorò il neo-laureato Turing, ma di cosa si tratta? In sostanza, Hilbert chiedeva di mostrare una procedura meccanica con cui fosse possibile dimostrare se una formula scritta nel linguaggio della logica del primo ordine (ovvero con connettivi logici, relazioni e quantificatori) fosse o meno un teorema della logica del primo ordine, cioè deducibile all’interno del sistema formale stesso. L’interesse per la risposta era dovuto al fatto che, se si fosse trovato tale metodo, sarebbe stato possibile risolvere ogni problema matematico. La risposta – non troppo inaspettatamente negativa – fu doppia e arrivò nel 1936 grazie allo statunitense Alonzo Church (1903-1995) e ad Alan Turing, che per la propria dimostrazione indipendente ideò la macchina su cui poniamo la nostra attenzione.
Come funziona la macchina di Turing
Andando al sodo, che cos’è davvero una macchina di Turing? A dire il vero ne esistono varie versioni, ma limitiamoci al modello base, ovvero la macchina di Turing a un nastro e istruzioni a cinque campi. Tale costrutto esemplifica qualsiasi metodologia di calcolo a noi nota e si basa su una testina mobile di input/output (I/O) e un nastro potenzialmente infinito da essa analizzato. Il nastro è diviso in celle successive, ciascuna contenente un singolo carattere scelto da un insieme iniziale (come la coppia 0/1 per un sistema binario o l’alfabeto latino) o uno spazio. Esso codifica i dati attuali del problema, dalle condizioni iniziali al possibile risultato finale. La testina di I/O è caratterizzata a ogni passo del calcolo da uno stato s, frutto dell’operazione precedentemente eseguita e codificante una specifica azione come conseguenza del carattere letto. Quando la macchina viene “accesa” la testina legge per ogni intervallo di tempo t il numero della cella che osserva in quel momento (sempre e solo una alla volta) ed il suo contenuto. Poi, in base al proprio stato attuale, può compiere azioni quali: scrivere nella casella un nuovo simbolo, cancellare il contenuto della casella, spostarsi di una casella a destra o a sinistra oppure fermarsi. Un’evoluzione della macchina indica allora la sequenza delle configurazioni (insieme dello stato e della casella osservata) attraverso cui essa passa e che può avere tre esiti. Può innanzitutto arrestarsi in un risultato utile, ovvero le celle codificano l’effettivo esito del processo. Poi, può terminare in un risultato inutile, se c’è stato un errore nell’algoritmo. Infine, può non concludersi affatto. Proprio in quest’ultima peculiarità sta la genialità dell’idea di Turing. Egli dimostrò che per ogni calcolo e ogni macchina costruita – e ciò vale ancora adesso – è possibile costruire una macchina di Turing che svolga autonomamente l’operazione e ciò è noto oggi con il nome di congettura di Church-Turing. Ciò ha permesso anche di definire la cosiddetta Turing-equivalenza, ovvero una relazione tra metodi di calcolo propria di quelli che hanno la stessa potenza di una macchina di Turing universale. Una macchina di Turing universale è, infatti, una macchina in grado di simulare l’evoluzione di ogni altra macchina di Turing, autoprogrammandosi per poi eseguire il medesimo calcolo sul nastro di partenza. I problemi sorgono quando si cerca il risultato della macchina: per alcune è possibile prevedere se avranno una fine o no, ma per altre è indimostrabile. Turing affrontò il problema dell’arresto proprio usando l’idea della macchina universale. Essa è tale che può predire l’esito di ogni macchina, quindi anche se stessa, ma ciò porta a un assurdo nel decidere l’esito del problema dell’arresto, vanificando le speranze di Hilbert. Se esistesse una tale macchina, essa dovrebbe, infatti, sapere se si fermerà mentre ancora è in funzione e ciò è assurdo. L’unica strada, quando non è possibile stabilire l’eventualità dell’arresto solo analizzando la struttura del codice, è allora provare il codice stesso e sperare che fornisca un risultato in tempi ragionevoli, sempre a patto di essere in grado di codificare i dati di ingresso e decodificare quelli in uscita.
Magic: the gathering fa della complessità virtù
Lo studio di giochi reali per formulare teorie o verificare affermazioni non è inusuale e rappresenta una sfida, dai primi tentativi di costruire macchine che giocassero a scacchi contro grandi maestri fino alle intelligenze artificiali attuali che padroneggiano una moltitudine di giochi umani. Anche Magic: the gathering, gioco di carte collezionabili nato da un’idea di Richard Garfield nel 1993 e distribuito da Wizards of the coast (la stessa casa di Dungeons&Dragons), è stato oggetto di ricerche e risale al 23 aprile 2019 un articolo che ha ridato vita all’interesse. Alex Churchill (ricercatore indipendente), Stella Biderman (Georgia Institute for Technology, Atlanta) e Austin Herrick (University of Pennsylvania, Philadelphia) hanno, infatti, raccolto l’eredità dei precedenti studi e dimostrato come costruire in una partita a Magic tra due giocatori una Macchina di Turing tale che il risultato della partita sia deciso solo dall’esito del problema dell’arresto ad essa legato. Qui sotto è riportato uno dei molti video, in questo caso in inglese, che mostra il mazzo ‘macchina di Turing’ in azione. Una piccola premessa è necessaria per coloro che non conoscono il gioco. In Magic i giocatori controllano un mazzo detto grimorio, le cui carte sono caratterizzate da uno o più colori tra i cinque previsti (rosso, bianco, verde, nero e blu oltre a quelle incolori) e la vittoria è ottenuta riducendo a zero il contatore dei punti vita avversari. Le tipologie di carte sono diverse, ma le principali sono le terre (forniscono energia, detta mana, per giocare altre carte), le creature (esseri che attaccano e difendono sulla base rispettivamente della propria forza e costituzione) e vari di tipi di magie che aggiungono varietà alla partita. Per avere un’idea dell’enormità del gioco, sommando tutte le espansioni uscite si arriva ad un totale di oltre 20.000 carte diverse. In passato, si era notato come fosse possibile programmare una macchina di Turing in giochi sandbox come Minecraft, senza però che tale macchina partecipasse in qualche tipo di competizione tra giocatori e determinasse vittoria o sconfitta. Ugualmente erano state costruite in Magic macchine funzionanti in partite a 4 giocatori, a patto che questi attivassero abilità e giocassero carte ogni volta che fosse loro possibile.
Come funziona il mazzo ‘macchina di Turing’
Le scelte dei tre studiosi sono state tutte compiute nell’ottica di creare un mazzo (valido tra l’altro nel formato standard nello stile dei tornei, secondo l’articolo) un meccanismo interamente deterministico in cui alla fine il risultato sia quello di una macchina che non lascia scelte ai giocatori, ma che giochi sostanzialmente da sola. La costruzione si basa sulla perfetta costruzione dei mazzi dei due contendenti (Alice e Bob, per semplicità) e sull’apparire esatto delle carte nelle prime mani. Il funzionamento è abbastanza complesso, ma si tenga presente che Alice è la prima giocatrice e che sarà lei il motore della macchina. Il nastro è composto da pedine creatura, ciascuna rappresentante una cella con il proprio carattere (il tipo di creatura, tra 18 previsti nel caso analizzato), la propria posizione (il valore di forza e costituzione) e la porzione di nastro (si creano pedine verdi per quelle a “sinistra” e bianche per quelle a “destra”). Tutte le pedine sono controllate da Bob, tranne quella letta nel turno in corso che appartiene ad Alice. Lo stato della macchina e il meccanismo di lettura e scrittura sono creati grazie alle carte Rianimatore pneumoputrido e Necromante di Xhatrid, opportunamente copiate e modificate negli effetti grazie ad altre carte: in sostanza la pedina creatura letta sarà mandata al cimitero e al suo posto sarà creata una specifica nuova pedina del tipo e colore voluto. Il nastro si posta idealmente modificando i valori delle altre pedine in gioco (cosicché aumentando tutte le bianche di 1, si crei lo spazio per inserire la nuova pedina centrale). La partita procede perché grazie alla carta Evocazione selvaggia Alice è costretta a giocare l’unica carta che può tenere in mano, che però non scarta ma rimette nel mazzo grazie a Ruota del sole e della luna, e perché Bob non pesca (e quindi non termina il mazzo) grazie a Riciclo. La macchina si ferma quando non cambia stato e nel gioco ciò fa vincere Alice, grazie all’apposita carta Coalizione vittoriosa, che fa vincere il giocatore date le giuste condizioni di carte in gioco. Il problema, come noto da prima, è proprio sapere se la macchina si ferma. Il deck valido per un torneo, a dire il vero, è leggermente diverso da quello della dimostrazione, ma si trova tutto nell’articolo di cui sotto è riportato il link. Tutto ciò ha risultati effettivi? Come affermano gli autori dello studio, è stato fatto certamente un passo in avanti rispetto alle convinzioni del passato e, sebbene si sia ancora lontani dalla partita perfetta, ha almeno mostrato che esistono giochi reali Turing equivalenti (o Turing completi che dir si voglia) e dall’esito non meccanicamente prevedibile.
