Loading ...
Sorry, an error occurred while loading the content.
 

[Better Version] Final Report for the 2-Frecells-based "DBM" Freecell Solver

Expand Messages
  • Shlomi Fish
    Hi all, I m sending a better version of this report for posterity. I ve written a report about attempting to solve the 2-freecell-based Windows Freecell deals
    Message 1 of 1 , Feb 11, 2012
      Hi all,

      I'm sending a better version of this report for posterity.

      I've written a report about attempting to solve the 2-freecell-based Windows 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) told 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-mail, out of the deals I reported as intractable:

      <<<
      In 2005, Danny A. Jones ran the first 50,000 deals for standard FreeCell with two freecells.
      Out of the first 32,000 deals, his solver found 25,381 solvable 2-fc deals (reported in the
      FAQ section "How often can I win?"), with 6,608 impossible and only 11 intractable.
      See the attached file.

      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 (= the University of Oslo - http://www.uio.no/english/ )
      high-performance-machines - the first one with 64 GB of RAM and more recently
      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).

      This is the final report of solving 2-Freecell deals using the "DBM" based
      Freecell Solver. This does not include the elusive deal # 982, which is
      intractable both by Danny A. Jones' solver and by ours (and which we hope that
      the Fully-connected-components (FCC)-based solver would be able to shed light
      on after some necessary modifications).

      It was generated using a Ruby script using the data provided by Amadiro
      using one of his university's high-performance machines. So thanks are extended
      to him and to his university. I'll upload everything to the Freecell Solver
      homepage soon.

      Regards,

      Shlomi Fish

      3129: Impossible (DAJ: Intractable) ; Reached: ~16700000/16736777 \
      Time: 461.755650997162
      5435: Solved (DAJ: Solved) ; Reached: ~317200000/402953588 \
      Time: 18934.7835159302
      6090: Solved (DAJ: Solved) ; Reached: ~159100000/199278081 \
      Time: 7538.81079888344
      7728: Solved (DAJ: Solved) ; Reached: ~581100000/709981356 \
      Time: 29172.0320699215
      9034: Solved (DAJ: Solved) ; Reached: ~382300000/450245763 \
      Time: 21436.9379889965
      11266: Impossible (DAJ: Intractable) ; Reached: ~167200000/167225796 \
      Time: 6174.17578792572
      12038: Impossible (DAJ: Intractable) ; Reached: ~12000000/12019785 \
      Time: 293.612964868546
      12064: Impossible (DAJ: Intractable) ; Reached: ~11600000/11617536 \
      Time: 325.979027032852
      13705: Solved (DAJ: Solved) ; Reached: ~6400000/7254365 \
      Time: 153.31712603569
      14790: Impossible (DAJ: Intractable) ; Reached: ~84600000/84606316 \
      Time: 2914.06726980209
      15804: Impossible (DAJ: Intractable) ; Reached: ~17500000/17511302 \
      Time: 480.840923070908
      17760: Intractable (DAJ: Solved) ; Reached: ~1468200000/1671598732 \
      Time: 97809.3720080853
      17880: Intractable (DAJ: Solved) ; Reached: ~1278800000/1616737805 \
      Time: 79754.6362040043
      18446: Solved (DAJ: Solved) ; Reached: ~70800000/99037155 \
      Time: 2694.79851603508
      19671: Solved (DAJ: Solved) ; Reached: ~505700000/547458213 \
      Time: 29875.1219639778
      20792: Impossible (DAJ: Intractable) ; Reached: ~30700000/30718221 \
      Time: 861.529717922211
      21779: Impossible (DAJ: Intractable) ; Reached: ~14200000/14215839 \
      Time: 405.994553089142
      26124: Impossible (DAJ: Intractable) ; Reached: ~13400000/13402138 \
      Time: 341.230257034302
      28188: Solved (DAJ: Solved) ; Reached: ~45400000/62734089 \
      Time: 2745.98109912872
      29577: Impossible (DAJ: Intractable) ; Reached: ~29400000/29400313 \
      Time: 794.414890050888


      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/

      Whitespace in Python is not a problem: just lay out all the whitespace first,
      then add the code around it.
      — sizz on Freenode's #perl

      Please reply to list if it's a mailing list post - http://shlom.in/reply .
    Your message has been successfully submitted and would be delivered to recipients shortly.