Loading ...
Sorry, an error occurred while loading the content.

challenging Freecell position

Expand Messages
  • newtton
    I ran across a Freecell position that gives your solver (and others) difficulty. (The moves leading to this position are given below.) Here s what happened:
    Message 1 of 4 , Oct 18, 2009
    View Source
    • 0 Attachment
      I ran across a Freecell position that gives your solver (and others) difficulty. (The moves leading to this position are given below.) Here's what happened: I was playing with Freecell Pro and got into this position. When I checked the solvability, I got Yes, but I couldn't see how myself. I fumbled around a bit and then checked the solvability again, and it said No. This would not have been a surprise except the only difference from the first position was a reversible move (the three of clubs can be moved freely between two columns.) What a shock! I thought the solver always told the truth (or came to no conclusion at all.)
      I reported the problem to Michael Keller and he suggested the newer version of FC Pro that has 3 solvers, including yours. Yours reports this position impossible. But the 3rd solver, Patsolve, reported it solvable -- whereever the 3 of clubs was placed. Using the solution generated by Patsolve I was able to see how to get out of the difficulty.
      This is just my opinion, but it seems to me that if you are going to release a program to the public and call it a solver, then it is understandable if it can't come to a conclusion about certain positions, but it should at least come to the correct conclusion if it does.

      #715037 Attempt: 5 NumFcs=4 (FCPro)
      8h 5d 5c 5b 5a d5 65 65 68 65
      6d 76 72 a2 6a 76 74 a7 6a 83
      72 c6 38 7c a7 83 38 6a 83 c6
      56 7c 38 83
    • Shlomi Fish
      Hi newtton! Thanks for your E-mail. See below for my response. ... Freecell Solver in some of it solver configuration uses heuristics that may report some
      Message 2 of 4 , Oct 18, 2009
      View Source
      • 0 Attachment
        Hi newtton!

        Thanks for your E-mail. See below for my response.

        On Sunday 18 Oct 2009 22:06:37 newtton wrote:
        > I ran across a Freecell position that gives your solver (and others)
        > difficulty. (The moves leading to this position are given below.) Here's
        > what happened: I was playing with Freecell Pro and got into this
        > position. When I checked the solvability, I got Yes, but I couldn't see
        > how myself. I fumbled around a bit and then checked the solvability
        > again, and it said No. This would not have been a surprise except the
        > only difference from the first position was a reversible move (the three
        > of clubs can be moved freely between two columns.) What a shock! I
        > thought the solver always told the truth (or came to no conclusion at
        > all.) I reported the problem to Michael Keller and he suggested the newer
        > version of FC Pro that has 3 solvers, including yours. Yours reports this
        > position impossible. But the 3rd solver, Patsolve, reported it solvable
        > -- whereever the 3 of clubs was placed. Using the solution generated by
        > Patsolve I was able to see how to get out of the difficulty. This is just
        > my opinion, but it seems to me that if you are going to release a program
        > to the public and call it a solver, then it is understandable if it can't
        > come to a conclusion about certain positions, but it should at least come
        > to the correct conclusion if it does.
        >

        Freecell Solver in some of it solver configuration uses heuristics that may
        report some solvable board layouts as unsolvable. This is due to the fact that
        it uses meta-moves (= sequences of several atomic moves and meta moves)
        instead of atomic moves, which move only one cards. However, there is a preset
        called "good-intentions" that first runs a good meta-moves heuristic and then
        a good (for some values of good) atomic moves one to yield a usually fast and
        absolutely accurate verdict. For more information, consult the Freecell Solver
        documentation here, or alternatively the Freecell Pro documentation:

        http://fc-solve.berlios.de/docs/#distributed-docs

        I should note that Freecell Pro, as great as it is, is relatively lacking and
        buggy and suffers from several major design and internals issues. It has also
        incorporated an incredibly old, under-optimised and buggy version of Freecell
        Solver, which I refuse to support (due to the fact that the current version of
        the fc-solve library should be backwards compatible with it, but greatly
        enhanced). I am now much happier with the integration of Freecell Solver into
        PySolFC:

        * http://pysolfc.sourceforge.net/

        * http://cards.wikia.com/wiki/PySol

        Like FreeCell Pro, PySolFC is open-source, but as opposed to it, it is cross-
        platform, running mostly natively on Windows, Linux, Mac OS X and other
        distributions, has much more Solitaire variants (many of which also have a
        Freecell Solver-supported solver and help system, which despite its historical
        name can now solve several other Solitaire variants besides Freecell). PySolFC
        is also arguably the most powerful and featureful open-source (and free-of-
        charge) Solitaire suite.

        > #715037 Attempt: 5 NumFcs=4 (FCPro)
        > 8h 5d 5c 5b 5a d5 65 65 68 65
        > 6d 76 72 a2 6a 76 74 a7 6a 83
        > 72 c6 38 7c a7 83 38 6a 83 c6
        > 56 7c 38 83
        >

        Well, using Freecell Pro would be a bit hard because I'm based on Linux (which
        luckily for you is still x86) and would need to use wine or Virtual Box. I'll
        try but you can ease my job by giving the board layout in the Freecell Solver
        notation:

        http://fc-solve.berlios.de/docs/distro/README.html

        Regards,

        Shlomi Fish

        --
        -----------------------------------------------------------------
        Shlomi Fish http://www.shlomifish.org/
        Why I Love Perl - http://shlom.in/joy-of-perl

        Chuck Norris read the entire English Wikipedia in 24 hours. Twice.
      • Gary Campbell
        I m not sure why Shlomi Fish or Michael Keller didn t mention my solver/player, but it has no difficulty with this game or your position within it. Here is
        Message 3 of 4 , Oct 18, 2009
        View Source
        • 0 Attachment
          I'm not sure why Shlomi Fish or Michael Keller didn't mention
          my solver/player, but it has no difficulty with this game or your
          position within it.  Here is the last point where your solution is
          solvable.  Beyond that you have made the position impossible.
          Please, people, mention my solver when you need to solve
          something beyond the capability of FCPro and you would like
          to use Windows as a program base.  I would appreciate it.
          -Gary Campbell
          (solver available free at http://numin8r.us/programs
           
           
          QC TS 9H KS 9D    7H QH 2D AC 2H   
          QD 3S 5C 6C 8S    7C KH 6D KD KC JC
          QS JH 2S TC 7D    3D 8H
          5S 2C 3H AS 6S    9S 4H
          8C 7S 5D 5H          3C
          6H TH JD JS            
          4C TD 4D 4S            
             9C                  
             8D                  
          GAME #715037 is solved partially as follows: {15 1 0 0 -2 -2 524 524 2 2 0 0 68 68 2000 100}
           8h 5d 5c 5b 5a d5 65 65 68 65
           6d 76 72 a2 6a[76]74 a7 6a 83
           72 c6 38 7c a7 83 38 6a 83 c6
           56 7c 38 83 ??
           
          ----- Original Message -----
          From: newtton
          Sent: Sunday, October 18, 2009 2:06 PM
          Subject: challenging Freecell position

           

          I ran across a Freecell position that gives your solver (and others) difficulty. (The moves leading to this position are given below.) Here's what happened: I was playing with Freecell Pro and got into this position. When I checked the solvability, I got Yes, but I couldn't see how myself. I fumbled around a bit and then checked the solvability again, and it said No. This would not have been a surprise except the only difference from the first position was a reversible move (the three of clubs can be moved freely between two columns.) What a shock! I thought the solver always told the truth (or came to no conclusion at all.)
          I reported the problem to Michael Keller and he suggested the newer version of FC Pro that has 3 solvers, including yours. Yours reports this position impossible. But the 3rd solver, Patsolve, reported it solvable -- whereever the 3 of clubs was placed. Using the solution generated by Patsolve I was able to see how to get out of the difficulty.
          This is just my opinion, but it seems to me that if you are going to release a program to the public and call it a solver, then it is understandable if it can't come to a conclusion about certain positions, but it should at least come to the correct conclusion if it does.

          #715037 Attempt: 5 NumFcs=4 (FCPro)
          8h 5d 5c 5b 5a d5 65 65 68 65
          6d 76 72 a2 6a 76 74 a7 6a 83
          72 c6 38 7c a7 83 38 6a 83 c6
          56 7c 38 83

        • Shlomi Fish
          ... Indeed, one omission of my email was not mentioning alternative solvers to Freecell Solver. I apologise for that. The most complete list I know of (and
          Message 4 of 4 , Oct 19, 2009
          View Source
          • 0 Attachment
            On Sunday 18 Oct 2009 23:40:49 Gary Campbell wrote:
            > I'm not sure why Shlomi Fish or Michael Keller didn't mention
            > my solver/player, but it has no difficulty with this game or your
            > position within it. Here is the last point where your solution is
            > solvable. Beyond that you have made the position impossible.
            > Please, people, mention my solver when you need to solve
            > something beyond the capability of FCPro and you would like
            > to use Windows as a program base. I would appreciate it.
            > -Gary Campbell
            > (solver available free at http://numin8r.us/programs
            >

            Indeed, one omission of my email was not mentioning alternative solvers to
            Freecell Solver. I apologise for that. The most complete list I know of (and
            which I prepared and maintain) is:

            http://fc-solve.berlios.de/links.html#other_solvers

            I tend to think that my solver is the most powerful, featureful, portable and
            most polished one (see for example - http://fc-solve.berlios.de/features.html
            ), and on top of it is distributed under the MIT/X11 Licence which is
            practically public domain. But naturally, it is possible that a different
            solver will supercede it in the future.

            Gary, regarding your solver, can you answer the following questions:

            1. How many board positions can it handle before it runs out of memory? Using
            my Indirect-stack-states scheme (where I store pointers to stacks in the stack
            collection instead of storing copies) I was able to scale Freecell Solver to a
            million states and more on a 32-bit x86 machine. On a 64-bit machine (Alpha
            AXP, x86-64, UltraSPARC, etc.) with enough RAM, it may be more, but naturally
            the pointers there are larger.

            Your solver seems to be a small 8086/8088 COM object binary and as such can
            probably only map 640KB of RAM. So assuming every board position consumes 8-
            bits of RAM (which is probably way-too-optimistic), it can only go up to an
            optimistic upper limit of 640,000 positions before exhaustion.

            I should note that I have an idea for states that are packed bit-by-bit as a
            big delta from the original state (I borrowed the idea from the original Don
            Woods solver.). This way a column in each state will usually occupy much less
            than even 32-bits. This will require some major internal changes in fc-solve
            and may make the solution slower due to the packing and unpacking, but it will
            conserve a lot of memory.

            2. What happens when your solver runs out of memory? Does it crash? Does it
            gracefully exit? Does it prune dead ends? Will it continue to run
            indefinitely?

            I should note that when my solver fails a malloc() it would try to access a
            NULL pointer and crash the entire process. My todo list had an item for
            implementing a graceful return propagation on a failed memory allocation, but
            it's not high on my priority list, for many reasons.

            3. Does your solver have an automated test suite? If not, how do you make sure
            bugs don't creep in? I should note that you can use this Perl/CPAN module I
            created (which is gratis and open-source) to help making sure the solutions
            are correct:

            http://fc-solve.berlios.de/verify-code/

            Regards,

            Shlomi Fish

            >
            > QC TS 9H KS 9D 7H QH 2D AC 2H
            > QD 3S 5C 6C 8S 7C KH 6D KD KC JC
            > QS JH 2S TC 7D 3D 8H
            > 5S 2C 3H AS 6S 9S 4H
            > 8C 7S 5D 5H 3C
            > 6H TH JD JS
            > 4C TD 4D 4S
            > 9C
            > 8D
            > GAME #715037 is solved partially as follows: {15 1 0 0 -2 -2 524 524 2 2 0
            > 0 68 68 2000 100} 8h 5d 5c 5b 5a d5 65 65 68 65
            > 6d 76 72 a2 6a[76]74 a7 6a 83
            > 72 c6 38 7c a7 83 38 6a 83 c6
            > 56 7c 38 83 ??

            This notation seems strange, incomprehensible and too terse. What does it all
            mean?

            --
            -----------------------------------------------------------------
            Shlomi Fish http://www.shlomifish.org/
            The Case for File Swapping - http://shlom.in/file-swap

            Chuck Norris read the entire English Wikipedia in 24 hours. Twice.
          Your message has been successfully submitted and would be delivered to recipients shortly.