Hace poco me encontré con un juego flash en línea que presenta una cuadrícula de m por m y la entrada del pad direccional (arriba, abajo, izquierda, derecha). En cualquier momento del juego, la cuadrícula contiene números ("bloques") del conjunto $\{2^i\},1\le i\lt n$ . Así, en cada paso del juego, cada celda de la cuadrícula está vacía o contiene un bloque de este tipo.
El juego procede en pasos discretos, con el jugador eligiendo una dirección para mover los bloques (es decir, las celdas no vacías) en la cuadrícula; todos los bloques se mueven en la dirección especificada por el jugador, si pueden - pero por ejemplo, si una fila entera está llena de bloques, un movimiento a la izquierda o a la derecha por parte del jugador no moverá ningún bloque, asumiendo que ninguno de los bloques es elegible para ser "fusionado" entre sí, como explicamos más adelante.
Los bloques pueden fusionarse si tienen el mismo número y, naturalmente, el valor del bloque resultante es el doble del de cualquiera de los bloques de entrada. Es decir, los bloques se suman. Si dos bloques cumplen los requisitos para fusionarse, se fusionarán si son adyacentes y si la dirección especificada por el jugador mueve un bloque hacia el otro; así que podemos decir que un bloque ("bloque de origen") se "fusiona con" otro ("bloque de destino"), con el primero moviéndose en la dirección especificada por el jugador, y el segundo permaneciendo en su sitio. Entonces, todos los bloques "detrás" del bloque de origen también se mueven en la dirección especificada y, por supuesto, los bloques "a partir" del bloque de destino permanecen en su sitio. Todo esto es muy intuitivo desde el punto de vista del jugador, pero quizá merezca la pena explicarlo.
El jugador gana si dos bloques se fusionan en un bloque con valor $2^n$ pero pierde si la cuadrícula se llena y no hay fusiones que hacer. La fuente de aleatoriedad en el juego es la aparición aleatoria de bloques con valor $2$ o $4$ Estos bloques también pueden aparecer en una posición ya ocupada por un $2$ o $4$ respectivamente, en cuyo caso el nuevo bloque se fusiona con el antiguo. Pero hay que tener en cuenta que esta posible fusión sólo puede tener lugar DESPUÉS de que los bloques se hayan movido, según la elección de la dirección del jugador. En cualquier caso, la posición o posiciones del nuevo bloque se eligen uniformemente entre el conjunto de celdas vacías que unen el conjunto de bloques fusionables para ese nuevo bloque (es decir, el conjunto de $2$ o $4$ bloques, respectivamente).
Así que la pregunta es, dado $m$ y $n$ El jugador debe hacer movimientos al azar, y un pequeño conjunto de bloques de partida adecuados, cuál es el tiempo esperado hasta que el juego se detenga, ganando o perdiendo el jugador ? Más allá de un nivel elemental, no puedo imaginar cómo proceder para resolver realmente el problema, así que me detendré aquí (no soy matemático). Pero espero que la explicación haya sido lo suficientemente clara, aunque no estoy 100% seguro de que el problema sea realmente solucionable tal y como está planteado. (Por ejemplo, ¿existe aquí una noción bien definida de lo "esperado"? ?)
De todos modos, aquí hay un ejemplo del juego para $m = 4$ y $n = 11$ que probablemente hará que el problema sea mucho más claro en comparación con la explicación anterior, pero pensé en proporcionar la explicación de todos modos en aras de la exhaustividad.
http://gabrielecirulli.github.io/2048/
Y otra, para $m=8$ y $n=53$ que cuenta con un mecanismo para jugar automáticamente jugadas al azar:
http://www.csie.ntu.edu.tw/~b01902112/9007199254740992/
NOTAS
En aras de la coherencia entre las respuestas, supongamos que la cuadrícula está vacía para empezar. Por supuesto, cualquiera es bienvenido a cambiar esto / solicitar que se cambie si hay una mejor opción de bloques de inicio.
Siguiendo el comentario de Dpiz más abajo, pensé que también podríamos considerar las probabilidades de inserción uniforme de $2$ y $4$ (como se ha comentado anteriormente) sean iguales, es decir, cualquiera de los dos números tiene la misma probabilidad de ser elegido para ser insertado en una celda elegible. Pero, a continuación, observe que, en un momento dado del juego, el conjunto de celdas elegibles para la inserción aleatoria por $2$ puede ser de un tamaño diferente al de $4$ en particular, aparte de las celdas vacías que son elegibles para ambos números, un $2$ puede ser insertado aleatoriamente donde un $2$ existe (y por lo tanto se fusiona inmediatamente en un $4$ ), mientras que un $4$ puede ser insertado donde un $4$ existe, siendo igualmente fusionado inmediatamente en un $8$ . Así que no estoy seguro de si el algoritmo de inserción aleatoria debe elegir primero la celda de destino, y luego elegir el número que se colocará allí (en cuyo caso las probabilidades $2$ y $4$ que se inserta al azar en cualquier lugar dependerá del estado del juego); o si un número $a\in\{2,4\}$ se elige primero, y luego su destino se elige uniformemente entre las celdas elegibles para $a$ . Espero que haya quedado claro. En cualquier caso, no estoy seguro de lo que el juego real hace - parece que tal vez $2$ aparecerá ligeramente más a menudo que $4$ ? ¿Denotamos la probabilidad de que $2$ se selecciona para ser $\rho_2$ y de la misma manera $\rho_4$ para $4$ ?
Además, creo que es seguro limitar el problema a $n\ge 3$ para que no tengamos, por ejemplo, un $4$ siendo insertado al azar y terminando el juego.
