How Windows FreeCell Gave Rise To Online Crowdsourcing 93
TPIRman writes "In 1994, a physics doctoral student named Dave Ring assembled more than 100 math and puzzle enthusiasts on Usenet for what became one of the earliest online 'crowdsourcing' projects. Their goal: to determine if every hand in Windows' FreeCell solitaire game was in fact winnable, as the program's help file implied. Their efforts soon focused in on one incredibly stubborn hand: #11,982. They couldn't beat it, but in the process of trying, they proved the viability of an idea that would later be refined with crowdsourcing models like Amazon's Mechanical Turk."
Finally! (Score:4, Funny)
I can figure out how to solve Free Cell...
(scrambles back to Spider Solitaire)
Re: (Score:3)
Spider even on two suits is fairly difficult, on four suits it's way harder than Freecell usually is :)
Re:Finally! (Score:4, Interesting)
I played about 5,000 hands of Spider Solitaire at 4 suits.. My win percentage is about 8% but I can go for many games at a time without a win and then get 2 wins in a row..and once 4 wins in a row.
Re: (Score:2)
I tried to crowdsource minesweeper (Score:4, Funny)
In real life, with real mines. Terrible results. While we did find most of the mines, it turns out that people are terrible at safely locating them. Lots of dead bodies, limbs, etc, everywhere.
Re: (Score:3)
Dude, you the chap who made this video? I shake your hand. http://www.youtube.com/watch?v=LHY8NKj3RKs [youtube.com]
Re: (Score:2)
I so thought you were linking to this one, http://www.youtube.com/watch?v=xvqjJzuaNSE [youtube.com] , which my kids love.
-l
Re: (Score:1)
In real life, with real mines. Terrible results. While we did find most of the mines, it turns out that people are terrible at safely locating them. Lots of dead bodies, limbs, etc, everywhere.
Please mod this anything you want, but not funny.
live PacMan (Score:2)
http://www.youtube.com/watch?v=pIrvpn3k9A4 [youtube.com]
reminded me of this guy playing PacMan for real.
Missing from article (Score:5, Interesting)
It doesn't look like he ever proved that the hand in question was not solvable. It only claims that by having many human players try to solve it and several different AI approaches, that it was never solved.
The article ends by implying that this was a victory, because the outcome of all 32,000 hands is now known. But, as far as I can tell, one hand is still undecided!
No mathematical proof (Score:3)
Re: (Score:1)
... if you exhaust the space of all legal moves and none are winnable you have proven the hand unsolvable
Re: (Score:2)
You have demonstrated it is unsolvable, you have not proven anything.
Re: (Score:2, Informative)
http://en.wikipedia.org/wiki/Proof_by_exhaustion
Re: (Score:2)
The great-grandparent of this post said that you have "proven the hand unsolvable", when he probably meant to say "proven the hand unwinnable."
So, the post you replied to was correct. If something is "demonstrated to be unsolveable", then nothing has been proven. I'm not sure if it's relevant, however, unless we are all extremely concerned about the proof-reading ability of the great-grandparent.
how is that not a proof? (Score:2)
Isn't this just a case of "proof by exhaustion"? We divide up the problem into the space of all legal moves given the initial starting point, then show that none of them lead to the desired state.
According to Wikipedia this is how the four colour theorem was proved.
Re:No mathematical proof (Score:5, Informative)
Here's a program that does it.
http://kurage.nimh.nih.gov/tomh/public_html/archives/patsolve-3.0.tgz
The program generates a list of axioms, followed by a list of transformations chosen from a finite set.
After a finite number of steps, the proof reaches a conclusion that that game (and that's the only one
out of the original 32000) is unsolvable. This is a real, valid mathematical proof. It's just very long
and hard to read. But it is of finite size, and follows all the normal rules of mathematical proof.
You're welcome to try to come up with a shorter proof.
Re:No mathematical proof (Score:4, Informative)
The article seemed to imply that it was proved unwinnable, but never absolutely stated it..
I found something a little better: http://www.solitairelaboratory.com/fcfaq.html [solitairelaboratory.com]
11982 has now eluded solution by probably thousands of human solvers, and at least eight independent computer programs I am aware of (most of which are designed to search exhaustively for a solution), and I am confident in calling it impossible.
I really wish the FAQ had been linked from the slashdot summary, it's far more interesting, and better written than the gaemological.com article.
As I understand the quote above, there is at least 5 different programs (ie. more than half of "at least eight") that have solved hand 11982, and all arrived at the same solution: #11982 is not winnable. This has persuaded the FAQ's author to call [winning the hand] impossible.
Re: (Score:2)
The logic here is that a given solver "might have a bug" and therefore not provide a correct answer.
Just throwing 5 or 8 different programs at it therefore might be suspect.
However. Freecell is really a very simple game. A computer program is very much like a mathematical proof, ask any programmer who has also written proofs. All of the solvers use optimizations to keep the search size down, but each of these optimizations is really a theorem stating that certain segments of the game tree do not have to be
Re: (Score:1)
...but it is trivial to generate an unsolvable free cell board. Just start by laying aces in the first row, then continue with kings, queens, jacks, tens, in descending order until you run out of cards. That is one example of many provably unsolvable free cell boards and proves the Microsoft help text to be wrong for free cell in general. You don't need Windows to play free cell.
No, but the help text only referred to the Windows version, not Freecell in general. Their point was that the algorithm that they use to generate games only produces solvable ones.
I'm not sure if it still works in recent Windows versions, but with XP and earlier there was an easter egg where you could request game -1 or -2 and it would present a neatly ordered and unsolvable game, just as you describe. I guess this was to prove that an unsolvable Freecell is easy to create, which makes their algorithm all
Re: (Score:1)
You have demonstrated it is unsolvable, you have not proven anything.
All you need is ONE hand to not be solvable, and their entire argument is invalid.
"Their goal: to determine if every hand in Windows' FreeCell solitaire game was in fact winnable, as the program's help file implied."
So any one non-winnable hand, means that every hand in FreeCell is NOT winnable.
(Proof By) Counterexample [wikipedia.org]
Re: (Score:2)
No, you can provably search the entire game tree. It has been done for all 32000 of the "original MS" games, and many more. Most of them are quite small and easily handled on even a modest computer.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
I would assume there's only a finite number of possible moves. I don't know how far they've gotten into it before getting stuck, but I would assume it's well before there's any open cells (other than the four up top), so I would imagine there's only a few hundred - or thousand at most - possibilities.
Re: (Score:2)
No because it's a branching game, one move now opens and closes other possible moves.
There's no doubt that a computer can solve it, and on modern hardware it probably wouldn't even be measured in years... but it's not a quick solution.
Re: (Score:2)
Unsolvable games are rather easy to prove. They usually have very small game trees (i.e., you get "stuck" pretty quickly). Many games have extremely large trees, and for those, you need to search a long time to find the solution. All of the original 32000 games have rather small trees, though, and it doesn't take very long to solve them all. But there are some pathological cases (some have been designed by hand) that can cause a given solver to get lost in the weeds. A different solver, or even the same one
Re: (Score:2)
My point (in the top post of this thread) was that the article is vague, which is very bad form for mathematical subject matter.
If you have to assume that they went "so far that...", then you've proved the point. The article is vague.
I really want to tell my friends that one of the 32,000 is cannot be won, and the article certainly seems to imply this, but from the article, it's just not clear if that is true.
The hypothetical question above ("At what point ... consider the experiment finished?") has a very
Re: (Score:1)
Re: (Score:1)
Re:Missing from article (Score:5, Informative)
FreeCell is not np-anything. It's a finite tree that can be exhaustively searched.
Generalized FreeCell is NP-Complete. [sciencedirect.com]
Re: (Score:2)
The tree might be finite, but still have more than 10^10000 nodes, in this case, you will never find the solution (especially if it is unique).
Re: (Score:1)
Re: (Score:2)
It would be easy to write a program to brute force it...which would be a proof even if there's no fancy theory telling you why.
Re: (Score:2)
It would be easy to write a program to brute force it...which would be a proof even if there's no fancy theory telling you why.
Um, writing a program to "brute force it" is always easy. The notion of "brute force" is that you don't worry about optimizations, because the problem you are solving can be solved in the given time, even without reducing the problem space. Therefore, the writing of a brute force method is always "easy".
Unfortunately, if the problem space is already reduced by identifying equivalent states, or by other elimination factors, and it still takes too long, then the solution is never to "brute-force it". That
Re: (Score:2)
Most of the existing solvers make use of theorems about certain move sequences to prune the tree. For example, it is trivial to get into a loop of repeated moves, and in this sense game trees can be "infinite". But those are obvious optimizations.
What would be interesting is to find theorems concerning more complicated positions that allow you to prune huge branches.
This is the only way to attack some problems. You probably won't find a "theorem" that applies to the starting position, but I'm sure there are
early distributed computing (Score:2)
The first large distributed computing project was zilla [wikipedia.org]. it predated this. It ran on the Next Computers. It is still baked into all OSX computers (it's in your sharing preferences.). Check out my sig.
Re: (Score:2)
That's not Crowdsourcing, really, it's a Networked mainframe.
Re:early distributed computing (Score:5, Interesting)
No, the first large distributed project is the Cunnigham project:
http://books.google.com/books?id=udr3tHHwBl0C&lpg=PA375&ots=s4GNA3LkQo&pg=PA375 [google.com]
that started in 1949 on the ENIAC !
And this project is still ongoing.
In fact, this search started with human efforts, so it was already heavily crowd-sourced since a least 3 centuries.
The culmination of the manual effort came in 1903, when Frank Nelson Cole showed that:
193,707,721 × 761,838,257,287 = 2^67 - 1
It took 3 years of Sundays to discover.
http://www.rutherfordjournal.org/article030105.html [rutherfordjournal.org]
Re: (Score:2)
Re: (Score:3)
It has, according to Wikipedia, been tested using exhaustive-solution solvers, which does prove it is impossible. So not undecided, no, but not proven by them (they were correct, though, so they deserve recognition for that.)
Re: (Score:1)
It has been shown to be unsolvable by exhaustive search. It's easy these days.
I wrote a program to exhaustively search the game tree myself.
http://members.tripod.com/professor_tom/archives/patsolve-3.0.tgz
This does constitute a mathematical proof. It is deterministic, finite, and easily checked to be correct. It's just really long, if you wrote it out on paper.
Re: (Score:1)
In other news, how Steve Ballmer gave rise to the dancing monkeys throwing chairs .
Not solved != proof (Score:3, Insightful)
FTFA:
So when that final push on No. 11,982—an effort aided by humans and even a handful of game-solving programs—met with failure, Ring celebrated. Is every hand in FreeCell winnable? No. Thirty-one thousand nine hundred ninety-nine hands are winnable. And one isn’t. He proved that.
No he didn't. Unless the exploration of the game space was exhaustive, there's no proof. A bunch of people playing the game and failing to solve it isn't a proof.
Re:Not solved != proof (Score:5, Informative)
Unless the exploration of the game space was exhaustive, there's no proof.
Wikipedia claims that exhaustive search has been performed, assuming that the same hand numbering is used:
http://en.wikipedia.org/wiki/FreeCell#Impossible_games [wikipedia.org]
Re: (Score:2)
Re:Not solved != proof (Score:4, Funny)
Based on my own results, I'd have to say that thirty-one thousand, nine hundred, and ninety-nine hands are not winnable, and one is.
As a corollary result, I seem to have proven that I really suck at FreeCell.
Re: (Score:1)
'Tis true. Finding a solution proves the hand is winnable. Not finding one does not prove the opposite, unless you examine every possibility.
In a case like this, it suggests that, but does not prove it. Even if the hand can be won, why this particular one is so stubborn is of interest all by itself.
Re: (Score:2)
Unsolvable deals often have very small game trees. You get stuck very quickly, and there are no more moves. So showing something to be unsolvable is usually rather easy. It's easy to search the ENTIRE game tree. That's a proof. A bunch of people trying for a long time might not search every possible position, but in this case, the computer can do it, provably.
If the solver takes days and days and days and still hasn't found a solution either way, then you have no proof of anything. Even if "most" unsolvable
Re: (Score:2)
GNU and Linux were in fact collaborative projects, but not with "crowds" - in fact, they have very small groups of highly knowledgeable experts. There are big differences in terms of the necessary mechanisms for coordination, trust, etc.
Re: (Score:2)
Re: (Score:1)
A coffee shop is one of those places you go to browse online forums.
Did they try all of them? (Score:2)
Don't forget hands -1 and -2.
Re: (Score:2)
Those are both solvable. If this is they. The exact implementation for the deal generator might not work the same way for negative numbers. This assumes they are 64 bits.
9D 9C KC 9H 2S 8H 6H
QD TH 4D 7S 2H 6D 3S
8D QC 3C AD TC 8S TS
AH QS AS KH 7C QH 5C
5S 3H 9S 6C JD 6S
JS 4C AC JH 3D 8C
7D 2C 2D JC 5D 5H
7H 4H 4S KD KS TD
---
#-2: A winner.
99 moves.
TC 8S 8C 6C 5H 5C 9C
2S TD 6D 8D 9H 9S 6S
JS TH 3S JD 4H QC 3D
5S QS KD AH AS JH 4S
4D 4C 7D JC 2D AD
6H KH TS 7H QD QH
3H 2C KC 2H 5D 9D
7C KS 8H 3C AC 7S
---
#-1: A winner.
78
Re: (Score:2)
You should check the actual game. I think -1 and -2 are special cases.
Nowhere near first (Score:2)
http://homes.cerias.purdue.edu/~ssw/cun/oldp/dir30/a01
Re: (Score:2)
More like 3 centuries ago. See my other comment about that.
There was a similar effort in the UK (Score:5, Informative)
Re: (Score:2)
-1 and -2 are not part of the actual gamespace - they will never be selected by Free Cell except by use of the "Select Game Number" function, and are designed specifically to be unsolvable.
They could have just asked my mom. (Score:3)
My mom did this during the 80s by herself. She had a (very) little list of which deals she couldn't solve. I wonder how many other people have done the same.
She still goes through 20 deals every day but with the new version she knows she'll never finish.
Re: (Score:2)
Yeah my dad started counting up and giving each one a difficulty rating. not sure how far he got with it.
Did it ever get solved? (Score:1)
stone soup (Score:2)
In ye olde England, Stone Soup was the first 'crowd sourcing' project. Whenever I read these 'first' summaries all I think is the shoulders of giants, this one experiment.
I think it's solvable. (Score:1)
Just because I have a Freecell game that permits undo, and I have yet to lose a game. Yes, cheating with undo. But I'm over 1,000 games and still no losses.
If I can get the deck for this Microsoft Freecell game, I'll get it into my flavor and go to work. The longest game I won took me well over 40 hours, but I got it.
Though, I admit, since there are a finite set of moves, it is *possible* that this is unsolvable. But I'll try. What the heck, all I lose is time spend watching Pawn Stars.
Re: (Score:2)
Re: (Score:2)
Were those 100 million perfectly random, or was a random deck generator created which has good odds of creating a winnable game? It's pretty easy to generate basic unwinnable subsets of the lower board, and then all permutations with that subset will be unwinnable. There are more subtle unwinnable games, too.
Of course, 52! is a huge space. It would be interesting to see a formal analysis of the game.
Re: (Score:2)
Nice record. The kicker is when you have a streak like that going, and then some family member using your computer decides to try a game or three and loses for you.
After that happened to me a couple times, I realized how easy it was to just go into the system registry and "fix" their mistake, but at that point the game lost its challenge because I also realized that I lacked the willpower to keep from "fixing" my own errors as well.
Project Gutenberg (Score:2)
You kids need to get off my lawn....
Even if the Cunningham project doesn't meet some arbitrary criteria for the first internet crowdsourced project, there's always Project Gutenberg, started in 1971.
linux versions are missing a key feature (Score:3)
Just thought I'd mention that the linux versions of freecell are all missing a key feature that the Windows version had: it told you the numeric seed used to generate the hand, and let you type it in again later if you wanted to play the same hand.
The linux versions I've seen will let you restart the game from the beginning, but don't let you save it, and sharing the game with someone else isn't as easy as just sending a number.
Re: (Score:1)
Patsolve and FreeCellSolver (Score:2)
Several people have commented on patsolve (which I wrote) and FreeCellSolver (Shlomi Fish).
The "patsolve-3.0" link that was mentioned was broken, I have updated it. You can find it here:
http://kurage.nimh.nih.gov/tomh/public_html/archives/patsolve-3.0.tgz [nih.gov]
FYI, searching the entire game tree for game number 11982 takes .7 seconds on a 3 GHz machine.
Get off my lawn... (Score:1)
The Pyramids of Giza, that's an earlier crowdsourced project...
Can 5 free cells solve all FreeCell puzzles? (Score:1)
Re: (Score:2)
11982 can be solved with 5 free cells. I don't know about "all" of them. There are too many to check all. Certainly most.
That's the kind of thing you'd need a more sophisticated proof for, since brute-force is still too slow.
(patsolve can run with any number.)
Another interesting question is which games can be solved with NO free cells. #164, #892, #1012, #1081, and #1150
are the first 5 that can be. There are only 207 in the first 100,000 games (using MS numbering).