Candy Crush e il problema del millennio, P versus NP

E se Candy Crush non fosse semplicemente un gioco?

https://play.google.com/store/apps/details?id=com.king.candycrushsaga&hl=it
0

Candy Crush Saga è un gioco per smartphone e Facebook che nasce nel 2012 ad opera di King. Fin dall’inizio riscuote un grande successo e attualmente ha un totale di 70 milioni di “mi piace” su Facebook. Un numero enorme, come enormi sono le rendite di questo gioco. Secondo App Annie, un sito di ricerca a tema applicazioni, è il terzo gioco più redditizio negli U.S.A. Nonostante il download sia gratuito King trae i propri profitti dalla vendita di mosse extra, booster e lingotti, che i giocatori possono usare per passare di livello. Questo presuppone quindi la necessità di livelli difficili per garantire le entrate.

Ma difficili fino a che punto? Al punto di essere NP-difficili e di poter dare una risposta, almeno in parte, al problema di P versus NP.

Andiamo con ordine. La prima cosa è capire che cosa abbia reso Candy Crush Saga il colosso che è e quali siano le strategie adottate per fidelizzare i giocatori.La premessa principale è che ci siano livelli facili e livelli difficili. I livelli facili presuppongono che il giocatore possa risolverli in circa cinque tentativi: I livelli difficili richiedono al giocatore 30 o più tentativi.

Di conseguenza funziona più o meno così. Il giocatore completa senza troppi problemi diversi livelli facili. Tutto ciò è positivo perché lo spinge a continuare a giocare, ma, alla lunga, potrebbe annoiare. Dopo un certo numero di livelli facili viene quindi inserito un livello difficile. Difficile ma non impossibile, altrimenti molti rinuncerebbero. Il livello difficile non viene mai, o quasi, risolto al primo tentativo. In media ne richiede 30 o più.

Il giocatore ha usato molto tempo e molte energie per passare i livelli facili. La voglia di non sprecare il tempo precedentemente usato lo spinge a continuare. Prova e riprova il livello successivo. Anche questo potrebbe diventare noioso se non fosse che nel momento in cui non si riesce a superare un livello difficile scatta un altro meccanismo. Il giocatore spera che il livello seguente sia più facile. Pur di arrivarci e verificare le proprie speranze, è invogliato a comprare booster e mosse extra.

Fin qui nulla di speciale, o meglio, una strategia molto ben studiata, ma non nuova. La vera novità è che due studenti di Informatica Teorica, Emanuele Natale e Stefano Leucci, in un articolo, nato quasi per gioco, hanno dimostrato che Candy Crush è un problema computazionalmente difficile (NP – hard). Non si tratta quindi solo di difficile nell’accezione comune, si tratta di difficile anche in un altro senso.

I due studenti hanno costruito dei livelli di Candy Crush (giocabili!) e hanno dimostrato che “se fosse possibile trovare un modo di completarli velocemente, ciò significherebbe che P è uguale a NP.”http://www.lanostra-matematica.org/2014/06/un-articolo-da-nerd-candy-crush-e-un.html

Ciò significa che il gioco è NP-completo, ovvero la categoria più difficile di problemi di NP. Non solo, è la classe di problemi a cui tutti i problemi NP possono essere ricondotti. In poche parole significa che se esiste un algoritmo in grado di risolvere velocemente un problema NP completo, allora tutti i problemi NP potrebbero essere risolti velocemente. Può sembrare un esperimento banale, ma non lo è per nulla. P versus NP è uno dei sette grandi problemi matematici irrisolti, i cosiddetti Millennium Problems. È un problema che riguarda la complessità computazionale, ovvero le risorse minime necessarie per la risoluzione di un problema.

Semplificando, di molto, la questione si risolve in: ogni problema del quale il computer può verificare (NP) la correttezza in un tempo accettabile è anche un problema che può essere risolto (P) dal computer in un tempo accettabile? Se la risposta alla domanda è no, allora esistono problemi per i quali è più complesso calcolare una soluzione piuttosto che verificarla. Dunque P non è uguale a NP.

Per ora nessuno è riuscito a dare una risposta a questa domanda. L’esperimento dei due studenti, per ora, non è una risposta univoca alla domanda, ma solo una svolta in senso positivo.

Ma noi, giocatori accaniti di Candy Crush Saga ci rallegriamo, perché a chi dice che è solo un gioco, ora sappiamo cosa rispondere.

Link all’articolo completo sulla ricerca: https://arxiv.org/abs/1403.5830

Leave A Reply

Your email address will not be published.

Cliccando su Accetta, acconsenti all'utilizzo dei cookie e di eventuali dati sensibili da parte nostra; secondo le normative vigenti GDPR. More Info

Questo sito utilizza i cookie per fornire la migliore esperienza di navigazione possibile. Continuando a utilizzare questo sito senza modificare le impostazioni dei cookie o cliccando su "Accetta" permetti il loro utilizzo.

Chiudi