Report: The solvability statistics of the Freecell Pro 4-Freecells Deals
Note to Freecell Solver’s Users
Shlomi Fish - the core developer of Freecell Solver, and the webmaster of this website - has been experiencing reliability problems with incoming and outgoing E-mail (such as legitimate messages being dropped or classified as spam). They also affect his GMail-dot-com account.
Therefore, one should preferably contact him using other electronic means.
Table of Contents
Introduction
Publishing Date: 12 December 2016.
Updated: 18 August 2018.
Theodore Pringle had posted an announcement to the "fc-solve-discuss" group, where he said that he ran a Freecell solver over all the deals in the 8 milliard (1 to 8,589,934,591) Freecell Pro deals range which are based on the original Microsoft FreeCell dealing. He ended up discovering that there are 102,032 impossible deals and 46 intractable deals. An “intractable” deal in this context means a deal for which all definitive solvers ran out of resources (usually memory) before determining whether it was solvable or impossible. (Also see a discussion about it on Reddit.) Further analysis reduced the number of intractable deals down to 9 - see the updated list.
I (= Shlomi Fish) set out to determine the solvability of these intractable deals while using Freecell Solver's depth_dbm_fc_solver, which is a solver which occupies relatively little RAM, and aims to completely scan all positions in a board and conclusively determine whether it is solvable or not. That solver was first ran on an Amazon Web Services (“AWS”) EC2 node with 256 GB of RAM. (Thanks to Jonathan Ringstad for the suggestion to use AWS.)
Running the solver there has shown that 8 out of the 9 deals were impossible to solve, while the 9th deal - Deal 6825625742 ran out of hard disk space (we were given only 8 GB of disk space by default, which turned out to not be enough). After some delay, a new EC2 node with the same amount of RAM (= 256 GB) but this time with more hard-disk space was rented and the solver was ran on deal 6825625742 again. This time, it ran to completion, and proved the deal to be impossible as well, thus yielding no remaining intractable deals in the FreeCell Pro range.
Conclusions
Out of the 8.6 milliard Freecell Pro deals, there are 102,075 ones that are impossible with 4 freecells, or approximately one impossible deal out of 84,000 random deals. The list of indices of these deals can be found in a GitHub repository in part based on a Google Drive folder maintained by Theodore Pringle.
Note that 6 deals in the range are also impossible to solve with 5 freecells. These deals are: 14720822, 647519280, 3015622123, 5705339228, 7273316239 and 7573544118. They are all solvable using 6 or more freecells.
Some Reflections
One surprising fact is that solving 4-freecells deals was much easier for us to do programatically than solving the same 2-freecells deals. An earlier report about their statistics, ran into more difficulties solving the first 400,000 2-freecells deals, which is a deals’ space smaller by over 4 orders of magnitude. Perhaps this can be explained by the fact that many more deals are winnable using 4 freecells.
Charts
Queue Items Per Iterations for Each of the Deals
Note: the depth_dbm_fc_solver uses a variation on breadth-first search where we keep a queue of items to check and check an iterations count of states. The x-axis - "Iterations" roughly corresponds to time while the y-axis, corresponds to the number of states in the queue.
Iterations Summary Table
| Deal No. | Iterations Reached |
|---|---|
| 219,837,216 | 977,634,853 |
| 1,252,215,044 | 358,506,418 |
| 2,255,988,055 | 566,936,438 |
| 2,901,685,480 | 330,747,308 |
| 2,902,413,565 | 348,126,072 |
| 4,260,084,873 | 1,144,307,654 |
| 6,687,921,694 | 354,953,970 |
| 6,825,625,742 | 7,062,586,101 |
| 7,489,392,343 | 507,133,501 |
Deal 219,837,216
Deal 1,252,215,044
Deal 2,255,988,055
Deal 2,901,685,480
Deal 2,902,413,565
Deal 4,260,084,873
Deal 6,687,921,694
Deal 6,825,625,742
Deal 7,489,392,343
Future Directions
The version of the depth_dbm_fc_solver that was used for solving the intractable deals in this report had poor multitasking/multi-threading scalability so work was done in the “feature-branch--depth-dbm-solver--batches--issue7” branch in an attempt to mitigate that. The benchmarks appeared to be encouraging.
Some further work has been done in the “feature-branch--depth-dbm-solver--condvars--issue8” branch but results are less conclusive and both “before” and “after” benchmarks yield a large variance.
One note is that we were told that the cost of additional disk space (beyond the pre-allocated 8 GB) on Amazon EC2 is prohibitive and that it would be cheaper to make use of Amazon S3. We wish to look into writing an optional S3 backend for the depth_dbm_fc_solver’s offloading queue by using the AWS SDK for C++ which is open source and appears to be well-maintained and stable.
Shlomi Fish also wishes to try to independently confirm the impossibility of the other deals on Theodore Pringle’s list, because he used a solver which used to have some false negatives. This effort ran into RAM shortage problems on his personal computer which only has 8 GB of RAM so it may require getting access to a more capable machine.
Another potential future direction is that we noticed that some terminal game positions are seemingly impossible to a human player but the computer solvers just move cards on top of each others and into empty slots using reversible moves. We wish to investigate some potential prunes to detect such terminal positions and avoid traversing them further.
Links and References
