Un Articolo Da Nerd: Candy Crush È Un Problema "NP- Hard"

Emanuele Natale e Stefano Leucci sono due studenti di dottorato (in Informatica Teorica) che di recente, assieme al ricercatore Luciano Gualà, hanno dimostrato che giocare al famoso gioco Candy Crush è un problema computazionalmente difficile (“NP-hard”; è disponibile il preprint su ArXiv).

La prova consiste nel mostrare come trasformare una formula booleana in un livello del gioco in modo che completare il livello equivalga a trovare un assegnamento di verità delle variabili che soddisfa la formula di partenza.

A un certo punto i nostri hanno pensato che sarebbe stato originale e divertente rendere giocabile tale “dimostrazione”, ed hanno creato il sito: http://candycrush.isnphard.com.


Ci raccontano di seguito la loro esperienza...in un articolo da nerd!

*****

Un articolo nato per gioco

Qualche tempo fa ci imbattemmo in un lavoro di Erik Demaine, professore al MIT, e di Giovanni Viglietta, giovane ricercatore italiano. Assieme ad altri ricercatori, Demaine e Viglietta avevano dimostrato che molti videogiochi classici del Nintendo sono intrinsecamente difficili. Con “intrinsecamente difficili” non s’intende una particolare opinione che uno può condividere o meno: parliamo dell’NP-completezza, una proprietà rigorosamente matematica che discuteremo meglio tra poco, ma diciamo subito che l’NP-completezza è un’idea davvero fondamentale in Informatica; per capirci, se qualcuno vi viene a dire che conosce le basi teoriche di quest’ultima, allora o sa cos’è l’NP-completezza o vi ha mentito. 

Demaine e Viglietta avevano dunque preso il concetto di NP-completezza e l’avevano accostato all’incarnazione informatica del divertimento: i video game. Da appassionati di videogiochi, l’articolo ci aveva lasciato una sensazione di stupore talmente piacevole che a distanza di tempo non riuscivamo a non tornarci su. E se avessimo fatto anche noi qualcosa di simile? L’idea ci allettava parecchio. Ma che gioco scegliere? Quale era il gioco più popolare del momento? Quale gioco portava le persone in metro a non staccare il naso dai loro smartphone? Ovvio: Candy Crush!

Cominciammo a lavorarci su.  Fu divertente, ma non fu facile. Però la spuntammo noi e, dopo un paio di mesi, avevamo la dimostrazione. Stavamo scrivendo l’articolo quando ci accorgemmo che, improvvisamente, era apparso un lavoro che sembrava dimostrare proprio il nostro risultato!
Ci affrettammo a leggerlo e tirammo un sospiro di sollievo: il gioco studiato era inspirato a Candy Crush, ma utilizzava delle regole differenti. Avevamo, inoltre, seguito un approccio più generale che rendeva la nostra prova valida  per molti altri giochi dello stesso tipo, come Bejeweled e Shariki, che può essere considerato uno dei precursori di questo genere di giochi.
Una settimana dopo, anche il nostro articolo era online: Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard.

Il problema più importante dell'informatica teorica

Per parlare del contenuto dell'articolo abbiamo prima bisogno di raccontarvi qualcosa sul problema più importante dell'informatica teorica: il problema P versus NP.
Quando erano ragazzini, alcuni di noi pensavano che ci sarebbe stato un giorno in cui i computer, se ben programmati, avrebbero potuto, in un battito di ciglia, dare la giusta risposta ad ogni problema. All'università poi scoprirono che, non solo Alan Turing aveva dimostrato che ci sono problemi non risolvibili attraverso un computer (questo prima che il primo calcolatore fosse realizzato), ma che un problema, se non lo risolvi con un algoritmo veloce, è come se non l'avessi risolto per niente. Non che il computer non sia così veloce come sembra: la tecnologia non c'entra, è una questione di algoritmi. Se un algoritmo è lento, anche se fatto girare su un computer potentissimo, potrebbe richiedere milioni di anni per fornire una risposta anche a casi relativamente piccoli di un dato problema.
Si tratta quindi di un algoritmo corretto, ma inutile. Si potrebbe dire che l'inefficienza di un algoritmo nega l'esistenza dello stesso. 
Il fatto è che, per molti problemi interessanti, si vuole trovare una specifica soluzione in un insieme enorme di possibilità che, se dovessero essere esplorate tutte, richiederebbero un'infinità di tempo. 

Ma quali problemi ammettono un algoritmo veloce? Questa è proprio la definizione della classe P, ovvero dell’insieme di problemi che ammettono un algoritmo efficiente che li risolve. Dentro la classe P ci sono molti problemi interessanti come, per esempio, il calcolo di un percorso di lunghezza minima per andare da una città ad un'altra. NP, invece, è la classe (l’insieme) dei problemi per i quali è possibile verificare velocemente una soluzione; vale a dire, non so se so trovare velocemente una soluzione, ma, se me ne viene data una, so capire velocemente se si tratta effettivamente di una soluzione corretta. Chiaramente la classe NP contiene tutti i problemi in P: saper trovare velocemente una soluzione richiede anche di saperla riconoscere velocemente, una volta trovata. La domanda a cui nessuno ancora ha saputo dare risposta è “P è uguale a NP”? 

Benché nessuno ad oggi abbia saputo dimostrarlo - e per inciso una tale dimostrazione varrebbe un milione di dollari, visto che questo è uno dei sette problemi del millennio per cui la Fondazione Clay ha messo in palio dei premi in denaro -, ci sono molti argomenti a favore del fatto che la precedente domanda abbia risposta negativa, primo fra tutti la seguente considerazione.

Dentro la classe NP è possibile individuare una sottoclasse di problemi, detti NP-completi, che sono i problemi più difficili in NP. Intuitivamente, un problema NP-completo è un problema a cui tutti gli altri problemi di NP possono essere ridotti, nel senso che un algoritmo veloce per un tale problema si tramuterebbe in un algoritmo veloce per tutti i problemi in NP. Ad oggi i problemi che si conoscono essere NP-completi sono decine di migliaia, e sfortunatamente molti sono problemi pratici davvero importanti (come programmare le partenze e gli arrivi dei treni in modo efficace, scovare somiglianze fra sequenze di DNA, o stabilire come posizionare in modo compatto i componenti elettronici su un circuito stampato). Chiaramente per nessuno di questi problemi si conosce un metodo risolutivo veloce. Dimostrare che tale metodo non può esistere o che ne esiste uno per uno qualsiasi di questi problemi vuol dire risolvere in senso negativo o positivo la questione P versus NP.

Il nostro articolo 

I contributi del nostro articolo sono due. 
Il primo è di natura puramente teorica. Detto in modo pittoresco, dimostriamo che è possibile esprimere il problema aperto più importante dell'Informatica Teorica attraverso Candy Crush. In particolare costruiamo dei livelli di Candy Crush e mostriamo che, se fosse possibile trovare un modo di completarli velocemente, ciò significherebbe che P è uguale a NP.
Dimostriamo, cioè, che il gioco Candy Crush è NP-completo. Questo risultato evidenzia una qualità  importante del gioco, lo caratterizza infatti dal punto di vista computazionale, inserendolo nella classe dei giochi e problemi per i quali è difficile trovare una strategia risolutiva efficiente.
Come abbiamo già detto, il  nostro non è certo il primo risultato di questo tipo. Sembra infatti che la maggior parte dei giochi e puzzle di successo siano NP-completi e non è azzardato supporre che, almeno in parte, sia proprio questa caratteristica computazionale a rendere questi giochi così impegnativi e in qualche modo divertenti. Del resto, per questi giochi è necessaria una buona dose di creatività e di intuizione, che è proprio il nucleo centrale sul quale si fonda la questione P versus NP.

Il secondo contributo, invece, è di natura più pratica. Forniamo una versione giocabile della dimostrazione. Da quel che sappiamo, il nostro è il primo caso di dimostrazione giocabile. 
La dimostrazione di NP-completezza di Candy Crush ha la seguente forma: dato un certo problema NP-completo (che quindi già si conoscere essere difficile), si costruisce un livello di Candy Crush che, se risolto, fornisce una soluzione al problema di partenza. 
Il problema di partenza che abbiamo utilizzato nella dimostrazione è noto con il nome 1 in 3 positive Sat: dato un insieme di variabili booleane (cioè variabili che possono valere solo vero o falso) e dei gruppi di 3 (o meno) variabili (detti clausole) si vuole assegnare un valore ad ogni variabile in modo tale che ogni gruppo abbia esattamente una sola variabile a vero.

Abbiamo quindi creato un sito web che, prese variabili e clausole, costruisce il corrispondente livello (giocabile!) di Candy Crush.
Questa cosa, oltre ad essere una trovata a nostro avviso squisitamente nerd, ha in realtà ragioni più profonde. La versione giocabile del livello di Candy Crush permette di capire e verificare la dimostrazione fornita nell'articolo. Inoltre, c'è una cosa più importante. Poiché come abbiamo accennato i problemi NP-completi sono tutti riducibili l'uno all'altro (si potrebbe dire che sono modi diversi per esprimere un unico problema), è possibile - almeno in linea teorica - prendere problemi reali, generare i corrispondenti livelli di Candy Crush e farli giocare a un certo numero di giocatori nella speranza che qualcuno li risolva, fornendo anche una soluzione al problema originale di partenza. 

Questo, al momento, ci sembra la tematica aperta più intrigante sollevata dall'articolo. È possibile trasformare problemi importanti in videogiochi divertenti? È la tematica dello human computing, che recentemente è stata applicata con successo nel campo del protein folding. Come abbiamo accennato, la difficoltà nel risolvere un problema NP-completo risiede nel trovare una specifica soluzione in un insieme enorme di possibilità. È come con un esercizio o un teorema da dimostrare. Una volta vista la soluzione all'esercizio o la dimostrazione del teorema è facile convincersi della correttezza. Ma inventare la soluzione o la dimostrazione è tutt'altra cosa. E certi giocatori sono come matematici intuitivi: sanno vedere soluzioni dove altri non riescono. Chissà, magari un giorno sapremo come usare questa creatività per risolvere problemi computazionali difficili, e riusciremo a migliorare il trasporto pubblico, a capire a fondo il nostro patrimonio genetico o dimostrare teoremi giocando a Candy Crush.

lucianoguala.isnphard.com

stefanoleucci.isnphard.com

emanuelenatale.isnphard.com

__________________________________

Riferimenti bibliografici

►Aloupis, Greg, Erik D. Demaine, and Alan Guo. "Classic Nintendo games are (NP-) hard." arXiv preprint arXiv:1203.1895 (2012).

►Walsh, Toby. "Candy Crush is NP-hard." arXiv preprint arXiv:1403.1911 (2014).

►Gualà, Luciano, Stefano Leucci, and Emanuele Natale. "Bejeweled, Candy Crush and other Match-Three Games are (NP-) Hard." To appear in 2014 IEEE Conference on Computational Intelligence and Games (CIG 2014)  (2014).

►Khatib, Firas, et al. "Algorithm discovery by protein folding game players." 
Proceedings of the National Academy of Sciences 108.47 (2011): 18949-18953.