Antecedentes y motivación
El juego de Yahtzee es un modelo para la toma de decisiones en condiciones de incertidumbre: en concreto, para saber cómo tomar decisiones óptimas cuando nos enfrentamos a una secuencia de ellas a lo largo del tiempo. Las técnicas utilizadas para analizar este juego se aplican directamente, por ejemplo, a las decisiones empresariales que se repiten, como la de realizar o no inversiones periódicas en una perspectiva de negocio y su cuantía. Por lo tanto, el tiempo y el esfuerzo dedicados a entender este sencillo juego pueden aportar ideas para desarrollar estrategias en situaciones complejas del mundo real.
Análisis de decisiones
En abstracto, un "prospecto" es un conjunto $\Omega$ de posibles "estados" de un juego, negocio u otra situación. Asociado a cada estado $\omega\in\Omega$ es un pago $X(\omega)$ (un número que puede ser positivo o negativo). En el caso más sencillo de una sola decisión, un conjunto de acciones u "opciones" $\mathcal{D}(\omega)$ está a disposición del responsable de la toma de decisiones; pueden depender del estado $\omega$ . Cada opción $d\in\mathcal{D}(\omega)$ conduce a una distribución de probabilidad sobre los estados $F(d)$ (que se conoce o se puede estimar con precisión). Así, asociado a cada opción $d$ es el valor esperado de la retribución,
$$v(d) = \mathbb{E}_{F(d)}(X).$$
Las mejores opciones son las que tienen los valores esperados más altos. Sea $d^{*}(\omega)$ ser una de las mejores opciones para cualquier estado $\omega$ . La función
$$X^\prime(\omega) = v(d^{*}(\omega))$$
que asigna a cada estado el valor de la elección de la mejor opción es la retribución disponible en la toma de decisiones óptima.
(Una generalización de esta teoría tiene en cuenta el riesgo sustituyendo la retribución esperada por la utilidad esperada).
![Figure]()
Esta figura muestra un diagrama de una perspectiva que consiste en dos estados llamados "11" y "001", que se muestran en la columna de la derecha. Asociados a ellos están los pagos $1$ y $0$ , respectivamente, indicando la retribución $X$ . Los posibles estados iniciales, mostrados en la columna de la izquierda, son los mismos dos estados. El conjunto de todas las opciones posibles se muestra en la pila central de nodos naranjas. No todas las opciones están disponibles desde cada uno de los estados iniciales: las que lo están, se muestran con flechas. Por ejemplo, la opción "2" no está disponible desde el estado "001", pero sí desde el estado "11".
La distribución de probabilidad $F(d)$ asociado a cada opción $d$ se muestra mediante flechas que señalan los estados: la probabilidad de cada estado viene dada por un número en cada flecha. (Las flechas sin números tienen una probabilidad $1$ .) La figura utiliza flechas más pesadas para mostrar mayores posibilidades. Se ha calculado la expectativa de cada distribución y se indica junto a cada opción. Por ejemplo, el valor de la opción "1" es $3/4$ porque su distribución de probabilidad asigna una posibilidad de $3/4$ para alcanzar el estado "11", cuya recompensa es $1$ y una posibilidad de $1/4$ para llegar a "001", cuyo pago es $0$ . Por lo tanto, la expectativa es $3/4\times 1 + 1/4\times 0 = 3/4$ como se muestra.
Las mejores opciones disponibles de los estados iniciales se muestran con flechas gruesas. Por ejemplo, las cuatro opciones disponibles desde el estado "001" son "0", "1", "01" y "001", con resultados esperados de $3/4$ , $3/4$ , $1/2$ y $0$ respectivamente. Los dos primeros son máximos, por lo que las mejores opciones son "0" y "1".
De este modo, tal diagrama de influencia contiene toda la información necesaria para calcular la mejor decisión a tomar en cualquier estado inicial, así como su valor esperado. Este muestra que $X^\prime$ asigna el valor $1$ a "11" y $3/4$ a "001".
Consideremos ahora una perspectiva que es una secuencia de decisiones que tendrán lugar en tiempos discretos indexados por $i=1, 2, \ldots, n$ . Las decisiones y sus circunstancias pueden variar a lo largo del tiempo, por lo que debemos indexar todo (incluidos los estados y las opciones disponibles de los mismos). Las decisiones óptimas pueden tomarse por "retropropagación" a través de este sistema, empezando por el final. En algún momento $i$ , $i=2, 3, \ldots, n$ , suponga la mejor retribución $X_i$ es conocido. Entonces $X_{i-1} = X_i^\prime$ es el mejor pago que estará disponible en el momento $i-1$ . Iterando desde $X_n = X$ hasta $X_1$ produce una secuencia de resultados (variables aleatorias) junto con una secuencia de decisiones óptimas a tomar para conseguir esos mejores resultados. Por último, el valor de esta perspectiva es la expectativa de $X_1$ sobre una distribución de probabilidad que rige el estado inicial en el paso $i=1$ .
Cómputo
Los cálculos son sorprendentemente sencillos, porque consisten en una secuencia de (a) encontrar una expectativa para cada opción para cada estado y (b) seleccionar una mejor opción para cada estado, actualizando así $X$ a $X^\prime$ . Sin embargo, para los problemas grandes pueden complicarse de forma amenazante: si hay muchas opciones para cada uno de los muchos estados, esto puede suponer mucho trabajo. (Los métodos de Monte-Carlo salen a relucir en estos casos: cuando no podemos hacer el cálculo completo, podemos muestrear entre las posibilidades y, al menos, encontrar aproximadamente las mejores opciones).
En el caso que nos ocupa, hay tantos puntos en común entre las opciones (independientemente del estado) y tanta similitud de la situación de una tirada a la siguiente, que con un poco de cuidado en el diseño de las estructuras de datos computacionales se puede hacer todo el cálculo rápidamente. En lugar de mantener un conjunto de opciones para cada estado, la unión de todas las opciones $\mathcal{D}=\cup_{\omega\in\Omega} \mathcal{D}(\omega)$ se puede calcular de una vez por todas. Entonces sólo tenemos que registrar que elementos de $\mathcal {D}$ están disponibles para cada estado. Esto sugiere escribir una función de actualización universal decide que calculará $X^\prime$ de $X$ . Sus argumentos serán los siguientes states $\Omega$ (que en Yahtzee son los mismos en cada tirada y por lo tanto no necesitan ser indexados), el payoff vector $X$ El options $\mathcal{D}$ y una matriz lógica available indicando las opciones disponibles en cada estado.
A modo de ejemplo, he aquí un R la implementación. Asume que los estados y las opciones pueden utilizarse para indexar en las matrices según convenga. Cuando más de una opción es la mejor, elige al azar entre las mejores (usando sample ). Si suponemos la existencia de una función argmax que identifica el valor más alto de una matriz indexada por un conjunto de opciones y devuelve ese valor y una de las opciones asociadas a él, el código necesita sólo dos líneas:
values <- options %*% payoff # Expected payoff for each option
x <- lapply(states, argmax) # Best option and its value, for each state
La primera línea (una multiplicación matricial rápida) calcula las expectativas para todas las opciones en $\mathcal{D}$ entonces se aplica la segunda línea argmax a todos los estados en $\Omega$ para obtener $X^\prime$ junto con las mejores opciones asociadas. Puede encontrar estas líneas, así como una implementación de argmax en el decide función que aparece al final de este post.
Solución
El resto es cuestión de calcular los estados y las opciones de Yahtzee, junto con la función $F(d)$ dando la distribución de probabilidad de los estados para cada opción. Esto puede ser un verdadero dolor de cabeza porque los cálculos no son sencillos. Tres ideas hacen que el cálculo sea relativamente sencillo:
-
Los estados, las opciones y las probabilidades se pueden encontrar simplemente tirando cinco dados en secuencia y llevar la cuenta de todos los resultados y probabilidades a medida que se avanza. No se necesita ninguna matemática combinatoria.
-
Las opciones disponibles de un estado son precisamente aquellas en las que el estado tiene una probabilidad no nula de resultar de la opción, tal y como se da en (1).
-
El cálculo puede ser muy eficiente si se adopta una notación adecuada para los estados.
En este caso, los valores reales que aparecen en los dados no importan: todo lo que nos importa es cuántos valores únicos hay, cuántos valores aparecen dos veces, etc. Una buena estructura de datos para esta información es un vector de longitud variable cuyo $i^\text{th}$ cuenta el número de valores que aparecen exactamente en $i$ dados. Podemos terminar el vector después de la última entrada no nula. Para ilustrar, los siete estados posibles en el juego de Yahtzee son
$$(5),(31),(12),(201),(011),(1001),(00001).$$
(Por comodidad, he omitido las comas entre los dígitos. A partir de ahora, también omitiré los paréntesis). El primer estado, $5$ representa cinco valores distintos, como $1, 3, 4, 5, 6$ mostrando en los dados. El estado $011$ es un pleno, como $4,4,1,1,1$ que aparece en los dados. El estado $00001$ es cinco de un tipo: el yahtzee.
Las opciones se pueden escribir con la misma notación si indicamos lo que aparece en los dados que no se vuelven a tirar. Por ejemplo, supongamos que la tirada inicial muestra $1,3,3,5,6$ . Su código es $(31)$ porque hay tres valores únicos $1,5,6$ y un valor duplicado $3,3$ . Si volvemos a tirar $1,5,6$ entonces los dados que quedan pueden ser indicados por el código $(01)$ . Hay 19 opciones en total, incluyendo la de volver a tirar todos los dados y los siete estados correspondientes a volver a tirar ningún dado. Por cierto, es conveniente romper la regla de que todos los vectores terminan con una entrada distinta de cero y escribir $(0)$ para el estado en el que no hay dados: eso hace que todos los vectores no estén vacíos.
Cálculo de la distribución de probabilidad $F(d)$ asociado a una opción $d$ es la parte más difícil del problema. Esta notación facilita la comprensión de lo que ocurre cuando un solo se tira el dado. El resultado es (a) incrementar en uno una de las entradas no nulas del vector de opciones, cuando la tirada coincide con una de las caras ya mostradas, o (b) incrementar en uno la primera entrada del vector, cuando la tirada muestra una cara nueva distinta. De hecho, (b) puede considerarse un caso especial de (a) si incluimos una entrada (invisible) número cero en cada vector de opciones igual al número de caras que aún no aparecen. Por ejemplo, a partir de la opción $01$ en la que el jugador ha cogido tres dados y ha dejado dos de la misma cara a la vista, examinamos el vector aumentado $(5,0,1)$ (el $5$ es el número de caras que no aparecen entre los dos dados). Puede resultar el vector $(4,1,1)$ en exactamente cinco formas diferentes y en el vector $(5,0,0,1)$ en un sentido (el nuevo rollo coincide con las caras que se mostraban).
Generalmente, a partir de la opción $d = (d_1,d_2,\ldots,d_k)$ podemos calcular lo siguiente:
-
Construir el vector aumentado $(d_0,d_1,d_2,\ldots,d_k)$ donde $d_0$ es el número de caras $f=6$ menos el número de valores no nulos $d_i$ .
-
Para cada posición $i$ donde $d_i \ne 0$ , pasar al vector $(d_0,d_1,\ldots,d_{i-1},d_i-1,d_{i+1}+1,d_{i+2},\ldots, d_k)$ con probabilidad $d_i/f$ . (Para $i=k$ , ver $d_{i+1} = d_{k+1} = 0$ .)
Realizando esto (un cálculo muy sencillo) repetidamente hasta que se hayan tirado los cinco dados, habremos determinado todos los posibles estados alcanzables desde $d$ junto con las posibilidades de esos estados, $F(d)$ . Para más detalles, consulte el outcomes en el código.
Respuestas
La probabilidad de conseguir un yahtzee es el valor esperado del indicador de yahtzee $X$ donde $X(\text{yahtzee})=1$ y $X(\omega)=0$ de lo contrario.
El comando yahtzee() (utilizando el R al final de este post) produce una amplia salida que muestra todas las estructuras de datos relevantes y los resultados intermedios. El principal de ellos es la secuencia de pagos $X_i$ :
$payoffs
5 31 12 201 011 1001 00001
After 1 0.0126314586 0.02906379 0.02906379 0.09336420 0.09336420 0.3055556 1
After 2 0.0007716049 0.00462963 0.00462963 0.02777778 0.02777778 0.1666667 1
After 3 0.0000000000 0.00000000 0.00000000 0.00000000 0.00000000 0.0000000 1
(Esto coincide con la tabla de http://en.wikipedia.org/wiki/Yahtzee#Any_Yahtzee . Esa tabla agrupa "31" y "12" en una categoría común y "201" y "011" en otra categoría común).
La línea en la parte inferior es el indicador de yahtzee $X_3$ El estado "00001" es un cinco en raya, el yahtzee. La penúltima línea es $X_2 = X_3^\prime$ son los resultados esperados cuando se eligen las mejores opciones en cada estado. La primera línea es $X_1 = X_2^\prime$ . Dado el resultado de la tirada inicial de cinco dados, nos dice la ganancia esperada (con la mejor jugada) para cada posibilidad, una por columna. Por ejemplo, si tras la primera tirada aparece una pareja (estado "31"), la probabilidad de conseguir un Yahtzee tras la tercera tirada es $0.029\ldots$ con la mejor jugada.
¿Cuál es la mejor jugada? Esto está contenido en el moves estructura de datos de la salida:
$moves
5 31 12 201 011 1001 00001
After 1 "0" "01" "01" "001" "001" "0001" "00001"
After 2 "0" "01" "01" "001" "001" "0001" "00001"
Tenga en cuenta que estos dan a mejor movimiento de cada estado, no necesariamente todo mejores jugadas, y por lo tanto esta tabla puede cambiar de una corrida a la siguiente. (Hay otro mejor movimiento al "1" desde el estado "5", que es intuitivamente obvio: volver a lanzar los cinco dados es lo mismo que volver a lanzar cuatro de ellos cualquiera). Sin embargo, muestra que la estrategia no varía de una tirada a otra y que equivale a lo siguiente:
-
Si los cinco valores son diferentes, vuelve a tirar todos los dados (o, lo que es lo mismo, todos los dados menos uno).
-
En caso contrario, conserva sólo una de las caras con mayor multiplicidad y vuelve a tirar todas las demás. (En particular, la mejor opción a partir de "12", que son dos pares, es retener sólo uno de esos pares y volver a lanzar tres dados en lugar de volver a lanzar el único dado impar).
Finalmente, el valor esperado se puede encontrar consultando la distribución de probabilidad $F(d)$ asociado a la opción "0" (no se muestran las caras):
$options
5 31 12 201 011 1001 00001
0 0.09259259 0.4629630 0.2314815 0.15432099 0.03858025 0.019290123 0.0007716049
Cuando se multiplica por la primera línea del payoffs matriz ("Después de 1") y sumados, esto da la posibilidad de conseguir un yahtzee con la mejor jugada. Es igual a $2,783,176 / 6^{10} \approx 0.04602864.$
Por cierto, no siempre la estrategia estática es la mejor. Si quieres conseguir un pleno "011", las mejores opciones cambian en realidad entre la primera y la segunda tirada de los dados: ¡pruébalo y verás!
Código de trabajo
La siguiente aplicación se encuentra en R . Elegí R por su popularidad en este sitio (y su disponibilidad gratuita), pero es un lenguaje problemático para trabajar con cualquier tipo de estructura de datos dinámica. Probablemente ha provocado muchos errores que aún no he descubierto, pero funciona correctamente en problemas pequeños que pueden ser comprobados a mano y funciona bien cuando se pasa por el modo de depuración en problemas más grandes.
Esta implementación maneja un número arbitrario de caras (todas equiprobables), números de dados, números de tiradas por movimiento y estados objetivo. (Es fácilmente modificable para resolver un problema en el que el objetivo es una distribución de probabilidad arbitraria de los estados, con un cierto coste de flexibilidad: después de todo, el propio código calcula cuáles son esos estados, por lo que no es sencillo diseñar una forma de entrada una distribución de probabilidad sobre ellos). Como prueba, el comando
yahtzee("11", 2, 3, 3)
encuentra el juego óptimo para conseguir una pareja de tres monedas justas, dadas tres tiradas. Su resultado incluye
$payoffs
11 001
After 1 1 0.9375
After 2 1 0.7500
After 3 1 0.0000
$moves
11 001
After 1 "2" "1"
After 2 "2" "0"
Las dos últimas líneas de payoffs y la última línea de moves resumir los cálculos en la figura anterior. Examinar el resto de la salida y compararla con la figura debería aclarar las estructuras de datos y ayudar a entender el código.
#
# Perform one step of a decision analysis.
#
decide <- function(states, payoff, options, available) {
#
# Find the best option (and its value) from state `state` given a payoff
# vector `payoff` indexed by all states.
#
# Rows of `options` are probability distributions over the states
# Columns of `available` are logical indicators of which options are
# available from each state.
#
argmax <- function(state) {
valid <- available[, state]==TRUE
expectations <- values[valid]
names(expectations) <- rownames(available)[valid]
#i <- which.max(expectations) # Returns definite results
best <- which(expectations == max(expectations))
if (length(best) > 1) best <- sample(best, 1)
return (list(option=names(expectations)[best], value=expectations[best]))
}
#
# Return a list of best (option, value) pairs indexed by the states.
#
values <- options %*% payoff # Expected payoff for each option
x <- lapply(states, argmax) # Best option and its value, for each state
names(x) <- states
return (x)
}
#==============================================================================#
#
# Generate all states and options by rolling dice.
#
yahtzee <- function(target, n.faces=6, n.dice=5, n.rolls=3) {
#
# R-specific helper functions.
# These manage some data types and data structures.
#
state.start <- "0"
identity.matrix <- function(inames) {
x <- outer(inames, inames, '==')
rownames(x) <- colnames(x) <- inames
return (x)
}
df.as.matrix <- function(x) {
rows <- unique(x$start) #$
cols <- unique(x$end) #$
a <- matrix(0, length(rows), length(cols), dimnames=list(rows, cols))
for (i in 1:nrow(x)) a[x$start[[i]], x$end[[i]]] <- x$prob[[i]] #$
return (a)
}
state.name <- function(s) {
n <- max(which(s != 0));
ifelse(n > 0, paste(s <- s[1:n], collapse=""), state.start)
}
name.state <- function(x) as.numeric(unlist(strsplit(x, "")))
#
# Function to compute the transition probabilities among all possible options.
#
outcomes <- function(s, f=n.faces) {
x <- name.state(s)
transition <- function(i) {
r <- (x - (1:n == i) + (1:n == i+1))
p <- x[i]
return(list(start=s, end=state.name(r[-1]), prob=p/f))
}
x <- c(f - sum(x), x, 0)
n <- length(x)
result <- as.data.frame(t(sapply(which(x > 0), transition)))
return(result)
}
#----------------------------------------------------------------------------#
#
# Verify that `target` is legitimate.
#
if (!missing(target)) {
s <- name.state(target)
if (sum(s != 0) > n.faces || sum(s * 1:(length(s))) != n.dice)
stop(paste0("Target `", target, "` is inconsistent with ",
n.faces, " faces and ", n.dice, " dice."))
}
#
# Roll dice to find all possible states and the transition probabilities
# between them.
#
states <- state.start
x <- list()
empty <- subset(outcomes(states, n.faces), subset=FALSE)
for (die in 1:n.dice) {
x[[die]] <- empty
for (s in states) {
x[[die]] <- rbind(x[[die]], outcomes(s, n.faces))
}
states <- unlist(unique(x[[die]]$end)) #$
}
#
# Convert the transition graph `x` into an options matrix.
#
x <- lapply(x[1:n.dice], df.as.matrix)
options <- x[[1]]
for (i in 2:n.dice) options <- rbind(options %*% x[[i]], x[[i]])
options <- rbind(options, identity.matrix(colnames(x[[n.dice]])))
available <- ifelse(options != 0, 1, 0)
#
# Allocate arrays for the results.
#
payoffs <- matrix(NA, n.rolls, length(states))
colnames(payoffs) <- states
rownames(payoffs) <- sapply(1:n.rolls, function(i) paste("After", i))
moves <- payoffs[-n.rolls, ]
#
# Compute the final payoff vector.
#
if (missing(target)) target <- paste(c(rep(0, n.dice-1), 1), collapse="")
payoffs[n.rolls, ] <- 0
payoffs[n.rolls, target] <- 1
#
# Perform the decision analysis, roll by roll.
#
if (n.rolls > 1) {
for (i in (n.rolls-1):1) {
x <- decide(states, payoffs[i+1, ], options, available)
payoffs[i, ] <- unlist(lapply(x, function(s) s$value))
moves[i, ] <- unlist(lapply(x, function(s) s$option))
}
}
#
# Compute the expectation based on the probabilitie of the starting state
# (that is, of the outcome of the first roll).
#
expectation <- as.vector(options["0", , drop=FALSE] %*% payoffs[1, ])
return (list(expectation=expectation, payoffs=payoffs, moves=moves,
options=options, available=available,
target=target, parameters=c(faces=n.faces, dice=n.dice, rolls=n.rolls)))
}
