Probabilidad de que los movimientos aleatorios en el juego 204

Question

Recientemente he jugado al juego 2048 creado por Gabriele Cirulli, que es divertido. Te sugiero que lo pruebes si no lo has hecho. Pero mi hermano me planteó esta pregunta sobre el juego:

Si escribiera un guión que realizara movimientos aleatorios en el juego 2048, ¿cuál es la probabilidad de que gane la partida?

La combinatoria no es mi área, así que ni siquiera intenté responder a esto, sabiendo que parece una pregunta difícil de responder. Pero pensé que alguien aquí podría tener una buena idea.

Además, como no nos preocupa el tiempo, sino sólo el hecho de ganar, podemos suponer que cada movimiento aleatorio da lugar a que se mueva una ficha.

Apéndice

Aunque las respuestas que aparecen a continuación arrojan luz sobre el problema, sólo BoZenKhaa se acercó a proporcionar una probabilidad, aunque fuera un límite superior. Así que me gustaría modificar la pregunta a:

¿Podemos encontrar límites superiores e inferiores decentes para esta probabilidad?

Answer 1

Implementé una simulación de 2048, porque quería analizar diferentes estrategias.

Como es lógico, el resultado es que moverse al azar es una estrategia realmente mala. Arriba puede ver las puntuaciones de $1000000$ juegos al azar (edit: actualizado tras la corrección de errores, gracias a misof ). La puntuación se define como la suma de todos los números generados por la fusión. Puede verse como una medida de lo lejos que llegas en el juego. Para ganar necesitas una puntuación de al menos $16384$ . Puede ver que la mayoría de los juegos terminan en una región a continuación $2000$ es decir, que generan como máximo un taco de 128 y lo pierden posteriormente. El montón de la derecha en $2500$ representa a los juegos que consiguen generar una ficha de 256 - esos juegos son bastante raros. Ningún juego llegó a los 1024 azulejos.

A petición, aquí está la trama para el número más alto en un azulejo: En lo que respecta a las "estrategias tontas", se obtienen mejores resultados realizando movimientos en bicicleta de forma determinista: mover hacia arriba, derecha, arriba, izquierda y repetir. Esto mejora el número más alto esperado en una ficha.

Puedes hacer tus propios experimentos utilizando el código aquí y aquí .

Answer 2

En lugar de intentar obtener una respuesta exacta, permítanme darles una estimación basada en una intuición muy aproximada, basada en algunas observaciones sobre el juego y una pregunta relacionada en el SO:

• Antes de llegar a la ficha de 2048, necesitarás tener al menos 10 fichas de diferentes valores en el tablero: $2,4,8,16,32,64,128,256,512$ y $1024$ .
• Tendrá que hacer por lo menos $520$ movimientos para llegar a la ficha de 2048 (cada vez que haces un movimiento, la suma de fichas en el tablero aumenta como máximo en 4).
• Este es el impresionante post en SO referente al mismo juego: https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048 . Cabe destacar que el mejor algoritmo mencionado en una de las respuestas ha afirmado tener una tasa de éxito de alrededor del 90%, es decir, no llega a ganar siempre.
• En el mencionado post, se sugiere que una buena estrategia ganadora es seleccionar un lado, digamos el superior, y luego tratar de no mover nunca su número más alto de ese lado. También se sugiere que si usted tiene que mover los números altos lejos de este lado de elección, puede ser difícil de salvar el día y todavía ganar.

Ahora, en aras de dar una estimación pseudo-rudimentaria, consideremos la idea de que el último punto es correcto sobre la estrategia ganadora y que esta estrategia cubre la mayoría de las estrategias ganadoras.

A continuación, imaginemos que nuestro Algoritmo Aleatorio (RAT) ha llegado a la fase en la que la mitad del tablero está cubierta por números diferentes, lo que significa que hay 8 números diferentes en el tablero $2,4,8,16,32,64,128, 256$ . Esto significa que estamos en el número de movimiento a lo sumo alrededor de $256 = \frac{1}{2}{\sum_1^{8} 2^k}$ .

Además, nuestra RAT ha llegado milagrosamente hasta aquí y ha conseguido mantener sus altos números en la parte superior del tablero, como en el último punto. Para la suposición final, asuma que si la RAT presiona la flecha inferior, siempre perderá el juego (porque es tan aleatorio, que no podrá salvar la situación).

Ahora, la posibilidad de que nuestro RAT gane después del movimiento 256 es seguramente menor que la posibilidad de que el RAT no presione la flecha inferior. Hay $3/4$ probabilidad de que el RAT no pulse la flecha hacia abajo en cada movimiento, y hay al menos 256 movimientos que hacer antes de que el RAT pueda conseguir la ficha de 2048. Por lo tanto, la probabilidad de que la RAT gane en nuestro escenario simplificado es menor $\frac{3}{4}^{256} \leq \frac{1}{2^{32}}$ .

$P=\frac{1}{2^{32}}$ hace que sea una ocurrencia bastante rara. Según el comentario de N.Owad, esta probabilidad es MUCHO menor que la de elegir un segundo específico desde el comienzo del universo. Esto debería darte una idea de lo improbable que es una victoria al azar en este juego.

Descargo de responsabilidad : No pretendo que P sea un límite de ningún tipo para la probabilidad real de ganar al azar debido a la naturaleza de las simplificaciones realizadas. Sólo trata de ilustrar un número que es probablemente mayor que la probabilidad de ganar al azar.

Answer 3

(Publicaría esto como un comentario, no como una respuesta separada, pero, por desgracia, como nuevo usuario no tengo la reputación. Culpa de los spambots.) Además, ten en cuenta que el contenido de esta respuesta es en parte un reenvío de mi puesto en Quora hace unos días).

La respuesta a la pregunta que se hace: Como ya se ha sugerido en otras respuestas, la probabilidad de ganar el juego haciendo movimientos al azar es esencialmente cero.

Algunos detalles más:

Las estadísticas en la respuesta de @benh son incorrectas. Hay al menos un error que conozco en su código, y hace que las estadísticas que ha publicado sean más bajas de lo que deberían. El error que veo está en cómo detecta el final del juego. En sus simulaciones, él termina el juego tan pronto como el tablero se llena. Sin embargo, en 2048 el juego sólo termina una vez que eso sucede y no hay dos fichas adyacentes que compartan el mismo número.

A continuación se muestran los resultados de mis simulaciones con una condición de terminación adecuada.

Estadísticas de las fichas más grandes para 5.000.000 de partidas, cada movimiento elegido uniformemente al azar:

  8:      78
 16:   13300
 32:  338969
 64: 1872573
128: 2382743
256:  391386
512:     951

Valor esperado de la ficha más grande al final de la partida: ~107.32

enlace a mi código

Answer 4

Desgraciadamente no tengo tiempo para hacer esto ahora mismo, pero aún así quiero pasar esta idea de cómo abordar este (muy difícil) problema.

Este método se asemeja en cierto modo al que se utiliza a menudo en la física estadística. Cf también a la teoría ergódica y similares (tendríamos que demostrar la ergodicidad.... pero bueno...).

Para cada campo almacena una matriz de probabilidades de que este campo en particular esté en el estado 0 (desocupado), 1 (tiene el número $2^1$ ), 2 (número $2^2$ ), ..., 11 (campo ganador $2^{11} = 2048$ ).

Dejemos que $P(i,j,x)$ denotan la posibilidad de que el campo con coordenadas $(i,j)$ está en el estado $0\le x \le 11$ .

Cada movimiento (arriba, izquierda, derecha, abajo) tiene un efecto claramente definido que puede expresarse como un conjunto de reglas, por ejemplo $$P'(i,j,x) = \underbrace{P(i,j,x)}_{\text{already was in this state}} - \underbrace{P(i,j,x) * (P(i+1,j,x)+P(i+1,j,x))}_{\text{leaves this state due to a join or move to the right}} + \underbrace{P(i,j,x-1)*P(i-1,j,x-1)}_{\text{joines this state due to join from the left}} + \dots $$ donde $\dots$ representa los términos más largos debido a las baldosas en movimiento (por ejemplo, en algún lugar a la derecha es una baldosa vacía y a la izquierda de mí fue el valor $x$ en el último paso).

La inserción de números aleatorios simplemente disminuirá la probabilidad de que cada campo esté desocupado y aumentará, respectivamente, el estado $x=1$ y $x=2$ oportunidades $$ P'(i,j,1) =P(i,j,1) + P(i,j,0)/16 \\ P'(i,j,2)=P(i,j,2) + P(i,j,0)/16 \\ P'(i,j,0)=P(i,j,0)*\frac{14}{16}\,. $$

Cualquier movimiento y el paso de inserción aleatoria se alternan en nuestro estado actual (los vectores de probabilidades). La probabilidad de perder en el paso actual es igual a la probabilidad de que todos los campos estén ocupados antes del paso de inserciones aleatorias. La probabilidad de ganar es la probabilidad de que cualquier campo esté en el estado $x=11$ después del movimiento elegido.*

Es evidente que las probabilidades debe estar correlacionados. Suponer que no lo están equivale en cierto modo al caos "molecular" que se supone en la física estadística/teoría ergódica. Pero, suponiendo que efectivamente seamos ergódicos con esta descripción del modelo, podemos obtener la posibilidad de ganar el juego después de $n$ pasos predefinidos (y no perderlo antes) iterando este $n$ tiempos. De esta forma se podrían comparar fácilmente diferentes estrategias, pero aún así habría que probar varias cadenas de movimientos al azar para obtener una media decente. (Sólo promediamos implícitamente sobre todas las posiciones posibles del $2$ y $4$ campos)

---

(*) Nótese que tenemos que eliminar cualquier estado ganador de nuestro vector de posibilidades antes de cada inserción aleatoria. Está claro que no hemos ganado todavía si seguimos jugando. (También esto es necesario para tener alguna posibilidad de ser ergódico)

Answer 5

$3.3\times10^{-32}$

Este resultado se ha conseguido utilizando 5 ejecuciones de simulación de ramificación con la siguiente configuración: Ejecutar 16777216 simulaciones de juego simultáneas. Cuando quede menos de la mitad de ellas, haga un clon de cada simulación restante. Ponderar el resultado de cada simulación en relación con la "generación" en la que termina, de modo que las simulaciones que terminen antes de la primera rama contarán para $1/16777216$ . Después de una rama es $1/33554432$ Después de dos $1/67108864$ y así sucesivamente.

Este método garantiza que cada simulación original tenga el mismo peso en el resultado final, mientras que la simulación sigue funcionando mucho más allá del punto en el que las simulaciones estándar se habrían detenido.

Debería ser obvio que, si se realizan suficientes simulaciones, el resultado medio convergerá hacia la respuesta. La parte menos obvia es que lo hace mucho más rápido que una simulación estándar. Esto sólo es posible debido a la naturaleza del juego y de la pregunta formulada, cuyas propiedades cruciales son las siguientes

• Estamos buscando una probabilidad muy baja.
• La variación de la probabilidad de éxito de cada nodo de la simulación es limitada, es decir, el juego no tiene "superestados" en los que la probabilidad de éxito sea anormalmente grande en relación con el estado medio del juego al mismo nivel de progreso.
• Existe un estado de fallo fácilmente identificable que puede utilizarse para podar la colección de simulaciones.

Teniendo en cuenta estas limitaciones, el juego y la pregunta parecen perfectos para el método de solución. Aunque hay una variación significativa en la probabilidad de éxito entre los nodos, no es tan grande como para que unos pocos nodos puedan dominar en una colección de varios millones.

Hasta ahora, el único medio para estimar la precisión del resultado que tengo es la comparación de los resultados de diferentes ejecuciones. Los resultados de 5 ejecuciones:

$$3.29\times10^{-32}$$ $$3.43\times10^{-32}$$ $$3.33\times10^{-32}$$ $$3.30\times10^{-32}$$ $$3.31\times10^{-32}$$

Mañana intentaré poner en línea el código fuente.