Hi all.
Great news everybody: we have finally reached a conclusive verdict regarding
the 2-Freecell Microsoft deal No. 982 : it was demonstrated to be impossible
(as I suspected for some time, and naturally barring any bugs in the solver’s
code.)
This conclusion was reached thanks to a worker from Washington State
University (
http://www.wsu.edu/ ; he's BCCed to this message) who was given
permission to deploy the dbm_fc_solver on one of his university’s
high-performance computing (HPC) nodes, which has 512 GB of RAM, and did the
necessary work of deploying it there, with my guidance. I'll also like to
thank Amadiro (also BCCed) who had deployed the solver earlier on a
University of Oslo (
http://www.uio.no/english/ ) HPC computer, with 128 GB of
RAM, which had enabled to solve most of the other intractable 2-freecell deals
and inspired many improvements to the codebase. Some of these improvements were
recent optimisations in RAM consumption (which I'd like to post about in a
separate post.).
Here are the last lines from the log of the solver’s run. A complete log is
available here:
http://fc-solve.shlomifish.org/downloads/dbm-fc-solver/982-fully-traversed.dump.xz
and a Perl program to process it and output a Tab-separated value file with
some run-time numbers and statistics, can be found here:
https://github.com/shlomif/fc-solve/blob/master/fc-solve/source/scripts/convert-dbm-fc-solver-log-to-tsv.pl
[LOG]
Reached 3095300000 ; States-in-collection: 3095579317 ; Time: 1337732245.947757
>>>Queue Stats: inserted=3095579317 items_in_queue=279317 extracted=3095300000
Reached 3095400000 ; States-in-collection: 3095642846 ; Time: 1337732248.707633
>>>Queue Stats: inserted=3095642846 items_in_queue=242846 extracted=3095400000
Reached 3095500000 ; States-in-collection: 3095691025 ; Time: 1337732250.920092
>>>Queue Stats: inserted=3095691025 items_in_queue=191025 extracted=3095500000
Reached 3095600000 ; States-in-collection: 3095742956 ; Time: 1337732253.286799
>>>Queue Stats: inserted=3095742956 items_in_queue=142956 extracted=3095600000
Reached 3095700000 ; States-in-collection: 3095790607 ; Time: 1337732255.441771
>>>Queue Stats: inserted=3095790607 items_in_queue=90607 extracted=3095700000
Reached 3095800000 ; States-in-collection: 3095838110 ; Time: 1337732257.554776
>>>Queue Stats: inserted=3095838110 items_in_queue=38110 extracted=3095800000
instance_run_solver_thread end
instance_run_all_threads end
handle_and_destroy_instance_solution start
Reached 3095862346 ; States-in-collection: 3095862346 ; Time: 1337732258.708077
>>>Queue Stats: inserted=3095862346 items_in_queue=0 extracted=3095862346
Could not solve successfully.
handle_and_destroy_instance_solution end
[/LOG]
So, the game’s graph spans 3,095,862,346 positions. Note that it excludes some
positions that were pruned using Horne’s play.
I'd like to post a report summarising the conclusion about the statistics of
solving all the 2-Freecell 1-32,000 Microsoft deals, but this will have to yet.
Moreover, it appears that the dbm_fc_solver still consumes much more RAM than it
should, so I'd like to look into the Partial-IDA* scan to see if it
will improve upon it. If anyone can recommend good online (or less preferably
offline) sources that explain it, I would be grateful.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Perl Humour - http://perl-begin.org/humour/
Comedy is simply a funny way of being serious.
— http://en.wikiquote.org/wiki/Peter_Ustinov
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Wed May 23 2012 - 02:04:38 IDT