Freecell Solver 3.14.1 was Released

Freecell Solver version 3.14.0, shortly followed by Freecell Solver 3.14.1, which fixed a build problem on Microsoft Windows, have been released. Freecell Solver 3.14.1 is available in the form of a source archive, and a Win32 self-installing executable, from the download page. Freecell Solver is an open source framework (library and some command line applications), for automatically solving several variants of card Solitaire / Patience games, including Freecell.

This release features several new features: we added a 6th Best-First-Search weight of the inverse of the number of cards not above parents, which has proven useful. We now also allow test groups inside the --tests-order and --depth-tests-order with the random-dfs scan to be ordered using the function =asw(…) based on those BeFS weights.

As a result, the preset -l amateur-star or -l as for short has been added, that uses that and is our fastest preset yet. Another new preset is -l micro-finance (or -l mf for short), which yields especially short solutions.

There are also some not-as-major features: input boards can now contain a leading colon (":") at the beginning of the line of columns, so they can be copy-and-pasted directly from the output of fc-solve with the -p flag. The dbm_fc_solver and depth_dbm_fc_solver now store the positions more compactly (which aided in researching two-freecell deals), and the core libfreecell-solver code was made more 64-bit enabled and many of the limits were converted to 64-bit friendly ones.

A final note: we have dropped support for building Freecell Solver with Microsoft Visual C++ and other non-GCC compatible compilers, which do not support the newer C standards, and other useful features of GCC. Building Freecell Solver with GCC, clang and other compatible compilers will be continued to be supported on Microsoft Windows as well as on Linux and other UNIX-like systems.

More information about all these can be found in the distributed documents of Freecell Solver.

Enjoy!

Two Freecell Solvability Report for the First 400,000 Deals

With some help from some people on the fc-solve-discuss list and off the list (namely Amadiro from the University of Oslo and someone else that I met on IRC , I ran my solvers on the first 400,000 Windows Freecell deals with only two available freecells to see how many of them can be solved.

Here is the report:

Start Index	End Index	Solved	Impossible	Intractable
1	32,000	25,381	6,619	0
32,001	50,000	14,302	3,698	0
50,001	100,000	39,775	10,225	0
100,001	400,000	238,415	61,584	1 (No. 384243)
Total		317,873	82,126	1

So about 79.47% of the deals can be solved and the rest are impossible. The only intractable deal that none of my solvers could yield a verdict for is No. 384,243, and it spans a very large number of states:

• The dbm_fc_solver got into Reached 12,821,000,000 ; States-in-collection: 13,620,999,440 before it failed to produce more results due to a limitation of the hardware where it was deployed on.

• The depth_dbm_fc_solver yielded this:

  Reached 13,763,700,000 ; States-in-collection: 16,226,294,490 ; Time: 1345126456.520408 Queue Stats: inserted=16,226,294,490 items_in_queue=2,462,594,490 extracted=13,763,700,000

  with a curr_depth of 38. However, that solver may have some yet undiscovered bugs.

So what's next? I’d like to investigate some ways to scale to a larger number of states, perhaps by creating a distributed solver. A Google search for distributed breadth first search yields some results:

I hope you enjoy the statistics for the time being.

Freecell Solver 3.12.0

Freecell Solver version 3.12.0 has been released. It is available in the form of a source archive from the download page. Freecell Solver is an open source framework (library and some command line applications), for automatically solving several variants of card Solitaire / Patience games, including Freecell.

The first item to note is that the URL of its site changed from under *.berlios.de to http://fc-solve.shlomifish.org/, and that there is a redirect in place. Moreover, we have switched the version control system from one based on Subversion to a git repository which is currently hosted on GitHub (though we may move it later).

This release adds a new flag - --show-exceeded-limits or -sel for short, that removes some ambiguity in the output, and fixes a problem with starting the solver with --set-pruning r:tf in conjunction with -opt. A new preset - -l three-eighty (or -l te for short) has been added, which provides somewhat better performance.

The experimental dbm_fc_solver is now less experimental and can now store the positions inside binary trees in memory, and its memory consumption has been greatly reduced since earlier versions. We also added another experimental solver called fcc_fc_solver which aims to determine the solvability of a deal by analysing fully-connected-components (“FCCs”).

We also added support for building and testing the distribution in an out-of-tree build, and there are some cleanups to the code.

More information about all these can be found in the distributed documents of Freecell Solver.

Enjoy!

Freecell Solver 3.10.0 was Released

Freecell Solver version 3.10.0 has been released. It is available in the form of a source tarball from the download page.

This release fixes two bugs - one with the --max-iters affecting only the last instance, and one with reading foundations with 0, and implements many small optimisations and cleanups. It also adds some experimental code with the so-called delta-states, where states are compactly encoded based on the original state. This functionality is not available in the main solver yet, but it powers the experimental on-disk-key/value-databases-based solver, which end up not scaling very well during testing.

Enjoy!

Freecell Solver 3.8.0 was Released

Freecell Solver version 3.8.0 has been released. It is available in the form of a source tarball from the download page.

This release fixes some crashes using --trim-max-stored-states, adds a more meaningful man page instead of the token one that was previously present, adds scripts/parallel-range-solver-total to solve a range of deals in parallel by splitting them into chunks, and many smaller improvements and fixes.

We also forgot to mention the 3.6.0 release, which fixed the installation of fcs_dllexport.h, added the --tracemem compile time option, added a bug fix for incrementally increasing the iterations/stored-states limits, added a built-in version of kazlib's balanced binary search tree as a possible back-end for storage, and had some other improvements.

Enjoy!

Freecell Solver™ Goes Webscale

1 April, 2011, Tel Aviv, Israel: Freecell Solver Enterprises™, Inc., on behalf of the Freecell Solver™ development team, is glad to announce the upcoming availability of the Webscale™ Edition of Freecell Solver™, the solver for various types of Patience games.

Freecell Solver™, has until now made use of a compile-time choice of primitive, in-memory, data-structures such as hash tables or self-balancing binary trees, but now we decided that it's time to move on to something more in the spirit of 2010s. Since SQL databases have already become passé, we decided to skip directly to the NoSQL trend of databases (also known as "Oh no! No SQL!") and to write alternative backends for Freecell Solver™ for distributed NoSQL stores such as Cassandra, MongoDB, or CouchDB.

Freecell Solver Enterprises™ is certain that using these modern, high-performance, and highly distributed stores will increase Freecell Solver™'s webscalability, and allow it to process a larger amount of stored positions than it could at the moment at a far greater speed and make Freecell Solver™ be ready for the cloud. As our CTO, Shlomi Fish, says “If you're not excited about it now, you should be.”

Expect the upcoming availability of Freecell Solver™ Webscale™ Edition from the homepage of Freecell Solver™.

Freecell Solver 3.4.0 was Released

Freecell Solver version 3.4.0 has been released. It is available in the form of a source tarball from the download page.

In this release, we've added the --set-pruning flag to turn on the Horne's play prune, which improves performance. There are two new presets - -l enlightened-ostrich (or -l eo for short), which makes use of --set-pruning and is the fastest preset yet, and -l maliciously-obscure (-l mo) which is slow but generates especially short solutions.

We added a compile-time option to use RCS-like states storage which conserves a lot of RAM and allowed Freecell Solver to scale to over 200 million positions on an x86-64 machine with 64 GB of RAM (which was utilised for that courtesy of Amadiro's university). There are many other major and minor speed and memory optimisations in this release.

The --ms and -M flags were added to the make_pysol_freecell_board.py program, to generate Microsoft deals even for numbers higher than 32,000, which are different in PySol and PySolFC. Furthermore, the CMake configuration was updated to use "lib${LIB_SUFFIX}", so it can be built on some 64-bit systems.

Finally, there's an experimental --trim-max-stored-states which currently may crash the solver, but we decided to release it despite this fact.

All of these changes prove to be a huge step forward for Freecell Solver making this release its best release yet.