Loading ...
Sorry, an error occurred while loading the content.

RFC: The Well and the Wall

Expand Messages
  • Shlomi Fish
    I am including here below of a (mostly complete) treatise I wrote entitle The Wall and the Wall . This is my answer to ESR Cathedral and Bazaar . Your
    Message 1 of 1 , Sep 17, 2002
      I am including here below of a (mostly complete) treatise I wrote entitle
      "The Wall and the Wall". This is my answer to ESR' "Cathedral and Bazaar".

      Your comments are welcome.


      Shlomi Fish

      The Well and the Wall


      The well of a project is the developer or two that does most of the work.
      He is important, but a project has known to survive his leaving or (heaven's
      forbid, death) The wall of a project is its license. It protects it against
      abuse of the code.

      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). 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

      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.

      Conclusion #1 turned out to be relatively true. Conclusion #2 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. 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 returning to good integrity 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, or that it does not
      apply to Open-Source. But rewriting is costy. Refactoring is much quicker, even
      if you are left with nothing of the same code after a while.

      What I did not do according to CatB 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 turned into 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 solitaires
      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
      goodness. 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

      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 favorite solitaire implementation. PySol is mine, now). Eventually, I contacted a developer
      directly, and he referred me to the maintainer. The latter was too 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 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 there and never will.

      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 license key, without charge, as he could not possibly
      charge me for it. I gladly accepted the license.

      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" dialog
      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.

      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[1]) 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

      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 GPL-ed 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

      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 overposessive
      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 optimized 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 cancel this trend.

      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

      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 I took
      off-line, but it was probably for the best because that way it would have
      had a lower Signal-to-noise ratio. Nevertheless it did bring a few insights

      One thing was that GeYong posted there an announcement about Freecell Tool,
      a Freecell Solver he wrote there. 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 could not agree

      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 does he is very 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 codebase 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. WebMetaLanguage had been a great help in doing the

      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
      regularily to Freshmat, 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.

      [1] - See for instance:

      "The GPL is not Compatible with itself":


      The "COPYING" file of Freecell Solver:


      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      "Let's suppose you have a table with 2^n cups..."
      "Wait a second - is n a natural number?"
    Your message has been successfully submitted and would be delivered to recipients shortly.