¿Cuál es la probabilidad de que una partida de solitario se pueda ganar?

Question

Por "solitario", entendamos Solitario Klondike de la forma "Roba 3 cartas, Reparte infinito".

¿Cuál es la probabilidad de que una partida de solitario se pueda ganar? O de forma equivalente, cuál es el número de juegos resolubles ?

Cuando se me ocurrió la pregunta, me pareció bastante razonable y pensé "seguro que ya tiene respuesta".

No tengo formación en probabilidad (salvo un curso introductorio de licenciatura), pero de todas formas me puse a pensar en cómo podría abordarse el problema.

Inmediatamente, mi interés pasó de la respuesta a la pregunta anterior a los métodos para responderla. Ni siquiera podía empezar a averiguar cómo ¡iría uno a resolver este problema!

¿Cómo se puede siquiera empezar a averiguar el número de juegos resolubles?

En el mismo enlace de la wikipedia, se afirma que

Para una partida "estándar" de Klondike (de la forma: Robar 3, Re-Deal Infinite, Ganar 52) el número de partidas resolubles (suponiendo que se conocen todas las cartas) está entre el 82-91,5%. El número de partidas no jugables es del 0,25% y el número de partidas que no se pueden ganar oscila entre el 8,5-18%.

La referencia para los umbrales es este documento por Ronald Bjarnason, Prasad Tadepalli y Alan Fern.

Me sorprendió que no se supiera realmente la respuesta y que sólo hubiera estimaciones. Intenté leer el artículo, pero estoy demasiado alejado de esas líneas de pensamiento para entender de qué hablan. Parece que hay algo de programación por ahí, pero ¿cuál es la gran idea detrás de su planteamiento de la cuestión?

Me gustaría terminar esta pregunta con un par de líneas del documento (el subrayado es mío):

El Solitario Klondike se ha convertido en una aplicación informática casi omnipresente, disponible para cientos de millones de usuarios de todo el mundo en los principales sistemas operativos, aunque los teóricos han tenido problemas con este juego, refiriéndose a la incapacidad de calcular las probabilidades de ganar una partida repartida al azar como " una de las vergüenzas de las matemáticas aplicadas " (Yan et al., 2005).

Answer 1

Los números que citas son para el "Solitario Pensado", es decir, el Solitario Klondike en el que se conocen las posiciones de las 52 cartas.

Así que en teoría podría ser posible mirar todos $52!\approx 8 \times 10^{67}$ permutaciones de las cartas y para cada una de ellas (o para una octava de ellas, teniendo en cuenta la equivalencia de palos) ver si es posible resolver ese caso o no con cualquiera de las muchas combinaciones de opciones mirando cada combinación de opciones. En la práctica, ninguna de esas dos opciones resulta práctica.

Para hacer frente al excesivo número de permutaciones, un enfoque sería tomar una muestra aleatoria y utilizar técnicas estadísticas para proporcionar intervalos de confianza cada vez más estrechos en torno a las estimaciones a medida que aumenta la muestra.

Para hacer frente al excesivo número de opciones, puede aplicar heurística que proporcionan buenos métodos para tomar decisiones sin investigar cada resultado final. Hacer esto recorta el árbol de decisión y así acortar el tiempo necesario para investigar las distintas posibilidades. Pero incluso entonces, las consecuencias de las distintas decisiones en el juego pueden tener a veces consecuencias tan trascendentales y complicadas que no todas las permutaciones iniciales pueden resolverse o no en un tiempo razonable. Ignorar aquellas que no producen un resultado con la suficiente rapidez conduce al amplio intervalo de probabilidad que se indica.

Answer 2

He creado un programa en C++ para intentar averiguar cuáles son las probabilidades. Mi versión tiene un número infinito de rondas en la pila de juego (sin límite de tres re-deals) y robar 3 cartas. Los resultados son alrededor de una victoria en 5,4 juegos jugados o 18,5% de los juegos son ganados. El conjunto de muestras estadísticas fue de millones de partidas jugadas. Este fin de semana pasado, modifiqué el programa para intentar resolver repartos. Tengo un conjunto de muestras muy pequeño, pero parece provisionalmente que alrededor del 50% de las manos perdidas se pueden resolver. Se trata de una muestra estadística muy pequeña. El verdadero problema es que, cuando una mano no se puede resolver, el programa tarda horas y millones de intentos en averiguarlo.

Todos estos resultados quedarán en nada cuando alguien encuentre un bug en mi programa :). Pongo aquí algunas estadísticas y el código fuente por si te interesa:

http://webpages.charter.net/jstefan/solitaire.htm

Espero publicar el código fuente del "solucionador" en las próximas semanas. No entiendo cómo se verifica este programa. Esto es realmente fuerza bruta y no estoy seguro de cómo esto se convertiría en un libro blanco. El solitario pensado es un animal completamente diferente.

Answer 3

Muestreo Monte Carlo y un buen solucionador.

Para obtener una estimación de la probabilidad de juegos resolubles, necesitamos una forma de determinar si un cierto juego es ganable, entonces necesitamos muestrear N juegos e intentar resolverlos. Si resolvemos W juegos, entonces la estimación es:

$ f_{winnable} = N/W $

En el informe Probabilidades humanas de ganar el Klondike con Monte Carlo el "solucionador" que utilizaron es un jugador humano, su estimación es $f_{winnable} ≈ 0.79 $ .

En este documento BUSCAR EL SOLITARIO EN TIEMPO REAL su solucionador examina Thoughtful Solitaire una versión de Klondike Solitaire en la que se conoce la ubicación de todas las cartas. Descubrieron que

$$ 0.82 \le f_{winable} \le 0.91 $$