Forgot your password?
typodupeerror
Math Windows Games

How Windows FreeCell Gave Rise To Online Crowdsourcing 93

Posted by samzenpus
from the mastering-the-game dept.
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."
This discussion has been archived. No new comments can be posted.

How Windows FreeCell Gave Rise To Online Crowdsourcing

Comments Filter:
  • Finally! (Score:4, Funny)

    by Anonymous Coward on Thursday April 12, 2012 @11:11AM (#39658113)

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

    (scrambles back to Spider Solitaire)

    • Spider even on two suits is fairly difficult, on four suits it's way harder than Freecell usually is :)

      • Re:Finally! (Score:4, Interesting)

        by digitalhermit (113459) on Thursday April 12, 2012 @12:11PM (#39659167) Homepage

        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.

  • by Anonymous Coward on Thursday April 12, 2012 @11:13AM (#39658135)

    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.

  • Missing from article (Score:5, Interesting)

    by uigrad_2000 (398500) on Thursday April 12, 2012 @11:18AM (#39658205) Homepage Journal

    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!

    • 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.
      • by Anonymous Coward

        ... if you exhaust the space of all legal moves and none are winnable you have proven the hand unsolvable

        • by Hillgiant (916436)

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

          • Re: (Score:2, Informative)

            by Anonymous Coward

            http://en.wikipedia.org/wiki/Proof_by_exhaustion

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

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

          • by Anonymous Coward on Thursday April 12, 2012 @01:28PM (#39660667)

            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.

            • by uigrad_2000 (398500) on Thursday April 12, 2012 @05:56PM (#39666037) Homepage Journal

              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.

              • by Dr. Tom (23206)

                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

          • 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]

      • by Dr. Tom (23206)

        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.

    • by krakelohm (830589)
      At what point would you call the hand unsolvable and consider the experiment finished?
      • Never. Call it "Not solved yet" and leave it open to the future to waste time on.
      • 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.

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

          • by Dr. Tom (23206)

            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

        • 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

      • by cohensh (1358679)
        About the same time you assume P != NP since no one has been able to solve an NP-complete problem in P.
      • I have a solution to this question that is quite elegant, however it is too long to fit in this comment.
    • by Joce640k (829181)

      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.

      • 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

        • by Dr. Tom (23206)

          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

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

    • by Baloroth (2370816)

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

    • by Anonymous Coward

      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.

    • by miknix (1047580)

      In other news, how Steve Ballmer gave rise to the dancing monkeys throwing chairs .

  • by roothog (635998) on Thursday April 12, 2012 @11:20AM (#39658241)

    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.

    • by tigre (178245) on Thursday April 12, 2012 @11:28AM (#39658341)

      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]

      • by canajin56 (660655)
        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.
    • by Anonymous Coward on Thursday April 12, 2012 @11:31AM (#39658391)

      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.

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

      • by Dr. Tom (23206)

        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

  • Don't forget hands -1 and -2.

    • by Dr. Tom (23206)

      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

  • The Cunningham project was running over a decade before that.
    http://homes.cerias.purdue.edu/~ssw/cun/oldp/dir30/a01
  • by digitig (1056110) on Thursday April 12, 2012 @11:58AM (#39658921)
    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.
    • by Kalriath (849904)

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

  • by Zatar (131299) on Thursday April 12, 2012 @11:58AM (#39658931)

    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.

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

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

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

    • by canajin56 (660655)
      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 lik
      • by Sancho (17056) *

        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.

    • by Turken (139591)

      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.

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

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

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

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

  • Can 5 free cells solve all FreeCell puzzles, just like 4 colors covers all maps?
    • by Dr. Tom (23206)

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

The shortest distance between two points is under construction. -- Noelie Alito

Working...