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.
Received on Thu May 28 2009 - 12:28:30 IDT