Hi all,
I'm sorry for posting from my GMail.com account, but at the moment
reading my _at_iglu.org.il email is unsuable due to a KMail misbehaviour.
In any case, with the help of "Amadiro", who provided me with access
to one of his university's High Performance Computing (HPC) Machines
with 64 GB of RAM, I have successfully ran my Black Hole solitaire
solver over the first 1 million PySolFC Black Hole Solitaire deals
(numbered 1 to 1000000) and either solved them all or proved them to
be unsolvable. This was partially enabled by translating the solver
from its original code in Perl to the C programming language which
made it faster and much less memory hungry.
Here are the results as reported for the solver's depth-first-search
(DFS) scan (which prioritises moves to those for columns with the
highest column numbers):
{{{{
Unsolved
---------------------------
Count: 130587
Min: 1
Max: 133195861
Average: 292400.883977731
StdDev: 2491612.46642446
Median: 9
Solved (Checked)
---------------------------
Count: 869413
Min: 52
Max: 215818993
Average: 553884.397341655
StdDev: 1625212.95852275
Median: 79042
Solved (Generated)
---------------------------
Count: 869413
Min: 96
Max: 215819025
Average: 553927.976527841
StdDev: 1625212.55666315
Median: 79085
}}}}
Some analysis:
1. The checked and generated states for the solved states are closely
related and generate similar statistics. This is expected.
They are the identical for the unsolvable games because all possible
positions in the spanned positions' space have been traversed.
2. It appears that 86% of the deals are solvable.
3. The unsolved deals states number median is 9 which indicates that
in at least half of the deals, you'll reach a dead end fairly quickly.
Nevertheless, many unsolved states have spun millions of positions.
4. Both the medians and means of the solved states are high, which
means there are many way to try and solve them. By converting the
solver to use BrFS (Breadth-first search), I might be able to
calculate the size of the spun positions' space, but it wasn't done
yet. However, one should note that BrFS won't make the solution
shorter as in Black Hole solitaire all solutions are the same length.
----------------
I should note that it took a lot of work to do this with many script
written and deployed on many machines. At one point I coded a small
Dancer-based web app (
http://perldancer.org/ - a micro
web-development framework for Perl) to distribute IDs to clients which
solved sequences of boards at home and thus formed a small cluster. It
was a lot of fun though.
Regards,
-- Shlomi Fish
--
------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Electrical Engineering studies. In the Technion. Been there. Done
that. Forgot a lot. Remember too much.
Received on Sat Sep 11 2010 - 09:25:22 IDT