¿Cuál es el número esperado de movimientos necesarios para terminar un juego de serpientes y escaleras?

¡Buena pregunta! Me incitó a ejecutar un programa de simulación rápida de Monte Carlo en C. Los resultados son los siguientes:

[1] Uno de tus cabeza de serpiente está ambiguo. Asumí una cabeza de serpiente en la posición 89.

[2] El número promedio de turnos requeridos es 23.244 y el número promedio de tiradas de dados es 27.984. Estoy usando la regla de que si sacas un 6, continúas el turno con otro tiro libre.

[3] ¡El juego mínimo es de 3 turnos y 5 tiradas! ¡Eso fue interesante! ¡Necesitas tirar la secuencia 2–6–6–2–3 para terminar el juego en 5 rollos y 3 turnos!

[4] ¡El peor juego necesitaba 86 turnos y 101 tiradas de dados!

Si necesita el código C, ¡podría publicarlo!

¡Muchísimas gracias por la interesante pregunta que hizo mi día!

EDITAR:

[1] Gracias a David Rutter por su mejor sugerencia de juego que se completa en solo 2 turnos y 4 tiradas PERO no estoy cambiando mi respuesta ya que se basa en una simulación de Monte Carlo y en el mejor espíritu de una simulación de Monte Carlo: solo indica algunas características de lo que está buscando. Una comprensión matemática o lógica más profunda obviamente producirá una mejor solución.

[2] Alguien más señaló que el peor de los casos es de movimientos infinitos. Una vez más, quiero señalar que la simulación de Monte Carlo que ejecuté fue de solo 1000 simulaciones y puede haber perdido el máximo teórico.

[3] Inspirado por los comentarios, hice un poco más de análisis: dado que obtienes un tiro libre por cada 6 lanzamientos, la proporción del número promedio de lanzamientos al número promedio de turnos será la suma de las series infinitas 1 + 1 / 6 + 1/36 + 1/216 … lo que equivale a 1.2. ¡Mi simulación me dio esta proporción como 1.204! ¡No está mal para una simulación tonta!

[4] El programa C en sí:

#include

#include

#include

#include

#include

#define NUMRUNS 1000

int main (int argc, char ** argv)

{

int irun, jroll, kturn, dieroll, pos = 1, newpos;

semilla larga int;

ARCHIVO * outfile, * logfile;

outfile = fopen (“snakes.txt”, “w”);

archivo de registro = fopen (“snakeslog.txt”, “w”);

jroll = 0;

kturn = 0;

// seed = (long) time ();

// srand (semilla);

para (irun = 0; irun

{

hacer{

kturn ++;

hacer

{

jroll ++;

dieroll = 1 + 6 * rand () / (RAND_MAX + 1.0);

newpos = pos + dieroll;

if (newpos <= 100) pos = newpos;

printf (“% d% d% d% d”, kturn, jroll, dieroll, pos);

fprintf (archivo de registro, “% d% d% d% d”, kturn, jroll, dieroll, pos);

// serpientes

if (pos == 34) pos = 1;

si (pos == 25) pos = 5;

si (pos == 47) pos = 19;

si (pos == 65) pos = 52;

si (pos == 87) pos = 57;

si (pos == 89) pos = 69;

if (pos == 91) pos = 61;

// escaleras

si (pos == 3) pos = 51;

si (pos == 6) pos = 27;

if (pos == 20) pos = 70;

si (pos == 36) pos = 55;

if (pos == 63) pos = 95;

si (pos == 68) pos = 98;

printf (“:% d \ n”, pos);

fprintf (archivo de registro, “:% d \ n”, pos);

}

while (dieroll == 6);

} while (pos <100);

printf (“\ n% d% d \ n”, kturn, jroll);

fprintf (archivo de registro, “\ n [[% d \ t% d]] \ n”, kturn, jroll);

fprintf (outfile, “% d \ t% d \ n”, kturn, jroll);

jroll = 0;

kturn = 0;

pos = 1;

}

fclose (archivo);

fclose (archivo de registro);

devuelve 0;

}

Esto se puede resolver fácilmente con la programación dinámica.

El subproblema aquí es que estás en una posición X después de algunos no. de tiros Ahora, ¿cuál es el número esperado de lanzamientos? Pero esta no es información suficiente porque hay ciclos y terminaría en una recursión mientras calcula los movimientos esperados. Por lo tanto, su estado se vería en 2 dimensiones. 1) Posición actual, 2) Tiros realizados. Esto nunca terminará en un ciclo. Entonces puedes usar esto.

Asumo las siguientes reglas:
1) Estás tirando un dado imparcial.
2) Si sacas un 6, obtienes un tiro libre.
3) Supongamos que arrojas un número que te hace moverte fuera del tablero, es un lanzamiento desperdiciado.
Ejemplo: supongamos que está en 98 si lanza un 3 o 4 o 5, se queda en la misma posición.

float find_expected_throws (int pos, int throwsDone) {
if (pos == 100) {
devuelve tiros Hecho;
}
if (throwsDone> 300) // Útil para evitar la recursión infinita causada por la regla no. 3. La probabilidad de llegar aquí * throwsDone es insignificante.
{
devuelve tiros Hecho;
}

if (dp [pos] [throwsDone] ya encontrado)
return dp [pos] [throwsDone];

if (isLadderPos (pos)) {
return find_expected_throws (pos + ladderJump, throwsDone);
}
sino if (isSnakePos (pos)) {
return find_expected_throws (pos-snakeDrop, throwsDone);
}

flotador ans = 0;
para (i = 1 a 6) {
ans + = 1.0f / 6 * find_expected_throws (pos + i <= 100? pos + i: pos, i == 6? throwsDone: throwsDone + 1);
}
return dp [pos] [throwsDone] = ans;
}

Todavía hay un pequeño error en mi código … Supongamos que sigue rodando 6 repetidamente, será una recursión infinita porque sigue obteniendo tiros libres repetidamente … Una de las formas de resolver es agregar un tercer estado llamado freeThrows. La probabilidad de obtener 10 tiros libres al lado del siguiente es insignificante (6 ^ -10). Entonces puede manejarlo así.

float find_expected_throws (int pos, int throwsDone, int freeThrows) {
…
…
if (freeThrows> 10) // Útil para evitar la recursión infinita causada por la regla no. 2. La probabilidad de llegar aquí * throwsDone es insignificante.
devuelve tiros Hecho;
if (dp [pos] [throwsDone] [freeThrows] ya encontrado)
return dp [pos] [throwsDone] [freeThrows];
…
para (i = 1 a 6) {
ans + = 1.0f / 6 * find_expected_throws (pos + i <= 100? pos + i: pos, i == 6? throwsDone: throwsDone + 1, i == 6? freeThrows + 1: 0);
}
…
}

Cadena de Markov. La junta tiene 100 estados. Construya una matriz de Markov [matemática] M [/ matemática] de orden [matemática] 100 * 100 [/ matemática] donde [matemática] M (i, j) [/ matemática] es la probabilidad de pasar del estado i al estado j ( lea el estado como cuadrado aquí) en un solo movimiento. Denotemos la matriz M multiplicada k veces como [matemática] M ^ k [/ matemática]. Ahora [matemática] M ^ k (i, j) [/ matemática] es la probabilidad de pasar del estado i al jth en exactamente k movimientos.

Por lo tanto, el número esperado de movimientos es
[matemática] M (1,100) + 2 * M ^ 2 (1,100) + 3 * M ^ 3 (1,100) +…. [/ matemática]

Tenga en cuenta que [math] M [/ math] depende de la configuración del tablero, excepto en la última fila, que es [math] M (100, j) = 0 [/ math] cuando j no es 100.

Tenga en cuenta que después de lanzar un dado, la posición del jugador solo puede estar en un estado estable, es decir, la posición que no es el comienzo de la escalera o el final de la serpiente. Considere [math] E (S) [/ math] como el valor esperado para alcanzar la celda final (100 aquí) del estado [math] S [/ math] en el tablero. En este problema necesitamos calcular el valor de [math] E (1) [/ math], por la definición del valor esperado podemos escribir,

• [matemáticas] E (S) = 1 + \ dfrac {1} {6} * E (S ‘) [/ matemáticas]

donde [math] S ‘[/ math] son ​​todos los estados posibles a los que se puede acceder desde [math] S [/ math] en un solo tiro de un dado.

Como es un sistema de ecuación lineal de la variable [math] S [/ math], se puede resolver utilizando el algoritmo de eliminación gaussiano en [math] \ mathcal {O} (S ^ 3). [/ Math]