The Probability of Unplayable Solitaire (Klondike) Games
The Solitaire game Klondike has a few idiosyncracies: not all Klondike games are solvable. Moreover, Klondike sometimes produces unplayable games. In such cases no moves are available to the player even at the beginning of the game. The probability of occurrence of unplayable games is an important number as it is a lower bound for the probability of occurrence of unsolvable games.
Klondike, the version bundled with Windows, consists of seven stacks of cards containing a total of 28 cards, a deck of 24 cards, and four initially empty suit stacks. The seven stacks are arranged in a single row with one card in the first stack, two cards in the second stack, three cards in the third stack, and so on. The objective of the game is to move all 52 cards to the four suit stacks (one for each suit) in order of rank.
Klondike has two variants; the player is either dealt three cards from the deck at a time, or is dealt one card at a time. In the three card at a time variant, only the topmost card is playable. The analysis described here is for the three card variant of the game.
At the start of a Klondike session, only fifteen cards are playable. Seven of the fifteen cards are the top-most cards of the row-stacks and the other eight cards are in the deck of 24 cards. Any aces present in these fifteen cards can be moved to the suit stacks. A pair of playable cards can be stacked, if the two cards are of different colors, differ by one rank, and the bottom car has higher rank. Cards from the deck can only be moved to either the row-stacks or the four suit stacks. The game has some additional rules as well but they are irrelevant to the discussion at hand, and are not described here.
An unplayable Klondike game satisfies the following three conditions simultaneously:
- No aces are in the fifteen playable cards
- None of the seven playable cards in the row-stacks can be moved to a different row-stack.
- None of the eight playable cards in the deck can be moved to any of the seven row-stacks.
The probability of satisfying only the first condition can be easily calculated.
This probability is the number of all possible arrangements (combinations) of
15 cards taken from a deck with no aces, divided by the number of all possible
arrangements of 15 cards taken from a deck that includes aces. The two numbers
in question can be computed using Binomial coefficients, and the following
expression gives the result of the calculation:
Binomial[48,15] / Binomial[52,15] = 0.2439
The number 0.2439 suggests that on average 24.39 percent of Klondike games start with no aces amongst the initially playable cards. Equivalently, 75.61 percent of Klondike games have at least one ace in the 15 initially playable cards.
Unfortunately, the number computed above is of no great help in computing the probability of occurrence of unplayable games. That calculation requires simultaneously satisfying all three conditions mentioned previously; there is no simple analytical approach to solving that problem.
A brute force approach to generate and test all possible Klondike games is not
feasible either. Even considering only the games where no aces occur in
the 15 playable cards, the number of all possible Klondike games is quite
large. Under the previous scenario, the number of games to be examined totals:
Binomial[48,7] * Binomial[41,8] = 7,035,128,610,578,640
This number is more than a handful for current computing hardware; therefore, a less computing intensive approach is required for solving this problem. One idea is to use Monte Carlo simulation to estimate the probability of unplayable games.
A Monte Carlo simulation consists of repeating an experiment a large number of times. An experiment in the context of Monte Carlo simulation is occurrence of a random event that either generates a favorable or an unfavorable outcome, e.g., a coin toss. The simulation proceeds by repeating the experiment some specified number of times and recording the number of favorable outcomes. The number of favorable outcomes divided by the total number of trials gives an estimate for the probability of the favorable outcome.
Designing a Monte Carlo simulation for modeling Klondike games is straightforward. Cards can be modeled as a set of 52 numbers, and random Klondike games can be generated by permuting this set of numbers. The favorable event under this scenario is an unplayable game. Checking a randomly generated Klondike games for unplayablity can also be accomplished easily.
A scheme program for this simulation problem was coded, and was used to simulate 10 million Klondike games. A total of 24,893 unplayable games were reported by the simulation. This gives 0.0025 (rounded to two significant figures) as an estimate of the probability of occurrence of unplayable games. This estimate suggests that on average 0.25 percent (one out of 400) of all Klondike games are unplayable.
As mentioned earlier, the probability of unplayable games is a lower bound for the probability of unsolvable games. All unplayable games are unsolvable, but some initially playable games are unsolvable as well. Many Klondike games allow some initial moves but then run out of possible moves. It is hard to estimate the probability of unsolvable games but a reasonable estimate would be 10-40 times the probability of unplayable games. This suggests that anywhere from 2.5 to 10 percent of all Klondike games are unsolvable.
Some players might be surprised by the above numbers. These numbers imply that majority of Klondike games are winnable; however, experience playing the game indicates otherwise. The reason players do not win majority of Klondike games is mainly the tremendous amount of guesswork involved in playing Klondike. A few wrong moves can easily make a player lose and this is what happens most of the time.
by Usman Latif [Feb 01, 2004]