Hi all,
a few days ago, when working on the Freecell Solver trunk, I decided
to work on the implementation of alternative results orderings for the
random-dfs scan within the ordered next-states groups, for example by
using the Best-First-State state rater. As a precursor, I decided to
implement a parameter for these state ordering based on the
depth of moves' irreversibility that was investigated previously in
the context of the depth_dbm_fc_solver.
So I implemented it - it was not too hard and timed the scan
"--flare-name 33 --method a-star -to 0123467589 -asw 0,0,0,0,0,100 -sp
r:tf -opt", which is a best-first-search scan that is based solely on
it. It didn't yield a good speed-wise result, but instead it featured
predominantly on the hybrid speed/short-solutions scan.
So I decided to see how much it improves the results upon the
shortest-solutions flare-based scan I have. Here are the results.
I ran this script to generate the results:
#!/bin/bash
# for I in `seq 1 32000` ; do
for I in `seq 8389 32000` ; do
printf "%-6s| %-30s | %-30s\n" \
"$I" \
"$(pi-make-microsoft-freecell-board -t "$I"|
./scripts/summarize-fc-solve -l mo)" \
"$(pi-make-microsoft-freecell-board -t "$I"|
./scripts/summarize-fc-solve --read-from-file
4,'/home/shlomif/progs/freecell/git/fc-solve/fc-solve/source/Presets/presets/further-split.sh')"
done
And this script was used to summarise the results:
cat my-summarize-range.output.txt |
perl -lne 'my _at_nums = /Length: (\d+)/g; print $nums[0] -
$nums[1]'
| sort -n | uniq -c
And the results are (first column is the number of states changes,
second column is the delta).
[Q]
30836 0
216 1
206 2
161 3
146 4
98 5
81 6
55 7
53 8
44 9
26 10
23 11
19 12
11 13
10 14
4 15
4 16
2 17
4 18
1 25
[/Q]
So it improved on solutions to about 1,200 deals, some of them quite
considerably.
There's still some things to investigate with new scans that involve
this new metric, and I'm also contemplating splitting it into two
metrics: one for the existing cards out (which is already
implemented) and one for the cards which are not on parents, for
greater flexibility. I also would like to finally implement the
configurable state ordering inside the random-dfs scan and to play with
it.
Regards,
Shlomi Fish
P.S: I've been spending a lot of time working on my Binary Puzzle
Solver:
https://github.com/shlomif/binary-puzzle-garden
Feel free to check it out.
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Original Riddles - http://www.shlomifish.org/puzzles/
If the mountain will not come to Muhammad, then Muhammad will go to the
mountain. If the mountain will not come to Chuck Norris, then the
mountain will suffer Norris’s wrath for not complying with his whims.
Please reply to list if it's a mailing list post -
http://shlom.in/reply .
Received on Tue Oct 23 2012 - 15:48:04 IST