## The Application of Human Monte Carlo to the Chances of Winning Klondike Solitaire

Klondike solitaire is one of the most popular forms of solitaire. The game consists of (i) a tableau that initially has seven piles (or columns) with 1 to 7 cards in each with the top card facing up and the other cards facing down, (ii) a deck with initially 24 cards in it, and (iii) a foundation with four spaces to place cards of the same suit all of which are initially empty.
For the rules, see How to Play Klondike Solitaire. The goal of the game is to place all 52 cards in the deck onto the four foundation piles. There are some variations in the rules of Klondike solitaire. In the version used in this report, we allow the player to go through the deck as many times as possible, turning three cards at a time, allowing the player to see all three cards but only permitting the player to move a top card to the tableau or foundation if possible. We also allow part or all of an alternating face-up sequence in one column of the tableau to be moved to another column in the tableau as long as card numbers decrease and the alternating color scheme is maintained. Once a card is played to a foundation pile, it may not be moved back to the foundation.
The question arises as to what fraction of Klondike solitaire games is winnable? The number of different games is 52! = 52x51x52…x3x2x1 = 80658175170943878571660636856403766975289505440883277824000000000000, which is approximately 8x1067. To analyze all the games and to decide which are winnable is an impossibly arduous task. When faced with such an enormous number of situations, mathematicians and scientists have developed an approximate way of determining questions such as the fraction of winnable Klondike solitaire games. It is called the Monte Carlo method.
In our case, one generates quite a few games. Call this number N. One then analyzes these games to determine which are winnable. Call this number W. Then, an estimate of the fraction, fwinnable, of winnable Klondike solitaire games is

fwinnable   ≈   W/N                 Equation (1)

As N gets larger, the accuracy of the estimate gets better. In the case where there are two possibilities for the outcome, which is the situation for Klondike solitaire (winning or losing), one can show that there is about a 68% chance that the true winnable fraction is within σ of the estimated fraction where

σ2 = fwinnable (1 -  fwinnable)/N                 Equation (2)

and a 95% change that it is within 2σ of the estimate.
Often a computer is used in the Monte Carlo method since it is good at repetitive calculations and one wants N to be as large as possible so as to obtain as-accurate-as-possible estimate. However, programming a computer to play Klondike solitaire perfectly is not easy. Hence, we have resorted to “human” Monte Carlo. We selected one of the brightest staff members at Jupiter Scientific to look at 100 games with all the tableau cards facing up so that winnability could be more easily determined. He was able to show that 79 of these were winnable. Of the remaining 21 games, he proves rigorously it was impossible to win 16 of them. He also provided strong arguments that a player could not win the remaining 5. A second Jupiter Scientific staff member reviewed the proofs.
Using Equation (1), one concludes that approximately 79% of Klondike solitaire games are winnable:

fwinnable   ≈   79%                 Equation (3)

and, using Equation (2), that there is a

95% chance that the true winnable faction is between 71% and 87%

In Reasons for Getting Stuck in Klondike Solitaire, we provide some insights into the nature of when a game is not winnable.
While generating this report, we uncovered a nice analysis that actually used a computer to conclude that 82% of the games were winnable and that there was a 99% chance that the true winnable fraction was between 80% and 85%. These figures are somewhat higher than the value of fwinnable in Equation (3) of 79%. However, the version of Klondike in that analysis allowed cards to be moved from the foundation back to the tableau and so the winnable fraction should be a bit higher.
In “real” Klondike solitaire, one is not allowed to see the face-down cards in the tableau. The question then arises as to what are one’s chances of winning when one is not allowed to view all the cards in the tableau. Our staff member was able to win 189 out of 442 games:

chances of winning with good play = 43%                 Equation (4)

This is several times the typical winning percentages of “recreational players”. The insights into the nature of when games are winnable have allowed us to construct some general strategies for increasing one’s chance of winning.
Of course, there may be better strategiesFootnote. Therefore Equation (4) is a lower bound:

chances of winning with best play ≥ 43%                 Equation (5)

In this report, we have used “human” Monte Carlo to obtain a lower bound on the chances of winning Klondike solitaire with good play and to obtain an estimate for the fraction of winnable games if a player was “clairvoyant” and “perfect.” Monte Carlo methods have many other applications particularly in the fields of physics, mathematics and engineering. They can be used to estimate integration over a multi-dimensional space, they were used for quantum chromodynamics to suggest that quark confinement was a property of the theory, and the method can even be used to demonstrate the correction solution of the three-door Monty Hall problem. See the Monty Hall page at UCSD.

This report was prepared by the staff of Jupiter Scientific, an organization devoted to the promotion of science through books, the internet and other means of communication.

This web page may NOT be copied onto other web sites, but other sites may link to this page.