🤖 AI

Strongly Solving 2048 4x3

Este artículo presenta la solución fuerte de la variante 4x3 del juego estocástico 2048, determinando una puntuación esperada óptima de aproximadamente 50.724,26 mediante el uso de una técnica de partición basada en la edad para gestionar su vasto espacio de estados de más de 1,15 billones de estados alcanzables.

Autores originales: Tomoyuki Kaneko, Shuhei Yamashita

Publicado 2026-05-26

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Tomoyuki Kaneko, Shuhei Yamashita

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina el popular juego de rompecabezas 2048 como una cocina gigante y caótica donde intentas combinar ingredientes (fichas) para preparar platos cada vez más grandes. En la versión estándar, tienes una cuadrícula de 4x4 (16 espacios). En este artículo, los autores decidieron reducir la cocina a una cuadrícula de 4x3 (12 espacios), convirtiéndola en un desafío más ajustado y abarrotado.

Aquí tienes un desglose sencillo de lo que hicieron, cómo lo hicieron y qué descubrieron, utilizando analogías cotidianas.

1. El Gran Desafío: Una Biblioteca Demasiado Grande para Leer

Los autores querían "resolver fuertemente" esta versión más pequeña del juego. En términos de juegos, esto significa que no solo querían saber el mejor movimiento para el inicio; querían conocer el movimiento perfecto para cada situación posible que el juego pudiera alcanzar jamás.

Piensa en las situaciones posibles del juego como una biblioteca.

La versión original de 3x3 (Mini2048) era como una pequeña estantería con unos 48.000 libros. Fácil de leer.
Esta nueva versión de 4x3 es una biblioteca masiva con más de 1,15 billones de libros (estados) y casi 740 mil millones de libros "intermedios" (estados posteriores).

Intentar leer cada libro de esta biblioteca uno por uno tomaría una eternidad y requeriría una computadora con más memoria de la que existe en el mundo. Los autores necesitaban un truco de magia para organizar esta biblioteca para poder resolverla en solo unos pocos días en una computadora personal normal.

2. El Truco de Magia: La "Edad" del Juego

La clave de su éxito fue un concepto al que llaman "Edad".

Imagina que cada vez que juegas, estás añadiendo peso a una balanza.

Cuando empiezas, tienes dos fichas (digamos, dos 2s). La "Edad" es la suma de todos los números en el tablero (2 + 2 = 4).
Cuando deslizas las fichas y las fusionas, los números se duplican, pero la Edad permanece exactamente igual. (Fusionar dos 2s en un 4 no cambia la suma total).
La única vez que cambia la Edad es cuando la computadora deja caer aleatoriamente una ficha nueva (un 2 o un 4). Esto añade 2 o 4 a la Edad.

La Analogía:
Piensa en el juego no como un laberinto, sino como un edificio de varios pisos.

Cada "piso" del edificio representa una Edad específica (por ejemplo, Piso 4, Piso 6, Piso 8...).
Puedes moverte libremente en el mismo piso (deslizando y fusionando fichas) sin subir ni bajar.
Solo te mueves al siguiente piso cuando la computadora deja caer una ficha nueva.

Como el juego siempre avanza en Edad (nunca regresas a una suma menor), los autores pudieron tratar la biblioteca piso por piso. No necesitaban mantener toda la biblioteca en su cabeza a la vez. Solo necesitaban mantener en su memoria el piso actual, el siguiente y el siguiente a ese. Una vez que terminaron de calcular los mejores movimientos para el Piso 100, podían desechar los datos del Piso 98 para hacer espacio para el Piso 102.

3. La Compresión: Meter una Ballena en una Mochila

Incluso con este truco de piso por piso, los datos seguían siendo enormes. Si intentaran escribir cada estado del juego en papel, ocuparía aproximadamente 4,4 Terabytes de espacio en disco duro (aproximadamente el tamaño de un centro de datos masivo).

Para solucionarlo, utilizaron una técnica inteligente de compresión de datos llamada codificación Elias-Fano.

La Analogía: Imagina que tienes una lista de 1.000 millones de personas, pero todas llevan camisetas rojas. En lugar de escribir "Camiseta Roja" al lado de cada nombre (lo cual desperdicia espacio), escribes un código especial que dice: "Todos en esta lista llevan camisetas rojas".
Encontraron una manera de comprimir las "tarjetas de identificación" de cada estado posible del juego hasta aproximadamente 1,4 Terabytes. Si solo les importaban los mejores movimientos (ignorando los datos brutos), podían reducirlo aún más a unos 300 Gigabytes (el tamaño del disco duro de una computadora portátil de gama alta).

4. Los Resultados: ¿Qué Aprendieron?

Al resolver el juego, calcularon la puntuación esperada perfecta para un jugador que nunca comete errores.

La Puntuación: Si empiezas con la configuración más común (dos 2s) y juegas perfectamente, puedes esperar una puntuación de aproximadamente 50.724 puntos.
El Factor "Mala Suerte": Descubrieron que empezar con una ficha 4 en lugar de dos 2s en realidad te pone en una ligera desventaja (unos 4 puntos menos). Es como empezar una carrera con una mochila pesada; tienes que trabajar más para ponerte al día.
El "Bache" de 2048: El gráfico de sus resultados mostró "valles" (bajadas en el rendimiento) cada vez que la Edad alcanzaba múltiplos de 2048. Esto confirma una sensación que muchos jugadores tienen: se vuelve increíblemente difícil crear la ficha 2048 porque te estás quedando sin espacio en tu pequeño tablero de 12 cuadrados. Necesitas una disposición perfecta para ajustar todos los números más pequeños (2, 4, 8... hasta 1024) antes de poder combinarlos.

Resumen

Los autores tomaron un juego que parecía demasiado complejo para resolver completamente debido a su enorme número de posibilidades. Se dieron cuenta de que el juego se organiza naturalmente por la "suma de números" (Edad). Al tratar el juego como una serie de pisos en lugar de una gran maraña, y al utilizar un sistema de archivo super eficiente (compresión), mapearon la estrategia perfecta para cada movimiento posible.

Demostraron que con una computadora estándar y unos pocos días de trabajo, se puede dominar matemáticamente un juego que normalmente depende de la suerte y la intuición.

Resumen Técnico: Solución Fuerte de 2048 en un Tablero 4×3

Definición del Problema

Este artículo aborda la "solución fuerte" de una variante estocástica de juego de un solo jugador: 2048 en un tablero 4×3 (denotado como 2048 $^{4\times3}$ ). A diferencia de la versión estándar 4×4, esta variante utiliza una cuadrícula de 12 celdas. El juego se modela como un Proceso de Decisión de Markov (MDP) donde un agente selecciona acciones (arriba, abajo, izquierda, derecha) para fusionar fichas adyacentes de igual valor. Tras una acción válida, el estado del tablero transiciona determinísticamente a un "postestado" (deslizamiento y fusión de fichas). Posteriormente, el entorno genera estocásticamente una nueva ficha (2 con probabilidad del 90%, 4 con probabilidad del 10%) en una celda vacía aleatoria, transicionando al siguiente estado.

El objetivo es calcular la política óptima $\pi^*$ y la función de valor óptima $v^*(s)$ , que representan la recompensa acumulada esperada desde cualquier estado alcanzable $s$ . El desafío principal radica en el tamaño del espacio de estados: la variante 4×3 contiene aproximadamente $1.15 \times 10^9$ estados alcanzables y $7.4 \times 10^8$ postestados. Esta escala es aproximadamente $10^4$ veces mayor que la variante 3×3 previamente resuelta (Mini2048), lo que hace inviable la enumeración y el almacenamiento directos en hardware estándar.

Metodología

Los autores proponen una solución basada en la partición del espacio de estados por "edad" y la representación compacta de datos.

1. Partición Basada en Edad

La innovación central consiste en definir la edad de un estado como la suma de todos los números de las fichas en el tablero ( $age(s) = \sum c_i$ ).

Invarianza: La edad permanece constante entre un estado y su postestado inmediato tras una acción válida (ya que fusionar fichas conserva la suma de valores y deslizar no cambia los valores).
Progresión: La edad aumenta en 2 o 4 durante la transición estocástica (generación de una nueva ficha).
Implicación Algorítmica: Esta propiedad permite particionar el espacio de estados en subconjuntos disjuntos basados en la edad.
- Paso Adelante (Enumeración): Los estados válidos de edad $n$ pueden generarse exclusivamente a partir de postestados de edades $n-2$ y $n-4$ . El algoritmo itera a través de edades crecientes, manteniendo en memoria solo tres conjuntos (edad actual, edad+2, edad+4) para enumerar todos los estados y postestados alcanzables.
- Paso Atrás (Cálculo de Valor): Los valores óptimos se calculan iterando hacia atrás desde la edad máxima hasta la edad inicial. El valor de un estado es el valor máximo de sus postestados alcanzables; el valor de un postestado es el valor esperado de sus siguientes estados alcanzables (ponderado por las probabilidades de generación).

2. Representación Compacta

Para manejar los requisitos de almacenamiento (estimados en ~4.4 TiB para IDs de 48 bits sin procesar), los autores emplean códigos de Elias-Fano para almacenar conjuntos de IDs de estados únicos.

Estructura: Los IDs únicos ordenados se dividen en bits de orden superior ( $h_i$ ) y bits de orden inferior ( $l_i$ ). Los bits inferiores se almacenan en un vector de bits contiguo, mientras que los bits superiores se codifican en un vector de bits disperso $H$ utilizando operaciones de rango.
Optimizaciones:
- Reducción de Simetría: Los IDs se normalizan al valor mínimo entre las simetrías horizontal, vertical y de rotación de 180 grados.
- Adaptación de Base: La base de codificación se ajusta según el valor máximo de ficha para una edad específica.
- Eliminación de Celda: Se elimina la información de una celda durante la codificación porque la suma (edad) restringe el total, permitiendo una reconstrucción completa posterior.
Eficiencia: Esto reduce el almacenamiento para todos los IDs de postestados de ~4.4 TiB a aproximadamente 1.4 TiB manteniendo capacidades de búsqueda eficientes. Para el juego óptimo específicamente, una representación especializada (utilizando el algoritmo BuRR) reduce el requisito a menos de 300 GiB.

Resultados Clave

Estadísticas del Espacio de Estados: El número total de estados alcanzables es 1,152,817,492,752, y el número de postestados es 739,648,886,170.
Puntuación Esperada Óptima: Para los estados iniciales más comunes (dos fichas de valor 2), la puntuación esperada bajo una estrategia óptima es aproximadamente 50,724.26.
- Los estados iniciales con una ficha 4 (edad 6) producen una puntuación esperada ligeramente menor (~50,720.62).
- Los estados iniciales con dos fichas 4 (edad 8) producen la más baja (~50,708.99), lo que indica una pequeña desventaja al comenzar con fichas de mayor valor.
Distribución de Estados: El número de estados por edad es generalmente manejable (menos de $3 \times 10^6$ por edad), permitiendo que el algoritmo mantenga varias capas de edad en memoria.
Estados Terminales: Los "valles" en la distribución de la cantidad de estados ocurren en edades que son múltiplos de 2048, reflejando la dificultad de formar fichas grandes con espacio limitado en el tablero. Ciertas edades (por ejemplo, 8190, 12286) tienen cero postestados válidos porque formar esas sumas requeriría más fichas de las que permiten las 12 celdas disponibles.
Sensibilidad a la Acción: La diferencia en valor entre acciones óptimas y subóptimas alcanza su punto máximo cerca de las edades 2048 y 4096, lo que sugiere que las decisiones tempranas inmediatamente después de formar fichas grandes son críticas.

Significado y Afirmaciones

El artículo afirma haber resuelto fuertemente la variante 2048 $^{4\times3}$ , una tarea previamente considerada intratable debido al tamaño del espacio de estados. El significado de este trabajo radica en:

Escalabilidad: Demostrar que un juego con más de $10^9$ estados puede resolverse en una computadora personal en unos pocos días aprovechando propiedades estructurales específicas del juego (edad) en lugar de métodos de fuerza bruta.
Contribución Metodológica: La introducción de la técnica de partición por "edad" permite la enumeración y el cálculo de valores de MDPs estocásticos donde los valores de estado dependen de expectativas, evitando efectivamente la necesidad de poda $\alpha\beta$ (que es ineficaz en entornos estocásticos).
Disponibilidad de Datos: Los autores proporcionan la función de valor óptima y una representación compacta del espacio de estados, sirviendo como línea base para futuras investigaciones en aprendizaje por refuerzo y análisis de juegos.
Eficiencia de Almacenamiento: La aplicación exitosa de códigos de Elias-Fano para comprimir un conjunto masivo de estados de juego a ~1.4 TiB hace que el conjunto de datos sea accesible para investigadores con recursos computacionales moderados (por ejemplo, SSDs de 4 TiB).

Los autores señalan que, aunque el objetivo principal fue resolver el juego, el conjunto de datos resultante y el concepto de "edad" pueden servir como base para estudios adicionales en juegos estocásticos y evaluación de aprendizaje por refuerzo.