How Windows FreeCell Gave Rise To Online Crowdsourcing

Finally! by Anonymous Coward · 2012-04-12 03:11 · Score: 4, Funny

I can figure out how to solve Free Cell...

(scrambles back to Spider Solitaire)

Re:Finally! by Drinking+Bleach · 2012-04-12 03:39 · Score: 2

Spider even on two suits is fairly difficult, on four suits it's way harder than Freecell usually is :)
Re:Finally! by Anonymous Coward · 2012-04-12 03:57 · Score: 0

I can figure it out too: Ctrl-Shift-F10
Re:Finally! by digitalhermit · 2012-04-12 04:11 · Score: 3, 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:Finally! by Anonymous Coward · 2012-04-12 15:11 · Score: 0

Spider may be harder to win, but nobody expects to win all hands of it. In free cell the objective is to never lose.
Re:Finally! by unixisc · 2012-04-12 19:10 · Score: 1

Usually, when I play Freecell, I make it tougher for myself by using a self-imposed rule that the cards released have to be in the sequence of SHCD, HCDS, CDSH or DSHC. That makes it more challenging and interesting. Of course, in the Freecells from Vista on, one can undo and put the card exactly in the slot one wants, so this is no longer a challenge there. As for the above game 11982, it would seem to me that anytime someone buried all the aces right at the bottom, such a game would be impossible to win.

I tried to crowdsource minesweeper by Anonymous Coward · 2012-04-12 03:13 · 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:I tried to crowdsource minesweeper by bruce_the_loon · 2012-04-12 03:24 · Score: 2

Dude, you the chap who made this video? I shake your hand. http://www.youtube.com/watch?v=LHY8NKj3RKs

--
Trying to become famous by taking photos. Visit my homepage please.
Re:I tried to crowdsource minesweeper by Anonymous Coward · 2012-04-12 03:44 · Score: 0

http://www.gichd.org/
Re:I tried to crowdsource minesweeper by Luyseyal · 2012-04-12 04:30 · Score: 1

I so thought you were linking to this one, http://www.youtube.com/watch?v=xvqjJzuaNSE , which my kids love.
-l

--
Help cure AIDS, cancer, and more. Donate your unused computer time to worldcommunitygrid.org. Join Team Slashdot!
Re:I tried to crowdsource minesweeper by ScaledLizard · 2012-04-13 01:01 · 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.

Missing from article by uigrad_2000 · 2012-04-12 03:18 · Score: 4, 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!

--
Free unix account: freeshell.org

Re:Missing from article by krakelohm · 2012-04-12 03:23 · Score: 1

At what point would you call the hand unsolvable and consider the experiment finished?

--
You are all a bunch of idots.
Re:Missing from article by Joce640k · 2012-04-12 03:27 · Score: 1

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.

--
No sig today...
Re:Missing from article by ciderbrew · 2012-04-12 03:30 · Score: 1

Never. Call it "Not solved yet" and leave it open to the future to waste time on.
Re:Missing from article by SJHillman · 2012-04-12 03:32 · Score: 1

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:Missing from article by Baloroth · 2012-04-12 03:46 · Score: 2

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

--
"None can love freedom heartily, but good men; the rest love not freedom, but license." --John Milton
Re:Missing from article by cohensh · 2012-04-12 04:08 · Score: 1

About the same time you assume P != NP since no one has been able to solve an NP-complete problem in P.
Re:Missing from article by AdrianKemp · 2012-04-12 04:24 · Score: 1

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:Missing from article by Anonymous Coward · 2012-04-12 05:16 · 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:Missing from article by Anonymous Coward · 2012-04-12 06:05 · Score: 0

It takes seconds on modern hardware. I'm totally serious, I've done it.
Seconds.
Re:Missing from article by Anonymous Coward · 2012-04-12 06:25 · Score: 0

FreeCell is not np-anything. It's a finite tree that can be exhaustively searched.
Re:Missing from article by miknix · 2012-04-12 06:40 · Score: 0

In other news, how Steve Ballmer gave rise to the dancing monkeys throwing chairs .
Re:Missing from article by cohensh · 2012-04-12 06:57 · Score: 1

My point wasn't that freecell is np anything, it's that people thing np != p because no one's been able to solve an np-complete problem in p, not because there's a formal proof.
Re:Missing from article by phaunt · 2012-04-12 08:02 · Score: 4, Informative

FreeCell is not np-anything. It's a finite tree that can be exhaustively searched.
Generalized FreeCell is NP-Complete.
Re:Missing from article by uigrad_2000 · 2012-04-12 09:27 · Score: 1

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 simple answer. Once you give up and stop researching the problem, you can consider the experiment finished. The bigger question (What is required for the experiment to be successful) was implied, but not asked.

--
Free unix account: freeshell.org
Re:Missing from article by uigrad_2000 · 2012-04-12 09:32 · Score: 1

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 would mean to throw away all your optimizations, and run an inefficient search. I'm not sure why you are suggesting that they do that.

--
Free unix account: freeshell.org
Re:Missing from article by Dr.+Tom · 2012-04-12 10:35 · Score: 1

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 with a small change in search order, might solve it quickly. These sorts of programs just search the tree in some order. There probably exist some "very high level" theorems that you could use to prune these extremely large trees, and those would make the solvers even faster than they are.
Even Sudoku is a "hard" game in general, although in practice it is mostly trivial for computers; solvers exist that take literally milliseconds to solve a given board.
Re:Missing from article by Dr.+Tom · 2012-04-12 10:37 · Score: 1

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:Missing from article by Dr.+Tom · 2012-04-12 10:50 · Score: 1

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 many positions where you can apply some reasoning, rather than simply trying all possible combinations. For example, don't move the same card twice in a row, don't move card A and then card B and then card A again, if the moves are not related, and in general don't make a move that brings a position back to one that you've been in before. And so on.
Some of these theorems might be very complex, and there might even be some set of them that always make the game tree "small". That's the kind of thing you really want, if you want to "prove" that you can or can't solve a game.
That said, most Freecell games have small game trees and are easily solved.
Email me if you want some harder ones.
Re:Missing from article by Stuarticus · 2012-04-12 23:52 · Score: 1

I have a solution to this question that is quite elegant, however it is too long to fit in this comment.

--
If you think someone isn't free to have a different definition of "freedom" you may be a tyrant.

Not solved != proof by roothog · 2012-04-12 03:20 · Score: 2, 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 by tigre · 2012-04-12 03:28 · 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
Re:Not solved != proof by Anonymous Coward · 2012-04-12 03:31 · 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:Not solved != proof by Anonymous Coward · 2012-04-12 04:35 · Score: 0

huh? you can do proofs without exhaustive searches using logic. in fact, they are usually preferred.
Re:Not solved != proof by Anonymous Coward · 2012-04-12 05:18 · Score: 0

It has been exhaustively searched. This constitutes a rigorous mathematical proof. The game tree for FreeCell isn't very big.
Re:Not solved != proof by canajin56 · 2012-04-12 05:22 · Score: 1

Actually you don't need to assume the same numbering scheme, as the citation for "believed unsolvable" actually says it's been exhaustively tested by machine and proved unsolvable.

--
ASCII stupid question, get a stupid ANSI
Re:Not solved != proof by Impy+the+Impiuos+Imp · 2012-04-12 07:58 · 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.

--
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
Re:Not solved != proof by Dr.+Tom · 2012-04-12 10:57 · Score: 1

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 games have small trees, there could be some that are large. We don't know, and searching all 52! deals hasn't been done yet. :-)
(Yes, I know, there aren't really that many, due to symmetry.)

No mathematical proof by Petersko · 2012-04-12 03:21 · Score: 2

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.

Re:No mathematical proof by Anonymous Coward · 2012-04-12 03:31 · Score: 1

... if you exhaust the space of all legal moves and none are winnable you have proven the hand unsolvable
Re:No mathematical proof by Hillgiant · 2012-04-12 04:46 · Score: 1

You have demonstrated it is unsolvable, you have not proven anything.

--
-
Re:No mathematical proof by Anonymous Coward · 2012-04-12 04:52 · Score: 2, Informative

http://en.wikipedia.org/wiki/Proof_by_exhaustion
Re:No mathematical proof by Anonymous Coward · 2012-04-12 05:28 · 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 by Shifty0x88 · 2012-04-12 08:44 · 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
Re:No mathematical proof by uigrad_2000 · 2012-04-12 09:47 · Score: 1

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.

--
Free unix account: freeshell.org
Re:No mathematical proof by uigrad_2000 · 2012-04-12 09:56 · Score: 3, 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

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.

--
Free unix account: freeshell.org
Re:No mathematical proof by Dr.+Tom · 2012-04-12 11:02 · Score: 1

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:No mathematical proof by Dr.+Tom · 2012-04-12 11:20 · Score: 1

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 searched. A stronger statement would be that just one program found a given game unsolvable, and that program uses only prunes (theorems) that have been proved to be correct. I happen to know that even with only very simple prunes that are quite trivial to show to be correct, game 11982 is not solvable. The proofs I used to arrive at this conclusion have been checked by others, too. I'm not sure anybody has published a formal document anywhere, but you are welcome to look at the code.
Of course, you can win if you cheat. :-)
(Even a "mathematical" proof might be shown to be wrong, in a way that even many experts might have missed. This doesn't really apply here, though, because the game tree for 11982 is actually quite small.)

GNU & GPL by Anonymous Coward · 2012-04-12 03:30 · Score: 0

I would be hard pressed to say that Freecell gave rise to this notion when GNU & Linux were more popular and earlier examples of crowdsourcing.

Re:GNU & GPL by icebraining · 2012-04-12 04:07 · Score: 1

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

early distributed computing by goombah99 · 2012-04-12 03:33 · Score: 1

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.

Re:early distributed computing by Canazza · 2012-04-12 03:48 · Score: 1

That's not Crowdsourcing, really, it's a Networked mainframe.

--
It pays to be obvious, especially if you have a reputation for being subtle.
Re:early distributed computing by eulernet · 2012-04-12 03:54 · 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
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
Re:early distributed computing by fatphil · 2012-04-12 05:10 · Score: 1

Damn - I would have modded this up if it wasn't for the fact that I've already posted a highly redundant post saying a fraction of the same thing!

--
Also FatPhil on SoylentNews, id 863

"Like a virtual coffee shop" by Anonymous Coward · 2012-04-12 03:40 · Score: 0

I like it when one needs an analogy to explain what is an newsgroup in 2012: "Newsgroups were a place where professional students could converge from across the globe, like a virtual coffee shop, each one catering to particular topics like politics or juggling or Tori Amos."

Concept so hard one needs a virtual coffee shop analogy, as if none is used internet. Hint: there is a easier analogy, it's called forum.

Re:"Like a virtual coffee shop" by tompaulco · 2012-04-12 09:07 · Score: 1

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.
Re:"Like a virtual coffee shop" by DahGhostfacedFiddlah · 2012-04-12 11:30 · Score: 1

A coffee shop is one of those places you go to browse online forums.

--
Last post!
Re:"Like a virtual coffee shop" by Anonymous Coward · 2012-04-15 10:24 · Score: 0

Coffee shop - where pretentious people go to hang out and look cool while drinking coffee.

Did they try all of them? by coldfarnorth · 2012-04-12 03:41 · Score: 1

Don't forget hands -1 and -2.

--
Lets start refering to The War Against Terror by it's initials. . .

Re:Did they try all of them? by Anonymous Coward · 2012-04-12 03:45 · Score: 0

I just played -3, it was pretty easy.
Re:Did they try all of them? by Dr.+Tom · 2012-04-12 10:23 · Score: 1

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 moves.
By the way, Freecell may be NP-hard ... If a game is UNSOLVABLE it is probably EASY to show, because typically, unsolvable games have VERY SMALL game trees. But this one, below, is an example of a game that has an ENORMOUS game tree, and in general it is very hard to predict the size of the tree. A program that does brute force search WILL solve even NP-hard problems, if you wait long enough. But long enough could be well over the lifetime of the universe (by many, many orders of magnitude).
AS AC KS KC 4S 4C QS
AD AH KD KH 4D 4H QD
7S 7C 2S 2C 6S 6C QC
7D 7H 2D 2H 6D 6H QH
5S 5C JS JC 8S 8C
5D 5H JD JH 8D 8H
3S 3C 9S 9C TS TC
3D 3H 9D 9H TD TH
A human might be able to solve that game anyway, if they get lucky. It's certainly not easy for my program.
This game was artificially constructed, obviously. It may not be solvable, I don't know. Maybe Shlomi's program can do it.
Re:Did they try all of them? by coldfarnorth · 2012-04-16 02:48 · Score: 1

You should check the actual game. I think -1 and -2 are special cases.

--
Lets start refering to The War Against Terror by it's initials. . .

Nowhere near first by fatphil · 2012-04-12 03:53 · Score: 1

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

Re:Nowhere near first by eulernet · 2012-04-12 03:58 · Score: 1

More like 3 centuries ago. See my other comment about that.

There was a similar effort in the UK by digitig · 2012-04-12 03:58 · Score: 4, Informative

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?

Re:There was a similar effort in the UK by Kalriath · 2012-04-12 09:29 · Score: 1

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

--
For a site about things like basic rights, Slashdot users sure do like to censor "dissent".

They could have just asked my mom. by Zatar · 2012-04-12 03:58 · Score: 2

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:They could have just asked my mom. by KingAlanI · 2012-04-18 08:22 · Score: 1

Yeah my dad started counting up and giving each one a difficulty rating. not sure how far he got with it.

--
I listen to both RIAA and non-RIAA stuff if I like the music, tangential business/politics nonwithstanding.

Did it ever get solved? by pwnyxpress · 2012-04-12 04:01 · Score: 1

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)

Re:Did it ever get solved? by Anonymous Coward · 2012-04-12 05:24 · Score: 0

A program to exhaustively search it is here:
http://kurage.nimh.nih.gov/tomh/public_html/archives/patsolve-3.0.tgz
or
http://members.tripod.com/professor_tom/archives/patsolve-3.0.tgz
Just the one unsolvable game.
Personally I prefer Seahaven Towers. There are many more unsolvable ones, and that's why I wrote the program. FreeCell is a simpler subset. There are some Seahaven games with extremely large game trees which are still unknown.
Re:Did it ever get solved? by Anonymous Coward · 2012-04-12 05:37 · Score: 0

see http://fc-solve.shlomifish.org/ for a program that proves this game unsolvable

stone soup by JackPepper · 2012-04-12 04:04 · 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. by rickb928 · 2012-04-12 04:11 · Score: 0

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.

--
deleting the extra space after periods so i can stay relevant, yeah.

Re:I think it's solvable. by Anonymous Coward · 2012-04-12 04:59 · Score: 0

Did you read tfa? They've exhausted the entire set of moves available. They are all not solutions. Thus it isn't solvable.
Re:I think it's solvable. by canajin56 · 2012-04-12 05:29 · Score: 1

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
Re:I think it's solvable. by Sancho · 2012-04-12 05:48 · Score: 1

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:I think it's solvable. by Turken · 2012-04-12 06:31 · Score: 1

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.

how is that not a proof? by Chirs · 2012-04-12 05:01 · Score: 1

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.

Project Gutenberg by ABadDog · 2012-04-12 05:17 · Score: 1

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.

FreeCell on TV - The Office by Anonymous Coward · 2012-04-12 05:22 · Score: 0

There is an early episode of "the office (US)" that shows the secretary playing FreeCell. I was able to get the number and her screen was a few moves in (not very good moves). It was then possible to finish and win the game.

Here is the game in question. by Anonymous Coward · 2012-04-12 05:51 · Score: 0

AH 3D KD JC 6C JD KC
AS 3H 6H 5D 2C 7D 8D
4H QS 5S 5C TH 8H 2S
AC QC 4D 8C QH 9C 3S
2D 8S 9H 9D 6D 2H
6S 7H JH TD TC QD
TS AD 9S KH 4S 4C
JS KS 3C 7C 7S 5H

The program has been written. See http://fc-solve.shlomifish.org/

linux versions are missing a key feature by doom · 2012-04-12 06:25 · Score: 2

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:linux versions are missing a key feature by mynamestolen · 2012-04-12 08:24 · Score: 1

yeah it sucks that linux versions don't have numbers but some linux people have done this brilliant history and analysis (hope this isn't reffed in the article which I haven't read) http://www.solitairelaboratory.com/fcfaq.html

--
work in progress
Re:linux versions are missing a key feature by Anonymous Coward · 2012-04-12 15:18 · Score: 0

You didn't look at KPatience? It does exactly that.

Patsolve and FreeCellSolver by Dr.+Tom · 2012-04-12 07:40 · Score: 1

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.

Get off my lawn... by mapuche · 2012-04-12 08:10 · Score: 1

The Pyramids of Giza, that's an earlier crowdsourced project...

Easy to create unsolvable free cell board by Anonymous Coward · 2012-04-12 11:24 · Score: 0

I wrote a program to solve free cell boards back in 1999 using a weighted tree structure. It would search the entire tree space if no solution could be found. I don't remember if that particular MS game was one of the unsolvable ones, 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.

By the way, the only programming challenge was memory, not speed. Every game can be completely searched quite quickly by a modern computer, but with my implementation, some took over a gig of memory.

After I wrote the program, I lost interest in solving them myself, though...

Re:Easy to create unsolvable free cell board by Malvineous · 2012-04-13 00:55 · 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 the more special as it only produces solvable games. I am curious how they achieve this.
Re:Easy to create unsolvable free cell board by Anonymous Coward · 2012-04-13 02:11 · Score: 0

I am curious how they achieve this.
The 'simple' way would be to start at the winning position, then randomly select moves until you end up at a starting position. With a few tricks thrown in to stop your algorithm stuck in loops and direct it to the evenly stacked columns.

Can 5 free cells solve all FreeCell puzzles? by bingbing · 2012-04-12 12:53 · Score: 1

Can 5 free cells solve all FreeCell puzzles, just like 4 colors covers all maps?

Re:Can 5 free cells solve all FreeCell puzzles? by Dr.+Tom · 2012-04-13 09:30 · Score: 1

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

live PacMan by KingAlanI · 2012-04-18 06:45 · Score: 1

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.

Slashdot Mirror

How Windows FreeCell Gave Rise To Online Crowdsourcing

93 comments