25 votos

Probabilidad de derrotar a un dragón en un turno lanzando un dado de 20 caras

En clase de matemáticas nos plantearon un problema opcional que no puedo resolver por mí mismo:

Estás luchando contra un dragón con 250 puntos de vida y tiras un dado de 20 caras para infligir daño. El dragón recibe el mismo daño que el número que salga en el dado, con 2 excepciones: Si sacas un 20 no infliges daño (el dragón es inmune al daño crítico) y si sacas un 1 rompes tu combo y el dragón te mata inmediatamente. Tiras hasta que el dragón es derrotado o sacas un 1 y rompes tu combo. ¿Cuál es la probabilidad de derrotar al dragón?

Mis planteamientos matemáticos incluían calcular el daño esperado por tirada $$ E_{ w }= \frac{ \sum_{ n=2 }^{ w-1 }{ n } }{ w } $$ donde $$ E_{ 20 }= 9.45 $$ y luego intente calcular la probabilidad de no fallar en el minimo numero de tiradas necesarias para derrotar al dragon pero al final eso me llevo a una probabilidad tan baja que cualquiera la consideraria 0 y para empezar no me parecio correcto.

Entendí que el problema es mucho más complejo de lo que parece, ya que la probabilidad cambia drásticamente con el número de tiradas antes de cualquier otra tirada y sus resultados.

Mediante pruebas empíricas con un pequeño programa python, la probabilidad de ganar resultó ser sólo de un 25%, lo que me sorprendió, dado que la probabilidad de infligir daño es del 90%.

¿Cómo se abordaría correctamente el problema e incluso dejarlo "parametrizado" para poder cambiar la HP del dragón y el número de caras del dado?

27voto

jldugger Puntos 7490

Su sugerencia de resolver una versión general del problema es acertada. Vamos a preparar esto.

El dado tiene dos resultados especiales: "muerte", que termina el proceso, y 0, que no tiene efecto. También podríamos eliminar el 0, creando un "dado truncado" de 19 caras. Sea la probabilidad de que el dado muestre un valor numérico $\omega$ sea $p(\omega)$ y que $p_{*}$ sea la probabilidad de muerte. $\Omega$ es el conjunto de todos estos posibles valores numéricos (sin incluir "muerte", que no es numérico).

Tu objetivo es alcanzar un total de $T$ antes de observar la "muerte". Cuando $T\le 0,$ ha alcanzado este umbral, por lo que la posibilidad de ganar es $1.$ De lo contrario, cuando $T \gt 0,$ dividir el evento "eventualmente gano" en los resultados numerados separados que ocurren dentro de $\Omega.$ Es un axioma de la probabilidad que la probabilidad de este suceso sea la suma de las probabilidades de sus componentes (no superpuestos).

$$\Pr(\text{Reach } T) = \sum_{\omega\in\Omega}p(\omega) \Pr(\text{Reach } T-\omega).$$

Este recursión puede llevarse a cabo con una sencilla forma de programa dinámico. A menos que los valores y las probabilidades sean muy especiales, no se puede esperar escribir una bonita fórmula cerrada para la solución. Basta con realizar el cálculo computando los valores de $T=1,$ $T=2,$ etc, en orden. (Esto se denomina "eliminando la recursividad de cola" en informática).

El número de cálculos realizados por este algoritmo es proporcional a $T$ veces el número de valores únicos en el dado truncado. Esto lo hace eficaz para $T$ y dados realistas.

Mediante un programa de este tipo (utilizando coma flotante de doble precisión) encuentro la posibilidad de alcanzar $T=250$ es $0.269880432506\ldots.$

Como dato realista, esperas infligir unos 9,5 puntos de daño por tirada, lo que sugiere que tardarás aproximadamente $250/9.5 \approx 27$ rueda para ganar. Pero en cada tirada hay un $1-1/20$ probabilidad de sobrevivir, por lo que su probabilidad de sobrevivir para entonces es $$(1-1/20)^{27} = \left[(1-1/20)^{20}\right]^{27/20} \approx \exp(-27/20) = 0.25924\ldots.$$

Es una respuesta bastante parecida a la que obtuve yo.

Como otra comprobación de la realidad, eso también se acerca a los resultados de tu simulación. De hecho, obtengo resultados de simulación comparables: no difieren significativamente de la respuesta exacta.

Te dejo que escribas el programa. Se necesitará una estructura de datos que pueda almacenar todos los valores de $\Pr(\text{Reach } T-\omega)$ que figura en la parte derecha de la fórmula. Considere la posibilidad de utilizar una matriz para ello, indexada por los valores $0,1,2,\ldots, T.$


BTW, hay otros métodos de solución. Este problema describe un Cadena de Markov cuyos estados son los valores totales que se han alcanzado (de $0$ a través de $T,$ ya que cualquier cosa mayor que $T$ bien podría combinarse con $T$ ), junto con un estado especial (absorbente) de "muerte". Esta cadena puede analizarse en términos de una gran matriz (que tiene $250+2$ dimensiones). En la práctica, esta formulación no tiene mucho valor, pero la teoría de las cadenas de Markov permite comprender el proceso. Puedes extraer de esa teoría información sobre tus posibilidades de ganar y sobre cuántas tiradas es probable que tardes en ganar si lo consigues.


Otro enfoque más se sugirió en un comentario a la pregunta: explotan una distribución geométrica. Se refiere a analizar el proceso en función de cuántas tiradas tendrá antes de morir. Para repartir puntos de golpe, imagina tirar el dado, con su cara de "muerte" quitada paralela a lanzar una moneda (sesgada), cuya función es determinar si mueres. (Así, en la situación de la pregunta, cada una de las 19 caras restantes del dado -incluida la $0,$ que debe dejarse dentro tiene un $1/19$ azar; más generalmente, el lado con valor $\omega$ tiene una oportunidad $p(\omega)/(1-p_{*}).$ ) Las dos caras de la moneda son "muerte" (con probabilidad $p_{*}$ ) y "continuar" (con probabilidad $1-p_{*}$ ). En cada turno tiras por separado el dado truncado y lanzas la moneda, acumulando puntos de golpe hasta alcanzar el umbral $T$ o la moneda sale "muerte".

Existe una simplificación, porque es fácil calcular la probabilidad de que nunca se produzca la "muerte" en el primer caso. $n=0,1,2,\ldots$ vueltas: es igual a $(1-p_{*})^n$ porque todas las vueltas son independientes. Formalmente, esto describe una variable aleatoria $N$ cuyo valor es igual a $n$ con probabilidad $p_{*}(1-p_{*})^{n}.$ (Esta es una distribución geométrica ).

Para modelar las tiradas del dado truncado, dejemos que $X_1$ sea su valor en la primera tirada, $X_2$ su valor en la segunda tirada, y así sucesivamente. La suma después de $n$ rollos por lo tanto es $S_n = X_1 + X_2 + \cdots + X_n.$ (Esta es una paseo aleatorio .) La probabilidad de alcanzar el umbral puede calcularse descomponiendo este suceso en la infinidad contable de posibilidades correspondientes al número de tiradas necesarias. Las reglas básicas de la probabilidad condicional nos dicen

$$\Pr(\text{Reach }T) = \sum_{n=0}^\infty \Pr(S_N\ge T\mid N=n)\Pr(N=n).\tag{*}$$

El lado derecho requiere que encontremos estas probabilidades de cada $S_n$ alcanzar el umbral. Aunque esto no es una gran simplificación para un dado general ( $S_n$ puede tener una distribución muy complicada) , conduce a una buena aproximación cuando es probable que el proceso realice muchas tiradas antes de morir o alcanzar el umbral. Esto se debe a que la suma de un gran número de las $X_i$ tiene aproximadamente una distribución Normal (según la Teorema central del límite ). Cuando la expectativa del dado truncado es $\mu$ (igual a $9.45/(1-0.05)$ en la pregunta) y su varianza es $\sigma^2,$ la distribución de $S_n$ tiene una expectativa de $n\mu$ y la varianza de $n\sigma^2$ (según las leyes básicas de la expectativa y la varianza aplicadas a las variables independientes $X_1,X_2,\ldots, X_n$ ). Escribir $\Phi(x;n\mu,n\sigma^2$ para la función de distribución Normal con expectativa $n\mu$ y varianza $n\sigma^2,$ obtenemos

$$\Pr(S_N\ge T\mid N=n) \approx 1 - \Phi\left(T-\frac{1}{2}; n\mu, n\sigma^2\right).$$

Introduciendo esto en $(*)$ junto con la ley de distribución geométrica da como resultado

$$\Pr(\text{Reach }T) \approx \sum_{n=1}^\infty \left(1 - \Phi\left(T-\frac{1}{2}; n\mu, n\sigma^2\right)\right)p_{*}(1-p_{*})^n.$$

En la práctica, podemos dar por terminada la suma en el momento en que $\sum_{i=n}^\infty p_{*}(1-p_{*})^i$ es inferior a un error tolerable $\epsilon\gt 0,$ porque el $\Phi$ nunca supera $1.$ Este límite superior es igual a $\log(p_{*}\epsilon)/\log(1-p_{*}).$ (Para la situación de la pregunta, ese límite superior está en torno a 418.) También podemos calcular un valor razonable para comenzar la suma (saltándonos los valores iniciales realmente pequeños). Eso nos lleva al código relativamente corto y sencillo que se muestra a continuación (escrito en R ). Su salida, obtenida mediante el comando dragon.Normal() es $0.269879\ldots,$ coincidiendo con la respuesta exacta con cinco cifras significativas.

# Use `NA` to specify the "death" sides of the die; otherwise, specify the 
# values on its faces.  `p` gives the associated probabilities.
dragon.Normal <- function(threshold=250, die=c(NA, 2:19, 0), p=rep(1/20,20), eps=1e-6) {
  #
  # Find and remove the "death" face(s) to create the truncated die.
  #
  i.death <- which(is.na(die))
  p.death <- sum(p[i.death])
  if (p.death <= 0) return(1)
  die <- die[-i.death]
  p <- p[-i.death]
  p <- p / sum(p)
  #
  # Compute the expectation and variance of the truncated die.
  #
  mu <- sum(die * p)
  sigma2 <- sum((die-mu)^2 * p)
  #
  # Establish limits for the sum.
  #
  N <- ceiling(log(eps * p.death) / log(1 - p.death))
  if (N > 1e8) stop("Problem is too large.")
  Z <- qnorm(eps)
  n <- min(N, max(1, 
       floor((Z * (1 - sqrt(1 + 4*threshold*mu/(Z^2*sigma2)))/(2*mu))^2 * sigma2)))
  #
  # Compute the sum.
  #
  n <- n:N
  sum(p.death * (1-p.death)^n * 
        pnorm(threshold - 1/2, mu*n, sqrt(sigma2*n), lower.tail=FALSE))
}

8voto

Creo que el método más comprensible para calcular probabilidades como éstas es definir una cadena de Markov que represente todos los estados posibles en los que puede estar el juego, con estados absorbentes que representen la muerte del jugador o del dragón.

Una cadena de Markov es un conjunto de estados junto con una matriz de transición de probabilidades asociada, donde las probabilidades de transición dependen sólo del estado actual. Almacenar todas las probabilidades de transición en una matriz es una cómoda herramienta de organización para calcular probabilidades condicionales compuestas como las que se encuentran en el juego.

En este ejemplo, puedes definir un estado separado para cada valor posible de daño que podría haber sufrido el dragón (de 0 a 249). Además, se necesitan dos estados absorbentes para representar cuando el jugador o el dragón mueren. En un estado de absorción, no hay escapatoria. Tienes un 100% de posibilidades de permanecer en ese estado eternamente.

A continuación, se definen las transiciones de probabilidad de cada estado. Por ejemplo, si has infligido 100 puntos de daño al dragón, tienes 1/20 posibilidades de pasar al estado 102 puntos de daño, 1/20 posibilidades de pasar al estado 103 puntos de daño, etc. hasta 119 puntos. También tienes 1/20 posibilidades de pasar al estado "muerte del jugador", y 1/20 posibilidades de quedarte en el estado 100 (si sacas un 20). Por ejemplo, si has infligido 249 puntos de daño, tienes 1/20 posibilidades de morir, 1/20 de quedarte en 249 y 18/20 de derrotar al dragón. Todas estas probabilidades se almacenan en una matriz de transición $P$ tal que $P_{ij} = $ la probabilidad de pasar del estado $i$ al estado $j$ .

Por último, define tu vector de distribución de probabilidad de estado inicial (en este caso tenemos un 100% de posibilidades de empezar en el estado de daño 0), y multiplica a la izquierda este vector por tu matriz de transición elevada a la potencia del número de veces que repites tus ataques. Así obtendremos las probabilidades exactas de estar en cada estado. En este juego, hay una posibilidad teórica de que la lucha dure arbitrariamente mucho tiempo si sigues lanzando golpes críticos. Una forma de evitar esta posibilidad es redefinir el juego para que funcione con un dado de 19 caras y eliminar la opción de golpe crítico, ya que en general es irrelevante para las probabilidades finales. Otra opción es simplemente atacar un gran número de veces, de forma que la probabilidad de que el combate no haya terminado sea esencialmente cero.

Ya que mencionaste Python, he escrito algunas funciones para ti que crean la matriz de transición de Markov y calculan las probabilidades de estado.

import numpy as np

def markov_matrix(hp,num_sides):
    #P is the transition matrix.
    # Need one state for each hp of the dragon, plus a 'player dies' state and a 'dragon dies' state
    # States 0-hp are damage done states, state -2 is 'player dies', state -1 is 'dragon dies'
    P = []

    for damage_done in range(hp):
        P_row = np.zeros(hp+2)

        #For each state, the probability for the player to die is 1/num_sides.
        P_row[-2] = 1/num_sides

        #Otherwise, there is an equal probability to deal 2 or more damage.
        for hit_damage in range(2,num_sides):
            new_state_index = damage_done+hit_damage

            #If the total damage would be enough to kill the dragon, that probability is added to the 'dragon dies' state.
            if new_state_index >= hp:
                P_row[-1] = P_row[-1] + 1/num_sides
            else:
                P_row[new_state_index] = 1/num_sides

        #If a crit is rolled, the dragon is immune.
        P_row[damage_done] = 1/num_sides

        P.append(P_row)
    #The 'player dies' and 'dragon dies' states are absorbing.
    player_dies_row = np.zeros(hp+2)
    player_dies_row[-2] = 1
    P.append(player_dies_row)

    dragon_dies_row = np.zeros(hp+2)
    dragon_dies_row[-1] = 1
    P.append(dragon_dies_row)

    P = np.stack(P)
    return P

def probability_of_dragon_death(hp,num_sides,max_num_attacks):
    P = markov_matrix(hp,num_sides)
    initial_state_probabilities = np.zeros(hp+2)

    #Initially we are in the 0 damage done state with 100% probability.
    initial_state_probabilities[0] = 1

    final_state_probabilities = initial_state_probabilities@(np.linalg.matrix_power(P,max_num_attacks))
    return final_state_probabilities[-1]

La ejecución de la función probabilidad_de_muerte_del_dragón(hp=250,num_sides=20,max_num_attacks=10000) devuelve una probabilidad de $\approx 0.269880$ .

Por diversión, también he adjuntado una figura que muestra su probabilidad de derrotar al dragón cuando se le da su HP.

enter image description here

3voto

ladidadadum Puntos 46

He aquí un enfoque que utiliza ideas de las cadenas de Markov y las funciones generadoras.

Plan: Construiremos la relación de recursión para las probabilidades en cuestión y, a continuación, aplicaremos técnicas de álgebra lineal para resolverla. (Lo bueno de este enfoque es que su complejidad computacional es independiente de cuántos puntos de salud tenga el dragón... así que no importa si el dragón tiene 250 o 250 millones de puntos, hacemos la misma cantidad de cálculos. Este no es el caso de los otros enfoques aquí).

Podríamos pasar directamente a la fórmula de recursión, pero vamos a calentarla y motivarla estableciendo la cadena de Markov de la que se deriva.

Nuestra cadena de Markov vive en el espacio de estados abarcado por dos tipos de estados

  • $ | 0 \rangle , | 1 \rangle , | 2 \rangle , \cdots$ denotando que el dragón tiene $n$ puntos de salud y seguimos vivos
  • $ | \ast \rangle $ denotando que estamos muertos.

La matriz de transición de Markov se define mediante $$ T | n \rangle = \frac{1}{m}| \ast \rangle + \frac{1}{m} \sum_{i=2}^{m-1} | n - i\rangle + \frac{1}{m} | n \rangle $$ $$ T | 0 \rangle = | 0 \rangle$$ donde $m$ es el número de caras, es decir $m=20$ .

Ganamos, y la cadena termina, una vez que hemos tomado todos los puntos de vida del dragón, es decir, una vez que la cadena de Markov alcanza cualquier estado $ |n \rangle $ con $ n \leq 0$ .

Llamemos a la probabilidad de derrotar a un dragón con $n$ puntos de salud $p(n)$ .

Ahora, después de una tirada del dado, podríamos

  • estar muerto, y nuestro combo ha terminado, por lo que nuestra oportunidad de ganar es 0
  • seguir con vida, y ahora estamos en una situación similar a la de antes, sólo que nos enfrentamos a un dragón con $n-i$ puntos de salud si $i$ daños. En este caso, de aquí en adelante nuestra oportunidad de ganar es $p(n-i)$

Podemos traducir esto en la ecuación $$ p(n) = \frac{1}{m} \cdot 0 + \frac{1}{m} \sum_{i=2}^{m-1} p( n - i ) + \frac{1}{m} p( n ) $$ con las condiciones iniciales $p(n) = 1$ para $n \leq 0$ . Obsérvese la similitud estructural con la ecuación de la matriz de transición... esto no es, por supuesto, ninguna coincidencia.

Reorganizando un poco esa ecuación llegamos a $$ p(n) = \frac{1}{m-1} \sum_{i=2}^{m-1} p( n - i ) $$

Si pudiéramos resolver esta relación de recursividad, nuestra respuesta sería $p(250)$ .

Hay muchas formas de resolver esta ecuación, por ejemplo desenrollando explícitamente la recursión, pero eso llevaría $O(n)$ pasos de cálculo.

Como esta ecuación es lineal, podemos hacerlo mejor.

Todas las soluciones de las ecuaciones de recursividad lineal son combinaciones lineales de exponenciales. (Obsérvese que todas las cadenas de Markov dan lugar a ecuaciones de recursividad lineal... ésta es, en última instancia, la razón por la que las cadenas de Markov son poderosas).

Podemos encontrar una base de soluciones haciendo el Ansatz $p(n) = x^{-n}$ donde $x$ es TBD. Introduciendo esto en la ecuación de recursión y simplificando un poco encontramos $$m-1 = \sum_{i=2}^{m-1} x^i$$ A veces se denomina ecuación característica de la cadena.

Es una ecuación polinómica de grado $m-1$ por lo que tiene $m-1$ soluciones.

Por desgracia, no existe una expresión cerrada para estas soluciones, pero podemos calcularlas numéricamente con mucha facilidad. Llamemos a las soluciones $x_\alpha$ donde $\alpha = 1, 2, \cdots, m-1$ . Entonces la solución general de la ecuación de recursión es $$ p(n) = \sum_{\alpha=1}^{m-1} w_\alpha x_\alpha ^{-n} $$ con cualquier coeficiente $w_\alpha$ .

Ya casi lo tenemos... sólo nos falta determinar el $w_\alpha$ .

Para ello, calculamos el primer $m-1$ valores de la secuencia $p(n)$ "manualmente", y luego resolver el sistema lineal de ecuaciones $$ p(n) = \sum_{\alpha=1}^{m-1} w_\alpha x_\alpha ^{-n} \quad \text{for } n = 1, \cdots , m-1$$ .

Esto equivale a una inversión de la matriz, y de nuevo se puede hacer numéricamente.

Por último, una vez determinada la $x_\alpha$ de la dinámica de la cadena y la $w_\alpha$ a partir de las condiciones iniciales, podemos calcular el número deseado como $$ p(250) = \sum_{\alpha=1}^{m-1} w_\alpha x_\alpha ^{-250} $$ .

Así es como se vería esto en python

>>> import numpy as np
>>> import pandas as pd

>>> m = 20

>>> characteristic_polynomial = np.polynomial.Polynomial((1 - m, 0) + (1, ) * (m - 2))
>>> characteristic_roots = characteristic_polynomial.roots()

>>> starting_values = np.ones(2 * m - 1)
>>> for i in range(m + 1, 2 * m - 1):
>>>     starting_values[i] = starting_values[i-m+1:i-1].sum() / (m - 1)

>>> starting_values = starting_values[m:]
>>> basis_matrix = characteristic_roots[:, None] ** (-np.arange(m-1))
>>> coefficients = starting_values @ np.linalg.inv(basis_matrix)

>>> np.real_if_close(coefficients @ (characteristic_roots ** (-250)))

0.26988043

Podemos generar fácilmente los valores para un rango de $n$

>>> result = coefficients @ (characteristic_roots[:, None] ** (-np.arange(300)))
>>> pd.Series(np.real_if_close(result)).plot()

enter image description here

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X