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

Creating a Meta-Scan that Minimises the Solution Length

Expand Messages
  • Shlomi Fish
    Hi all! I reported about the solutions length of the Freecell Solver s Good Intentions preset ( -l gi ), here:
    Message 1 of 5 , May 28, 2009
    View Source
    • 0 Attachment
      Hi all!

      I reported about the solutions' length of the Freecell Solver's "Good
      Intentions" preset ("-l gi"), here:

      http://tech.groups.yahoo.com/group/fc-solve-discuss/message/937

      However, with the motivation that Gary (Campbell) provided me, I kept thinking
      of other ways to make Freecell Solver's solutions shorter. A few days ago it
      occurred to me that maybe I can somehow create meta-scans that will optimise
      for the resultant solution's length instead of the time it took them to
      finish.

      Now the original algorithm for generating a meta-scan (see
      http://xrl.us/beuigz ) was:

      {{{{
      # First we record the number of iterations (= states scanned) it took the
      scans' to solve a given board for each of a large set of boards. (in our case
      the Microsoft 32,000).
      # Then, we allocate a certain number of iterations, and assign this quota to
      the scan that solves the most boards within this quota.
      # Repeat.
      # The configurations generated by this algorithm yield very good performance.
      }}}}

      So I thought of a variation of this algorithm that instead of assigning the
      quota to the scan that solves the most boards, it is assigned to the scan
      which generates the minimal average solution length for the boards that it
      solves within the quota.

      Naturally, this involved collecting the data of the solutions' length of each
      of the individual scans (took a long time - I left the computer running with
      it overnight), and later tweaking the code itself. I played a little with
      http://pdl.perl.org/ to get it to do what I want, and adapted the existing
      code to do this.

      Eventually, I ran my improved meta-scan-generating algorithm and after a few
      seconds got the following meta-scan, which I called "gooey-unknown-thing":

      http://xrl.us/beuih4

      After running the dump of its run through the statistics generator, I got the
      following results:

      {{{{{{{{{{{{{{{{{{
      FCS Solution Length
      ---------------------------
      Min: 74
      Max: 174
      Average: 113.432794774837
      StdDev: 11.4235614803861
      Median: 113

      FC-Pro (with auto-moves) solution length
      ---------------------------
      Min: 33
      Max: 148
      Average: 78.3220413137911
      StdDev: 13.1618468886974
      Median: 77
      }}}}}}}}}}}}}}}}}}

      So the average and the median of the FC-Pro moves (which were the focus of the
      optimisation) decreased by 12 moves, and the standard deviation was also
      reduced. I'm mostly pleased with these results.

      The "gooey-unknown-thing" meta-scan seems to be much slower than the "good-
      intentions" one, but I haven't given it a proper benchmarking yet.

      Since Gary has inspired this work, I give him the honour of naming the atomic
      moves meta-scan that will be optimised for solutions' length and the complete
      scan for the meta-moves scan followed by the atomic ones. These names should
      be short two-or-three words names, with weird/funny connotations and an
      original acronym. The existing ones are:

      {{{{{{{{{{
      abra-kadabra - a meta-moves preset
      cool-jives - a meta-moves preset
      crooked-nose - an atomic-moves preset (guarantees an accurate
      verdict)
      fools-gold - an atomic-moves preset
      good-intentions - runs cool-jives and then fools-gold
      gooey-unknown-thing - a meta-moves preset that aims to minimise the
      outcome solution's length.
      hello-world - a meta-moves preset
      john-galt-line - a meta-moves preset
      rin-tin-tin - a meta-moves preset
      yellow-brick-road - a meta-moves preset
      }}}}}}}}}}

      Gary, what shall you choose?

      Regards,

      Shlomi Fish

      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      "Star Trek: We, the Living Dead" - http://xrl.us/omqz4

      God gave us two eyes and ten fingers so we will type five times as much as we
      read.
    • Shlomi Fish
      ... So, Gary, what are you going to choose? Regards, Shlomi Fish -- ... Shlomi Fish http://www.shlomifish.org/ First stop for Perl beginners -
      Message 2 of 5 , Jun 5, 2009
      View Source
      • 0 Attachment
        On Thursday 28 May 2009 22:24:37 Shlomi Fish wrote:
        > Since Gary has inspired this work, I give him the honour of naming the
        > atomic moves meta-scan that will be optimised for solutions' length and the
        > complete scan for the meta-moves scan followed by the atomic ones. These
        > names should be short two-or-three words names, with weird/funny
        > connotations and an original acronym. The existing ones are:
        >
        > {{{{{{{{{{
        > abra-kadabra - a meta-moves preset
        > cool-jives - a meta-moves preset
        > crooked-nose - an atomic-moves preset (guarantees an accurate
        > verdict)
        > fools-gold - an atomic-moves preset
        > good-intentions - runs cool-jives and then fools-gold
        > gooey-unknown-thing - a meta-moves preset that aims to minimise the
        > outcome solution's length.
        > hello-world - a meta-moves preset
        > john-galt-line - a meta-moves preset
        > rin-tin-tin - a meta-moves preset
        > yellow-brick-road - a meta-moves preset
        > }}}}}}}}}}
        >
        > Gary, what shall you choose?

        So, Gary, what are you going to choose?

        Regards,

        Shlomi Fish

        --
        -----------------------------------------------------------------
        Shlomi Fish http://www.shlomifish.org/
        First stop for Perl beginners - http://perl-begin.org/

        God gave us two eyes and ten fingers so we will type five times as much as we
        read.
      • Gary Campbell
        ... Call this sand-stone ... Call this slick-rock
        Message 3 of 5 , Jun 5, 2009
        View Source
        • 0 Attachment
          > On Thursday 28 May 2009 22:24:37 Shlomi Fish wrote:
          >> Since Gary has inspired this work, I give him the honour of naming the
          >> atomic moves meta-scan that will be optimised for solutions' length and the
          >> complete scan for the meta-moves scan followed by the atomic ones. These
          >> names should be short two-or-three words names, with weird/funny
          >> connotations and an original acronym. The existing ones are:
          >>
          >> {{{{{{{{{{
          >> abra-kadabra - a meta-moves preset
          >> cool-jives - a meta-moves preset
          >> crooked-nose - an atomic-moves preset (guarantees an accurate
          >> verdict)
          >> fools-gold - an atomic-moves preset
          >> good-intentions - runs cool-jives and then fools-gold
          >> gooey-unknown-thing - a meta-moves preset that aims to minimise the
          >> outcome solution's length.
          >> hello-world - a meta-moves preset
          >> john-galt-line - a meta-moves preset
          >> rin-tin-tin - a meta-moves preset
          >> yellow-brick-road - a meta-moves preset
          >> }}}}}}}}}}
          >>
          >> Gary, what shall you choose?
          >
          Oh My Gosh! Off the top of my head, and for no good reason, how about:

          >> the atomic moves meta-scan that will be optimised for solutions' length
          Call this "sand-stone"

          >>the complete scan for the meta-moves scan followed by the atomic ones
          Call this "slick-rock"
        • Shlomi Fish
          ... OK, got you. Thanks, I will name them this way. Regards, Shlomi Fish -- ... Shlomi Fish http://www.shlomifish.org/ Best Introductory Programming
          Message 4 of 5 , Jun 6, 2009
          View Source
          • 0 Attachment
            On Saturday 06 June 2009 02:33:00 Gary Campbell wrote:
            > > On Thursday 28 May 2009 22:24:37 Shlomi Fish wrote:
            > >> Since Gary has inspired this work, I give him the honour of naming the
            > >> atomic moves meta-scan that will be optimised for solutions' length and
            > >> the complete scan for the meta-moves scan followed by the atomic ones.
            > >> These names should be short two-or-three words names, with weird/funny
            > >> connotations and an original acronym. The existing ones are:
            > >>
            > >> {{{{{{{{{{
            > >> abra-kadabra - a meta-moves preset
            > >> cool-jives - a meta-moves preset
            > >> crooked-nose - an atomic-moves preset (guarantees an accurate
            > >> verdict)
            > >> fools-gold - an atomic-moves preset
            > >> good-intentions - runs cool-jives and then fools-gold
            > >> gooey-unknown-thing - a meta-moves preset that aims to minimise the
            > >> outcome solution's length.
            > >> hello-world - a meta-moves preset
            > >> john-galt-line - a meta-moves preset
            > >> rin-tin-tin - a meta-moves preset
            > >> yellow-brick-road - a meta-moves preset
            > >> }}}}}}}}}}
            > >>
            > >> Gary, what shall you choose?
            >
            > Oh My Gosh! Off the top of my head, and for no good reason, how about:
            > >> the atomic moves meta-scan that will be optimised for solutions' length
            >
            > Call this "sand-stone"
            >
            > >>the complete scan for the meta-moves scan followed by the atomic ones
            >
            > Call this "slick-rock"
            >

            OK, got you. Thanks, I will name them this way.

            Regards,

            Shlomi Fish

            --
            -----------------------------------------------------------------
            Shlomi Fish http://www.shlomifish.org/
            Best Introductory Programming Language - http://xrl.us/bjn84

            God gave us two eyes and ten fingers so we will type five times as much as we
            read.
          • Shlomi Fish
            ... [SNIP] ... Now that the performance of the auto-moves in the FC-Pro moves have been sorted out, I performed another run of gooey-unknown-thing, and ran the
            Message 5 of 5 , Jun 7, 2009
            View Source
            • 0 Attachment
              On Thursday 28 May 2009 22:24:37 Shlomi Fish wrote:
              > Hi all!
              >
              > I reported about the solutions' length of the Freecell Solver's "Good
              > Intentions" preset ("-l gi"), here:
              >
              > http://tech.groups.yahoo.com/group/fc-solve-discuss/message/937
              >

              [SNIP]

              > Eventually, I ran my improved meta-scan-generating algorithm and after a
              > few seconds got the following meta-scan, which I called
              > "gooey-unknown-thing":
              >
              > http://xrl.us/beuih4
              >
              > After running the dump of its run through the statistics generator, I got
              > the following results:
              >
              > {{{{{{{{{{{{{{{{{{
              > FCS Solution Length
              > ---------------------------
              > Min: 74
              > Max: 174
              > Average: 113.432794774837
              > StdDev: 11.4235614803861
              > Median: 113
              >
              > FC-Pro (with auto-moves) solution length
              > ---------------------------
              > Min: 33
              > Max: 148
              > Average: 78.3220413137911
              > StdDev: 13.1618468886974
              > Median: 77
              > }}}}}}}}}}}}}}}}}}
              >

              Now that the performance of the auto-moves in the FC-Pro moves have been
              sorted out, I performed another run of gooey-unknown-thing, and ran the
              statistics on it again. Here is the result of -l gut -opt (the optimisation
              scan improves the results somewhat for some boards):

              {{{{{{
              FCS Solution Length
              ---------------------------
              Min: 74
              Max: 174
              Average: 113.43157598675
              StdDev: 11.4225419737591
              Median: 113

              FC-Pro Solution Length
              ---------------------------
              Min: 27
              Max: 145
              Average: 73.8513078533704
              StdDev: 13.6255617253829
              Median: 73
              }}}}}}

              So we are down to 73-74 median/average which is an improvement of 4 moves.

              Regards,

              Shlomi Fish

              --
              -----------------------------------------------------------------
              Shlomi Fish http://www.shlomifish.org/
              Why I Love Perl - http://xrl.us/bjn88

              God gave us two eyes and ten fingers so we will type five times as much as we
              read.
            Your message has been successfully submitted and would be delivered to recipients shortly.