37 votos

Máxima posición en el tablero en la partida de 2048

Un juego llamado 2048 está haciendo rondas en los medios sociales. Estoy tratando de determinar la máxima puntuación posible para este juego. Asumamos que el WLOG sólo devuelve 2s (si 4s son posibles la puntuación máxima se duplica).

Primero, relajaré algunas de las reglas para crear un juego, $ \mathcal {G}$ que puede alcanzar una puntuación al menos tan alta como la original, 2048 juego. Una carrera $R$ de $ \mathcal {G}_n$ consiste en una secuencia de movimientos $m_1, \ldots ,m_k$ que manipulan un multiset, $ \mathcal {S}$ del tamaño máximo n. Cada uno $m_i$ es cualquiera de los dos:

  • una puesta $p$ que inserta un 2 en $ \mathcal {S}$ o
  • una fusión, $ \alpha_i $ que sustituye a dos $2^i$ elementos de $ \mathcal {S}$ con un solo $2^{i+1}$ elt.

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

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

Nota: La posición final debe tener sólo valores únicos, de lo contrario una fusión y puesta sería posible en el aumento de la puntuación.

Afirmo que es $ \sum_ {i=1}^{n} 2^i$ pero no se le ocurrió ningún buen argumento de inducción. 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 peliagudo, y además no cubre todo el espacio.

17voto

DanielV Puntos 11606

Una tabla óptima justo antes de que el último número se juegue en 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 entonces un 4 cae por suerte en el cuadrado vacío dando el mayor número que se puede crear es $2^{17} = 131072$ . El hecho es que, para hacer un número $2^n$ Entonces tienes que tener todos los números $[4 \dots 2^{n-1}]$ ya presente en el tablero.

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

Esta posición del tablero se puede construir fácilmente teniendo siempre una secuencia creciente en las casillas no vacías del camino que comienza en la parte 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 que el siguiente número caiga en la última casilla vacía del camino.

Además, esto resulta ser una estrategia muy eficaz para jugar el juego con gotas no óptimas también.

Editar: James Grime al rescate de nuevo. Hizo un video de youtube bastante entretenido para abordar esta cuestión.

3voto

David Puntos 137

Para empezar, encontremos el mayor número posible que puede entrar en el juego. Y para facilitarnos la vida, vamos a trabajar con el logaritmo de los números.

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

Por lo tanto, para un $m\times m$ tablero el mayor número puede ser $m^2 + 1$ . Con el mismo razonamiento, la tabla máxima se llenará con $m^2 + 1, m^2, m^2 - 1,...,3,2.$

Cada bloque del tablero se hace añadiendo otros dos bloques. Omitiendo el cálculo, para un bloque de valor $2^k$ el máximo de puntos conseguidos por el bloque es $(k-1)2^k - 4$ . Si se observa la forma en que se están haciendo los puntos, esto es fácilmente alcanzable.

Por lo tanto, la puntuación máxima que se puede hacer 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 demostrar por inducción.

Con ello, 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)$

1voto

Usor Puntos 11

Creo que se puede construir el tablero de máxima puntuación de Flowers por inducción con bastante facilidad (dado que controlamos la colocación en este juego). En primer lugar, sólo para establecer esto, vamos a estar de acuerdo en que:

  1. (WLOG con respecto a qué lado/esquina se utiliza) un tablero maximizado tendrá su valor más alto en la esquina superior/izquierda, disminuyendo secuencialmente los valores que van a la derecha a lo largo de 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, disminuyendo secuencialmente los valores a 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 de un cuadrado ( $n\times n$ ), puede obtenerse a partir de una cuadrícula inicialmente vacía (esto es obvio, ya que si se mueve sólo a la izquierda/derecha dentro de una misma columna se obtendrá $2^n$ , luego muévelos todos hacia la derecha y luego apílalos).

Una vez que estamos de acuerdo con el punto 2, entonces todo lo que necesitamos es la hipótesis de inducción: - $2^{(n-1)^2}$ se puede obtener en un lugar inicialmente vacío $(n-1)\times(n-1)$ subgrid.

Así que cuando se pone el $2^{n^2}$ en la parte superior izquierda queda mucho espacio para empezar a construir el siguiente componente de la serpiente (a saber, $2^{(n-1)^2}$ ) ya que un $(n-1)\times(n-1)$ subgrid permanece, más un $(n-1)$ cuadrados en los bordes superior e izquierdo.

Ah, sí, y para el caso base (un $2\times2$ rejilla) no es difícil de averiguar por su cuenta (lo hice en papel para estar seguro, sólo que no hay un formato conveniente para mí para escribir el procedimiento).

EDIT: Se me olvidó mencionar esto, pero según sus reglas parece que no estamos obligados a alternar entre un movimiento de izquierda/derecha/arriba/abajo frente a una colocación de fichas, ¿correcto? Esto significa que, por ejemplo, puedo empezar llenando una fila con 2's y luego simplemente desplazarlos todos juntos con varios movimientos a la derecha en secuencia.

0voto

Bienvenido David Puntos 131

¿No es teóricamente posible conseguir 131072? 16 casillas en el tablero. 2^16 = 65536 Suma una potencia a 2 porque la pieza inicial más alta posible es 2^2 en lugar de 2^1.

0voto

slinkp Puntos 1154

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 la gente significa los puntos ganados al fusionar bloques, mientras que Isaac parece estar usando la palabra para significar el valor máximo mostrado en un solo bloque. Utilizaré la definición de la mayoría. Y me disculpo por no tener un acceso rápido y práctico a todos los símbolos y superíndices; por favor, tened paciencia.

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

Por desgracia, no puedo ofrecer una prueba rigurosa, pero puede ofrecer mis números y dejar que ustedes hagan de ellos lo que quieran. Principalmente hablaré del juego estándar, del que la variante de Isaac podría considerarse un subconjunto, ya que no incluye los 4 bloques.

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

El valor máximo de puntuación de un bloque determinado valorado 2^k, según mi razonamiento, es (2^k)(k-1). Como, o bien estoy interpretando mal la fórmula de Flowers, o bien he llegado a una conclusión diferente, razono de la siguiente manera: como la puntuación se gana cada vez que se fusionan bloques, el número máximo de fusiones para crear un bloque de 2^k se haría con bloques de tamaño 2, y sería 2k-1. Para obtener la puntuación, imagine una línea de bloques de 2 lo suficientemente larga como para sumar el valor deseado de 2^k, y luego llévelos a través de sucesivas fusiones por pares (fusionando cada par de bloques adyacentes a lo largo de la línea en una sola operación) hasta terminar con el bloque único de 2^k. Cada una de estas fusiones por pares sumaría 2^k puntos. El número de fusiones por pares necesario sería (k-1).

Un breve ejemplo para ilustrar k=3: una línea de 2222 se fusiona en pares con 44 (cada 4 puntos, total 8), y luego se vuelve a fusionar en pares con 8 (con 8 puntos). Cada combinación de pares valía 2^k puntos, y se produjeron k-1 de ellos, por lo que (2^k)(k-1) para el valor total de la puntuación de 16.

Dado que en el juego real sólo pueden producirse fusiones de bloques iguales, y que cada valor 2^k debe construirse mediante fusiones sucesivas, no encuentro ninguna razón lógica para que este método no derive el máximo valor de puntuación posible para un bloque 2^k dado. Sin embargo, como a veces aparecen bloques de 4 en el juego, el actual La puntuación obtenida puede ser menor... de hecho, será 4 puntos menos 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, por tanto, 2097152. Para la variante de Isaac (k=16) sería 983040.

A partir de esa base de puntuación máxima posible de un solo bloque, y conociendo la posición máxima del tablero, podemos entonces sumar las puntuaciones máximas de cada bloque en ese tablero para obtener una puntuación máxima posible para todo el tablero. Reconozco que en este punto he hecho "trampa" y he utilizado Excel para hacer los totales y luego he deducido la fórmula a partir de ellos, 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 sea 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, que te aseguro que es una puntuación mucho más alta que la que yo he obtenido. Sin embargo, esta suma no tiene en cuenta el hecho de que para que se produzca el bloque k=17, tiene que haber aparecido un bloque 4 (como se ha dicho antes) en un punto concreto, y como cada bloque 4 reduce la puntuación en 4 puntos, el valor real es (2^k)(2k-4)-4, es decir, 3932156. Lo cual sigue siendo mucho más alto de lo que voy a puntuar nunca...

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X