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

Proposed Prune for Freecell-like Patience Variants Where Empty Columns Cannot Be Filled

Expand Messages
  • Shlomi Fish
    Hi all, as I’ve been playing some Baker’s Dozen (see http://en.wikipedia.org/wiki/Baker%27s_Dozen_%28solitaire%29 ) lately, I came to a realisation of one
    Message 1 of 4 , Jun 16 10:30 PM
      Hi all,

      as I’ve been playing some Baker’s Dozen (see
      http://en.wikipedia.org/wiki/Baker%27s_Dozen_%28solitaire%29 ) lately,
      I came to a realisation of one way we could prune the moves there, and in
      other variants where empty columns cannot be filled by any card, and which I
      believe would still guarantee a correct verdict.

      What I thought of is that there is no point in moving the last card in a column
      to a parent on a different column, because then the column won't be able to be filled,
      and will be left to disuse. Furthermore, after moved to a parent, the card might block
      other cards that can be placed on the parent.

      A variation of this prune for variants where only kings can fill empty columns is that if
      there are enough columns to provide hosting for all the kings that are active, then there
      is no point in clearing a column of cards.

      Does this sound reasonable to you?

      Regards,

      Shlomi Fish


      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      My Aphorisms - http://www.shlomifish.org/humour.html

      Chuck Norris reads all messages posted to LKML (= the Linux Kernel Mailing
      List), understands them all, and he kills all gnomes he sees in sight.

      Please reply to list if it's a mailing list post - http://shlom.in/reply .
    • Shlomi Fish
      Hi all, On Sun, 17 Jun 2012 08:30:53 +0300 ... OK, so I implemented this prune in commit 7cd599215f83a82241bb10abd97434903e8bf88b in the repository (titled
      Message 2 of 4 , Jun 19 5:24 AM
        Hi all,

        On Sun, 17 Jun 2012 08:30:53 +0300
        Shlomi Fish <shlomif@...> wrote:

        > Hi all,
        >
        > as I’ve been playing some Baker’s Dozen (see
        > http://en.wikipedia.org/wiki/Baker%27s_Dozen_%28solitaire%29 ) lately,
        > I came to a realisation of one way we could prune the moves there, and in
        > other variants where empty columns cannot be filled by any card, and which I
        > believe would still guarantee a correct verdict.
        >
        > What I thought of is that there is no point in moving the last card in a column
        > to a parent on a different column, because then the column won't be able to be filled,
        > and will be left to disuse. Furthermore, after moved to a parent, the card might block
        > other cards that can be placed on the parent.
        >

        OK, so I implemented this prune in commit
        7cd599215f83a82241bb10abd97434903e8bf88b in the repository
        (titled "Prune for tests__is_filled_by_none().") and bechmarked the first
        two-hundred (200) PySolFC Baker’s Dozen deals. The results are that:

        1. With the prune it now runs in 742 wallclock seconds instead of 938s (a 26% improvement).

        2. It now solves 127 deals instead of 89.

        3. It's not all roses, because some of the previously solved deals are now intractable.

        4. Only one deal was found to be unsolvable in both cases, and it's the same deal.

        ---------------

        Note that this is with the default Freecell Solver configuration.

        So overall I am happy - it did not require a lot of coding work, and it yielded good results.

        Regards,

        Shlomi Fish

        > A variation of this prune for variants where only kings can fill empty columns is that if
        > there are enough columns to provide hosting for all the kings that are active, then there
        > is no point in clearing a column of cards.
        >
        > Does this sound reasonable to you?
        >
        > Regards,
        >
        > Shlomi Fish
        >
        >



        --
        -----------------------------------------------------------------
        Shlomi Fish http://www.shlomifish.org/
        Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/

        He has a high degree of idealism, a high degree of stubbornness, and an even
        higher degree of inability to distiniguish between the two.

        Please reply to list if it's a mailing list post - http://shlom.in/reply .
      • MichaelK
        ... I would consider this highly suspicious, and certainly undesirable. How can pruning make deals which were solved before suddenly become intractable? The
        Message 3 of 4 , Jun 25 11:38 PM
          >
          > 3. It's not all roses, because some of the previously solved deals are now intractable.
          >

          I would consider this highly suspicious, and certainly undesirable. How can pruning make deals which were solved before suddenly become intractable? The logic of your argument (not moving a lone card in a column to an occupied column in NoFill games) seems sound. Could there be a bug in the code?
        • Shlomi Fish
          Hi Michael, thanks for your E-mail. On Tue, 26 Jun 2012 06:38:30 -0000 ... Well, the problem is that there are many factors at play here as the algorithm is
          Message 4 of 4 , Jun 26 10:31 AM
            Hi Michael,

            thanks for your E-mail.

            On Tue, 26 Jun 2012 06:38:30 -0000
            "MichaelK" <wgreview@...> wrote:

            > >
            > > 3. It's not all roses, because some of the previously solved deals are now intractable.
            > >
            >
            > I would consider this highly suspicious, and certainly undesirable. How can pruning make deals
            > which were solved before suddenly become intractable? The logic of your
            > argument (not moving a lone card in a column to an occupied column in NoFill
            > games) seems sound. Could there be a bug in the code?
            >

            Well, the problem is that there are many factors at play here as the algorithm
            is affected by many things. If we clear a column, then we may opt to choose
            different game positions first, and so traverse the game’s graph in different
            ways. And this is without starting to consider the random-DFS scan which
            randomises the results.

            While some bugs may be present, I am hesistant to blame the
            newly-unsolved-deals on that, given the complexity of Freecell Solver, and so
            far all the tests in the automated test suite are still passing.

            I have ran the Baker’s Dozen solver on more deals, and will report about them
            soon.

            Regards,

            Shlomi Fish

            --
            -----------------------------------------------------------------
            Shlomi Fish http://www.shlomifish.org/
            UNIX Fortune Cookies - http://www.shlomifish.org/humour/fortunes/

            The only things worse than XSLT are Excel and Sugar‐Less Tea (XSLT).

            Please reply to list if it's a mailing list post - http://shlom.in/reply .
          Your message has been successfully submitted and would be delivered to recipients shortly.