In this post I wanna talk about the Freecell Project. I beg pardon of the reader if he is familiar with it, but I thought it provides me a good starting point to discuss a similar project with plspider.

Freecell is one of the best-known variants of Solitaire, and distinguished by the fact it is almost always won with best play. Moreover, Microsoft has included a FreeCell computer game with every release of the Windows Operating system since 1995 including the dreaded 4112141 41111 that probably originated in the Ninth Circle of Hell and dare not speak its name (Letters replaced with point-values in Scrabble)

But we digress. ☹

The original Freecell has 32,000 deals corresponding to seed numbers in the range 1-32,000. That means if you input the same seed number you always get the same hand. This allows players to verify the results of others.

In case you’re already bored by me waxing eloquent about things you already know, here’s a little-known fun fact. Many years ago, I used Microsoft Freecell at work by pretending it was a password management system. For instance, if I agreed beforehand that passwords are obtained by reading letters and numbers of the left-most column then a seed number of 11982 will generate A3KJ6JK. If I needed to update my password then I can compute the string of letters and numbers corresponding to a seed number 11983 etc. Obviously A3KJ6JK is a terrible password by today’s standards but you get the gist. Time has moved on and my workplace, rightly or wrongly, no longer has Microsoft Solitaire (or other games) installed.

Oops … I digressed again ☹

If you wanted to play a number of pseudo-random Freecell hands you could start with a seed number such as 27. After completing each game, you take the seed number and call it N. If N is odd then the next seed number is 3N+1. If N is even then the next seed is N/2. You keep going until you reach 1 or exceed 32,000. If you reach an infinite loop other than 1-4-2-1-4-2-1 then too bad! Whenever you solve a hand, you can add the solution to a shared repository and other players can verify that you indeed succeeded.

But if you’re part of a large team dedicated to testing every deal from 1 – 32,000 then you probably wanna do things a bit more systematically. If you had a team of 320 players then it is probably wise to assign each player a run of 100 consecutive hands rather than mucking about with the Collatz conjecture – and the observant reader has noticed that I digressed again. Oops! ☹

In the nineties, Dave Ring did exactly that. He started the Freecell Project to solve as many deals as possible using human solvers. If you’re thinking the number 11982 from my previous digression was familiar then you’re probably right. The project was finished in 1995 and only game 11,982 is (probably) unsolvable.

I say probably because I am not aware of any proof that it really is unsolvable. Google searching shows many have tried and failed, including both carbon-based and silicon-based entities. Some have even posted incorrect solutions. But that is no guarantee that a Ninja Monkey making random moves would not stumble upon a solution tomorrow.

Modern versions of Freecell have many more than 32,000 deals and it is estimated that 99.999% of deals are solvable.

The plspider project is similar. Only 32,000 hands were generated. This is not a coincidence – the logic for defining the permutation of cards is based on the same logic for Freecell. Obviously it can’t be the exact same hands since Spider has twice as many cards as Freecell, but the algorithm is similar. As an analogy you can think of applying SHA-256 cryptographic function once, twice, or thrice to obtain different strings. They look completely different even though they are based on the same algorithm.

In any case, it was found that (at least) 31998 games are solvable assuming unlimited undo/restart privileges. Converting to a percentage yields a win rate of 99.994%. That’s the same as Donald Bradman’s batting average but with an extra 9 added.

Oops, I digressed again ☹

One difference is that certain hands can be proven unwinnable. For instance, one hand did not allow the player to reveal any Sixes in the tableau or stock. I have yet to come across this phenomenon in actual play – even my most disgusting losses allowed me to verify the two decks contained least one occurrence of every rank.

Note that with plspider, I am unable to test the program on “custom hands” because that was not relevant to the original goal of the plspider project. And I assume the Freecell project is similar.

Final Thoughts

The plspider program succeeded in what it set out to do: estimate a win rate of randomly generated Spider Solitaire hands, assuming the player has unlimited undo/restart privileges. It was not designed to determine if a particular Spider Solitaire server is biased (e.g. dealing progressively harder hands without informing a strong human player).

Previous discussion with the author of plspider suggested I might have inspired Alex to add the feature of testing custom hands. The real problem is probably something to do with Past Alex rather than Present Alex … and Present Alex has warned me the source code is truly atrocious.