This is an interim progress report on what's new on the Freecell Solver
version control repository since the last report for r3001 (we're now at
r3018 ):
1. There are new benchmarks on /trunk/fc-solve/benchmarks/log.txt .
2. There's a new patch at:
/trunk/fc-solve/rejects/patches/get-rid-of-new-state-conditional.diff
It should have improved performance, but didn't.
{{{
This patch gets rid of the new-state conditional but doesn't improve
performance (at least not on gcc-4.5.0 / linux) I don't know why.
}}}
3. Made fc_solve_check_and_add_state a method of hard_thread instead of s_t.
soft_thread was not used anywhere there.
4. Small optimisation to THE_TESTS_LIST in scans.c .
5. Add the first version of:
/trunk/fc-solve/docs/delta-to-original-states-spec.txt
This details this:
http://fc-solve.berlios.de/to-do.html#orig_calc_states .
6. Add a TODO to investigate if Selection Sort yields better performance
than the currently used Insertion Sort. I also read in the book
"The Algorithms Design Manual" that Shell Sort is very fast.
7. There are some new scripts and data in the 2-cells-freecell configuration.
8. Add scan #26.
It yielded an especially short solution for:
make_pysol_freecell_board.py -F 77262416109319812498
so I wanted to experiment with it.
It is --method a-star -asw 5,4,0,0,0
9. Added several new -dto scans optimised for 2-freecell deals.
10. Now allowing the Find-Optimised-Sequence program to
continue from the middle of the algorithm so it can be resumed after being
stopped.
11. Added a way to change the size of the packs in alloc.c / alloc.h.
I experimented with different pack sizes and it did not seem to improve
performance on my P4-2.4GHz. I hoped the fewer mallocs will make a difference
but apparently they didn't.
-------------------------------------------
I benchmarked the 2-freecells run using "freecells-solver-range-parallel-
solve".It took it 9,868.26628994942 seconds to run (or 2 hours and 44 minutes)
- very
long. It also yielded 167 intractables and 6,690 unsolved boards. This
means 25,143 boards were successfully solved. The Freecell FAQ
(
http://www.solitairelaboratory.com/fcfaq.html ) says that "With two
freecells, there are at least 24,161 solvable deals." - this means we solved
more two freecell deals than were previously known to be solvable.
I've still began to go over some of the intractables and unsolved boards and
tried to find good solutions for them somehow. For example, with deal #12
which was marked as intractable I found this solution:
<<<
shlomi[fcs]:$trunk/fc-solve/source$ pi-make-microsoft-freecell-board 12 | \
./fc-solve --freecells-num 2 -to '[012][347]' \
--method random-dfs -seed 33 | tail -3
This game is solveable.
Total number of states checked is 209.
This scan generated 334 states.
>>>
This was done using the scripts/find_seed.bash script in the fc-solve/source
directory.
With deal #197 (reported as intractable), I could only find atomic moves based
heuristics and they all appear to yield pretty long heuristics:
{{{
shlomi[fcs]:$trunk/fc-solve/source$ pi-make-microsoft-freecell-board 197 | \
./fc-solve --freecells-num 2 -mi 500000 -to '01AB[CDE]' \
--method random-dfs -seed 922 -opt | grep ==== | wc -l
244
}}}
If anyone can find a shorter solution, I'll appreciate it.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Freecell Solver - http://fc-solve.berlios.de/
God considered inflicting XSLT as the tenth plague of Egypt, but then
decided against it because he thought it would be too evil.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Fri Jul 09 2010 - 23:58:14 IDT