Due giochi di fusione, una domanda: si può giocare l'uno o l'altro senza errori? La risposta passa per l'angolo di una griglia, un avversario che non arriva mai e un numero alto diciassette esponenti.
Scritto e redatto in inglese. Questa versione italiana è stata prodotta con traduzione automatica; dove conta la precisione, fa fede l'originale inglese. Leggi l'originale in inglese →
Cominciamo dal gioco che tutti conoscono. 2048, quattro direzioni, una griglia 4×4, tessere che raddoppiano quando si toccano, è, a rigore, irrisolto. Nessuno ha scritto un algoritmo che lo giochi alla perfezione. Quello che abbiamo sono approssimazioni molto forti. Una ricerca expectimax, che guarda avanti di circa otto mosse e valuta ogni griglia con una manciata di euristiche calibrate a mano (celle libere, tessere grandi fissate a un bordo, regolarità), raggiunge la tessera 32768 in più di un terzo delle partite, 1 e il più forte motore pubblico tocca la tessera 65536 in una piccola percentuale dei casi. 2 Generalizzato a una griglia m×n, anche solo decidere se una tessera obiettivo sia raggiungibile è NP-difficile. 3 Forte non è la stessa cosa di risolto.
Quanto in alto può salire una singola tessera? Su sedici celle la risposta è un piccolo, elegante esercizio di conteggio. Disponi la griglia come una scala discendente, 65536, 32768, 16384, giù fino a un 2 solitario. Ogni tessera è esattamente una potenza di due sotto la sua vicina, così le sedici potenze distinte da 21 a 216 riempiono perfettamente la griglia, e 65536 = 216 siede in cima: un esponente per cella. Questo è il tetto se il gioco ti dà sempre e solo dei 2. Ma 2048 genera un 4 una volta su dieci, e un solo 4 arrivato al momento giusto introduce di contrabbando un diciassettesimo esponente, portando il vero massimo a 131072 = 217, diciassette tessere di potenze stipate in sedici caselle. 4 Nessun essere umano l'ha costruita; qualche IA l'ha sfiorata.
Perché queste griglie premiano chi infila la tessera più grande in un angolo? Una tessera al centro può essere spinta in quattro direzioni, e continua a essere separata dalle tessere con cui vorrebbe unirsi. Una tessera d'angolo tocca due pareti; le spinte verso le pareti a cui è già addossata non possono spostarla, e finché eviti di spingere nella direzione opposta resta ferma mentre tutto il resto si organizza attorno a lei. Concatena le altre in un serpente monotono, la più alta nell'angolo, ripiegato avanti e indietro in ordine decrescente, e un solo gesto può innescare una cascata di fusioni. 1 È l'euristica che domina il gioco umano occasionale, ed è quasi esattamente ciò che le IA riscoprono quando le lasci calibrare da sole i propri pesi.
Un gioco di fusione con generazioni casuali non ha un avversario, solo il meteo. «Risolverlo» significa battere i dadi in media, non battere una mente.
Ora inclina la griglia nella terza dimensione. 3927 è il cugino cubico di 2048: un reticolo 3×3×3 di 27 celle, sei direzioni di spinta invece di quattro, e tessere che si fondono a tre a tre, da 3 a 9 a 27 a 81, in base tre dove 2048 è in base due. 5 L'accumulo nell'angolo sopravvive alla dimensione in più? Un cubo ha otto angoli, e una cella d'angolo ora tocca tre facce anziché due: dovrebbe essere ancora più stabile, bloccata da tre pareti insieme, anche se le sei direzioni danno alla griglia più modi per scardinare la tua struttura. Il serpente diventa un percorso ripiegato che attraversa tutti e tre gli strati. Per quanto ho potuto trovare, nessuno ha stabilito se l'analogia regga davvero: è un ragionamento, non una misura.
E il tetto? La regola di un esponente per cella suggerirebbe 327 ≈ 7.600 miliardi come limite superiore largo. Ma l'analogia si sfilaccia parecchio. L'esponente in più di 2048 veniva da un 4 fortunato; 3927 genera sempre e solo la tessera più piccola, un semplice 3, quindi non c'è alcun bonus. Peggio ancora, una fusione tripla richiede tre tessere allineate, e ogni riga, colonna e pilastro di un cubo 3×3×3 è lungo esattamente tre celle, quindi ogni fusione consuma un'intera linea. Questo vincolo morde molto più di qualsiasi cosa nel gioco piatto e quasi certamente trascina il vero massimo ben al di sotto di 327. Quale sia quel numero reale, non l'ho trovato calcolato da nessuna parte. (Ragionamento dichiarato come tale; le meccaniche descritte sopra sono ricavate dai documenti di progettazione del gioco.)
Ecco la sottigliezza che rende sfuggente il «gioco perfetto». Un gioco di fusione con generazioni casuali è un gioco stocastico a un solo giocatore, un solitario contro un dado, non un duello. Nulla sceglie la generazione peggiore per rovinarti; c'è solo il generatore di numeri casuali, indifferente. Quindi la nozione giusta di gioco ottimale è l'expectimax: massimizzare l'esito atteso sulla distribuzione delle generazioni. Non è affatto il minimax: il minimax presuppone un avversario, e se davvero lasci che sia un avversario a piazzare ogni tessera («evil 2048», il 2048 malvagio), il gioco diventa qualcosa di più crudele, in cui si può essere costretti a perdere. Poiché i dadi possono in linea di principio servire qualsiasi sequenza, una strategia che garantisca una data tessera può semplicemente non esistere. Così la risposta onesta a «esiste una strategia perfetta?» è che, per un gioco stocastico, il massimo che si possa anche solo definire è una strategia ottima in media, e calcolarla esattamente è fuori portata per 2048 6 e del tutto aperto per 3927.