The Winnability of Klondike Solitaire and Many Other Patience Games

Imagine you are sitting at a kitchen table with a deck of cards, trying to solve a game of Solitaire. You shuffle the cards, deal them out, and start moving them around. Sometimes, you win easily. Other times, you get stuck, and you wonder: "Is this specific arrangement of cards actually winnable, or am I just playing a game that was doomed from the start?"

For over a century, mathematicians and card enthusiasts have been obsessed with this question. They wanted to know the exact percentage of Solitaire games that can be won. But here's the catch: there are billions of possible ways to shuffle a deck. Checking them all by hand is impossible, and even checking them with a computer is incredibly hard because the "decision tree" of moves is so massive.

This paper, written by Charlie Blake and Ian Gent, is like a super-powered detective that finally solved this mystery for not just one game, but dozens of different card games.

The Detective: Meet "Solvitaire"

Think of the researchers' creation, Solvitaire, not as a rigid robot programmed for one specific game, but as a universal translator.

The Old Way: Before this, if you wanted to study Klondike (the classic Windows Solitaire), you needed a specific computer program. If you wanted to study FreeCell, you needed a totally different program. It was like needing a different key for every single door in a giant mansion.
The New Way: Solvitaire is a master key. The researchers wrote a flexible "rulebook" (using a language called JSON) that can describe almost any card game. You just feed the rules into Solvitaire, and it instantly becomes an expert at that specific game. It can switch from Klondike to Spider to Golf in a heartbeat.

How It Works: The "Deep Rabbit Hole"

To figure out if a game is winnable, Solvitaire uses a method called Depth-First Search. Imagine you are in a giant, dark maze (the game).

You pick a path and walk down it as far as you can.
If you hit a dead end, you walk all the way back to the last fork in the road and try a different path.
You keep doing this until you either find the exit (a win) or you have checked every single possible path and confirmed there is no exit (a loss).

The problem is, these mazes are huge. A single game of Solitaire can have more possible paths than there are atoms in the universe. To make this manageable, the team used several "AI tricks" to speed things up:

Transposition Tables (The Memory Bank): Imagine you walk down a path, turn left, then right, and end up in a room you've already visited. Instead of walking that path again, Solvitaire checks its "Memory Bank" and says, "I've been here; I know this leads to a dead end." This saves massive amounts of time.
Symmetry Breaking (The Mirror Trick): In many games, the order of the piles doesn't matter. If you have three empty spots on the table, it doesn't matter which empty spot you put a card in first; the result is the same. Solvitaire realizes this and stops wasting time checking identical mirror-image scenarios.
Dominances (The "Common Sense" Rules): This is the paper's biggest mathematical breakthrough. Sometimes, you can prove that a certain move is always a bad idea, or that a certain move is always the right one to make immediately.
- Analogy: Imagine you are packing a suitcase. If you know you need to wear your red shirt tomorrow, and you have a red shirt in your pocket, you don't need to check if you can put the red shirt in the suitcase later. You just put it in now. Solvitaire proved mathematically that for many card games, moving a card to the "foundation" (the winning pile) immediately is always the right move if it's safe to do so. They didn't just guess this; they wrote mathematical proofs to prove it works every time.

The Big Results: What Did They Find?

The team ran millions of simulations, using about 30 years of total computer time (running many computers in parallel). Here are the headline numbers:

Klondike (The Classic): In the version where you know where all the cards are (called "Thoughtful" Solitaire), 81.945% of games are winnable.
- Why this matters: Previous estimates were rough guesses with huge margins of error (like saying "82% plus or minus 3%"). The new result is incredibly precise: 81.945% ± 0.084%. They reduced the uncertainty by 30 times!
FreeCell: Almost all FreeCell games are winnable (99.9988%), confirming the old internet legend that only one specific deal out of 32,000 is impossible.
The "Thoughtful" Twist: The paper focuses on "Thoughtful" Solitaire, where the player knows the location of every hidden card. This is like playing Solitaire with a cheat sheet. In the real world, where you don't know the hidden cards, the win rate is much lower, but this paper sets the "ceiling" for how good a player could possibly be.

Why This Matters to You

You might think, "So what? It's just a card game." But this research is a huge deal for Artificial Intelligence.

Solving the Unsolvables: They solved a problem that Stanislaw Ulam, the father of the famous "Monte Carlo" method (used in nuclear physics and finance), originally tried to solve with Solitaire in the 1940s. They finally gave him the precise answer he was looking for.
The Power of General AI: They proved that you don't need a super-specialized AI for every single problem. A smart, flexible AI that understands the rules of a game can outperform specialized programs on a wide variety of tasks.
Fixing Bugs: In the process, they found bugs in other people's solvers. They discovered that some "expert" programs were actually wrong about whether certain games were winnable, proving that even human experts can get it wrong without rigorous mathematical proof.

The Bottom Line

This paper is like building a universal map for the world of card games. Instead of guessing if a game is winnable, they used a powerful, flexible AI to explore every single path, prove the rules of the road, and give us the most accurate win-rate statistics the world has ever seen.

They didn't just play the game; they mapped the entire universe of the game, proving that for the classic Klondike, if you play perfectly and know the cards, you have about an 82% chance of winning. The rest of the time, the cards were just stacked against you from the very first shuffle.

1. Problem Statement

The paper addresses the long-standing challenge of determining the winnability percentage (the probability that a randomly dealt instance of a game can be solved) for single-player card games, collectively known as "patience" or "solitaire" games.

The Gap: Despite the immense popularity of these games (e.g., Microsoft Solitaire is played 100 million times daily), the exact winnability of the most famous variant, Klondike, was previously unknown with high precision. Previous estimates had wide confidence intervals (e.g., $\pm 3\%$ ), described by the authors as "one of the embarrassments of applied mathematics."
The Challenge: Calculating winnability requires determining if any legal sequence of moves leads to a win. For games with hidden cards (like Klondike), the authors focus on the "thoughtful" variant, where the player knows the location and rank of all cards from the start. This transforms the problem into a deterministic search through a massive state space.
Scope: The paper aims to solve not just Klondike, but a diverse range of 35 different games and 73 variants, many of which had never been analyzed computationally before.

2. Methodology: The Solvitaire Solver

The authors developed Solvitaire, a general-purpose, depth-first search (DFS) solver capable of handling a wide variety of patience games defined by a flexible rule-description language.

A. Core Search Algorithm

Depth-First Backtracking: Solvitaire uses an exhaustive DFS to explore the state space. The primary goal is to prove whether an instance is winnable or unwinnable, rather than finding the shortest solution.
State Representation: To optimize memory and speed, the solver uses trailing (modifying state in place and reversing changes upon backtracking) rather than copying the entire state at every node.
K+ Representation: For games with a stock (draw pile) and infinite redeals (like Klondike), the solver uses a specialized representation that calculates the set of obtainable cards from the stock, effectively collapsing multiple stock-draw moves into a single logical step to reduce search depth.

B. Key AI Optimizations

To make exhaustive search feasible on modern hardware, Solvitaire integrates several advanced AI techniques:

Transposition Tables: A cache stores visited states to prevent re-exploring identical board configurations reached via different move orders. The authors use a compressed representation of states to maximize cache size (up to hundreds of millions of entries).
Symmetry Breaking: The solver identifies equivalent states (e.g., swapping two empty tableau piles or swapping suits in games where suit doesn't matter) and reduces them to a canonical form before caching, drastically reducing the search space.
Dominances (Pruning Rules): The paper introduces and proves the correctness of two critical dominance rules that allow the solver to prune branches without losing completeness:
- Safe Moves to Foundations: If a card can be moved to a foundation without preventing a future win, the solver commits to this move immediately, avoiding backtracking.
- Partial Pile Moves: In games like Klondike, moving a partial built pile is only allowed if the card immediately above the moved pile can be immediately built onto a foundation. The authors provide the first formal proof of this rule's correctness.
Streamliners: These are heuristic constraints that speed up finding solutions for winnable instances but may produce false negatives (reporting a winnable game as unwinnable). The solver uses a "Smart Streamliner" approach: it first attempts a fast, streamlined search; if that fails, it re-runs a full, exhaustive search to guarantee correctness.

C. Rule Description Language

A significant architectural feature is the use of a JSON-based rule language. Instead of hard-coding rules for specific games, Solvitaire reads a JSON file defining the game mechanics (e.g., number of piles, build policies, stock rules). This allows the same engine to solve vastly different games (e.g., FreeCell, Spider, Klondike) without code modification.

3. Key Contributions

High-Precision Winnability Estimates: The authors report winnability percentages for 73 variants of 35 games with a 95% confidence interval of $\pm 0.1\%$ or better.
Klondike Breakthrough: The winnability of thoughtful Klondike is calculated as 81.945% $\pm$ 0.084%. This represents a 30-fold reduction in the confidence interval compared to the best previous result.
Formal Proofs of Dominance: The paper provides the first rigorous mathematical proofs for two key dominance rules used in patience solvers, ensuring that the pruning strategies do not incorrectly discard winning paths.
Bug Discovery and Correction: By comparing Solvitaire against existing specialized solvers (for Klondike, Canfield, and FreeCell), the authors identified and corrected subtle bugs in previous implementations, including incorrect dominance rules and flaws in pseudorandom number generators.
Comprehensive Dataset: The study covers a wide spectrum of games, including entirely new results for games like British Canister (0.000129% winnability) and Fortune's Favor (99.9999879% winnability).

4. Key Results

Klondike Variants: The study analyzed how winnability changes with draw size and rule variations.
- Standard Klondike (Draw 3): 81.945%
- Draw 1: 90.480%
- Draw 7: 23.779%
- The paper also quantified the "necessity" of "worrying back" (moving cards from foundation to tableau), showing it becomes necessary in ~9% of winnable instances when the draw size is 13.
Rule Sensitivity: Experiments showed that combining restrictive rules (e.g., "Any Suit" build policy + "No Spaces" allowed) can cause winnability to drop precipitously (e.g., from ~99% to near 0%), highlighting the sensitivity of these games to rule combinations.
New Games: The authors provided the first accurate estimates for games like Carpet, Alpha Star, and Worm Hole.

5. Significance and Impact

Resolution of a Classic Problem: The paper effectively resolves the "embarrassment" regarding Klondike's winnability, providing a definitive answer that has eluded mathematicians and enthusiasts for decades.
Validation of Monte Carlo Methods: The work serves as a modern realization of Stanislaw Ulam's original motivation for inventing Monte Carlo methods (calculating solitaire winnability), but with the precision of modern exhaustive search and AI techniques.
Generalizability: The success of Solvitaire demonstrates that a single, general-purpose AI solver can outperform or match highly specialized, hand-tuned solvers across a diverse domain. This challenges the notion that specific heuristics are always required for specific games.
Open Science: The authors released the source code (under GPL), the JSON rule definitions, and the full experimental dataset, enabling reproducibility and future research into constraint solving and game theory.

In conclusion, this paper represents a landmark achievement in computational game theory, combining rigorous mathematical proofs, advanced AI search techniques, and massive-scale computation to solve a class of problems that have fascinated humans for over 200 years.