The Winnability of Klondike Solitaire and Many Other Patience Games
Our ignorance of the winnability percentage of the solitaire card game Klondike' has been described as "one of the embarrassments of applied mathematics". Klondike, the game in the Windows Solitaire program, 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 named Solvitaire' can be used to determine the winnability percentage of 73 variants of 35 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.945%+/- 0.084% (in the `thoughtful' variant where the player knows the rank and suit of all cards), a 30-fold reduction in confidence interval over the best previous result. The vast majority of our results are either entirely new or represent significant improvements on previous knowledge.
Code (1)
Tasks
Card GamesKlondikeSolitaireSimilar Papers 제목 키워드 기반
Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learning
Morpion Solitaire is a popular single player game, performed with paper and pencil. Due to its large state space (on the order of the game of Go) traditional search algorithms, such as MCTS, have not been able to find go…
Game of Goreinforcement-learningReinforcement LearningReinforcement Learning (RL)+2Assortment Optimization with Repeated Exposures and Product-dependent Patience Cost
In this paper, we study the assortment optimization problem faced by many online retailers such as Amazon. We develop a \emph{cascade multinomial logit model}, based on the classic multinomial logit model, to capture the…
Assortment OptimizationApologia Pro Vita Sua: The Vanishing of the White Whale in the Mists
There are many analogies among fortune hunting in business, politics, and science. The prime task of the gold digger was to go to the Klondikes, find the right mine and mine the richest veins. This task requires motivati…
Irreversible investment under weighted discounting: effects of decreasing impatience
This paper employs an intra-personal game-theoretic framework to investigate how decreasing impatience influences irreversible investment behaviors in a continuous-time setting. We consider a capacity expansion problem u…
Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among impartial games in their disjunctive su…