The Winnability of Klondike Solitaire and Many Other Patience Games
  Our ignorance of the winnability percentage of the game in the Windows
Solitaire program, more properly called 'Klondike', has been described as "one
of the embarrassments of applied mathematics". Klondike is just one of many
single-player card games, generically called 'patience' or 'solitaire' games,
for which players have long wanted to know how likely a particular game is to
be winnable. A number of different games have been studied empirically in the
academic literature and by non-academic enthusiasts. 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% (in the 'thoughtful'
variant where the player knows the location of all cards), a 30-fold reduction
in confidence interval over the best previous result. Almost all our results
are either entirely new or represent significant improvements on previous
knowledge.
