Hi all,
I've written a report about attempting to solve 2-freecell-based Freecell deals
using Freecell Solver here:
http://fc-solve.blogspot.com/2010/07/solvability-statistics-of-two-freecell.html
As Michael Keller (of Freecell FAQ / Solitaire Laboratory Fame) noted to me in
a private E-mail, I didn't quote the right part of the Freecell FAQ, and Danny
A. Jones's solver had been more conclusive on more deals than mine. Quoting
from the E-mails, out of the deals I reported as intractable:
<<<
Of the 33 you have listed, he [= Danny A. Jones] reported:
8 impossible (891, 7214, 14445, 15957, 16462, 17184, 19678, 27799),
11 intractable (982, 3129, 11266, 12038, 12064, 14790, 15804, 20792, 21779, 26124,
29577),
14 solved (5435, 6090, 7728, 9034, 13659, 13705, 14262, 16322, 17684, 17760, 17880,
18446, 19671, 28188)
>>>
I took determining the solvability of the other deals that my solver had
determined as intractable (including those that Jones's solver did) as a
challenge. I eventually was aided by Amadiro (an Internet
friend of mine (who is BCCed to this message)), and he has given me access to
two of his university's (=
http://www.uio.no/english/ )
high-performance-machines - the first one with 64 GB of RAM and more recently
to one with 128 GB of RAM. This allowed my solvers to scale to large
counts of graph positions (~ 1.6 milliard positions) before either crashing
from lack of memory (thus declaring the initial position intractable), or
better yet finding a solution or proving it to be unsolvable (barring bugs in
the code and other issues).
Today, Amadiro sent me the dumps of the boards that finished running, and one
which was still running. Here is their report:
#. Deal #982 (DAJ intractable) remains intractable.
#. Deal #3129 (DAJ intractable) was shown to be impossible. The last line in the
run-time display (updated every 100,000 checked states) is:
<<<
Reached 16700000 ; States-in-collection: 16736777 ; Time: 1327655663.031178
>>>
#. Deal #5435 (DAJ solvable) was solved.
#. Deal #6090 (DAJ solvable) was solved.
#. Deal #7728 (DAJ solvable) was solved.
#. Deal #9034 (DAJ solvable) was solved.
#. Deal #11266 (DAJ intractable) was shown to be impossible. Last line is:
<<<
Reached 167200000 ; States-in-collection: 167225796 ; Time: 1327738952.936415
>>>
#. Deal #12038 (DAJ intractable) was shown to be impossible. Last line is:
<<<
Reached 12000000 ; States-in-collection: 12019785 ; Time: 1327739252.599388
>>>
#. Deal #12064 (DAJ intractable) was shown to be impossible. Last line is:
<<<
Reached 11600000 ; States-in-collection: 11617536 ; Time: 1327739582.003678
>>>
#. Deal #13705 (DAJ solvable) was solved.
#. Deal #13790 (DAJ intractable) was shown to be impossible. Last line is:
<<<
Reached 84600000 ; States-in-collection: 84606316 ; Time: 1327742657.162413
>>>
#. Deal #15804 (DAJ intractable) was shown to be impossible. Last line is:
<<<
Reached 17500000 ; States-in-collection: 17511302 ; Time: 1327743141.519897
>>>
#. Deal #17760 (DAJ solvable) is still intractable by the parallel-BrFS-based solver (but had been shown to be solvable by other solvers).
#. Deal #17880 (DAJ solvable) is work in progress. Last line given is:
<<<
Reached 429200000 ; States-in-collection: 564548879 ; Time: 1327873843.632686
>>>
#. Further deals are yet to be processed.
-------------------------------
One can find the full dumps so far here:
http://www.shlomifish.org/Files/files/dbm-fc-solver-intermediate-dumps.tar.xz
(short URL -
http://xrl.us/bmp6zs ).
some future directions are:
1. I've detailed a method, which may help conserve memory further:
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1093
I'm currently working on it, but it is time-consuming and I need to juggle
some other priorities and interests. Once I have it implemented and tested
to work well, I can try deploying it on my home machine and on Amadiro's HPC
machine.
2. It may be a good idea to investigate why the CPU utilisation of the
parallelised Breadth-first search (BrFS) implemented in the so-called
“dbm_fc_solver” did not scale too well to a large number of worker threads.
So far the maximum was 170% CPU utilisation at 12 threads, where a similar
amount of CPU utilisation was achieved on my home Core i3 machine (which is
a single CPU machine with two cores and two hyperthreads-per-core).
-------------------------
Hopefully, we'll keep you posted on further developments.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
http://www.shlomifish.org/humour/ways_to_do_it.html
<rindolf> If you repeat a scene 50k times, then the movie will have less
entropy and will compress better. ( irc://irc.freenode.org/#perlcafe )
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sun Jan 29 2012 - 16:09:10 IST