Hi all.
In a private conversation with Gary Campbell (CCed to this message), he told
me that in one of the versions of his FCELL.COM solver, it solved a given
board using three different scans and then picked up the shortest solution.
This inspired me to do something like that for fc-solve.
I decided to run several scans for certain quotas and pick up the shortest
solution. So I ran a statistical analysis on the iterations of the various
atomic scans in my arsenal using the newly written process-for-shortness.pl
script in the presets directory, and picked up the 90% percentile of every
scan. I gave a top-limit for the iterations' count to 10,000 but the 90% mark
was always lower.
Then I constructed a new meta-scan, based on these alternative instances,
which I temporarily named "flairs"[Flair]. Now since the freecell_solver_user_
API does not yet have a support for it, I decided to prototype it first. I
initially wanted to use python and CTypes for that, but since
fc_pro_range_solver.c was already written in C and contained a lot of logic
that was hard to extract, I used it as a base and wrote it in C instead.
{{{
[Flair] - it's just a word I like. According to
http://en.wiktionary.org/wiki/flair it means "a natural or innate talent or
aptitude; a knack".
}}}
So I wrote the flair-based interpreter and after resolving a few bugs
successfully ran it. The first thing I should note was that it was very slow:
the whole thing took 674,667,532 iterations (670 Million or 0.67
Milliard/Giga) and lasted for 7,514 seconds on my Pentium 4 2.4 GHz machine -
roughly 2.08 hours.
That put aside, the output has improved since the latest shortest-length meta-
scan that I tried (here:
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/980 ). The results
are:
<<<<<
FCS Moves
---------------------------
Min: 69
Max: 211
Average: 106.320603768868
StdDev: 8.77032953217722
Median: 106
FC-Pro Moves
---------------------------
Min: 29
Max: 180
Average: 68.1308165880184
StdDev: 10.6856135271265
Median: 68
>>>>>
Compared to the previous results (of the "gooey-unknown-thing" scan), one can
see that the average decreased by 10 steps, and there was also a decrease of 9
steps in the median, and that the standard deviation has also decreased. The
minimum has decreased, but the maximum increased a little.
In any case, I should note that the only board that this meta-scan reported as
intractable was the unsolvable 11,982, which means all the rest of the boards
were successfully solved. I still haven't resumed the flairs after a case
where they all report the board as intractable, which should yield an even
more accurate result.
Right now I'd like to investigate how to construct configurations that will be
less time intensive and yet yield relatively short solutions. See for example
this Perl Quiz on the subject:
*
http://article.gmane.org/gmane.comp.lang.perl.qotw.discuss/2655
*
http://community.livejournal.com/shlomif_tech/45610.html
Naturally, I also need to put this in the FCS core.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
"Star Trek: We, the Living Dead" - http://shlom.in/st-wtld
Deletionists delete Wikipedia articles that they consider lame.
Chuck Norris deletes deletionists whom he considers lame.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Wed Feb 24 2010 - 22:34:08 IST