Posición máxima del tablero en el juego 2048

Question

Un juego llamado 2048 está dando vueltas en las redes sociales. Estoy tratando de determinar la puntuación máxima alcanzable para este juego. Vamos a asumir sin pérdida de generalidad que solo se devuelven 2s (si los 4s son posibles, la puntuación máxima se duplica).

Primero, relajaré algunas de las reglas para crear un juego, $\mathcal{G}$, que pueda alcanzar una puntuación por lo menos tan alta como la del juego original, 2048. Una serie $R$ de $\mathcal{G}_n$ consiste en una secuencia de movimientos $m_1,\ldots,m_k$ que manipulan un multiconjunto, $\mathcal{S}$, de tamaño máximo n. Cada $m_i$ es o bien:

• un "put" $p$, que inserta un 2 en $\mathcal{S}$, o
• una fusión, $\alpha_i$, que reemplaza dos elementos $2^i$ de $\mathcal{S}$ por un solo elemento $2^{i+1}$.

Permito movimientos secuenciales del mismo tipo porque 2048 permite múltiples fusiones o turnos sin fusión. La puntuación de una posición es la suma de $\mathcal{S}$.

¿Cuál es la puntuación máxima posible en un juego de orden n?

Nota: La posición final debe tener solo valores únicos, de lo contrario una fusión y un "put" serían posibles para aumentar la puntuación.

Afirmo que es $\sum_{i=1}^{n} 2^i$, pero no pude idear ningún buen argumento inductivo. Es bastante fácil probar que un elemento $2^k$ es producible en un juego $\mathcal{G}_k$, pero probar un límite superior para la producción se volvió un poco complicado y además no cubre todo el espacio.

Answer 1

Una tabla óptima justo antes de que se juegue el último número en un tablero 4x4:

$$\begin{array} {|c|c|c|c|} \hline & 256 & 512 & 65536 \\ \hline 4 & 128 & 1024 & 32768 \\ \hline 8 & 64 & 2048 & 16384 \\ \hline 16 & 32 & 4096 & 8192 \\ \hline \end{array}$$

... y luego cae un 4 por suerte en el cuadrado vacío dando como resultado el número más grande que se puede crear es $2^{17} = 131072$. De hecho, para hacer un número $2^n$, entonces debes tener todos los números $[4 \dots 2^{n-1}]$ ya presentes en el tablero.

El número más grande que se puede hacer es entonces $2^{\left(n^2 + 1\right)}$, o si asumes que no caerán 4, entonces es $2^{\left(n^2\right)}.

Una posición de tablero así se puede construir fácilmente teniendo siempre una secuencia creciente en los cuadros no vacíos del camino comenzando en la esquina superior izquierda:

$$\begin{array} {|c|c|c|c|} \hline \downarrow & \rightarrow & \downarrow & \circ \\ \hline \downarrow & \uparrow & \downarrow & \uparrow \\ \hline \downarrow & \uparrow & \downarrow & \uparrow \\ \hline \rightarrow & \uparrow & \rightarrow & \uparrow \\ \hline \end{array}$$

y luego haciendo que el próximo número caiga en el último cuadrado vacío del camino.

Por otra parte, esto resulta ser una estrategia muy efectiva para jugar el juego con caídas no óptimas también.

Editar: James Grime viene al rescate nuevamente. Hizo un video de Youtube bastante entretenido para abordar esta pregunta.

Answer 2

Para empezar, busquemos el número más grande posible que pueda entrar en el juego. Y para facilitar las cosas, trabajemos con el logaritmo de los números.

Para que un número $n$ sea alcanzable, el grupo más pequeño de bloques que tenga que existir al menos en un momento debe ser $n-1, n-2, n-3,...2,2$, donde 2 es un 4 en el juego (ya que los 4 son el número más grande que se puede generar). Eso significa que para hacer un bloque n debe haber n-1 celdas libres.

Por lo tanto, para un tablero $m\times m$ el número más grande puede ser $m^2 + 1$. Con el mismo razonamiento, el tablero máximo estará lleno con $m^2 + 1, m^2, m^2 - 1,...,3,2$.

Cada bloque en el tablero se hace añadiendo otros dos bloques. Saltando el cálculo, para un bloque de valor $2^k$, los puntos máximos hechos para el bloque es $(k-1)2^k - 4$. Si observas cómo se hacen los puntos, esto es fácilmente alcanzable.

Por lo tanto, la puntuación máxima que se puede lograr es $-4m^2+\sum_{i=1}^{m^2} i\cdot2^{i+1}$.

Para simplificar, $\sum_{i=1}^{n} i\cdot 2^{i+1} = (n-1) 2^{n+2} + 4$. Esto se puede probar por inducción.

Con eso, la puntuación máxima es $-4m^2 + (m^2-1)2^{m^2+2}+4 = (m^2-1)2^{m^2+2} - 4(m^2-1) = 4(m^2-1)(2^{m^2}-1)

Answer 3

Creo que puedes construir fácilmente el tablero de puntuación máxima de Flowers por inducción (dado que controlamos la ubicación en este juego). Primero, solo para configurar esto, acordemos que:

1. (Sin pérdida de generalidad en cuanto al lado/esquina que se utiliza) un tablero lleno tendrá su valor más alto en la esquina superior izquierda, valores en disminución secuencial yendo hacia la derecha en la fila superior, luego el siguiente paso hacia abajo en la secuencia debajo de la entrada más a la derecha de la segunda fila, valores en disminución secuencial hacia la izquierda a lo largo de la segunda, etc (llamemos a esto un patrón de serpenteo)

2. $2^{n^2}$, el valor más alto en un cuadrado ($n\times n$), se puede obtener de una cuadrícula inicialmente vacía (esto es obvio ya que moverse solo hacia la izquierda/derecha dentro de una sola columna te llevará hasta $2^n$, luego muévelos todos hacia la derecha y luego apílalos).

Una vez que acordamos en el punto 2, entonces todo lo que realmente necesitamos es la hipótesis de inducción: - $2^{(n-1)^2}$ se puede obtener en una subcuadrícula inicialmente vacía de $(n-1)\times(n-1)$.

Así que cuando colocas el $2^{n^2}$ en la esquina superior izquierda queda mucho espacio para comenzar a construir el siguiente componente de la serpiente (es decir, $2^{(n-1)^2}$) ya que queda una subcuadrícula completa de $(n-1)\times(n-1)$, más $(n-1)$ cuadrados adicionales a lo largo de los bordes superior e izquierdo.

Oh sí, y para el caso base (una cuadrícula de $2\times2$) no es difícil de descifrar por tu cuenta (lo hice en papel para estar seguro, simplemente no hay un formato conveniente para que pueda escribir el procedimiento).

EDICIÓN: Olvidé mencionar esto, pero bajo tus reglas parece que no estamos obligados a alternar entre un movimiento izquierda/derecha/arriba/abajo versus una colocación de ficha, ¿verdad? Esto significa que, por ejemplo, puedo comenzar llenando una fila con 2's y luego simplemente desplazándolos todos juntos con varios movimientos hacia la derecha en secuencia.

Answer 4

No estoy seguro, pero creo que puede haber una diferencia en el significado de "puntuación" en la discusión anterior. "Puntuación" para la mayoría de las personas significa los puntos obtenidos al fusionar bloques, mientras que Isaac parece estar usando la palabra para referirse al valor máximo mostrado en un solo bloque. Utilizaré la definición mayoritaria. Y pido disculpas por no tener acceso rápido y fácil a todos los símbolos y superíndices; por favor, tengan paciencia conmigo.

Para responder primero a Saryu, sí, para el juego estándar (Isaac's game utiliza solo 2, por lo que 2^16 es el valor máximo del bloque para su juego). 2^17 es alcanzable solo si aparece un bloque de 4 en lugar de un bloque de 2 cuando el tablero alcanza su estado máximo para el patrón de 2^16, lo que permite que ocurra otra serie de fusiones.

Desafortunadamente, no puedo ofrecer una prueba rigurosa, pero puedo ofrecer mis números y ustedes pueden interpretarlos como deseen. Principalmente discutiré el juego estándar, del cual la variante de Isaac podría considerarse un subconjunto ya que no incluye bloques de 4.

Los valores del bloque en un tablero máximo (m = n^2 = 16) se establecen como 2^(m+1), 2^m, 2^(m-1)...2^3, b (sea un 2 o un 4).

El valor de puntuación máximo de un bloque dado valorado en 2^k, según mi razonamiento, es (2^k)(k-1). Ya que tal vez no esté leyendo correctamente la fórmula de Flowers o haya llegado a una conclusión diferente, razono de la siguiente manera: dado que se obtiene puntuación cada vez que se fusionan bloques, el número máximo de fusiones para crear un bloque de 2^k se lograría con bloques de tamaño 2, y sería 2k-1. Para derivar la puntuación, imagina una línea de bloques de 2 lo suficientemente larga como para sumar el valor deseado de 2^k, y luego llévalos a través de fusiones sucesivas por pares (fusionando cada par de bloques adyacentes en la línea en una sola operación) hasta terminar con el solo bloque de 2^k. Cada una de estas fusiones por pares puntuaría 2^k puntos. El número de fusiones por pares necesarias sería (k-1).

Un breve ejemplo para ilustrar k=3: una línea de 2222 se fusiona por pares a 44 (cada 4 puntúa 4 puntos, total 8), y luego se fusiona por pares nuevamente a 8 (puntuando 8 puntos). Cada fusión por pares valía 2^k puntos, y k-1 de ellas ocurrieron, por lo tanto, (2^k)(k-1) para el valor total de puntuación de 16.

Dado que en el juego real las fusiones solo pueden ocurrir de bloques iguales, y dado que cada valor de 2^k debe construirse mediante fusiones sucesivas, no puedo encontrar ninguna razón lógica por la cual este método no derive el valor máximo de puntuación posible para un bloque de 2^k dado. Sin embargo, dado que a veces aparecen bloques de 4 en el juego, la puntuación real obtenida puede ser menor... de hecho, será 4 puntos menor por cada bloque de 4 que aparezca, ya que no se obtendrán puntos por la creación de ese bloque de 4 a partir de un par de bloques de 2. Si mi razonamiento hasta ahora es correcto, el valor máximo de puntuación para el tamaño máximo de bloque del juego oficial (k=17) es así 2097152. Para la variante de Isaac (k=16) sería 983040.

A partir de esa base para el valor máximo de puntuación posible de un solo bloque, y sabiendo la posición máxima del tablero, entonces podemos sumar los máximos valores de puntuación de cada bloque en ese tablero para obtener un valor máximo de puntuación posible para todo el tablero. Admito que en este punto "hice trampa" y usé Excel para hacer cálculos y luego deduje la fórmula a partir de ahí, pero creo que las conclusiones siguen siendo válidas.

Para la versión de Isaac, la suma para k=2...m de (2^k)(k-1) es igual a (2^k)(2k-4)+4, o 1835012.

Para un tablero estándar, la suma para k=3...m+1 de (2^k)(k-1) es igual a (2^k)(2k-4). Esto es 3932160, lo cual le aseguro que es una puntuación mucho mayor de la que he obtenido. Sin embargo, esta suma no tiene en cuenta que para que ocurra el bloque de k=17, debe haber aparecido un bloque de 4 (como se mencionó anteriormente) en un punto específico, y dado que cada bloque de 4 reduce la puntuación en 4 puntos, el valor real es (2^k)(2k-4)-4, or 3932156. Lo cual aún es mucho más de lo que voy a puntuar...

Answer 5

¿No es teóricamente posible obtener 131072? 16 cuadrados en el tablero. 2^16 = 65536 Agregue un poder a 2 porque la pieza de inicio más posible es 2^2 en lugar de 2^1.