L'informatico che trova lezioni di vita nei giochi

Nel Shan-Hua Teng, l'informatica teorica non è mai stata puramente teorica. Ora 58enne, Teng è professore di informatica presso la University of Southern California e due volte vincitore del Premio Gödel, un premio annuale che riconosce il lavoro teorico rivoluzionario. Ma spesso si sforza di collegare quella teoria astratta alla vita di tutti i giorni in modi sia pratici che giocosi.

Nato a Pechino alla vigilia della Rivoluzione culturale cinese, Teng è venuto negli Stati Uniti per studiare architettura dei computer, ma presto ha cambiato direzione per concentrarsi su una teoria matematica più astratta. Ha conseguito il dottorato alla Carnegie Mellon University nel 1991 per aver dimostrato un teorema sul modo migliore per partizionare i grafi: ragnatele di punti, o nodi, collegati da linee o bordi.

Sebbene teorico, il lavoro aveva applicazioni pratiche e spesso, scoprì, le applicazioni pratiche portavano a nuove intuizioni teoriche. Durante una borsa di studio estiva della NASA nel 1993, Teng si unì a un team che simulava la dinamica dei fluidi utilizzando metodi di "elementi finiti", che modellano strutture complesse come assemblaggi di molti piccoli pezzi. Questi assemblaggi possono essere trattati come grafici e il compito di Teng era quello di adattare il metodo di partizionamento della sua ricerca universitaria a questa nuova impostazione. Ma è diventato curioso della tecnica di partizionamento che il team della NASA aveva utilizzato in precedenza e ha iniziato a indagare sulla sua struttura matematica sottostante insieme al collega scienziato informatico Daniele Spielman, ora professore di informatica alla Yale University. Quel progetto di ricerca congiunto ha dato il via a una collaborazione decennale che ha vinto i due Premi Gödel.

Non è stata l'unica volta in cui ha visto un legame profondo tra teoria e pratica. "Ogni volta, queste cose apparentemente totalmente pratiche avevano dietro di sé questa meravigliosa matematica", ha detto Teng.

Più di recente, Teng ha rivolto la sua attenzione alla meravigliosa matematica dietro giochi come tris, scacchi e Go. In questi giochi “combinatori” non c'è alcun elemento di casualità, ed entrambi i giocatori sanno sempre tutto sullo stato del tabellone. Eppure i giochi combinatori rimangono impegnativi perché il numero di modi in cui un gioco può svolgersi potrebbe essere vertiginosamente grande.

I ricercatori di teoria dei giochi amano generalizzare tali giochi a tabelloni sempre più grandi, aumentando il tris da quadrati 3 per 3 a n-By-n, ad esempio - e quantificare la difficoltà di determinare quale giocatore vincerà dato uno stato iniziale del tabellone. Le diverse risposte possibili ordinano i giochi nello stesso "classi di complessità” che affiorano in tutta l'informatica teorica.

Una famosa classe di complessità va sotto il nome prosaico P, per "tempo polinomiale", e contiene il tipo di problemi che possono essere risolti in un ragionevole lasso di tempo, grosso modo. I problemi nell'altrettanto famosa classe NP possono richiedere una quantità di tempo irragionevole per essere risolti, ma le loro soluzioni sono facili da verificare. Per i problemi in un'altra classe di complessità, denominata PSPACE, anche una verifica così efficiente non è garantita. Quando i ricercatori considerano la "logica profonda" dei giochi a due giocatori - "se fai X, e poi se io faccio Y, e poi se fai Z" e così via - spesso si ritrovano a parlare di PSPACE. Ma come Teng ha contribuito a dimostrare, la matematica dei giochi combinatori non è sempre semplice.

Quanta ha parlato con Teng di recente per discutere del suo percorso verso l'informatica, la matematica alla base dei giochi da tavolo e l'influenza di suo padre. L'intervista è stata condensata e modificata per chiarezza.

Com'è stato ricevere un'istruzione in Cina?

Sono nato poco prima della Rivoluzione Culturale e mio padre era professore universitario di ingegneria civile. Quando è avvenuta la rivoluzione, era in cattività nel campus. Quindi l'intero campus è stato mandato in profondità nella campagna.

Raccoglievo spazzatura da vendere fino a quando non stavo praticamente finendo le medie, e poi improvvisamente la Cina è cambiata. Se studiavi potevi entrare all'università e non avevamo altra prospettiva di avere un lavoro regolare. Mi sono svegliato e ho detto: "Ho bisogno di studiare".

Come hai scelto l'informatica?

Volevo studiare biologia dopo il liceo. Non so perché, ma mio padre non ne era molto contento. Stavo andando bene in matematica e mi ha chiesto se volevo fare matematica. Ho detto no. [Ride.] E poi ha detto: "Sai, c'è una nuova disciplina chiamata informatica, ed è davvero buona". In qualche modo, mi ha spinto a specializzarmi in informatica.

L'istruzione a quel tempo era molto semplice. Non eravamo esposti alla maggior parte delle cose e l'informatica non era nemmeno un dipartimento; era una specializzazione in ingegneria elettrica. Ma per una fortuna del tutto casuale siamo stati addestrati come studenti di matematica in matematica, e ho imparato alcune cose che alla fine sono state utili per diventare un teorico. Senza quello probabilmente non avrei avuto nessuna possibilità di passare. In questi giorni i ragazzi hanno molto più talento: dal liceo in poi sono matematici più dotati di me quando sono arrivato in questo paese.

In che modo queste lacune nelle tue conoscenze hanno influenzato la tua esperienza alla scuola di specializzazione?

Un giorno [il mio consulente, Gary Miller,] scoprì che non avevo mai sentito parlare di NP. Era in una discussione. Ha detto: "Questo problema sembra NP-difficile". Ho detto: "Uh-huh". Disse: "Non mi credi?" E poi ha iniziato a dimostrarlo, ea metà si è girato bruscamente verso di me, perché ero solo seduto lì, e ha detto: "Sai cos'è NP-hard?" Ho detto no.

Pensavo fosse il mio ultimo giorno di lavoro con lui, ma ha continuato e mi ha detto la definizione. Disse: "Se non sai, non importa, purché tu sia in grado di pensare". Ha avuto un enorme impatto su di me.

Sei principalmente un teorico, ma nel corso della tua carriera hai fatto incursioni nell'industria. In che modo questo lavoro pratico si collegava alla tua ricerca teorica?

Nella mia tesi ho sviluppato alcuni metodi geometrici per partizionare grafi. Sono stato in grado di dimostrare che questa famiglia di metodi geometrici ha fornito tagli dimostrabilmente buoni per i grafici ad elementi finiti.

Su raccomandazione del mio mentore, ho iniziato a tenere discorsi alla NASA e alla Boeing Aerospace. In Boeing, ricordo che il modello 3D di una delle ali aveva già quasi un milione di elementi: non potevano nemmeno caricarlo in una macchina. Quindi volevano tagliare questo grafico in diversi componenti, metterli su macchine diverse con carichi computazionali simili e ridurre al minimo la comunicazione. Ecco perché matematicamente la formula è un taglio grafico.

Nell'informatica teorica, spesso i principi matematici sottostanti rimangono invariati anche quando l'aspetto del problema cambia drasticamente, dall'ottimizzazione alla teoria dei giochi. Quando fai la ricerca, non sembra un cambiamento drastico.

A proposito di teoria dei giochi, ho visto che hai aiutato a progettare un gioco da tavolo. Come è successo?

Oh, adoro i giochi da tavolo! Ci sono bellissime connessioni con la teoria della complessità. Ma soprattutto sono lo studente dei miei studenti.

Stavo tenendo una conferenza alla Boston University su un bellissimo teorema discreto chiamato lemma di Sperner. È molto semplice in una dimensione. Hai un segmento di linea in cui un'estremità è rossa e un'estremità è blu. Lo dividi in sottosegmenti [con nodi ad entrambe le estremità] e colori ogni nuovo nodo in rosso o in blu. Quindi [non importa come li colori] sappiamo che deve esserci un segmento che ha entrambi i colori.

In due dimensioni, è molto affascinante. Hai un triangolo e ora hai tre colori: un angolo è rosso, uno è blu e uno è verde. Dividi questo triangolo in triangoli più piccoli, quindi i bordi sono spezzati in segmenti. Ogni bordo esterno segue la regola unidimensionale: i nodi possono utilizzare solo i colori delle due estremità. All'interno del triangolo, puoi fare tutti e tre i colori come preferisci. Il lemma di Sperner dice che in qualsiasi modo lo dividi, se fai questa colorazione, deve esserci un triangolo che ha tutti e tre i colori.

Kyle Burke era un mio studente, all'epoca lavorava all'analisi numerica. È venuto nel mio ufficio e ha detto che potrebbe esserci un bellissimo gioco da tavolo del lemma di Sperner: due giocatori colorano iterativamente un tabellone e chiunque induca un triangolo di tre colori perderà la partita. I migliori giochi da tavolo hanno vincitori piuttosto che un pareggio, e qui, chiaramente qualcuno vincerà. Come mai? Perché il lemma di Sperner!

Ho chiamato il mio amico David Eppstein di Irvine per parlare di ciò che rende un buon gioco da tavolo. Ha detto: "Un buon gioco ha regole semplici e un bellissimo tabellone, e deve essere difficile per PSPACE". Perché se riesci a risolverlo in tempo polinomiale, un computer ti batterebbe sempre.

Quindi abbiamo esaminato questi criteri. Kyle ha detto: "Questo gioco è semplice?" Ho detto: "Sì, è una frase!" Ha detto: "Questo gioco è colorato?" Ho detto: "In base alla progettazione!" Poi ha detto: "Se dimostro che è difficile per PSPACE, posso ottenere un dottorato di ricerca?" Ho detto di sì, e lui l'ha fatto. Ci sono molte diverse sfaccettature del suo teorema. Rivela alcune cose sui punti fissi, che sono un concetto molto bello in matematica.

Posso giocare ovunque?

È disponibile, con alcune modifiche, online.

A quali giochi ti piace giocare?

Sono un teorico dei giochi. [Ride.] Gioco un po' con mia figlia, ma non sono cresciuto interpretandole. A differenza dei miei studenti, che hanno giocato per tutta la vita.

Quale altro lavoro hai svolto sulla matematica dei giochi da tavolo?

Noi avevamo un carta di recente su una domanda aperta: se metti insieme due giochi risolvibili in tempo polinomiale, uno accanto all'altro, ciò li renderebbe difficili per PSPACE? Ad ogni mossa puoi giocarne solo uno. Questo si chiama sommatoria dei giochi.

Cosa significa mettere insieme due giochi?

Nell'antico gioco Go, quando metti giù abbastanza pietre, ottieni molte arene separate, quindi in un certo senso stai giocando una somma di partite. Devi preoccuparti di questo e quell'angolo. Vuoi vincere tutto, ma questo non significa che devi vincere ogni parte.

È filosoficamente interessante, vero? È come se avessi una guerra, e ha molte battaglie, ma la tua attenzione è limitata. In qualsiasi momento puoi prendere una sola decisione su uno dei campi di battaglia e il tuo avversario può rispondere o raddoppiare in qualche altro campo di battaglia. Stavo cercando di spiegarlo a mio padre. Quando giochi una somma di partite, significa davvero: come perdi strategicamente?

L'abbiamo dimostrato per due giochi, ma puoi mettere insieme tre giochi e il teorema è ancora vero: tre giochi polinomiali messi insieme possono diventare difficili per PSPACE.

Dato che ti ha spinto verso l'informatica, come ha risposto tuo padre al diverso lavoro che hai svolto negli anni?

Spesso mi chiedeva: "Perché lo fai?" Lavorando in teoria, spesso non hai risultati per anni, e lui lo ha capito gradualmente. All'inizio potrei parlare del metodo degli elementi finiti: lo insegnano anche nell'ingegneria civile. Ma non riuscivo a capire come parlare di questa matematica ricreativa.

Poi ho pensato a un idioma derivato da questo famoso romanzo cinese chiamato Il romanzo dei tre regni. Uno dei personaggi, Zhuge Liang, era quasi uno stratega perfetto, e l'idioma dice: "Tre riparatori di scarpe sono meglio di Zhuge Liang". È usato in questo modo spensierato per dire che tre persone normali possono essere perfette quando mettono insieme le loro teste. Ma quando guardi alla storia di questo idioma, le cose venivano pronunciate in modo diverso nelle diverse regioni, e "calzolaio" aveva lo stesso suono di "campo generale". Quindi dice: "Tre generali sul campo insieme sono meglio di questo perfetto stratega".

Ho detto a mio padre che è esattamente il teorema che abbiamo dimostrato con la somma dei giochi. I generali di campo rappresentano [algoritmi per la risoluzione] di giochi a tempo polinomiale: su ogni campo di battaglia, sanno come vincere. Ma la parte difficile è sapere quando perdere, non come vincere ciascuno dei giochi componenti. Se qualcuno può giocare a quel gioco difficile, è davvero il miglior stratega. I generali sul campo non prendono queste decisioni logiche profonde, ma in qualche modo se le metti bene insieme, non sono peggio di questo perfetto stratega.

Ho detto a mio padre: "Finalmente ho capito questo teorema di matematica che è equivalente a uno dei nostri famosi modi di dire!" Aveva 94 anni a quel tempo, molto acuto, e disse: "È un buon tentativo". Non l'ho convinto del tutto. Quella è stata la mia ultima conversazione tecnica con lui; pochi mesi dopo morì. Ogni volta che penso a spiegare il mio lavoro, questo è il mio punto forte.