Slashdot Mirror
How Windows FreeCell Gave Rise To Online Crowdsourcing
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."
I can figure out how to solve Free Cell...
(scrambles back to Spider Solitaire)
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.
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!
Free unix account: freeshell.org
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.
The only way to "prove" it would be to identify a definitive proving mechanism, and nobody has done so. No computer simulations have been able to solve it, nor have any participants. That's going to be as good as it gets.
The first large distributed computing project was zilla. 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.
Some drink at the fountain of knowledge. Others just gargle.
Don't forget hands -1 and -2.
Lets start refering to The War Against Terror by it's initials. . .
The Cunningham project was running over a decade before that.
http://homes.cerias.purdue.edu/~ssw/cun/oldp/dir30/a01
Also FatPhil on SoylentNews, id 863
This was also done at about the same time in the UK, by a group of people on Cix (a CoSy conferencing system), with the same conclusion, except we found two more unsolvable ones that I suspect the American team didn't look at: -1 and -2. For what it's worth, I invented the notation we used to document solutions, and one of the team produced a solver that exhaustively checked the game space for 11 982 and indeed found it impossible. So give or take formal proof of the solver's correctness, it is proven that not all games are solvable.
Quidnam Latine loqui modo coepi?
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.
Cause if it didn't, this is going to drive me nuts until i find the answer or write a program to solve it for me. (God knows I have a hard enough time solving the easy ones)
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.
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.
Dilbert RSS feed
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.
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.
TFA says that out of 32,000 games that the original FreeCell can deal (it can't deal all 52! hands), all have been one by humans except ONE, and exhaustive testing shows that that last game has been exhaustively shown with 100% certainty to be unsolvable. Out of 100 million games with a less constrained dealer, only 1282 have not been solved by a human or machine. So using one of these unconstrained versions of FreeCell, you can probably assume that the odds of getting an unwinnable game are something like 0.00001%, so essentially you can always win a random game.
ASCII stupid question, get a stupid ANSI
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.
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.
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.
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
FYI, searching the entire game tree for game number 11982 takes .7 seconds on a 3 GHz machine.
The Pyramids of Giza, that's an earlier crowdsourced project...
I'm familiar with newsgroups, can someone give me an analogy to explain what is a coffee shop?
If you are not allowed to question your government then the government has answered your question.
A coffee shop is one of those places you go to browse online forums.
Last post!
Can 5 free cells solve all FreeCell puzzles, just like 4 colors covers all maps?
...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 the more special as it only produces solvable games. I am curious how they achieve this.
http://www.youtube.com/watch?v=pIrvpn3k9A4
reminded me of this guy playing PacMan for real.
I listen to both RIAA and non-RIAA stuff if I like the music, tangential business/politics nonwithstanding.