20
$\begingroup$

By "solitaire", let us mean Klondike solitaire of the form "Draw 3 cards, Re-Deal infinite".

What is the probability that a solitaire game be winnable? Or equivalently, what is the number of solvable games?

When I came up with the question, it seemed a pretty reasonable thing to ask, and I thought "surely it must have been answered".

I have no probability formation (save for an introductory undergraduate-level course), but anyway I started thinking on how could the problem be tackled.

Immediately my interest shifted from the answer to the above question, to the methods involved in answering it. I couldn't even begin to figure out how would one go solving this problem!

How does one even begin to find the number of solvable games?

In the same wikipedia link, it is stated that

For a "standard" game of Klondike (of the form: Draw 3, Re-Deal Infinite, Win 52) the number of solvable games (assuming all cards are known) is between 82-91.5%. The number of unplayable games is 0.25% and the number of games that cannot be won is between 8.5-18%.

The reference for the thresholds is this paper by Ronald Bjarnason, Prasad Tadepalli and Alan Fern.

It came as a surprise to me that the answer is not really known, and that there are only estimates. I tried reading the paper, but I'm too far away from those lines of thinking to understand what they're talking about. There seems to be some programming going around, but what is the big idea behind their approach to the question?

I would like to end this question with a couple of lines from the paper (emphasis by me):

Klondike Solitaire has become an almost ubiquitous computer application, available to hundreds of millions of users worldwide on all major operating systems, yet theoreticians have struggled with this game, referring to the inability to calculate the odds of winning a randomly dealt game as “one of the embarrassments of applied mathematics” (Yan et al., 2005).

$\endgroup$
4
  • 2
    $\begingroup$ I added the "recreational mathematics" tag because I wondered about this in a moment of recreation. I'm not implying the mathematics involved in the paper is recreational :P $\endgroup$ Mar 17, 2012 at 13:23
  • $\begingroup$ Can't find any source for the statement that "The number of unplayable games is 0.25%." It was probably deleted from Wiki and I haven't seen it in any other source. $\endgroup$
    – Cohensius
    Jul 5, 2020 at 11:54
  • 3
    $\begingroup$ Charlie Blake, Ian P. Gent, The Winnability of Klondike Solitaire and Many Other Patience Games arXiv 2019 now suggests $81.956\%±0.096\%$ $\endgroup$
    – Henry
    Nov 18, 2020 at 0:32
  • $\begingroup$ What about flipping the question? What makes a game of solitaire unwinable? A card that you need is trapped under a higher value card and there’s no way to extract it? What percentage of the time do those conditions present themselves? By knowing the percent of times unwinable games happen you can calculate the remaining percentage of winnable games. $\endgroup$
    – Dugan
    Jan 22 at 22:57

3 Answers 3

13
$\begingroup$

The numbers you quote are for "Thoughtful Solitaire", i.e. Klondike Solitare where the positions of all 52 cards are known.

So in theory it might be possible to look at all $52!\approx 8 \times 10^{67}$ permutations of the cards and for each one (or for a eighth of them, taking account of the equivalence of suits) see whether it is possible to solve that case or not with any of the many combinations of choices by looking at every combination of choices. In practice neither of those two options are practical.

To deal with the excessive number of permutations, one approach would be to take a random sample and to use statistical techniques to provide steadily narrowing confidence intervals around the estimates as the sample gets bigger.

To deal with the excessive number of choices, you can apply heuristics which provide good methods for taking decisions without investigating every final result. Doing this trims the decision tree and so shortens the time needed to investigate different possibilities. But even then, the consequences of different decisions in the game can sometimes have such far reaching and complicated consequences that not all initial permutations can be found to be solvable or not within a reasonable time. Ignoring those which do not produce a result quickly enough leads to the wide reported range for the probability.

$\endgroup$
4
  • $\begingroup$ "The positions of all 52 cards are known"? Do we both know the same Klondike Solitaire? I was thinking the OP was referring to the one in Windows: there are seven rows of cards with increasing numbers of cards from one to seven, placed left to right, and the top card of each row only is face up. The remainder of the deck is all face down, and three cards are turned up at a time. $\endgroup$
    – Lee Sleek
    May 31, 2013 at 14:36
  • 1
    $\begingroup$ @Lee Thoughtful Solitaire is the same, but you know the locations of the cards you cannot see. Look at web.engr.oregonstate.edu/~afern/papers/solitaire.pdf for details $\endgroup$
    – Henry
    Jun 2, 2013 at 14:27
  • 1
    $\begingroup$ Okay, we've established we can't get an exact answer through brute force methods (even with decision trees and other optimizations). But that doesn't mean we can't get an answer through math. Consider rewriting the problem as "put all the cards into the solved solitaire state (4 stacks, same suits, king on top, ace on bottom). Now, how many possible unique configurations can be generated by playing solitaire backwards. Now, divide that number by the possible board configurations (52!≈8*10⁶⁷)." (Continued on next comment) $\endgroup$ Nov 18, 2020 at 0:16
  • 1
    $\begingroup$ While this is still difficult, it is more doable. The first move must be either putting a king onto the draw pile, or onto one of the 7 slots. The next move would either be one of the kings, or the queen below the removed king. This is still very very very verrrry difficult, but given all the crazy papers released throughout the years by experienced mathematicians, a morbidly curious mathematician could feasibly use patterns and recursion to find the exact answer. $\endgroup$ Nov 18, 2020 at 0:35
7
$\begingroup$

I put together a C++ program to try and figure out what the odds are. My version has infinite number of go rounds on the play stack (no limit of three re-deals) and draw 3 cards. The results are about one win in 5.4 games played or 18.5% of games are won. The statistical sample set was millions of games played. This past weekend, I modified the program to try and solve deals. I have a very small sample set but it tentatively appears that about 50% of lost hands are solvable. This is very small statistical sample set mind you. The real problem is, when a deal isn't solvable, it's taking the program hours and millions of tries to figure that out.

All of these results will be rendered moot when someone finds a bug in my program :). I put some statistics and the source code here if it interests you:

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

I hope to publish the source code for the "solver" in the coming weeks. How this program gets verified is beyond my understanding. This is really brute force and I'm not sure how this would get turned into a white paper. Thoughtful solitaire is whole different animal.

$\endgroup$
2
$\begingroup$

Monte Carlo sampling and a good solver.

To get an estimation of the probability of solvable games, we need a way to determine if a certain game is winnable, then we need to sample N games and try to solve them. If we solve W games, then the estimation is:

$ f_{winnable} = N/W $

In the report Human Monte Carlo Chances of Winning Klondike the "solver" they used is a human player, their estimation is $f_{winnable} ≈ 0.79 $.

In this paper SEARCHING SOLITAIRE IN REAL TIME, their solver examine Thoughtful Solitaire, a version of Klondike Solitaire in which the location of all cards is known. They found that

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.