History and game design of Klondike solitaire

Klondike solitaire is a former gambling game, world's most popular solitaire, and a computationally complex problem that is played on super computers. This is an English summary wall of text and a companion post to a presentation at Tracoff 2.0 online convention.

The presentation is in Finnish but the summary of the presentation and sources are in English.

Prologue

My name is Mikko Voima and I make video games. Come 2021, I started researching the game design, history, and solvability of the Klondike solitaire in an effort to write my bachelors thesis [1]. The playable Klondike solitaire game prototype was developed as a practical implementation to analyze the mechanics. However, when I ventured into the 'Forest of all knowledge' I encountered many portals such as one into the 'What is true?' -dimension [2]:

Just about any academic topic will have experts who have spent their entire lives thinking about this one area and who also violently disagree with each other.  Which can leave you, the non-expert, to wander dangerously close to the "What is True?" dimension, which, if you're not careful, will suck you into an unproductive, downward spiral of "How do we know anything is true?
—CGP Grey

History of solitaires/patience games

Solitaire games are thought to have originated in France as many old and famous solitaires have French names. According to David Parlett, a Nordic or Baltic origin is also possible [3]. All early card games are competitive social games by their very nature as described in The Compleat Gamester [4]. Puzzles are known at the time but these are not thought of games per se at the time. Solitaire game rules first appear in Das neue königliche l'Hombre in 1788 [5] although it describes a two player game in which only one of the players plays the game at a time. An early French book [6] describes how solitaire games provide resources against the cruelest enemy — boredom:

La solitude! Que je la crains!
—— ressource contre notre ennemi la plus cruel, l’ennui!
—— à la construction d’une barricade contre l’ennui?

David Parlett also asserts that solitaire games appear at the same time as fortune-telling with cards (cartomancy) [3]. For example, the 'Fortune-telling patience' appears in later solitaire books [7]. Superstitious people at the time might make decisions based on whether a game of patience comes out. Leo Tolstoy's book War and Peace [8] provides one example:

“If this patience comes out, ——Then it will mean that I must go to the army,” said Pierre to himself. 

History of Klondike solitaire

Klondike solitaire appears during the time period known as the Gilded Age (1870–1910) is US history [9]. At that time Richard Canfield, 'the King of Gamblers', is running illegal casinos in New York [10]. The establishments attract the multimillionaires of the time and are described as palatial [14]. Those who lost would get a split of champagne [11] and Canfield would offer credit so that thick stacks of cash wouldn't ruin tuxedos [12]. The casino chips at the casino are made of ivory [13]. Allegedly a solitaire game was played at the casino such that the player would pay 52 counters for the pack and receive 5 counters for every card in the Foundation. The game became known as Canfield [15, 16, 21] and sometimes known as Klondike [15, 17].

Wikipedia is mistaken

The controversy with Canfield solitaire involves two games that are often mistaken for one another. One game is known in the literature as Fascination [18], Demon patience [20], or Fooliana [19]. In this post I will refer to it as Demon. The other game can be traced to games called Triangle [19, 20], Thumb and pouch [20], or Small triangle [21], and shall be referred to as Klondike.

Meanwhile Richard Foster writes a 600 page encyclopedia on all indoor games — but includes only includes a couple of solitaire games. The 1897 edition includes neither Demon nor Klondike [23]. The revised 1909 edition [24] adds Klondike:

This game is sometimes called Canfield when the player pays fifty-two chips for the pack and gets five for every card he gets out.

Meanwhile, Hoyle's Games [17] calls both games Klondike saying:

There are several ways of playing this game.

Foster's 1914 editions [25, 26] now includes both games with different names. Klondike is called Klondike thusly:

This game is sometimes mistakenly called "Canfield" but that is a distinct game...."

Foster later works as the editor for The Official Rules of Card Games published by U.S. Playing Card Company. In the 1915-16 edition [31] Klondike is still the gambling game with counters as bets but Demon is called Canfield like in Foster's other books.

Later on in the 1940's Morehead & Mott-Smith quote Foster and state explicitly that the game played at Canfield's casino was definitely Demon and called Canfield [27]. Morehead & Mott-Smith also falsely claim that Demon and Fascination are regional names for Klondike [29]. Later still, Parlett uses Morehead & Mott-Smith as a major source repeating the claim that Demon should be called Canfield [28]. Michael Keller also wrote an article discussing this very question [22].

In the 1930's Herbert Asbury wrote a book on the history of gambling in United States. He also tried to trace the origin of Canfield solitaire and "ran into a curious maze of confusion" [10]. He concludes maybe Harris B. Dick took advantage of Canfield's notoriety and continues:

Another conclusion, possibly more logical, is that the whole thing is a mess.

Game rules and mechanics

The Klondike game rules and different rule variants are explained in more detail in my thesis [1].

In terms of difficulty, both Demon and 'Draw 1 & No redeal' Klondike are regarded as difficult games. The difficulty could suggest a gambling origin as the casino would make profit if the player loses money. In computer simulations, 71% of Demon games are solvable [30]. These percentages are only possible if you can undo moves and experiment freely. Parlett also played 10 games and claims to have won $95 [28].

The 'Draw 3 & infinite redeal' Klondike could be thought of as a gamified gambling game to make it more likely to win and thus more fun.

Solvability

The solvability and different studies are described in detail in my thesis [1]. Solitaire: Man vs. Machine [33] is the first academic study to use the rollout method and computers to solve Klondike. The study contains the most famous quote in the academic solitaire research literature:

It is one of the embarrassments of applied mathematics that we cannot determine the odds of winning the common game of solitaire.

The quote is often attributed to Persi Diaconis, who is a former professional magician turned math professor. He has also appeared on Numberphile to discuss the best method of shuffling playing cards [34].

Finally in 2019, Charlie Blake studied 45 different solitaire games on Edinburgh University super computers (EPCC) [36].

Computational complexity

The computational complexity of Klondike is also addressed in my thesis [1]. The so called 'N versus NP problem' has been described as follows [37]:

Unsolved problem in computer science
If the solution to a problem is easy to check for correctness, must the problem be easy to solve?

In this context a possible solution for Klondike is easy to check: you just have to follow the proposed solution and see if the game solves itself. Finding the solution, on the contrary, is hard. In the worst case scenario you have to exhaust all possible combinations of legal moves. Hypothetically all Klondike games are also easy to solve if we just pick the correct moves by sheer luck every time (if a solution exists).

The MIT professor Erik Demaine [38] explains how this is unrealistic phrases it as:

You can't engineer luck!

Game studies

In the Finnish survey Pelaajabarometri 2020 [39] solitaire is the most popular digital game series — after the betting games by the government-owned betting agency Veikkaus. Maybe we haven't moved that far away from Canfield's casinos after all.

I also considered the question: which genre should the single player card games be if they weren't categorized as solitaires or patience games? Various competitive PvP versions of solitaires exist such as Double Canfield [16] (Klondike with two packs). A fast paced six player PvP variant of Demon exists digitally as NERTS Online [40]. Old Windows Solitaire gives time bonuses so it could be considered a speed-running game. Thoughtful solitaire could be considered a puzzle game that is so hard that the optimal strategy is still not known. I ended up playing my own prototype as a pseudo co-op game with Discord screenshare trying to look for solutions to the same set of games together. Casual could be considered as simply a passing the time (in Finnish literally time killing) activity.

Ultimately I found the historical perspective from Miss Jones [7] deeply touching and poetic:

 In days gone by, before the world lived at the railway speed it is doing now, the game of Patience was looked upon with somewhat contemptuous toleration, as a harmless but dull amusement for idle ladies, and was ironically described as "a roundabout method of sorting the cards"; but it has gradually won for itself a higher place.

For now, when the work, and still more the worries, of life have so enormously increased and multiplied, the value of a pursuit interesting enough to absorb the attention without unduly exciting the brain, and so giving the mind a rest, and, as it were, a breathing-space wherein to recruit its faculties, is becoming more and more recognised and appreciated. Patience, therefore, claims to be not only of negative, but of positive merit; and one charm of the game or, to speak more correctly, the series of games is the infinite variety. 

——Mary Whitmore Jones

Even Klondike can be traced to an earlier, slightly different, game called Triangle [19] of which Cheney writes:

Much skill can be employed in this game, and it may often be won by careful changes and rearrangements when it seems to be lost.
—— succeeds often enough to encourage the player.

Perhaps Klondike need not be a depressing game of chance but an encouraging game of Patience after all. I'd like to close with a quote from Cheney [19]:

It has been a welcome thought that this humble work has helped many a poor sufferer in exercising the virtue whose name it bears; has cheered the loneliness of old age, and even soothed the pangs of sorrow. May it go on ever developing and improving, until " Patience has its perfect work " in mitigating the sufferings of humanity.

Thank you for reading through patiently.

List of sources

Source follow the following format: Author (birth–death), publication (year originally published) [, Edition (year)]. Link, if publicly available.

1. Mikko Voima (author), Klondike solitaire solvability (2021). https://www.theseus.fi/handle/10024/501330
2. CGP Grey, CGP Grey was WRONG (2020). https://www.youtube.com/watch?v=ua4QMFQATco
3. David Parlett (1939–present), History of Patience/Solitaire. https://parlettgames.uk/histocs/patience.html
4. Charles Cotton (1630–1687), The Compleat Gamester, 1721 edition (unknown editor). https://archive.org/details/gpl_1738356/page/n13/mode/2up
5. Unknown author, Das neue königliche l'Hombre, 12th edition (1788). https://play.google.com/store/books/details?id=TqZZAAAAcAAJ
6. Comtesse de Blanccoeur, Le Livre Illustré des Patiences (1880). https://archive.org/details/LeLivreIllustrDesPatiences/page/n1/mode/2up
7. Mary Whitmore Jones (1823–1915), Games of patience for one or more players. Second series (1898). https://archive.org/details/gamesofpatiencef00joneiala/page/n3/mode/2up
8. Leo Tolstoy (1828–1910), War and Peace (1867), Project Gutenberg eBook, Chapter XVIII. https://www.gutenberg.org/ebooks/2600
9. Esther Crain, The Gilded Age in New York, 1870-1910, Kindle edition (2016). https://www.amazon.com/Gilded-Age-New-York-1870-1910-ebook/dp/B01BU1IU0E/
10. Herbert Asbury (1889–1963), Sucker’s Progress: An Informal History of Gambling in America (1938), Google Play Edition (2016). https://play.google.com/store/books/details?id=jFlODQAAQBAJ
11. Saratoga Springs Preservation Foundation, “Preservation Matters” Strolling Through History: Canfield Casino (2020). https://www.saratogapreservation.org/preservation-matters-strolling-through-hist...
12. Saratoga.com -- Patrick Kerrison, Fists vs Wits – Part II: Richard Canfield (2010). https://www.saratoga.com/much-ado/2010/08/fists-vs-wits-part-ii-richard-canfield...
13. Saratogaliving.com -- Natalie Moore, Was the Casino Chip Really Invented in Saratoga Springs? (2020). https://saratogaliving.com/casino-chip-intvented-saratoga-springs/
14. W. Somerset Maugham (1874–1965), The Gentleman In The Parlour (1930), Google Play Edition (2010). https://books.google.fi/books?id=MnNF7FDyP9sC
15. Lady Adalaide Cadogan (1820–1890), Lady Cadogan's Illustrated Games of Solitaire or Patience (1869), New Revised Edition, including American Games, unknown editor (1914), p. 118–119. https://catalog.hathitrust.org/Record/100485062
16. George Hapgood, Solitaire and Patience (1908), 1920 Edition. https://archive.org/details/solitaireandpat00hapggoog/page/n4/mode/2up
17. Edmond Hoyle (1672–1769), Hoyle's games, Autograph edition, unknown editor (1914). https://catalog.hathitrust.org/Record/011206253/Home
18. Harris Brisbane Dick, Dick's games of patience, Second Series (1898). https://catalog.hathitrust.org/Record/008684200
19. Ednah Cheney (1824–1904), Patience: a series of games with cards (1869), 3rd Edition (1895). https://catalog.hathitrust.org/Record/011209893
20. Mary Whitmore Jones (1823–1915), Games of patience for one or more players, Series 1–5 (1900). http://classic.cincinnatilibrary.org/record=b2969794
21. Mary Whitmore Jones (1823–1915), New games of patience (1911). https://archive.org/details/dli.ministry.17835/page/n7/mode/2up
22. Michael Keller, What game was played at Canfield's Casino? (2013). http://www.solitairelaboratory.com/canfield.html
23. Richard F. Foster (1853–1945), Foster's encyclopedia of games, 8th Edition (1897). https://catalog.hathitrust.org/Record/011206253
24. Richard F. Foster (1853–1945), Foster's Complete Hoyle: An Encyclopedia of Games, New revised and enlarged edition (1909). https://catalog.hathitrust.org/Record/100487149
25. Richard F. Foster (1853–1945), Foster's Complete Hoyle: An Encyclopedia of Games, New revised and enlarged edition (1914). https://catalog.hathitrust.org/Record/011204898
26. Richard F. Foster (1853–1945), Foster's encyclopedia of games, 1914 Edition. https://catalog.hathitrust.org/Record/100489608
27. Albert H. Morehead (1909–1966) & Geoffrey Mott-Smith (1902–1960), The Complete Book of Solitaire and Patience Games (1949), Google Play Edition (2015). https://play.google.com/store/books/details?id=1XB-CgAAQBAJ
28. David Parlett (1939–present), Solitaire: aces up and 399 other card games (1979). https://archive.org/details/solitaireacesup300parl
29. Albert H. Morehead (1909–1966) & Geoffrey Mott-Smith (1902–1960), Hoyle up-to-date (1959), 1988 Printing. https://archive.org/details/hoyleuptodate00albe/page/n3/mode/2up
30. Jan Wolter, Experimental Analysis of Canfield Solitaire (2013). https://politaire.com/article/canfield.html
31. Richard F. Foster (1853–1945), Official rules of Card Games, Hoyle up-to-date 1915-16, Publisher's 20th Edition (1914). https://catalog.hathitrust.org/Record/102720847
32. Chris Kuykendall & Dana McKenzie, Analyzing Solitaire, SCIENCE vol 283 (1999).
33. Xiang Yan, Persi Diaconis, Paat Rusmevichientong & Benjamin Van Roy, Solitaire: Man versus machine (2004). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.6247
34. Numberphile & Perci Diaconis, The Best (and Worst) Ways to Shuffle Cards (2015). https://www.youtube.com/watch?v=AxJubaijQbI
35. NewScientist -- Dana McKenzie, We finally know the odds of winning a game of solitaire (2019). https://www.newscientist.com/article/2223643-we-finally-know-the-odds-of-winning...
36. Charlie Blake & Ian P. Gent, The Winnability of Klondike Solitaire and Many Other Patience Games (2019). https://arxiv.org/abs/1906.12314
37. Wikipedia, P versus NP problem. https://en.wikipedia.org/wiki/P_versus_NP_problem
38. Erik Demaine, Computational Complexity (2013). https://www.youtube.com/watch?v=moPtwq_cVH8&t=1964s
39. Jani Kinnunen, Kirsi Taskinen & Frans Mäyrä, Pelaajabarometri 2020: Pelaamista koronan aikaan. https://trepo.tuni.fi/handle/10024/123831
40. Zachtronics, NERTS! Online (2021). https://store.steampowered.com/app/1131190/NERTS_Online/