Interview with Paul Alfille

Phone interview by Denny Cronin on May 4, 2000

Paul Alfille wrote the original version of Freecell which ran on the PLATO computer system at the University of Illinois in the mid-70's. All subsequent versions of the game, Microsoft's included, owe their existence to his original competitive multi user implementation. His original implementation provided almost every feature you see now in my humble NetCELL clone, all the while running on computers that were far, far less powerful than those we have today. I had the honor of doing a phone interview with the Father of Freecell. Freecell addicts of the world, meet Paul, the creator of the original Freecell game.

Let's talk about this Freecell game. When did this first start?

I guess the first thing would be, I'm not sure exactly where the game itself comes from. I remember as a child reading about some solitaire games, and one of the games was a game similar to this. What they said was that this was a game that was similar to chess in that you could see all the cards at once. And so it was purely strategy and not the chance, the unknown that you have with unexposed cards.

I fiddled around with the game, and I used to play it with cards. My complaint though playing with actual playing cards was that you'd end up with a very sorted deck of cards at the end of it, in numerical order by suit. And I wasn't very good at shuffling so I found that rather tedious.

So this progenitor game had multi column moves and all like Freecell?

Well no, this was Freecell. Before it was ever written for computer it obviously was played with actual cards.

One of the other Freecell sites has some information about other early Freecell-like games. They talk about some games mentioned in an old solitaire book. They name a progenitor game, but they suggest there was a key variation you introduced.

Well that's probably true. Where did they say the progenitor was from?

I don't know. I'll get you the link ( Michael Keller's Freecell FAQ

I'd be very interested in finding out the name of the book that somebody thought they saw a version of Freecell... I'm sure it wasn't named that, I think I made up the name.

I probably read that book as a child, and then it was just based on my memory, I just played with it... I don't know what the variant was that I might have introduced. So I played this one myself with cards, and then I had the opportunity at the University of Illinois to actually program it into a computer. It was mostly for my own convenience so I could play it and not have to shuffle the cards afterwards.

(laugh)

The reason I made it available for other people to use was that I was curious about the mathematics of it, what fraction of games are actually winnable or not.

In retrospect, that's rather naive because that the fraction of games people actually win which is not quite the same thing. People don't play at their peak.

What's interesting is that for the standard 8x4 game, that's the one that you get on the game Microsoft has, almost every game is winnable. But you can construct games that are unwinnable. Essentially put the cards in inverse order; low cards on top and high cards on the bottom.

[Here I fill him in a bit on the Dave Ring's Internet Freecell Project and other studies on the net]

But back to your original version...

Well, with what I programmed in, the constraint was really screen real estate. PLATO had a 512x512 gas plasma display (side note: one of the earliest bit mapped displays for a computer, very much ahead of its time) so if you rearranged things and were as conservative as possible you could get as many as ten columns across, (and obviously ten cells) and as few as four columns-- they'd get to be rather long.

So I allowed people to choose any range within there.

So you went down to as few as four columns?

Four columns with ten cells, and that's actually fairly frequently winnable. It's a different game, in a sense that you can go very deep into a column, but then you're really constrained by... well it's very unusual to clear out an entire column.

Or 10x1 is actually a very interesting game, often winnable, maybe ten percent of the time or so, and you really have to... it's a different mentality obviously. You have to think it through a long time before you make the one move.

So the other key ingredient of the game is the concept of "streaks", and that would be an element of the game you definitely added with the aid or Mr. Computer I would suppose...

It was easy to do. I couldn't store people's winning percentages but I could store, or it was easier for me to store how many games in a row they won. Sort of made it interesting and competitive.

That seems to be one of the real addictive factors of the game, the "streak" factor.

I had the advantage that it was on a central computer, so you couldn't cheat quite as easily. It still would occasionally go down but there was something you could check to see whether a person killed the system, stop-one, shift-stop was the way to kill a program, or whether the computer went down for scheduled maintenance or something.

There were a few monster streaks I remember in the 1000+ region, and folks theorized that they were sys-ops that could conveniently crash the machine when they hit a...

One of them Gary Johnson was his name, and as far as I know he was a physics student at another institution, so he wasn't at U of I so I don't think he could.

Now it seems evident that there are just folks who are very good at the game.

I think I only left enough bits there to reach about 4000 wins before it would turn over, so I don't know what happened after that.

Yes, about the implementation. Let's talk about that a little bit.

It was written in TUTOR, a procedural language, really made for computer based instruction. It had an elaborate system for asking questions and for building sort of quizzes. It had no local variables, it had, talking about old time constraints, I think it had a total of 64 variables, but you could split them up and get sort of bit slices of variables, all global of course.

I don't think there was any recursion in the language so I had to use an iterative process, one big loop.

The other thing I found tedious was games that would make you collect all the cards at the end when the moves were obvious. So I added a look one move ahead, to make any obvious moves. And that could also tell you if it was a losing position.

That's something I've always wondered about. I've never implemented that test for a losing position. How did you implement that?

It's not that complex. You just look at, um.... actually one of my complaints with the Microsoft implementation is that it's not that aggressive in making moves.

There are two things: there's the auto move up to the aces process, and there's the recognizing a losing position, and those are actually two different problems.

Recognizing a losing position was actually very simple-minded. I would look and see how many moves were possible. If there was only one move possible, it would make that move, and remember it. And then if the next move, there was only one move possible, it would make it unless it was a reversal of the previous one, in which case you lost.

So it was not a "solver" per se...

No, there was no recursion, it would be hard to build a list structure, and they actually limited the number of processor cycles you could have.

Speaking of machine cycles, I remember Avatar (an early multi-user dungeon (MUD) adventure game) was the big machine cycle hog back there. How did Freecell stack up against Avatar?

Oh, it was pretty low actually, because you spent most of your time staring at the screen thinking about your moves. So it was actually a well-behaved program from that point of view.

I think it burned its fair share of student time though.

(Laughs) Certainly, of people time, that's true.

Do happen to remember at peak times about how many people would you have seen playing?

Oh yeah, I did record that, didn't I. 100, 150, I don't recall if it was more than that.

Yeah, I remember it was a pretty good number (this was way pre-Internet you have to remember)

For what there was available at the time. And then of course a lot of places would block it out.

So folks would get work done...

I would presume so, or they wouldn't the waste computer time on frivolous things.

Now did you write the whole thing yourself, or did you have some students involved?

Well I was a student. I was a medical student.

Oh, well I guess I'd always assumed you were a computer science professor or something.

Nope, nope, nope, now I'm an anesthesiologist as Massachusetts General Hospital and I was a medical student at the time. But I'd done programming to help put myself through college or help pay for college, and so I'd been doing that for a number of years. I was familiar with how to program, certainly enjoyed it. And this was done, um, instead of studying.

(laugh) How big was the program? How much disk space did it use?

This was on a CDC something, Control Data Corporation cyber-something computer. So it was a mainframe. In those days they really constrained the amount of disk space you could have. It also used a strange large word format, 60 bits was a word. I usually used it broken down into 10 bytes, each one 6 bits long, which could represent numbers 0-63. Which worked out well if you were looking at cards in a deck. You could encode which card in the deck you had pretty easily, and the column and row, so that worked out nicely.

The whole program fit into three what they called blocks which were each 320 words long (2400 modern 8 bit bytes). So it would have been about 6k total.

The whole program was in 6k?!?

Oh yeah, yeah.

Wow!

The storage for all the records was in another seven blocks which would be about, if I have my math right, about 20k.

Amazing! And yet I remember huge long lists of streaks...

The fun part for me was that, although I liked playing the game or playing games, there's something very rewarding about building something that a lot of people are using and giving you feedback on.

It's certainly a well-loved game these days. How 'bout that as a segue into... how did you feel about it when Microsoft rolled out their version?

Well I was a little surprised, and I guess the first thing a felt was a little shocked, or dismayed. I'd never heard about this. At the time we sold all our programs to the University of Illinois who licensed them, and you'd get a little bit of royalties from it. So I asked them what they'd done; they hadn't made any ??? there. They weren't interested in enforcing licenses or anything like that, and I certainly wasn't interested in pursuing it. Um, I guess the only thing I really felt was that I could have gotten... if somebody had talked to me about it, or gotten some recognition for the work and the original idea.

Certainly. Have you ever talked to Jim Horne who I believe was the author of the Microsoft version?

No, no I don't know him at all.

No email or anything like that?

No.

I gather he was a student back there and played it, and cloned it. Um, let's see, now these days there are quite a few Freecell clone variants which add this or that to the game...

Oh, what have they added?

I don't know, some have added larger numbers of deals...

[ a discussion of algorithms for generating deals ensues that would probably only be of interest to the most nerdy among us ]

Are you a good Freecell player? What's you biggest streak?

Oh, probably a couple hundred games, but I don't have the patience to play it over and over like that.

And what's your average win time?

Well I don't play it as much anymore as I used to...

Well in your heyday?

My "heyday" was spent mostly programming it rather than playing it.

So I don't think I'm as good a player, never as good as the best that were there. To have a long streak you have to have... you can't get tired. It's a lot of concentration and persistence. I think I eventually get frustrated and just make a move rather than think it through.

And I really like the constrained games, with fewer columns and fewer cells.

I'm trying to remember, you had the tournaments back then. Were there any other aspects of the early Freecell environment. I mean I've shamelessly, on my site, cloned a bunch of the...

Oh really? I'll have to see your site. What is it?

It's freecell.net.

OK, that'll be easy to find.

[ I fill him in a bit on the nature of said "shameless clone", the NetCELL community, chat, and the worldwide parties, and the interest in Freecell on the 'net in general. ]

So there's quite a bit of interest...

Has anyone done solvers for it?

Yes, yes, that's another value-add of some of the other Freecell packages out there. I think there are at least two or three solvers you can lay hands on, to attack the games.

Because that'd be interesting. I'd approach it with a looking at, there are some moves that are reversible and some that are irreversible, and how you scale those or how you'd approach them, how you'd sort, prune the tree, that'd be very interesting to see.

Do you still do any computer programming?

Yeah, I do. More for my own interest, or for projects at work. Recently I've been using Javascript and Perl. I do most of my stuff now on Linux.

The NetCELL server runs on Linux...

I guess after TUTOR I did mostly C work, and now I'm looking for something besides C.

[ more discussions of very nerdy language topics ]

Do you still play?

I have to say each time I go back and play the game, months between times, I do enjoy it again. I remember why I wanted it in the first place.

Yes, a lot of folks worldwide are very appreciative of it.