On Saturday 11 September 2010 18:50:57 Shlomi Fish wrote:
> Hi all,
>
> I'm sorry for posting from my GMail.com account, but at the moment
> reading my @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
>

As a followup to this here are the numbers of deals out of the first 1 million
whose span is below a certain number:

{{{
sqlite> SELECT COUNT(*) FROM bhs_runs WHERE status = 'U' AND num_checked <=
10;
71238
sqlite> SELECT COUNT(*) FROM bhs_runs WHERE status = 'U' AND num_checked <=
20;
86600
sqlite> SELECT COUNT(*) FROM bhs_runs WHERE status = 'U' AND num_checked <=
30;
94261
sqlite> SELECT COUNT(*) FROM bhs_runs WHERE status = 'U' AND num_checked <=
40;
99127
sqlite> SELECT COUNT(*) FROM bhs_runs WHERE status = 'U' AND num_checked <=
100;
110661
}}}

Regards,

Shlomi Fish


> 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/
Rethinking CPAN - http://shlom.in/rethinking-cpan

<rindolf> She's a hot chick. But she smokes.
<go|dfish> She can smoke as long as she's smokin'.

Please reply to list if it's a mailing list post - http://shlom.in/reply .