Juego de dados muy sencillo

Question

Dos jugadores compiten por alcanzar un determinado número N de puntos (por ejemplo 100) para ganar la partida lanzando cada uno dos dados normales y anotando la cantidad acumulada desde su primera tirada. Así, el primer jugador que alcance N puntos gana la partida.

Cada partida comienza con una apuesta de S dólares. Se lanza una moneda justa para designar al primer jugador.

Cuando un jugador que va a tirar siente que tiene una ventaja suficiente, puede optar, antes de tirar los dos dados, por ofrecer doblar la apuesta del juego a 2S dólares. El jugador contrario puede:

-rechazar la oferta, pero conceder el juego al hacerlo y perder S dólares, O

-aceptar la oferta: entonces la apuesta del juego se duplica (a 2S). Cuando un jugador acepta un doble, toma el control del derecho a (re)doblar la apuesta y es el único jugador que puede hacer la siguiente oferta de un nuevo doble (a 4S), etc.

Suponiendo que el jugador que tira ha alcanzado s1 puntos (N-s1 para ir a N) y su oponente tiene s2 (N-s2 para llegar a N), cómo calcular si y cuándo:

-debe ofrecer doblar (redoblar)

-su oponente debe aceptar

Answer 1

Es fácil calcular la estrategia óptima para $N$ razonablemente pequeño (digamos, hasta $N \le 10000$ ). Sólo hay que iterar hacia atrás desde el final del juego. Hay tres posibles estados de duplicación:

1. Ambos jugadores tienen derecho a doblar (es decir, nadie ha doblado todavía);
2. Tienes derecho a doblar;
3. Su oponente tiene derecho a doblar.

Tenga en cuenta que el número que aparece actualmente en el dado de doblar -para usar el término de backgammon- es irrelevante para su estrategia (aunque no es irrelevante para su ganancia/pérdida esperada).
Así que para cada estado de duplicación $s \in \{1,2,3\}$ se quiere calcular la ganancia esperada $E(s,x,y)$ expresado como un múltiplo del número del dado de duplicación, donde $s$ es el estado de duplicación, $x$ es el número de puntos que necesitas para ganar, y $y$ es el número de puntos que su oponente necesita para ganar.
$x$ y $y$ no pueden ser ambos cero, por lo que podemos empezar a rodar la pelota con $E(s,0,y) = 1$ , $E(s,x,0) = 0$ . Luego hay que establecer una serie de ecuaciones sencillas pero tediosas que expresan $E(s,x,y)$ en términos de $E(s', x', y)$ para $x' < x$ y todos los valores de $s$ y $s'$ . Entonces puedes trabajar hacia atrás para calcular $E(s,x,y)$ para todos $s,x,y$ .
Los detalles son, como he dicho, tediosos, y no voy a detallarlos a menos que me pagues. Sólo ten en cuenta que tienes que almacenar los valores intermedios en una tabla de tamaño $3N^2$ . No te dejes seducir por la solución recursiva obvia: su complejidad asintótica es exponencialmente peor.