La prossima volta che qualcuno vi farà notare che giocate troppo a Candy Crush, potete rispondergli tranquillamente: “lo faccio per la scienza”. Per superare un quadro del videogioco sviluppato dalla King.com infatti, bisogna risolvere un rompicapo assimilabile ad una classe di problemi matematici definiti NP difficili, la cui soluzione ha delle implicazioni fondamentali nel campo dell’informatica teorica. Lo dimostra uno studio realizzato da Toby Walsh, ricercatore del dipartimento di Computer Science and Engineering della University of New South Wales, in preprint su ArXiv.
Nella sua analisi, Walsh ha studiato una versione ipotetica di Candy Crush Saga in cui il tabellone del gioco ha una grandezza indefinita, e ha preso in esame alcune specifiche sequenze di caramelle, equivalenti, almeno da un punto di vista matematico, a proposizioni logiche, cioè affermazioni a cui in logica può essere assegnato il valore vero o falso. Walsh ha dimostrato quindi che capire quali caramelle bisogna girare per ottenere un determinato punteggio a Candy Crush equivale a risolvere un problema di soddisfacibilità booleana, un problema matematico che consiste nel determinare quali proposizioni logiche devono essere vere o false perché risulti vera l’espressione da loro composta.
Poiché i problemi di soddisfacibilità booleana sono per definizione NP difficili, deve quindi esserlo anche Candy Crush Saga. Più precisamente, il videogioco appartiene a un sottoinsieme di questi problemi matematici definiti NP completi, che hanno la caratteristica di diventare sempre più complicati con l’aumentare delle variabili prese in esame. Si tratta di rompicapo che ci troviamo ad affrontare anche nella vita di tutti i giorni, per esempio quando dobbiamo pianificare la rotta migliore per compiere un determinato viaggio, e trovare un metodo teorico per risolverli può avere quindi anche importanti ripercussioni pratiche. Si tratta inoltre di uno dei campi di studio più importanti dell’informatica teorica, tanto che un problema del genere, il cosiddetto problema delle classi P e NP, è stato inserito tra i sette problemi del millennio, per la cui soluzione l’Istituto matematico Clay di Cambridge ha offerto in premio un milione di dollari.
Candy Crush Saga, con i suoi milioni di utenti, potrebbe aiutare i matematici in questa ricerca? Può darsi. “Sarebbe interessante scoprire se è possibile approfittare delle ore che gli essere umani dedicano a risolvere i problemi di Candy Crush”, scrive infatti Walsh nello studio. Quel che è certo è che la complessità di Candy Crush Saga non è un caso isolato nell’universo dei videogames. Con la stessa strategia di soluzione utilizzata da Walsh , era già stato dimostrato per esempio che anche alcuni titoli classici della Nintendo, come Super Mario e Zelda, sono assimilabili a problemi NP difficili.
Riferimenti: http://arxiv.org/abs/1403.1911
via Wired.it
