> While playing solitaire to while away the time during rest, Ulam asked himself a straightforward question: what are the chances that a hand laid out with 52 cards will come out successfully? It is a deceptively challenging problem—there are around 8 × 10^67 ways to sort a deck of cards (a number approaching the estimated number of atoms in the observable universe). He wondered if instead of applying pure combinatorial calculations, which would be monstrously difficult, he could simply lay out the cards one hundred times and count the number of successful plays. Implicit was the assumption that each play started with randomized conditions.

Indeed, the best “results”, to this day, are still approximations based on brute-forcing a huge number of deals (aka, using Monte-Carlo.)

“The probability of being able to win a game of Klondike [Solitaire] with best-possible play is not known, and the inability of theoreticians to precisely calculate these odds has been referred to by mathematician Persi Diaconis as "one of the embarrassments of applied probability"” — https://en.wikipedia.org/wiki/Klondike_(solitaire)#Probabili...

“Here we show that a single general purpose Artificial Intelligence program, called “Solvitaire”, can be used to determine the winnability percentage of 45 different single-player card games with a 95% confidence interval of ± 0.1% or better. For example, we report the winnability of Klondike as 81.956% ± 0.096%” — https://arxiv.org/pdf/1906.12314v3 (2019)

More on HN here: https://news.ycombinator.com/item?id=42372083