Browse Groups

• ## Creating a Meta-Scan that Minimises the Solution Length

(5)
• NextPrevious
• 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
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:

{{{{{{{{{{
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
}}}}}}}}}}

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
• ... So, Gary, what are you going to choose? Regards, Shlomi Fish -- ... Shlomi Fish http://www.shlomifish.org/ First stop for Perl beginners -
Message 1 of 5 , Jun 5, 2009
View Source
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
• ... Call this sand-stone ... Call this slick-rock
Message 1 of 5 , Jun 5, 2009
View Source
> 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
Message 1 of 5 , Jun 6, 2009
View Source
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
• ... [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 1 of 5 , Jun 7, 2009
View Source
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