I rompicapi di Alice: Un complicato problema di fusione

Uno dei miei giochi per smartphone preferiti è Triple Town. E' classificato come match-three game, evoluzione dei tile-matching game. Il gameplay di base di questo genere di giochi è abbastanza semplice: si prendono tre o più oggetti simili, li si avvicinano e possono succedere due cose differenti, o scompaiono o vengono sostituiti, come nel caso di Triple Town, da una loro versione evoluta.

Un po' di storia

I tile-matching game iniziano la loro storia nel mondo videoludico a partire dal famoso Tetris e simili, dove si devono incastrare una dentro l'altra delle forme geometriche. Quando una riga nella plancia di gioco, di base una griglia rettangolare $n \times m$, è occupata completamente da celle piene, questa riga scompare, liberando spazio per riempire una nuova riga.
Il primo dei match-three game propriamente detti è Shakiri, sviluppato nel 1994 su MS-DOS dal programmatore russo Eugene Alemzhin⁽¹⁾. L'obiettivo del gioco è accostare tre o più palle dello stesso colore lungo una linea, orizzontale o verticale. Per ottenere tale obiettivo, bisogna spostare una palla da una posizione a una adiacente. Nel caso in cui si ottiene una serie di tre o più palline simili, queste scompaiono mentre il punteggio del giocatore aumenta, altrimenti le palline spostate ritornano nelle posizioni originali. Quando le palline vengono rimosse, il loro posto viene preso da un numero uguale di palline, ma con colori casuali. Il gioco si conclude quando non è più possibile compiere mosse sulla griglia.
Il primo è più famoso clone⁽²⁾ di Shakiri è Bejeweled della PopCap Games, rilasciato nel 2001, dove alle palline vengono sostituite delle gemme colorate. La fama del gioco è stata successivamente superata da Candy Crush Saga, sviluppato dalla King per Facebook e rilasciato nell'aprile del 2012.
Limitandosi al gioco delle gemme è possibile tracciare una sorta di albero genealiìogico del gioco⁽³⁾:

Riformulando in maniera matematica il gameplay di Bejeweled, ad esempio ponendo un numero limitato di gemme denominandole con le lettere dell'alfabeto dalla A alla F, è possibile dimostrare che particamente tutti i match-three game sono NP-hard (ne avevo scritto brevemente alcuni anni fa su Doc Madhattan). Andiamo con ordine.
Con NP si indica una classe di problemi decisionali (situazioni in cui è necessario prendere una decisione) che sono risolvibili da una macchina di Turing in un tempo polinomiale. Nel contesto della computazione, per tempo polinomiale si intende un intervallo di tempo limitato superiormente da un'espressione del tipo $n^k$, con $k$ costante, ovvero da un polinomio. Un problema è detto NP-hard se il suo livello di difficoltà è almeno pari a un problema NP, anche se potrebbe essere ben più difficile.
Per studiare Bejeweled e cloni nell'ottica di questo genere di problemi, il gioco viene ridotto alle seguenti domande⁽³⁾:

1. Esiste una sequenza di mosse che consente al giocatore di far esplodere una gemma specifica?
2. Il giocatore è in grado di ottenere un punteggio minimo pari a $x$?
3. Il giocatore è in grado di ottenere un punteggio minimo pari a $x$ in meno di $k$ mosse?
4. Il giocatore è in grado di far esplodere almeno $x$ gemme?
5. Il giocatore è in grado di giocare per almeno $x$ turni?

Ognuna di queste domande è un problema NP-completo⁽³⁾, ovvero la classe di problemi NP più difficili, che potremmo considerare come i problemi NP-hard più semplici.
La complessità del semplice gameplay di Bejeweled viene, però, elevata dai moderni match-three game di cui Triple Town è il precursore più noto.

Evoluzione

La plancia di gioco di partenza di Triple Town è una griglia 6$times$6 non completamente vuota⁽⁴⁾. Una delle celle è dedicata per mantenere uno dei pezzi che il gioco ci invia casualmente a disposizione, come nel Tetris, e che poi dovremo mettere sul terreno. I pezzi, quando vengono messi uno accanto all'altro, quando sono uguali o superiori a 3, si fondono per formare un oggetto di un livello superiore: ad esempio tre cespugli permettono di creare un albero. In questo modo si prosegue fino a ottenere un castello volante, il livello massimo raggiungibile. Ovviamente l'obiettivo è sfruttare al meglio lo spazio per ottenere più castelli volanti possibile e dunque il punteggio maggiore. Questo gameplay unisce quello tipico dei match-three game con quelli della serie di Grow, dove bisogna combinare gli oggetti uno con l'altro per sviluppare un mondo e ottenere un macchinario finale funzionante: in pratica vengono inseriti elementi presi dall'evoluzione.
I programmatori hanno anche inserito una serie di imprevisti, che sono degli orsi che disturbano la strategia del giocatore, che da un certo punto in poi deve in qualche modo adattare nel tentativo di raggiungere in ogni caso l'obiettivo che si è prefisso. Come facilmente immaginabile, la combinazione tra la necessità di evolvere gli oggetti sulla plancia, le ridotte dimensioni della griglia e gli imprevisti presenti rende il gioco più elaborato e complesso, e dunque ancora più hard della versione originale di Shakiri.
Sullo stesso genere, al momento, sto provando Merge Dragon, dove le griglie di gioco hanno forme leggermente differenti rispetto a quella standard di una griglia rettangolare, mentre ai vari livelli proposti viene anche accostato un "accampamento": l'obiettivo del gioco è dunque concludere i vari livelli, che peraltro vengono periodicamente aggiunti, e sviluppare l'accampamento raccogliendo oggetti nei livelli, durante gli eventi speciali o nell'accampamento stesso grazie allo sviluppo delle risorse utilizzate dal giocatore. Inoltre, come intuibile dal titolo, parte della strategia va dedicata allo sviluppo di una popolazione di draghi, che viene utilizzata dal giocatore per mantenere attivo e in buona salute l'accampamento stesso.
Anche in questo caso le strategie possibili vengono moltiplicate dalla combinazione in modi leggermente differenti dei due principali gameplay descritti brevemente: quello di Shakiri e quello di Grow. Ottenendo, così, dei passatempi molto più intelligenti e stimolanti di quel che si potrebbe pensare in prima battuta.

---

1. Una possibile storia di dei tile-matching game, e in particolare dei match-three game, viene raccontata nell'articolo
   Juul, J. (2007). Swap adjacent gems to make sets of three: A history of matching tile games. Artifact, 1(4), 205-216. (pdf)
   Potete leggerlo direttamente sul sito dell'autore. ↩
2. In questa categoria ho trovato un brevetto su Google patents che descrive in maniera abbastanza dettagliata i match-three game. ↩

3. Guala, L., Leucci, S., & Natale, E. (2014, August). Bejeweled, Candy Crush and other match-three games are (NP-) hard. In 2014 IEEE Conference on Computational Intelligence and Games (pp. 1-8). IEEE. (arXiv)
   Il lavoro dei ricercatori relativo a Bejeweled ha anche prodotto una applicazione web che può essere sperimentata su Complexity of games ↩↩↩

4. Alcuni link di approfondimento su questo specifico gioco: Triple Town tactics; intervista a Daniel Cook, uno dei creatori del gioco; Optimal Triple Town algorithm ↩