Hi all!
(Note to Ben Pfaff: I discuss Freecell Solver's integration with libavl2 below
shortly).
There's quite a lot that's new on the trunk, so I guess I should get started.
First of all, I did quite a lot of code cleanup - renaming files, moving
declarations and definitions to different files, etc. As a result, the code
should be somewhat easier to dive into.
Next I added a script for gcc's Profile Guided Optimisations which I discussed
in the previous message, and also adapted the makefile to such a scenario. As
I explained, the results were not promising so far.
Afterwards, I tweaked the CMake build system and the Freecell Solver code
itself to be able to make use of any of libavl2's binary trees
implementations. This seems to work fine and not complain. One can use a
different tree type (or something else altogether) for both the states and the
columns. From my benchmarks, it seems like the Right-Threaded AVL trees
provided by libavl2 are a bit slower than libJudy and much slower than when
Freecell Solver is using my own custom hash. One still needs to benchmark more
tree types.
In the process the libJudy code was fixed, as it got broken previously.
After many obstacles along the way, I finally collected all the data I needed
to generate the "sand-stone" preset of atomic moves that optimises for the
solution length. The results are: (fg is optimise-for-speed, ss is "sand-
stone" - optimise for solution length).
{{{{{{{{{{{{{{{{{{{
shlomi:$trunk/fc-solve/source$ perl scripts/statistical-analysis.pl fg.txt
Field No. 0
---------------------------
Min: 79
Max: 4081
Average: 294.754269972452
StdDev: 161.758713537058
Median: 255
Field No. 1
---------------------------
Min: 48
Max: 4062
Average: 262.54098201264
StdDev: 157.231280702358
Median: 225
shlomi:$trunk/fc-solve/source$ perl scripts/statistical-analysis.pl ss.txt
Field No. 0
---------------------------
Min: 77
Max: 3172
Average: 155.793394869336
StdDev: 86.5599136070277
Median: 133
Field No. 1
---------------------------
Min: 40
Max: 3059
Average: 124.967693598657
StdDev: 82.5992142675541
Median: 103
}}}}}}}}}}}}}}}}}}}
It can be seen that both the median and the average are smaller by 100 steps,
and that the standard-deviation is smaller too, but that being over 100 steps,
they are still very long. This may be expected of atomic (= single-card)
moves.
Finally, while running the fools-gold preset, I encountered a Microsoft
Freecell deal that was intractable with Atomic moves in Freecell Solver and
ended up consuming over 70% of my machine's RAM.
The deal is No. 30857:
{{{{{{{{{
2C AS 3H TC 7D 8H QD
AC 2S 7S 7C KD QH TS
8S 9C 3C 2H 6D 4S JC
KS KC 5C 8C QS 9H QC
4H 4D KH 6C 3S JS
5D 2D 9D 6S AD JD
AH TD 8D JH 4C 9S
6H 3D TH 5H 7H 5S
}}}}}}}}}
Here is what my investigation yielded:
1. "./fc-solve 30857.board" solves it in 1,431 iterations. (It's a meta-moves
preset)
2. "./fc-solve -l gi 30857.board" solves it in 944 iterations. A meta-moves
preset too.
3. "./fc-solve -l fg --freecells-num 3 30857.board" (an atomic moves preset
with the Freecells Number restricted to 3 freecells) solves it in 1,444,370
iterations.
4. Freecell Solver version 2.8.x also runs into a problem with it, so it's not
a recent regression.
5. "./fc-solve -to ABCDE01 30857.board" (atomic moves and not a meta-scan)
solves it in 1,230,350 moves. "--freecells-num 3" seems to make it worse.
6. The game is reported to be unsolvable with 2 freecells.
7. I played the game by hand and it wasn't too difficult.
8. Tom Holroyd's Patsolve solves it after:
{{{
6.72user 0.03system 0:06.83elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+8outputs (0major+6965minor)pagefaults 0swaps
}}}
with the default preset. With -S it is solved after:
{{{
0.08user 0.00system 0:00.09elapsed 85%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+8outputs (0major+439minor)pagefaults 0swaps
}}}
I assume FCELL.COM does not have a problem with it either.
-----------------------
That's it for now. Bye all.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Interview with Ben Collins-Sussman - http://xrl.us/bjn8s
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Sat Jun 06 2009 - 10:41:21 IDT