Como nos adelantaba la mayor puntuación de este problema sobre los anteriores es el más complicado de los tres de la fase de calificación. La dificultad estriba en que tenemos que darnos cuenta de un detalle del problema que nos va a permitir resolverlo por un método que no es el directo. Pero no adelantemos acontecimientos.
El problema trata de calcular la probabilidad de un evento, en este caso la victoria del jugador Tennison en un partido de tenis (¿a qué podía jugar si no con ese nombre?). Los problemas de probabilidad se resuelven sumando la probabilidad de todos los casos favorables, es decir los casos en los que sucede el evento. Sólo hay que preocuparse de generar todos los casos, sin repetir ninguno, calcular bien la probabilidad de cada caso individual y, por supuesto, sumar correctamente eligiendo la precisión adecuada.
Afortunadamente no nos han hecho introducirnos en el complicado sistema de tanteo de un partido de tenis y se han limitado a tener en cuenta la puntuación de último nivel de este deporte, es decir, los sets. Por contra nos han alargado la duración del partido ya que si los partidos reales se juegan normalmente al mejor de tres o cinco sets, esto es gana el jugador que primero se anota dos o tres sets, en nuestro problema gana el jugador que antes se anote K sets, donde K puede ser tan grande como cien. O lo que es lo mismo, Tennison puede jugar un partido al mejor de 199 sets...
Teoría de probabilidades (básico)
Un poquito de teoría de seguro innecesaria:
Aunque estemos acostumbrados a hablar de probabilidades como tantos por ciento, matemáticamente la probabilidad de un suceso se expresa con un número real entre cero (suceso imposible) y uno (suceso seguro).
La probabilidad de que sucedan dos sucesos independientes entre sí es el producto de las probabilidades de que sucedan cada uno por separado. O sea como la probabilidad de que al tirar una moneda salga cara es 0.5, la probabilidad de que al tirar dos veces salgan dos caras es de 0.25 (0.5 multiplicado por 0.5).
La probabilidad de que suceda uno de varios sucesos excluyentes entre sí, osea que no pueden suceder a la vez, es la suma de las probabilidades de cada suceso individual. Así por ejemplo la probabilidad de sacar una cara y una cruz al tirar dos monedas es la suma de sacar primero una cara y luego una cruz (0.25 como vimos en el párrafo anterior) y la de sacar primero una cruz y luego una cara, es decir, 0.5 (0.25 + 0.25).
Método fuerza bruta
Como decía al principio nos piden que calculemos la probabilidad de que Tennison gane un partido. El evento ganar el partido se traduce en que gane K sets antes que lo haga su oponente. En cada set que comienza Tennison tiene dos probabilidades diferentes de ganarlo en función del tiempo que haga: sol o lluvia. En realidad lluvia es equivalente a no sol, lo que nos simplifica la vida. El problema reside en que conocemos la probabilidad de que haga sol al comienzo del partido pero ésta va a variar a lo largo del mismo en función del resultado. Si Tennison gana el set la probabilidad de sol puede aumentar o puede quedar igual, y si lo pierde la probabilidad puede disminuir o puede quedar igual. Las probabilidades de que aumente o disminuya o no según quién gane el set son fijas durante todo el partido y las cantidades en que se incrementa o disminuye la probabilidad del sol también son fijas. ¡Menos mal!
Algoritmo:
Veamos cómo resolveríamos el segundo de los casos propuestos como ejemplos:
Se trata de un partido a dos sets en los que la probabilidad de victoria con sol es de 0.6 y sin sol de 0.2, la probabilidad inicial de sol es de 0.5 y las probabilidades de que aumente la probabilidad de sol con la victoria en 0.1 es 1 (siempre sube) y la de que baje 0.1 con la derrota es 1 también.
Comienza el partido, la probabilidad de que vayan 0-0 es 1 obviamente.
Tenemos dos posibilidades (con 0-0) que haya sol con probabilidad 0.5 y que llueva con probabilidad 0.5.
Tennison puede ganar el primer set en ambas condiciones, así que la probabilidad de que gane el primer set es la suma de las probabilidades de que lo gane con sol más que lo gane con lluvia. Con sol tendrá una probabilidad de 0.5*0.6=0.3 (producto de las probabilidades de que haga sol y que gane con sol) y con lluvia, análogamente, 0.5*0.2=0.1. Por lo tanto la probabilidad de vencer el primer set es 0.3+0.1=0.4. Obviamente si no gana el set lo pierde, por lo que la probabilidad de que pierda el primer set es 1-0.4=0.6.
Así que la probabilidad de que el resultado sea 1-0 es 0.4 y 0-1 0.6. En ambos casos nadie gana ni pierde el partido.
Vamos a seguir la rama de posibilidades (sí, todos los eventos se organizan en un árbol) del 1-0. Como Tennison ha ganado el último set la probabilidad de sol puede aumentar o no, así que tenemos dos posibilades: que el resultado sea 1-0 y la probabilidad de sol aumente hasta 0.6 o que el resultado sea 1-0 y la probabilidad de sol permanezca en 0.5. El primero caso tiene una probabilidad de 0.4*1=0.4 (producto de la probabilidad acumulada hasta el resultado 1-0 por la probabilidad de que aumente la probabilidad de sol), el segundo caso tendrá 0.4*(1-1)=0, suceso imposible por lo que no tendremos que avanzar por esta rama más.
Continúa el partido, la probabilidad de que gane el 2º set será otra vez la suma de que gane con sol o lluvia: 0.6*0.6+0.4*0.2=0.44. Hay que multiplicarlo por la probabilidad de que haya ganado el primer set y que la probabilidad haya subido hasta 0.6, o sea: 0.4*0.44=0.176. En este momento Tennison gana el partido así que esta es la probabilidad de la primera combinación de eventos que conducen a la victoria. Lo sumamos.
La probabilidad de que pierda el set será 1-0.44=0.56 que también tendremos que multiplicar por 0.4 para obtener la probabilidad de que el resultado sea empate después de ganar el primer set (perdiendo el primer set también se puede llegar a la condición de empate): 0.4*0.56=0.224. Nuevamente la probabilidad de sol puede bajar hasta 0.5 con probabilidad de 1 o quedar en 0.6 con probabilidad de 0. Así la probabilidad de empate 1-1 con probabilidad de sol de 0.5 será 0.224*1=0.224 y la probabilidad de empate 1-1 con probabilidad de sol 0.6 será 0.224*0=0.
Siguiendo el partido desde 1-1 con probabilidad de sol 0.5, la probabilidad de victoria del set en estas condiciones es 0.5*0.6+0.5*0.2=0.4, así la probabilidad del 2-1 es 0.224*0.4=0.0896 que acumularíamos con los 0.176 del 2-0 quedando una probabilidad de victoria hasta aquí de 0.176+0.0896=0.2656.
La derrota conduciría al 1-2 y la pérdida del partido.
Seguiríamos analizando desde el 0-1 con probabilidad de sol 0.4 que tenía una probabilidad de 0.6. La probabilidad de victoria en este caso sería 0.4*0.6+0.6*0.2=0.36, multiplicado por la probabilidad acumulada 0.6*0.36=0.216 que multiplicado por 1 nos da la probabilidad de empate 1-1 con probabilidad de sol 0.5 es 0.216. La derrota del set provoca la pérdida del partido por lo que no tenemos que seguir analizando esa rama.
Desde el 1-1 con probabilidad de sol 0.5 la probabilidad de victoria del set es 0.4, así que la victoria 2-1 tendrá una probabilidad de 0.216*0.4=0.0864. Lo sumamos con la probabilidad acumulada y obtendremos la probabilidad de victoria: 0.352
Rutina re-entrante:
Así es como vamos a codificar el algoritmo de esta solución, con una rutina re-entrante o, lo que es lo mismo, una función que se llama a sí misma.
Como hemos visto resolviendo el problema a mano, partimos de un resultado, una probabilidad de sol y una probabilidad de que suceda esta situación en el partido. Todos estos serán los parámetros de llamada a nuestra función: el número de sets ganados, el número de sets perdidos, la probabilidad de sol y la probabilidad acumulada del evento.
Con esas condiciones calculamos la probabilidad de que Tennison venza en el siguiente set.
Si al vencer alcanza los K sets incrementa la probabilidad de victoria en el producto de la probabilidad de vencer el set por la probabilidad acumulada del suceso. Si no llega a K sets tendremos dos posibilidades: que aumente o no la probabilidad. Esto se traducirá en dos llamadas a la misma función en donde el número de sets ganados se habrá incrementado en uno, la probabilidad de sol habrá aumentado en una llamada y en la otra no y la probabilidad acumulada se habrá multiplicado por la probabilidad de victoria y por la probabilidad de que aumente le probabilidad de sol en el primer caso o de que no aumente en el segundo.
Y lo mismo considerando una derrota en el set. En este caso si el número de sets perdidos alcanza K no hacemos nada.
La función tendría este aspecto:
void nextGame(int gw,int gl,double psun, double p)
{
if (psun>1.0) psun=1.0;
if (psun<0.0) psun=0.0;
double win=psun*ps+(1-psun)*pr;
if (++gw==K)
{
pwin+=p*win; // win
}
else
{
nextGame(gw,gl,psun+pu,p*win*pw);
nextGame(gw,gl,psun,p*win*(1-pw));
}
gw--;
double lost=1-win;
if (++gl==K) // lost
{
plost+=p*lost;
}
else
{
nextGame(gw,gl,psun-pd,p*lost*pl);
nextGame(gw,gl,psun,p*lost*(1-pl));
}
gl--;
}
Las dos primeras instrucciones obligamos a que la probabilidad de sol no se salga de los límites.
Todas las variables que se emplean, excepto los parámetros de la función, están definidas fuera de las funciones del programa, incluso fuera de la función main, para que su ámbito sea global a todo el programa.
Cada nivel del árbol nos generará una nueva llamada a la función. El compilador se ocupa por nosotros de guardar los parámetros de llamada a la función, de acordarse dónde tiene que regresar cuando acabe de explorar el árbol, etc.
El peligro de usar este tipo de algoritmos es olvidarse de programar alguna condición de finalización, es decir, en algún momento la llamada a la función debe terminar sin llamarse a sí misma otra vez.
El segundo peligro es la cantidad de memoria que va a emplear. Hay que tener en cuenta que cada parámetro de llamada y cada variable definida local en el interior de la función necesitan memoria para ser almacenada en cada nivel de llamadas a la función puesto que los valores son distintos aunque la variable se llame igual.
Nuestro problema se resolverá haciendo una llamada desde el método main a esta función con los siguientes valores:
nextGame (0,0,pi,1.0);
donde pi es la probabilidad inicial del sol, dato del problema y 1.0 es la probabilidad del resultado 0-0.
Problema del método de fuerza bruta:
Aquí está el programa completo, ¿pero resuelve el problema?
La respuesta es lamentablemente no. De hecho yo ni siquiera hubiera llegado a programar este método porque el número de casos que se pueden generar es inabordable. De hecho vemos que en cada llamada a la función nos genera 4 llamadas como mínimo hasta que alcancemos el nivel K, luego puede que alguna rama no esté completa. Pero incluso contando sólo con nivel 100 en el último nivel del árbol habrá 4^100 casos, que es una cantidad con 60 cifras. No creo que su ordenador sea capaz de evaluar tantos casos. De hecho ni siquiera el caso del ejemplo en el que K=25 terminará con este programa.
Me ha venido bien para explicar el funcionamiento de las rutinas re-entrantes y para ver cómo se resuelven en general los problemas relacionados con probabilidades, que no es poco.
Algunas veces implementar un método que sabes que no va a funcionar por ineficiente puede servirte como base para ver cómo evoluciona el problema y, entonces, encontrar la idea brillante que resuelva el problema.
Método paso a paso
En este caso nos damos cuenta que hay demasiados caminos posibles, pero muchos de ellos conducen a los mismos resultados. De hecho en el ejemplo que hicimos a mano ya vimos que pasábamos dos veces por el resultado 1-1.
Osea que hay relativamente pocos resultados intermedios diferentes en el partido. Si K=100 está claro que se jugarán menos de 200 sets. Si hemos jugado N juegos pueden repartirse entre los dos jugadores de N+1 formas distintas por lo que tendremos muchas menos de 200x200 posibilidades diferentes. Eso es muy poco para un ordenador.
Podríamos ir avanzando juego a juego y calculando la probabilidad de cada resultado a partir de las probabilidades del nivel con un juego menos. Igual que en el método de la fuerza bruta iríamos sumando las probabilidades de todos los resultados que supongan la victoria de Tennison.
Lamentablemente tenemos una variable adicional. En cada momento del partido no sólo importa el marcador sino la probabilidad de que haya sol, y esta es una variable real, no entera. Si fuera entera podríamos añadir una dimensión más a nuestra tabla de probabilidades y calcular la probabilidad de todos los resultados y todas las probabilidades de buen tiempo.
¿Podemos convertir un real entre cero y uno en un entero? La respuesta es sí si el número de decimales está limitado. ¿Está limitado en nuestro problema? ¡Bingo! La respuesta es sí. Entre las condiciones del problema nos indican que todas los datos de probabilidades van a venir con tres decimales. Como vamos a sumar o restar cantidades de tres decimales a la probabilidad de buen tiempo siempre se van a mantener en tres decimales. Así que si multiplicamos por mil se convertirá en un entero entre 0 y 1000.
1000x200x200 sigue siendo una cantidad manejable por un ordenador.
Así que el algoritmo será construir una tabla en el que el primer índice será el número de sets jugados. Variará entre 0 y 2*K-1. El segundo el número de sets ganados por Tennison. Variará entre 0 y N para el nivel de N sets jugados (primer índice). Y el tercer índice será la probabilidad de sol. Variará entre 0 y 1000.
En el nivel 0 del primer índice el segundo sólo puede valer 0. las probabilidades del tercer nivel (entre 0 y 1000) valdrán todas 0 excepto la probabilidad correspondiente con la probabilidad de sol inicial del problema.
Calcularemos el nivel N+1 a partir del nivel N. Calcularemos la probabilidad de victoria para cada probabilidad de buen tiempo e iremos sumando la posición de la tabla correspondiente al nivel N+1 correspondiente al resultado de ganar o perder el set y mantener o incrementar/disminuir la probabilidad de buen tiempo.
El algoritmo es mucho más sencillo que el de fuerza bruta. Consiste simplemente en un triple bucle anidado e. igual que en el caso de fuerza bruta, una variable en donde acumular las propiedades de los eventos que conducen a una victoria del partido.
Aquí está el programa completo, no creo que necesite una mayor explicación.
Flags en streams
Bueno sí que podemos aclarar un pequeño trozo del programa, la salida de resultados para cumplir con las especificaciones del formato de salida:
cout.setf(ios::fixed, ios::floatfield);
cout.setf(ios::showpoint);
cout << "Case #" << t << ": " << setprecision(6) << pwin << endl;
Hemos empleado el método setf, con dos formatos diferentes, para establecer el modo de salida de los datos que enviemos al stream.
La primera llamada establece la escritura de reales en notación en coma fija en vez de notación científica.
La segunda llamada fuerza a que se visualice el punto decimal.
Finalmente, en la cadena de operadores << que hacen salir los resultados al stream, hemos añadido una llamada que no produce ninguna salida de datos sino que acomoda la forma en que saldrán los siguientes datos (setprecision), en este caso fuerza a que salgan 6 decimales.
Aquí está la descripción completa del método setf y aquí la descripción de setprecision.
No hay comentarios:
Publicar un comentario