On Wed, 24 Oct 2012 00:48:00 +0200
Shlomi Fish <shlomif_at_shlomifish.org> wrote:
> 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]
After experimenting some more, I found a scan that yields even better results
on average:
-nf --flare-name 34 --method a-star -to 0123467589 -asw 0,0,0,0,50,50 \
-sp r:tf -opt
It also relies on the depth of the board in the traversal graph (which is the
fifth "-asw" parameter).
Here are the results vs. the original scan and the new one:
From Initial
26094 0
1015 1
833 2
749 3
639 4
581 5
500 6
381 7
273 8
234 9
198 10
137 11
100 12
78 13
62 14
38 15
24 16
19 17
14 18
5 19
7 20
4 21
2 22
3 23
1 25
3 27
2 28
1 29
1 30
1 35
1 40
From -asw 0,0,0,0,0,100
2 -18
1 -17
1 -16
2 -14
3 -13
4 -12
5 -11
13 -10
18 -9
33 -8
29 -7
34 -6
50 -5
70 -4
102 -3
142 -2
154 -1
25699 0
1021 1
833 2
755 3
634 4
553 5
452 6
348 7
259 8
211 9
169 10
117 11
85 12
55 13
46 14
31 15
20 16
14 17
14 18
5 19
6 20
2 21
1 23
1 25
3 27
1 29
1 35
1 40
Strangely enough, setting the ratio to 75%/25% yielded the exact same results
as the 50%/50% ratio.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
What does "Zionism" mean? - http://shlom.in/def-zionism
Chuck Norris is the greatest man in history. He killed all the great men who
could ever pose a competition.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Wed Oct 24 2012 - 05:34:24 IST