Subject: RFC: The Well and the Wall

From: Shlomi Fish <[email-masked]>
Date: Wed, 18 Sep 2002 09:10:18 +0300 (IDT)

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.

Regards,

	Shlomi Fish

The Well and the Wall
---------------------

Prologue:
---------

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

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

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

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
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
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":

http://www.linux.org.il:8080/Control_Panel/Products/Squishdot/IGLU/1017635388/index_html

The "COPYING" file of Freecell Solver:

http://cvs.berlios.de/cgi-bin/viewcvs.cgi/fc-solve/fc-solve/source/COPYING?rev=1.1.1.1&content-type=text/vnd.viewcvs-markup

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"