Analysis of the Quality of the Various Freecell Solvers

Introduction
The Analysis Itself
Conclusion

Introduction

As you recall, Gary Campbell’s comment provided the motivation for my investigation into what makes a project high-quality and which quality-increasing-measures are not elements of quality by themselves. And since Freecell Solver has been my pet project, and as I’m still interested in techniques for solving Solitaire, I’d like to conclude this essay by analysing the various solvers according to the parameters I described. The natural caveat is that I may be somewhat biased due to the fact that I authored a solver of my own.

I was not so sure including this section is a good idea, but I feel the article is incomplete without it. Feel free to skip it, in case you are not that interested in it. [FC-S-Comp]

The Analysis Itself

As is not uncommon in many software niches, some Freecell solvers are not commonly available for downloading or even for buying. For example, Bill Raymond’s solver (named “Cat in the Sack”) which he has been talking about extensively, has not been released yet, under any licensing terms. Similarly, Danny A. Jones has kept his solver (mentioned in the introduction) for himself, and has not released it to the wild in either source or binary forms.

As such, the utility of such solvers is heavily reduced. For once, they cannot be used as integrated solvers of Solitaire apps, because no one is going to wait for an email to the author to be sent, and the author to reply with the solution. Also, many researchers won’t trust solutions given by them without the ability to inspect the source code.

Most other solvers are available for free download, and many are accompanied with the source, most probably under an open-source licence.

Gary Campbell’s Solver is written in 8086 Assembly, with some 32-bit extensions, and only runs on DOS and DOS-compatible platforms. The assembly is compiled using a self-hosting macro assembler written by Campbell. The Assembly source code of the solver or the assembler are not available. As such modifying the code of the executable may prove to be problematic.

It is tempting to think that x86 and DOS are a very low common denominator, but that is not always the case. Imagine that you are writing a Freecell game for an embedded device running a non-x86 architecture such as ARM or PowerPC. In that case, in order to run Campbell’s solver, you’ll need to embed an x86-and-DOS emulator (such as DOSBox) inside the device, which will complicate things, consume a lot of memory, and slow things down. On the other, an ANSI C-based solver, such as Freecell Solver, or Tom Holroyd’s Patsolve, can be easily made to compile and run there with few if any modifications. So they would be preferable.

Similarly, when writing portable programs for the various Unix flavours and other POSIX-capable or ANSI C-capable operating-systems, then writing code in x86 Assembly exclusively will make it a non-starter. [Portions of Assembly]

Some Freecell solvers also don’t build out of the box. For example, typing make inside the patsolve distribution yields the following output:


shlomi:~/patsolve-3.0$ make
make clean
make[1]: Entering directory `/home/shlomi/patsolve-3.0'
rm -f patsolve *.o param.c param.h core win .depend
make[1]: Leaving directory `/home/shlomi/patsolve-3.0'
touch .depend
param.py param.dat
make: param.py: Command not found
make: *** [param.h] Error 127

        

This is relatively easy to fix, but still frustrating. Freecell Solver on the other hand, has been fully converted to the GNU Autotools, and can be built as a static and shared library (a.k.a DLL). It also has some built-in proof-of-concept, but still usable, command line utilities that link against it.

Freecell Solver has very good usability: it mostly respects the Unix conventions and best practices, it can start solving from any arbitrary Solitaire board position given to it as input, and has kept command line interface usability in mind. Campbell’s solver on the other hand, as of this writing, does not operate on a standard input/standard output manner, is poorly documented, and is counter-intuitive for someone who is used to Unix conventions (and most DOS conventions). I’m not even sure it can accept any arbitrary board as input, but I may be wrong.

Regarding the homepage of the solver: the Freecell Solver homepage has many pages, a navigation menu, a common look-and-feel and many links and information. On the other hand, Patsolve’s homepage is nothing but a link in Tom Holroyd’s software archive, which can easily be missed. Gary Campbell’s homepage for his solver has a Baroque design and quite a lot of marketing-speak. And it’s only one page with no anchors or a navigation menu, and very few links. Most other solvers don’t fare better than that, and certainly worse than my own.

Licensing, a necessary, but important, evil. The Freecell Solver’s ANSI C source is distributed under the Public Domain licence, which allows virtually any use, including linking, modifying and sublicensing under any different licence by a third party.[PD-LICENSE] On the other hand, Patsolve is distributed under the GPL licence which while usable is considerably more restrictive than Public Domain, or BSD-style licences. This is also the case for this Common Lisp solver by Kevin Atkinson and Shari Holstege. Many other solvers, including Campbell’s are binary-only, “All Rights Reserved”, which makes them a complete no-starter for most open-source applications out there. Furthermore, many non-open-source applications will prefer to use a Public Domain solver, rather than paying royalties or risking “copyrights” and source availability problems.

Freecell Solver (FCS) is extensively documented, and even its online help is helpful and usable by itself. The other solvers are much less documented, but arguably they also have much fewer options and features than Freecell Solver does.

Which brings us to the features - Freecell Solver has a long list of features, and I’m not aware of any other solver with so many. Especially of note is that it can solve many other Solitaire variants, including Simple Simon, of which FCS is probably the only solver capable of solving.

Most of the solvers out there are fast, but some are more than others. Normally, for solving an individual game on the command-line, almost any solver will do, and the only cases where such speed matters more is for Solitaire research, and for analysing large sets of different games. (see the Freecell FAQ for more information).

In his original message, Mr. Campbell claimed that the Freecell Pro solvers (Freecell Solver, Patsolve and the solver that originated from Don Woods) generated long and unusable solutions. That has not been my experience with Freecell Solver in some of its (practically infinite) configurations. Using the so-called “good-intentions” configuration I typically get solutions that are less than 200 moves. It is highly possible this is not the default in Freecell Pro. But like I said, there are many different parameters for quality than just speed and solution-length. Another fact worth of noting is that a beta-tester who tried out some of the Freecell Solver solutions in Freecell Pro, said that he found them to be very “creative” and interesting.

Freecell Solver has some other advantages: it is capable of being fully instantiated, as it stores everything in an “instance” C-struct, while using global variables only for constants (and not using static variables). This makes doing parallelised testing using mutli-threading much easier. It also has namespace-purity in the sense that all variables start with the freecell_solver_ prefix. Moreover, FCS has a well-defined and stable API, which is not well-documented, but should be easy-to-use.

Part of the API is a parser for a list of command-line-like strings, which allow for configuring without making many standalone function calls.

Conclusion

All things considered, I still feel that Freecell Solver is probably the best quality Solitaire solver out there. While it still has a lot of room for improvement, the rest of its competition have much bigger issues, or have not been made available (yet or ever).

Several factors contributed for its success: the fact that I announced many releases on Freshmeat.net, that I received a lot of input from my users and co-developers, that I was determined to constantly improve it and work on it, and that I worked on creating and maintaining a good web-site and documentation.

While most of the contributions of code I received were limited, the input from the users of the software proved to be crucial for its prosperity. Like I noted earlier, I lost interest in working on it (at least temporarily), but still maintain it, and feel that it is good enough as it is.

I hope this document, and similar resources it referenced will help you in working on your software, and improving its quality for the benefit of your users and you.

Happy Hacking!



[FC-S-Comp] This section is not meant as a comprehensive comparison of the Freecell solvers. The latter has yet to be written and would be much more difficult than what I’m doing here. It would be complicated by factors such as:

  1. Some solvers are binary-only and only run on DOS or Windows. Open-source command-line ones may probably perform better on Linux or other Unix systems.

  2. Some of them are not publicly available in any form.

  3. Some of them can only solve Freecell, while others are more generic and can solve other Solitaire variants. (which in turn may hurt their performance.)

  4. They differ in their solving algorithms. For example, some use atomic (= one-card) moves, some move entire sequences at a time, and some are based on meta-moves.

[Portions of Assembly] In some cases, the developers of portable software maintain versions of parts of the code in Assembly of selected architectures, while keeping more portable versions written in C or C++. This is done to optimise some parts for common CPU architectures.

[PD-LICENSE] As noted earlier, a Public Domain non-licence has some problems, which may make the software problematic for many corporations and in some jurisdictions. However, I don’t have problem in exempting the licence of the Freecell Solver code (at least not the Public Domain code that I fully originated), from the Public Domain, including under the MIT X11 Licence, assuming this is necessary.

I’m also considering relicensing Freecell Solver and other older software of mine under the MIT X11 licence, or possibly having a dual-Public Domain and MIT X11 licensing terms (which seems somewhat silly, but may be a good idea.)