Freecell Solver - “The Well and the Wall”

Prologue

The well of a project is the developer or two that do most of the work. They are important, but a project has known to survive their demise. The wall of a project is its license. It protects it against abuse of the code.[Humanity]

Many people would automatically assume that the license should be GPL or LGPL. However, Freecell Solver was released under the Public Domain. And I think releasing it under the Public Domain was the best thing I've done. (to semi-quote Linus Torvalds who said that "Making Linux GPL'd was definitely the best thing I ever did."). And here's the funny part: I think Linus would agree with me.

Note that I come to praise the "Cathedral and the Bazaar" not to bury it. I'm just saying that I did things a little different; that it worked (Freecell Solver is a category killer) and that I'm happy that I did it this way, albeit may have done better the next time.

How it all started

I must have told the story a lot of different times in different contexts. Once, on a short break between two semesters, I went out running and while I did I wondered how I can solve Freecell programmatically. I reached two conclusions:

  1. A depth-first scan would probably be better than a breadth-first scan. (I figured the number of states as the function of the depth N grows very largely).
  2. Using atomic moves (moving one card or one sequence at a time) would be silly, and I have to make meta-moves (= compound moves of doing more than one move at a time) to achieve good results.

The first conclusion turned out to be relatively true. The second conclusion turned out to be false, but as you will see later, it had a very pleasant side-effect.

I decided that I just want to write it down to see if it works. So I coded a Perl version that used a list as an excuse for a states collection. It was too slow for its own good. I decided to convert it to C, this time using a sorted array with a sort margin. It worked nicely even when I implemented only some of the "tests": the types of meta-moves I had in mind. When I implemented all of them it worked well for most boards I've tried. (I generated 1000 sample boards using a Perl script), and it took a lot of time for many of them, but I was glad it was usable.

I then, made sure my code compiles as ANSI C (I started with C++ while using only the advantage of middle-scope variables), packed it with the makefile I wrote in an archive. I put it under a sub-site on my site, and announced it on Freshmeat under the name "Freecell Solver" with version 0.2.

One thing you can notice is that I actually threw one version away. I'm still not sure the program would have been too slow in Perl, if I did it right. But I still think the C version is much faster than the equivalent Perl or Lisp one. Can't tell about C++ or Java.

Since then I'm happy to say, that the code was never entirely re-written from scratch. Nor do I intend or think it is the right thing to do. Open Source Projects were known to survive a re-write. (that's one of the advantages of Open-Source) Nevertheless, I'm too attached to the code to throw it all away so fast. I can much more easily refactor or rewrite the parts I need to while still convert the code back to a working condition after a while. There' s a lot of logic in the code that has nothing to do with anything else. Many people think Joel Spolsky does not know what he's talking about, when he advises against rewriting a large code-base from scratch or that it does not apply to Open-Source. But rewriting is costly. Refactoring is much quicker (again, a link to Joel-on-Software), even if you are left with practically nothing of the same code after a while.

What I did not do according to "the Cathedral and the Bazaar" was look for similar effort. As I discovered, most of the Freecell Solvers out there did not use Meta-Moves, so it turned out that my thought experiment that was realised into working code was a good thing. Now, I always look for similar effort. But I still make thought experiments (seeing if this thing would work in Haskell, etc.). I like to code, and I like the look of a blank gvim window eager to accept my input.

A useful contribution

Eric Warmenhoven sent me a program to generate the boards of GNOME Freecell. I thanked him for it, and set out to write the same for other solitaire implementations I knew. I had to clean up Eric's program a bit, but it was still nicer than digging the source trying to extract the program.

Eric also said he liked my program very much. It made me happy to feel the program was useful to someone. There's nothing that beats that feeling. A thank you goes along way. E-mail a developer today.

The Freshmeat Effect

Naming the program "Freecell Solver" made it the first hit for the query "freecell solver" on Google immediately. As I released more versions, placed them online and announced them on Freshmeat, the situation got steadily worse. I found all kind of junk of it there, like obscure packages of various distributions of Linux and FreeBSD, and rarely something of any good. What I did find from time to time were reviews of it or mentioning.

I link to all the reviews I can find online on my site. And if you know of more, feel free to send them to me. A good review goes along way for a developer.

I regret not giving Freecell Solver a more original name, because I still hated to see Google and other search engines clogged like this.

What people did with the code

On my TODO list I had an item of "Integrate with PySol and/or GNOME Freecell and/or GNOME AisleRiot and/or kpat". I actually tried to push it so the GNOME guys would accept it. (At that point GNOME Freecell was my favourite solitaire implementation. My favourite is PySol, now). Eventually, I contacted a developer directly, and he referred me to the maintainer. The latter was to o busy to do anything with it.

However, later on, after version 1.0.0 that included a user API was released, Stephan Kulow informed me that he integrated Freecell Solver into the KPatience (a.k.a kpat) of KDE 2.1. I was a bit disappointed that he did not use the API I created and instead asked him to convert it to the user API while adding functions as he see fit. (I told him "I'll sleep better at nights" if that was so and it was true because the internals of the program were subject to change, and very un-user-friendly) As a result he did just that, and sent me a patch to the program.

At roughly the same time, I contacted Markus Oberhumer (of PySol fame) about integrating Freecell Solver with PySol (which I started to really like). He sent me another patch. His problem was that he wanted the solver to be stable. I.e: that if State S1 recommends going to S2, then if running the solver on S2 would not lead back to S1. It turned out that was not the case, and I told Markus, that making sure this was the default would be too time consuming as far as I could see. I also said that running the solver for each state, would be a brain-dead decision, as the solver already returns all the moves up to the solution.

I lost contact with Markus, and he did not answer any of my E-mails for a long time. PySol 4.80 included a Python class to integrate with a Freecell Solver bindings, but I could not find the C back-end anywhere. I'm toying with the idea of integrating it myself, but so far did not have the time to. (I also don't like Python too much)

After I got to know him, I contacted Michael Keller (who wrote the Freecell FAQ) if he can forward me to Adrian Ettlinger, who was the author and maintainer of Freecell Pro, a Freecell implementation for Windows, that featured its own solver (originally written by Don Woods and later modified by Calahan and Ettlinger himself) and many other features. Adrian said he would be glad to integrate Freecell Solver as well.

Adrian is a hacker in his seventies, who originally started as an Electrical Engineer and gradually converted to programming. Furthermore, he does not have an active knowledge expertise in UNIX concepts. A lot of the Freecell Pro code suffered from bad design decisions, and Adrian himself admitted to me that the quality of his code leaves a lot to be desired.

Working with Adrian proved to be an enlightening experience anyhow. It took me a lot of time to get Freecell Solver to work flawlessly with Freecell Pro, including writing some routines to convert it to Microsoft-Freecell-compatible moves. Now it works perfectly, but it took more than a year. Note that I still don't regret putting the effort into this.

Adrian also talked with Dr. Tom Holroyd, patsolve's author about integrating patsolve with it. Adrian became convinced right from the start that it would be a good idea to release the Freecell Pro Solver Evaluation Edition as Open-Source and he eventually chose the GPL for it.

I am the most happy with the integration of Freecell Solver into Freecell Pro, from all the programs that integrated it, as Freecell Pro can run it in several modes, some of them customizable.

Note that I am toying with the idea of coding a cross-platform Freecell implementation myself written in C++ using wxWindows, Qt or something similar. Nevertheless, I did not have the time yet to do it, and the internals of Freecell Solver and other projects are much more exciting at the moment.


Dave Wilkinson e-mailed me at March 7, 2002 and informed me he has integrated Freecell Solver into Freecell3D, a three-dimensional implementation of Freecell for Windows 32. He thanked me for making Freecell Solver available under the Public Domain and for making it "so easy to integrate". He then said he would send me a free licence key, without charge, as he could not possibly charge me for it. I gladly accepted the licence.

I was thrilled to discover he could integrate FCS without any of my help, and actually found it encouraging and boosting.

Now for some discussion of the license in respect to all that. All the people who integrated Freecell Solver into their products (at least those that I know of) mentioned Freecell Solver and its homepage in their "About" dialogue box. I don't know how I'm going to feel if someone integrated Freecell Solver there and did not acknowledge me, but I'd rather have it under a GPL compatible license than try to make it otherwise. (See the Original BSD licence's advertising clause problem)

I initially chose the Public Domain simply because it has no restrictions , and at the time I did not like the GPL very much. (I still like to ridicule it on every possible occasion[GPL]) I don't regret choosing the PD. As David J Goehrig. noted to me once, if a commercial entity wants to take an open-source code and release an enhanced version, then "all the power to them".

I personally don't see much business opportunity in creating an enhanced version of Freecell Solver. However, putting it under the Public Domain, is one thing that can kill any other GPL competition, making Freecell Solver the cutting edge technology, not only now but for a long time into the future.

I really don't have a policy against people forking a GPLed copy. However, I do ask them that unless they intend to make it proprietary, to keep it under the Public Domain. So far, all contributors respected that.

Getting People to Contribute

Getting people to contribute on Freecell Solver has turned out to be hard for more than one reason:

  1. I hate those developers that whine about people not contributing. (it usually is a bad idea)
  2. I like working on Freecell Solver, and albeit am not over-possessive about the code, I do like to do things on my own.
  3. Freecell Solver's source code contains some very advanced (IMHO) techniques, and some relatively optimised for speed code. I do announce what I intend to do next and what I did to the mailing list. However, I do not know how many of its members understand it enough to contribute.

Note that, from my impression, most of the mailing list members stay there to hear about the cool techniques and re-organizations I add there, so I don't try to avoid posting such stuff there..

Usability and Social Engineering

As I noted in an Advogato Editorial, "Human Engineering" is not just about answering users politely and actually transcends to the design of the product and to its homepage. If you spot a pattern in users' questions, then there is probably a feature that should be implemented.

The most common question I received, was from Windows users, who try to double click the command line application and get an empty dos box in return (as it accepts standard input). Recently, I made sure Freecell Solver outputs two lines to the standard error in that case.

Another thing I did was made sure the --help screen was much less crowded (it became 7 less-clicks long), but that it could also be set to a different screen by using an environment variable.

Finally, I added presets, which were files that could be used to configure the program (whose configuration lines became quit insane) in one way or another.

The Mailing List

I formed the mailing list in an attempt to centralize the discussions I had with Stephan Kulow, Markus Oberhumer, Tom Holroyd (author of patsolve) and others I had a few transactions with. Most of them joined there and some of them left.

The mailing list did not completely eliminate discussions that took place off-line, but it was probably for the best because that way it would have had a lower Signal-to-noise ratio.

One thing that happened on the mailing list was that GeYong posted there an announcement about Freecell Tool, a solver for Freecell that he wrote. I tried it out and noticed it had a randomized scan. I thought it was a good idea and implemented it in Freecell Solver, too. Like ESR said, recognizing good ideas from your users is equally as important if not more than having them yourself, and I cannot not agree more retrospectively.

Like I said earlier, the mailing list hosts some high-level posts of algorithms and techniques, which are not for the ordinary mundane programmer. The mailing list has a steady subscribers' list and from my impression most of them actually enjoy these posts.

The mailing list has some colour besides myself. Most notable are:

  1. Bill Raymond - a Freecell solver guru who claims to have written the best solver that ever was, yet is reluctant to release it to the public in one form or another. Bill tends to be a little flamatory, but since he knows what he is saying (and naturally adds spice to the list) I am still keeping him.
  2. Adrian Ettlinger - Adrian is not as good a computer scientist as I or Bill Or Tom Holroyd, but he is still an expert in Freecell solving. He tends to be very kind and restrained.
  3. Tom Holroyd - the author of patsolve, another solve for Freecell and Freecell-like games, he makes very few posts, usually related to patsolve, somehow. He is a formidable computer scientist and also a good Freecell and Seahaven Towers enthusiast.

So, all in all, fc-solve-discuss, has its niche in the world and you are most welcome to join it if the topic interests you. Contributions to the Freecell Solver code-base are welcome, but are not absolutely necessary.

Publish or Perish

Freecell Solver had a dedicated site all along. The site took several transformations. First, it was split into several pages, and then I applied a common look and feel with a navigation bar, CSS stylesheets and :hover links to it. I think it also makes the site more usable, especially for people with disabilities. Website Meta Language had been a great help in doing the latter.

I kept a news section dedicated to what's new in every stable version of Freecell Solver, and kept all the old news items. I also kept posting regularly to Freshmeat, sometimes to announce a non-stable release that was a milestone as far as new features and stability was concerned.

As far as I know, Freecell Solver is the only solver that has such a dedicated homepage and is so actively maintained. This gives is a lot of edge in making it the category killer. It also makes perfect sense that it would be considering those circumstances.

Footnotes

  • [Humanity] - the Well and the Wall are a reference to my open-content (CC-by-sa-licensed) screenplay "Humanity - The Movie", which you are encouraged to read. I drew inspiration for it from the title of Eric Raymond's "The Cathedral and the Bazaar" essay, before I started reading it.

    I should note that I originally had delusions that this movie was already made by someone else as part of a Clinical Mania I have experienced, and later was fond of the idea enough to write it as an actual screenplay.

  • [GPL] - See for instance:

    1. "The GPL is not Compatible with itself"
    2. The "COPYING" file of Freecell Solver