🤖 AI

Strongly Solving 2048 4x3

Questo articolo presenta la soluzione forte della variante 4x3 del gioco stocastico 2048, determinando un punteggio atteso ottimale di circa 50.724,26 mediante l'utilizzo di una tecnica di partizione basata sull'età per gestire il suo vasto spazio degli stati, composto da oltre 1,15 trilioni di stati raggiungibili.

Autori originali: Tomoyuki Kaneko, Shuhei Yamashita

Pubblicato 2026-05-26

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Tomoyuki Kaneko, Shuhei Yamashita

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina il popolare gioco di puzzle 2048 come una cucina gigantesca e caotica in cui stai cercando di combinare ingredienti (piastrelle) per preparare piatti sempre più grandi. Nella versione standard, hai una griglia 4x4 (16 caselle). In questo articolo, gli autori hanno deciso di restringere la cucina a una griglia 4x3 (12 caselle), rendendola una sfida più stretta e affollata.

Ecco una semplice spiegazione di ciò che hanno fatto, come l'hanno fatto e cosa hanno scoperto, utilizzando analogie di tutti i giorni.

1. La Grande Sfida: Una Biblioteca Troppo Grande per Essere Letta

Gli autori volevano "risolvere fortemente" questa versione più piccola del gioco. In termini di gioco, ciò significa che non volevano solo conoscere la mossa migliore per l'inizio; volevano conoscere la mossa perfetta per ogni singola situazione possibile che il gioco potrebbe mai raggiungere.

Pensa alle situazioni possibili del gioco come a una biblioteca.

La versione originale 3x3 (Mini2048) era come una piccola libreria con circa 48.000 libri. Facile da leggere.
Questa nuova versione 4x3 è una biblioteca enorme con oltre 1,15 trilioni di libri (stati) e quasi 740 miliardi di libri "intermedi" (stati successivi).

Cercare di leggere ogni libro di questa biblioteca uno per uno richiederebbe un'eternità e un computer con più memoria di quanta ne esista al mondo. Gli autori avevano bisogno di un trucco magico per organizzare questa biblioteca in modo da poterla risolvere in pochi giorni su un normale computer personale.

2. Il Trucco Magico: L'"Età" del Gioco

La chiave del loro successo è un concetto che chiamano "Età".

Immagina che ogni volta che giochi al gioco, tu stia aggiungendo peso a una bilancia.

Quando inizi, hai due piastrelle (diciamo due 2). L'"Età" è la somma di tutti i numeri sulla scacchiera (2 + 2 = 4).
Quando fai scorrere le piastrelle e le unisci, i numeri raddoppiano, ma l'Età rimane esattamente la stessa. (Unire due 2 in un 4 non cambia la somma totale).
L'unico momento in cui l'Età cambia è quando il computer fa cadere casualmente una nuova piastrella (un 2 o un 4). Questo aggiunge 2 o 4 all'Età.

L'Analogia:
Pensa al gioco non come a un labirinto, ma come a un edificio a più piani.

Ogni "piano" dell'edificio rappresenta una specifica Età (ad esempio, Piano 4, Piano 6, Piano 8...).
Puoi muoverti liberamente sullo stesso piano (facendo scorrere e unendo le piastrelle) senza salire o scendere.
Ti sposti solo al piano successivo quando il computer fa cadere una nuova piastrella.

Poiché il gioco si muove sempre in avanti nell'Età (non torni mai a una somma inferiore), gli autori potevano trattare la biblioteca piano per piano. Non avevano bisogno di tenere tutta la biblioteca in testa contemporaneamente. Avevano solo bisogno di mantenere nella memoria il piano corrente, il successivo e quello dopo. Una volta finito di calcolare le mosse migliori per il Piano 100, potevano scartare i dati del Piano 98 per fare spazio al Piano 102.

3. La Compressione: Adattare una Balena a uno Zaino

Anche con questo trucco piano per piano, i dati erano ancora enormi. Se avessero cercato di scrivere ogni singolo stato di gioco su carta, occuperebbero circa 4,4 Terabyte di spazio su disco rigido (circa le dimensioni di un enorme data center).

Per risolvere il problema, hanno utilizzato una tecnica di compressione dei dati intelligente chiamata codifica Elias-Fano.

L'Analogia: Immagina di avere una lista di 1 miliardo di persone, ma indossano tutte camicie rosse. Invece di scrivere "Camicia Rossa" accanto a ogni singolo nome (il che spreca spazio), scrivi un codice speciale che dice: "Tutti in questa lista indossano camicie rosse".
Hanno trovato un modo per comprimere le "tessere identificative" di ogni possibile stato di gioco fino a circa 1,4 Terabyte. Se avessero interessato solo delle migliori mosse (ignorando i dati grezzi), avrebbero potuto ridurlo ulteriormente a circa 300 Gigabyte (le dimensioni del disco rigido di un laptop di fascia alta).

4. I Risultati: Cosa Hanno Imparato

Risolvendo il gioco, hanno calcolato il punteggio atteso perfetto per un giocatore che non commette mai errori.

Il Punteggio: Se inizi con la configurazione più comune (due 2) e giochi perfettamente, puoi aspettarti di ottenere circa 50.724 punti.
Il Fattore "Sfortuna": Hanno scoperto che iniziare con una piastrella 4 invece di due 2 ti mette effettivamente in uno svantaggio lieve (circa 4 punti in meno). È come iniziare una gara con uno zaino pesante; devi lavorare di più per recuperare.
La "Cima" 2048: Il grafico dei loro risultati mostrava "valli" (cali di prestazioni) ogni volta che l'Età raggiungeva i multipli di 2048. Questo conferma una sensazione che molti giocatori hanno: diventa incredibilmente difficile creare la piastrella 2048 perché stai esaurendo lo spazio sulla tua piccola scacchiera da 12 caselle. Hai bisogno di un ordinamento perfetto per far stare tutti i numeri più piccoli (2, 4, 8... fino a 1024) prima di poterli combinare.

Riepilogo

Gli autori hanno preso un gioco che sembrava troppo complesso da risolvere completamente a causa del suo enorme numero di possibilità. Hanno realizzato che il gioco si organizza naturalmente in base alla "somma dei numeri" (Età). Trattando il gioco come una serie di piani invece che come una gigantesca ragnatela intrecciata, e utilizzando un sistema di archiviazione super efficiente (compressione), hanno mappato la strategia perfetta per ogni possibile mossa.

Hanno dimostrato che con un computer standard e pochi giorni di lavoro, è possibile padroneggiare matematicamente un gioco che di solito si basa sulla fortuna e sull'intuizione.

Riepilogo Tecnico: Soluzione Forte di 2048 su una Scacchiera 4×3

Definizione del Problema

Questo articolo affronta la "soluzione forte" di una variante stocastica di gioco a un giocatore: 2048 su una scacchiera 4×3 (denotata come 2048 $^{4\times3}$ ). A differenza della versione standard 4×4, questa variante utilizza una griglia di 12 celle. Il gioco è modellato come un Processo Decisionale di Markov (MDP) in cui un agente seleziona azioni (su, giù, sinistra, destra) per fondere tessere adiacenti di uguale valore. Dopo un'azione valida, lo stato della scacchiera transita deterministicamente in un "afterstate" (scorrimento e fusione delle tessere). Successivamente, l'ambiente genera stocasticamente una nuova tessera (2 con probabilità del 90%, 4 con il 10%) in una cella vuota casuale, transitando al successivo stato.

L'obiettivo è calcolare la politica ottimale $\pi^*$ e la funzione di valore ottimale $v^*(s)$ , che rappresentano la ricompensa cumulativa attesa da qualsiasi stato raggiungibile $s$ . La sfida principale risiede nella dimensione dello spazio degli stati: la variante 4×3 contiene circa $1,15 \times 10^9$ stati raggiungibili e $7,4 \times 10^8$ afterstate. Questa scala è circa $10^4$ volte più grande della variante 3×3 precedentemente risolta (Mini2048), rendendo l'enumerazione e l'archiviazione dirette non fattibili sull'hardware standard.

Metodologia

Gli autori propongono una soluzione basata sulla partizionamento dello spazio degli stati per "età" e sulla rappresentazione compatta dei dati.

1. Partizionamento Basato sull'Età

L'innovazione fondamentale consiste nel definire l'età di uno stato come la somma di tutti i numeri delle tessere sulla scacchiera ( $age(s) = \sum c_i$ ).

Invarianza: L'età rimane costante tra uno stato e il suo afterstate immediato dopo un'azione valida (poiché la fusione delle tessere preserva la somma dei valori e lo scorrimento non modifica i valori).
Progressione: L'età aumenta di 2 o 4 durante la transizione stocastica (generazione di una nuova tessera).
Implicazione Algoritmica: Questa proprietà permette di partizionare lo spazio degli stati in sottoinsiemi disgiunti basati sull'età.
- Passo Avanti (Enumerazione): Gli stati validi di età $n$ possono essere generati esclusivamente dagli afterstate di età $n-2$ e $n-4$ . L'algoritmo itera attraverso età crescenti, mantenendo in memoria solo tre insiemi (età corrente, età+2, età+4) per enumerare tutti gli stati e gli afterstate raggiungibili.
- Passo Indietro (Calcolo del Valore): I valori ottimali sono calcolati iterando all'indietro dall'età massima all'età iniziale. Il valore di uno stato è il valore massimo dei suoi afterstate raggiungibili; il valore di un afterstate è il valore atteso dei suoi prossimi stati raggiungibili (pesato secondo le probabilità di generazione).

2. Rappresentazione Compatta

Per gestire i requisiti di archiviazione (stimati in circa 4,4 TiB per ID grezzi a 48 bit), gli autori impiegano i codici Elias-Fano per memorizzare insiemi di ID di stati unici.

Struttura: Gli ID unici ordinati sono suddivisi in bit di ordine superiore ( $h_i$ ) e bit di ordine inferiore ( $l_i$ ). I bit inferiori sono memorizzati in un vettore di bit contiguo, mentre i bit superiori sono codificati in un vettore di bit sparso $H$ utilizzando operazioni di rango.
Ottimizzazioni:
- Riduzione della Simmetria: Gli ID sono normalizzati al valore minimo tra le simmetrie orizzontale, verticale e di rotazione di 180 gradi.
- Adattamento della Base: La base di codifica viene adattata in base al valore massimo della tessera per una specifica età.
- Eliminazione della Cella: Le informazioni di una cella vengono omesse durante la codifica poiché la somma (età) vincola il totale, permettendo il completo ripristino in seguito.
Efficienza: Ciò riduce l'archiviazione per tutti gli ID degli afterstate da circa 4,4 TiB a circa 1,4 TiB, mantenendo capacità di ricerca efficienti. Per il gioco ottimale specificamente, una rappresentazione specializzata (utilizzando l'algoritmo BuRR) riduce il requisito a meno di 300 GiB.

Risultati Chiave

Statistiche dello Spazio degli Stati: Il numero totale di stati raggiungibili è 1.152.817.492.752, e il numero di afterstate è 739.648.886.170.
Punteggio Atteso Ottimale: Per gli stati iniziali più comuni (due tessere di valore 2), il punteggio atteso sotto una strategia ottimale è di circa 50.724,26.
- Gli stati iniziali con una tessera 4 (età 6) producono un punteggio atteso leggermente inferiore (~50.720,62).
- Gli stati iniziali con due tessere 4 (età 8) producono il punteggio più basso (~50.708,99), indicando un piccolo svantaggio nell'iniziare con tessere di valore più alto.
Distribuzione degli Stati: Il numero di stati per età è generalmente gestibile (meno di $3 \times 10^6$ per età), permettendo all'algoritmo di mantenere diversi livelli di età in memoria.
Stati Terminali: I "valloni" nella distribuzione del conteggio degli stati si verificano a età che sono multipli di 2048, riflettendo la difficoltà di formare tessere grandi con uno spazio limitato sulla scacchiera. Certi valori di età (ad esempio, 8190, 12286) hanno zero afterstate validi perché la formazione di quelle somme richiederebbe più tessere di quante consentite dalle 12 celle disponibili.
Sensibilità all'Azione: La differenza di valore tra azioni ottimali e subottimali raggiunge il picco vicino alle età 2048 e 4096, suggerendo che le decisioni iniziali immediatamente dopo la formazione di tessere grandi sono critiche.

Significato e Affermazioni

L'articolo afferma di aver risolto fortemente la variante 2048 $^{4\times3}$ , un compito precedentemente considerato intrattabile a causa della dimensione dello spazio degli stati. Il significato di questo lavoro risiede in:

Scalabilità: Dimostrare che un gioco con oltre $10^9$ stati può essere risolto su un computer personale in pochi giorni sfruttando proprietà strutturali specifiche del gioco (età) piuttosto che metodi di forza bruta.
Contributo Metodologico: L'introduzione della tecnica di partizionamento per "età" permette l'enumerazione e il calcolo del valore di MDP stocastici in cui i valori degli stati dipendono dalle aspettative, aggirando efficacemente la necessità di potatura $\alpha\beta$ (che è inefficace negli ambienti stocastici).
Disponibilità dei Dati: Gli autori forniscono la funzione di valore ottimale e una rappresentazione compatta dello spazio degli stati, servendo come linea di base per future ricerche sull'apprendimento per rinforzo e analisi dei giochi.
Efficienza di Archiviazione: La corretta applicazione dei codici Elias-Fano per comprimere un enorme insieme di stati di gioco a circa 1,4 TiB rende il dataset accessibile ai ricercatori con risorse computazionali moderate (ad esempio, SSD da 4 TiB).

Gli autori notano che, sebbene l'obiettivo principale fosse risolvere il gioco, il dataset risultante e il concetto di "età" possono servire come fondamento per ulteriori studi su giochi stocastici e valutazione dell'apprendimento per rinforzo.