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 tableau.
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.
Copyright ©2013 by Jupiter Scientific
To Jupiter Scientific's Information Page