Quanto è difficile The Witness? Un gruppo di matematici prova a darci una risposta scientifica - articolo
Algoritmi, monomi, dottorati di ricerca e testimoni.
"Ogni tipo di indizio ha offerto un interessante problema da studiare."
The Witness è un gioco molto particolare. Per qualcuno è un esempio di pretenziosità, per altri è un modello matematico complesso. Le regole del gioco sono spiegate da simboli posizionati su griglie che a prima vista possono sembrare semplici, ma che sotto sotto sono tutt'altro che banali tanto che qualcuno ha deciso di studiarne i problemi sfruttando le proprie conoscenze matematiche.
Erik Demaine, professore di computer science al MIT, applica al suo insegnamento metodologie da ricercatore e spesso chiede ai suoi studenti di risolvere problemi unendosi in gruppi. Per farlo, usa uno stile di ricerca che chiama supercollaborazione.
Stando al sito internet di Demaine (linkato qui sopra), la supercollaborazione è un metodo di ricerca innovativo che permette ai ricercatori di risolvere problemi complessi mettendo da parte il proprio ego. Si supercollabora, insomma, nel senso che il lavoro di squadra ha la precedenza sugli input individuali. Qui sotto potete vedere un video di una classe all'opera, se vi incuriosisce la cosa.
Demaine è tra gli autori principali di una ricerca del 2018 chiamata Who witnesses The Witness?, che rappresenta un esempio perfetto di ricerca supercollaborativa e allo stesso tempo parla di cosa rende The Witness un gioco meritevole di essere studiato da matematici e dottori in computer science. La risposta, principalmente, si trova nella sua difficoltà.
Per chi non fosse esperto in materia, il termine "witness" ("testimone", in italiano) è un valore utilizzato per capire se qualcosa esiste, se esiste in almeno un caso, o se esiste solo se vengono soddisfatte determinate condizioni. Nel caso del gioco, il testimone ha a che fare con la metodologia di risoluzione degli enigmi, con le strategie effettivamente di successo e insomma con il percorso sulla griglia che concretizza queste strategie.
Ecco perché andare a caccia del "witness" in The Witness non è poi così facile, ed ecco perché dottori e professori si sono interessati al tema.
Demaine e i suoi colleghi spesso studiano i giochi cercando algoritmi efficienti da applicare poi alla risoluzione di problemi in altri campi, seguendo la teoria che spesso le soluzioni si trovano procedendo orizzontalmente.
"Prima di tutto volevamo individuare il confine tra aspetti computazionali difficili e facili dei puzzle di The Witness," ha detto Demaine. "Alcuni enigmi usano un tipo di indizi, mentre altri ne usano diversi. Volevamo capire perché alcuni tipi di indizi mescolati tra loro rendessero i puzzle più difficili da risolvere per un computer e quindi, di conseguenza, difficili anche per gli umani. E poi chiaramente anche capire quali indizi li rendessero più facili per i computer (ma non necessariamente più facili anche per noi). Di solito, esempi del secondo caso sono piuttosto rari, ecco perché è stato particolarmente interessante studiare i puzzle basati su monomi," ha aggiunto.
L'analisi della difficoltà è uno dei principali obiettivi della ricerca e dell'insegnamento di Demaine. L'arte di codificare la difficoltà è complessa: richiede di identificare gli elementi che rendono difficile un puzzle scomponendolo in vari problemi. Nel farlo, vengono scoperti algoritmi interessanti che possono poi rivelarsi utili anche in altri campi, in un processo che di solito rende sempre più complessi i calcoli a livello computazionale, ma li semplifica in superficie rendendoli più digeribili agli umani.
Adam Hesterberg è un altro dei ricercatori firmatari della ricerca. Sebbene stesse studiando per il dottorato di ricerca in matematica al MIT quando ha iniziato a lavorare con Demaine, ora è passato alla computer science. Per lui, The Witness è "computazionalmente interessante."
"Ho giocato a The Witness per la prima volta solo quando abbiamo deciso di lavorare sulla sua complessità computazionale, anche se devo dire che conosco quel tipo di enigmi logici," ha detto. "Mi piacciono i giochi da tavolo, a partire da quelli di gestione economica delle risorse di stampo tedesco come Gaia project, fino a qualsiasi gioco firmato da Vlaada Chvátil (a cui ho dedicato il mio appartamento). Il nostro gruppo di ricerca, di tanto in tanto, analizza anche altri giochi."
Demaine e i suoi colleghi hanno iniziato a lavorare su "Who witnesses The Witness?" nel 2016, due anni prima che venisse pubblicata come FUN (dalla conferenza internazionale Fun with Algorithms) nel 2018. Poi, la ricerca è stata completata da 10 accademici provenienti da tre diversi dipartimenti del MIT e da un'università tedesca.
Il focus, però, non è solo l'opera di Jonathan Blow. Il gruppo di ricerca analizza sistemi computazionali in diversi altri giochi, spesso alla ricerca di cosa rende difficile un puzzle difficile, con l'obiettivo di scoprire algoritmi alternativi.
"La complessità computazionale di giochi e puzzle è un argomento che mi è particolarmente caro, e che sto studiando più o meno dal 2000," ha detto Demaine. "La mia prima pubblicazione era su Clickomania, che abbiamo analizzato di nuovo di recente."
Se vi interessa il tema, Demaine ha pubblicato studi anche su Tetris (spiegando che può essere risolto da alcuni algoritmi di ricerca di tipo "brute force") e Super Mario Bros, tra le ricerche più complesse che ha firmato. Ma cosa rende così particolare The Witness? "Quando è uscito sembrava perfetto per noi con la sua varietà di puzzle e indizi," ha spiegato Demaine. "Parte del gioco consiste nello scoprire il significato degli indizi, quindi abbiamo deciso di avvisare il gruppo di ricerca e incoraggiarli a giocare per conto loro prima di iniziare gli studi, così da avere un'esperienza senza spoiler."
"Due settimane dopo ci siamo dedicati all'analisi, scoprendo che ogni tipologia di indizi offre un problema interessante da studiare."
Jeffrey Bosboom, dottore di ricerca al MIT dal 2011 e cofirmatario, ha scoperto The Witness durante una delle riunioni settimanali dedicate alla supercollaborazione. "Questo vuol dire che mi hanno spoilerato praticamente tutte le tipologie di puzzle, ma non credo di essermi divertito meno giocandolo per questo. Tutti i puzzle introduttivi nelle varie aree hanno funzione didattica in ogni caso, ed è stato piacevole sentire la transizione da conoscenza esplicita (dire a qualcuno il significato di un simbolo) e conoscenza implicita (guardare un puzzle e capire immediatamente quale deve essere la soluzione)."
Uno degli aspetti più particolari dei puzzle di The Witness, dice Demaine, è che il completamento di alcuni e di classe Sigma_2. Chiaro, no? Facciamo un ripassino: si tratta della classificazione della complessità richiesta per il loro completamento. Al livello più basso c'è la classe NP, che può essere risolta semplicemente provato soluzioni a casaccio finché non si trova quella giusta. Sigma_2 è a un livello superiore di complessità, e poi c'è la classe PSPACE che aggiunge la variabile temporale (sia quanto tempo è necessario a un computer per risolvere un problema, che quanto tempo serve per calcolare l'algoritmo necessario).
Non è facilissimo da seguire se non si è del mestiere, ma ci basti sapere che, secondo Demaine, buona parte dei puzzle di The Witness sono della seconda classe. "Un livello sopra alla complessità NP, quella base, anche se decisamente inferiori alla complessità PSPACE, che invece troviamo in puzzle che richiedono molte mosse per essere risolti (come nel puzzle game Rush Hour)".
Nella ricerca di Demaine, alcuni indizi sono stati chiamati "anticorpi" perché sono regole logiche che annullano gli effetti di altri indizi in una determinata regione dell'enigma, aggiungendo una variabile che va tenuta presente, e richiedendo dunque un approccio più ipotetico alla risoluzione del problema. Questo aumento della complessità computazionale fa si che alcuni problemi possano essere mescolati tra loro per individuare nuovi algoritmi più efficienti, cosa che qualifica i puzzle come Sigma_2, appunto.
"Un altro aspetto interessante riguarda gli indizi monomi," aggiunge Demaine. Un monomio è un singolo quadrato di un polinomio, che a sua volta è una forma creata appiccicando insieme quadrati della stessa forma. In The Witness, troviamo puzzle di entrambi i tipi.
Secondo Demaine, questi enigmi sono risolvibili da algoritmi efficienti tramite riduzione (la trasformazione di un problema in una variante più complessa di se stesso) e individuazione di punti sul perimetro esterno che vanno visitati necessariamente per raggiungere la soluzione. Questo processo, è importante nella scoperta e definizione di algoritmi.
"In questi enigmi dobbiamo trovare un percorso che visiti determinati vertici o punti sul confine di un grafico planare, di fatto un sottosistema del cammino hamiltoniano," ha detto Demaine. "L'algoritmo che utilizziamo per risolvere questo problema può essere utile anche in altri campi."
"Il sottoinsieme dei cammini hamiltoniani si inserisce nel campo degli algoritmi grafici (non nell'analisi degli enigmi), e quindi contribuisce ad arricchire quel campo. All'inizio pensavamo di dover solo risolvere un puzzle divertente, ma poi abbiamo incontrato un problema di grafico dall'interesse più vasto, e l'abbiamo risolto. Non si tratta di un risultato fine a se stesso però, perché l'algoritmo che abbiamo individuato può essere utile per la risoluzione anche di altri problemi."
"Il mio puzzle preferito di The Witness è l'enigma audio "sordo" nella camera anecoica" ha detto Bosboom. "È un enigma facile, serve solo a capire se il giocatore ha capito il rapporto che c'è tra due tipo di pannelli audio diversi, ma è il puzzle che mi ha fatto sentire più in linea con i designer. Se analizzo la mia carriera accademica devo dire che The Witness è una fonte molto ricca di problemi computazionalmente complessi, ed è pure capace di interessare il pubblico più ampio. È un ottimo gioco, sebbene non sia perfetto e non abbia nessun elemento mistico."
Secondo Demaine, la maggior parte dei giochi è interessante dal punto di vista della complessità computazionale. "Anche i giochi con pochi puzzle possono essere interessanti," ci ha detto. "Per esempio, due dei coautori della ricerca hanno lavorato a un altro documento sulla cooperazione in Team Fortress 2, Super Smash Bros. e Mario Kart. Sono giochi in cui il nostro approccio computazionale è molto, molto difficile."
"Individuare cosa rende divertente un gioco è difficile, ma penso che uno dei motivi che ci spingono a giocare sia proprio la sfida, e questa ricerca spiega cosa vuol dire per un gioco offrire una sfida. In qualche modo stiamo osservando un aspetto fondamentale del divertimento nei giochi." Stando a Demaine, ci sono ricercatori secondo cui studiare i giochi è attività puramente ricreativa, praticamente una perdita di tempo. "Io invece credo che l'intrattenimento interattivo sia un'importante campo di studio," ha detto. "Soprattutto perché incuriosisce gli studenti e rende le attività didattiche e di ricerca particolarmente divertenti da svolgere."