Simple juego de dados: estrategia Óptima?

Question

Aquí está la descripción de un juego de dados que me intriga desde hace bastante tiempo (el juego viene de un libro que ofrece una bastante insatisfactoria solución - pero entonces, su enfoque era el de programación, así que probablemente este sea excusable).

El juego va como sigue:

Dos jugadores juegan uno contra el otro, comenzando con una puntuación de 0 cada uno. El ganador es el jugador para llegar a un puntaje de 100 o más. Los jugadores juegan por turnos. El puntaje agregado en cada ronda se determina de la siguiente manera: El jugador tira un dado. Si al morir no muestran un 1, se tiene la opción de parar y tener los puntos que se suman a su puntuación, o para continuar lanzando hasta que se detiene o se pone un 1. Tan pronto como se pone un 1, su turno termina y no se agregan puntos a su puntuación, los puntos que ha acumulado en esta ronda se pierden. Después es el segundo turno del jugador.

La pregunta es ahora, ¿cuál es la mejor estrategia para ese juego. El libro sugerido para probar cual de las dos estrategias siguientes se da un mejor resultado:

• Tirar 5 veces (si es posible), luego se detiene.
• Si los puntos acumulados en esta ronda añadir hasta 20 o más, detener, de lo contrario continúe.

La razón es que desea que el siguiente tiro para aumentar la puntuación esperada. Por supuesto, no necesita pruebas para ver que la segunda estrategia es mejor: Si usted ha acumulado por ejemplo, 10 puntos, no importa si has acumulado con 5 veces lanzando un 2, o 2 veces lanzando un 5.

Sin embargo, también es fácil ver que esta segunda estrategia no es la mejor: Después de todo, el objetivo final no es para maximizar el aumento por todo el año, pero para maximizar la probabilidad de ganar.; ambos están relacionados, pero no el mismo. Por ejemplo, imagine que ha sido muy mala suerte y se encuentran todavía en una puntuación muy baja, pero su oponente ya ha 99 puntos. Es tu turno, y que ya ha acumulado algunos puntos (pero esos puntos no se puede conseguir por encima de 100) y tienen que decidir si parar o seguir. Si se detiene, se fijan los puntos, pero tu oponente tiene una 5/6 oportunidad de ganar en el siguiente movimiento. Digamos que si se detiene, la estrategia óptima en el siguiente paso será intentar conseguir 100 puntos en una carrera, y que la probabilidad de alcanzar ese es $p$. A continuación, si se detiene, ya que su oponente, entonces, tiene su oportunidad de ganar el primer, el total de la probabilidad de ganar es $1/6(p + (1-p)/6 (p + (1-p)/6 (p + ...))) = p/(p+5)$. Por otro lado, si usted continúa a 100 puntos, ahora mismo, usted tiene la oportunidad de $p$ a ganar esta ronda antes de que el otro tiene la oportunidad de intentarlo, pero una menor probabilidad de $p'$ para ganar en rondas posteriores, dando una probabilidad de $p + p'/(5+p')$. Es obvio que incluso si tuviéramos $p'=0$ (es decir, si usted no tiene éxito ahora, vas a perder), usted todavía tiene la probabilidad de $p>p/(p+5)$ ganar por continuar, por lo que debe seguir no importa cuán delgado de sus posibilidades, y aun si sus puntos acumulados de esta ronda son superiores a los 20, porque si te detienes, la oportunidad será peor, seguro. Ya que en algún momento, la estrategia óptima se tiene un paso en el que intenta ir más allá de los 100 (porque es donde gana), por inducción se puede decir que si tu oponente tiene ya 99 puntos, su mejor estrategia es, incondicionalmente, para intentar conseguir 100 puntos en una carrera.

Por supuesto, esta "fuerza bruta de la regla" es para esa situación específica (también se aplica si el oponente tiene 98 puntos, por razones obvias). Si quieres jugar a que la fuerza bruta de la regla desde el principio, se iba a perder, incluso en contra de alguien que sólo se lanza una vez cada ronda. De hecho, si ambos son iguales, y lo suficientemente lejos de la final de los 100 puntos, intuitivamente creo que los 20 puntos de la regla es bastante buena. También, intuitivamente creo que si está muy avanzada en contra de su oponente, usted aún debe jugar más seguro y parada antes.

Como la actual situación de juego es descrito por los tres números de su puntuación ($Y$), la puntuación de tu rival ($O$) y los puntos recogidos en esta ronda ($P$), y su decisión es continuar ($C$) o dejar ($S$), una estrategia es completamente determinado por una función $$s:\{(Y, O, P)\}\to \{C,S\}$$ donde las reglas siguientes son obvias:

• Si $Y+S\ge 100$ $s(Y,O,P)=S$ (si ya han acumulado 100 puntos, la única razonable movimiento es la parada).
• $s(Y, O, 0)=C$ (no tiene sentido parar antes de que se lanzara al menos una vez).

También, acabo de arriba deriva la siguiente regla:

• $f(Y,98,P)=f(Y,99,P)=C$ menos que la primera regla de patadas en el.

Yo creo que la siguiente regla debería también llevar a cabo, pero que no tienen idea de cómo demostrarlo):

• Si $f(Y,98,P)=S$ también $f(Y,98,P+1)=S$

Si que creen que es la verdadera, a continuación, la descripción de una estrategia puede ser simplificada a una función de $g(Y,O)$, lo que da a los más pequeños a $P$ a que se debe detener.

Sin embargo, eso es todo lo que hemos averiguado. Lo que realmente me gustaría saber es: ¿Cuál es la estrategia óptima para este juego?

Answer 1

Cuando ambos están lejos de la meta, se debe maximizar la espera de puntos por turno. El esperado regreso de otro lanzamiento es $\frac 56 (2+3+4+5+6) - \frac 16 P$, que dice que usted debe dejar de arriba $20$ y hacer lo que quieras en $20$. Tienes razón esto se perturba cuando estés cerca de la final.

Answer 2

No hay ninguna descripción simplificada del equilibrio de Nash de este juego.

Usted puede calcular la mejor estrategia a partir de las posiciones donde ambos jugadores están a punto de ganar y va hacia atrás desde allí. Deje $p(Y,O,P)$ la probabilidad de que usted gana si usted está en la situación de $(Y,O,P)$ y si tomar las mejores decisiones. La dificultad está en que para el cálculo de la estrategia y la probabilidad de ganar en alguna situación $(Y,O,P)$, de hacer su elección en función de la probabilidad de $p(O,Y,0)$. Así que usted tiene un (a trozos afín y contratación) función decreciente $F_{(Y,O,P)}$ tal que $p(Y,O,P) = F_{(Y,O,P)}(p(O,Y,0))$, y, en particular, es necesario encontrar el punto fijo de la composición, $F_{(Y,O,0)} \circ F_{(O,Y,0)}$ a fin de encontrar el verdadero $p(O,Y,0)$, y deducir de todo desde allí.

Después de hacer este cálculo para un total de 100 puntos juego y algunas de la inspección, no hay ninguna función $g(Y,O)$ de manera tal que la estrategia se simplifica a "parar si usted acumulado $g(Y,O)$ o más puntos". Por ejemplo, en $Y=61,O=62$,usted debe parar cuando usted tiene exactamente $20$ o $21$ puntos, y continuar de otra manera.

Si dejas $g(Y,O)$ el menor número de puntos de $P$ tal que debe dejar a $(Y,O,P)$, $g$ no se ve muy bien en todo. No es monótono y hace cosas extrañas, excepto en la región donde usted debe seguir jugando hasta que lo pierde o gana en $1$ mover.