Freecell Solver's Future Directions
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.
About
While Freecell Solver is a fairly usable package that satisfies the needs of a large part of the users, it is by no means complete. This page hopes to address some of the long-term, primary issues in which I'd like to enhance it in the future. It is based on the to-do list file, but is more elaborated and detailed.
Note that it is possible to work on Freecell Solver if you would like to give or get academic credit.
Table of Contents
- About
- Tasks to be Considered in the Future
- Derived State Ordering and Incorporating Patsolve's Logic
- States Calculated from the Original
- Safety from Failed Memory Allocations
- A provably correct solver for Freecell and similar games (with a verified proof)
- avoid use of YUI by Solitairey
- 2freecell Deals
- Generalising Freecell Solver to non-card Games
- Finale
- Completed Tasks
Tasks to be Considered in the Future
Derived State Ordering and Incorporating Patsolve's Logic
From any given position Freecell Solver reaches it uses some move functions to generate a list of subsequent positions that can be reached from it. Each one of those functions corresponds to one move type, and they output the derived states in the order they found them. FCS (= Freecell Solver) groups the lists into test groups, and then either try them one by one, or randomizes them.
What can be done, is to order the derived states based on some parameters, other than simply randomizing them. Currently there is a code for a state prioritization that is used in the best-first-search code. Aside for that, there is also the prioritization Tom Holroyd implemented for Patsolve. What I would like to have for the next release, is a generic way to order derived positions, implementing all of the random, mine, and Tom's back-ends, and an ability to implement more in the future.
States Calculated from the Original
In the variants of Solitaire supported by Freecell Solver, during the game, each column has a few of the cards from the start of the game, followed by a sequence of cards that decrease in rank. Thus, we can simply store:
- The number of original cards. 0-104 for two deck games - we need 7 bits for that. (8-bits for parity)
- The number of cards in the sequence. 0-13 - we need 4 bits for that.
- Possibly the first top card - if no original cards are left in the column. (6-bits)
- For each of the cards in the sequence we need to store their suit. That is 0-3 which is 2-bits.
Since we can determine the number of suit units from the number of cards in the sequence, we can store them after the column header, and thus store the column headers compactly. For a typical game we need 12 bits*$NUM_COLUMNS plus at most 2 bits * 52 * $NUM_DECKS. For Freecell, that would make it 12*8+2*52 == 200 bits, which is 25 bytes. Or less in many cases.
In comparison, the "Indirect Stacks" allocation (which is the most compact one implemented yet) takes 4-bytes for each column on a 32-bit machine (because it uses a pointer), which makes it 32 bytes, plus more to store the cards in the columns. This becomes worse on 64-bit computers.
While this (the calculated from original) representation is not suitable for inspecting the state, in order to calculate the derived moves from it, it would be suitable for storing the state in the states collection. Thus, we will have to convert to and from that representation.
This suggested feature was inspired by a similar technique used by the Don Woods solver.
Note: this was implemented in dbm_fc_solver, and depth_dbm_fc_solver, but not in libfreecell-solver yet.
Safety from Failed Memory Allocations
Freecell Solver uses many calls to the memory allocations, but does not check that they return a valid buffer pointer. Should the memory run out, and they fail, it can easily cause the entire process running it to crash.
What needs to be implemented is a way to check if malloc()
and realloc
calls returned NULL, and if so, free all other allocated memory and propagate the memory upward to the calling functions. There are several ways in which it can be achieved. One would be by defining an exception class, much like that of Java only passed as one of the function parameters and handled explicitly in each function. Another option would be to keep all malloced pointers inside an Apache Portable Runtime-like memory pool and to explicitly free it should an allocation failed.
This will involve a great deal of extra code and complexity, but will make Freecell Solver more secure and fail-proof.
A provably correct solver for Freecell and similar games (with a verified proof)
MS Freecell Deal #11982 is believed to be impossible, and even though several exhaustive Freecell solvers have completely traversed its game graph, as far as we know none of them was implemented using a proof assistant which verified and validated its correctness proof.
To further strengthen the belief that it (and other deals) are impossible, we would like to see such a solver written.
avoid use of YUI by Solitairey
2freecell Deals
Sorry for the late reply, but I have proof that 384,243 is impossible with 2 freecells. The critical position the computer couldn't solve is after the following moves (384243, two freecells):
13 78 63 52 6a 62 16 46 7b 76 74 16 76 14 16 a1 b1 7a 87 43 47 37 8b 87 57 57 b8 4b 47 46 17 27 21 24 14 28 21 23 23 b3 2b a2 5a 52 8h 68 61 a5 65 81 85 15 4a 4h b4 64 62 42 68 48Note that in the fourth line, 21 24 14 is the supermove 24.
The only way out in the resulting position that computers couldn't solve is to put up the hearts and/or diamonds to the homecell, but Patsolve proved the resulting positions impossible. I checked alernatives earlier, but again Patsolve proved them impossible.
That proves 384,243 impossible with two freecells.
Generalising Freecell Solver to non-card Games
This is a very pipe-dream goal. As some of you may be aware I already wrote LM-Solve as a solver for several types of Logic Mazes, which are another type of single-player games (which are much easier to solve using a computer). It is written in Perl, still runs quite quickly, but is still largely incomplete. It is also still a standalone program without a usable API.
Now, I also thought about writing a solver for the old DOS game StoneAge, and generally there are other single-player card games for which Game AI heuristics are required to solve. Most of the logic of Freecell Solver is quite generic, and I suppose may prove useful to other games. So, instead of having separate solver (in C, LISP, Perl, Python or whatever) for each one of these games, we can have a unified solver with several game plug-ins. This would be cool, because it would mean hackers of single-player game AIs will not have to re-invent the wheel time and again; instead, they can only implement suitable test functions, and prioritization functions for their own games, and still enjoy the power that the Freecell Solver framework gives them.
Notice that my attempt at solving several talon-based games Solitaire Card games like Klondike or Gypsy was not successful. That does not mean it can't be done. Michael Mann was more successful with his port of Freecell Solver, and Stephan Kulow has an interesting heuristic for single-card-deal Klondike in kpat that can solve on average 50% of the games. (I don't think it is a back-tracking heuristic, though).
Finale
If all or most of these changes take effect, Freecell Solver will become much more "bloated" with features and enhancements than it already is today. Freecell Solver has already turned, from a proof-of-concept solver I used to test if my initial idea on how to solve Freecell would work, to an architecture dedicated to solving Freecell and similar Solitaires. I think it satisfies the needs of most users quite adequately. However, I think that enhancing it further is still a good idea, because it will make the code more modular and more maintainable, and would allow it to become a reference implementation or a base for similar projects with the needed subset of functionality.
Note that Freecell Solver was not the first computerized solver for Freecell to be written. (One of the first was the one by Don Woods, and Woods is very famous for many of his other endeavours.) It will also not the last that will be written (there is in fact an AI course in the University of Massachusetts, given each year, in which the students are assigned to write a Freecell solver as one of their work assignments). I recommend reading Eric Raymond's The Cathedral and the Bazaar to understand why adding more features can still be a good idea. IT discusses fetchmail which is still actively developed, despite the fact it will give anything most users will need and more. I don't see a reason to stop developing Freecell Solver just because it has reached a similar state. So people, hack on! (On Freecell Solver or something else.)
Completed Tasks
Shortening the Identifier Prefix
At the moment, the global Freecell Solver identifiers use the freecell_solver_
prefix. However, this prefix is too long and makes the code hard to read. Using the fcs_
prefix wouldn't be desirable either, because we don't own the fcs prefix. However fc-solve is ours and as a result, we can use fc_solve_
instead. Note that for backwards compatibility, the Freecell Solver interface functions should be named freecell_solver_user_
. This is not an issue because they are not used internally.
Writing an Automated Testing Framework
Freecell Solver at the moment has very little if any automatic tests that were prepared to it. Testing it is done manually and relies on the developer's intuition and the users' feedback. So far, most stable x.y.0 releases were followed by several minor version that fixed some things. (usually minor) Many of the tests performed are semi-automatic and just a matter of keying the same command sequence over and over again. A unified automatic testing framework may go a long way into ensuring the quality of the released product and while not eliminating the need for an experienced developer/Q&A engineer, will make things easier in the long run.
There are several types of tests I have in mind:
- Regression Tests - making sure the output of various runs of Freecell Solver is identical to runs of previous versions (by comparing MD5 checksums). The solving algorithm was known to change from release to release, but it is still expected to be the same unless explicitly modified. If it does, one can re-initialize the checksums.
- Unit Tests - making sure every module of Freecell Solver is not broken by explicitly testing its interface.
- Validity and Stability Tests - making sure various runs of Freecell Solver do not crash and produce valid output. (that can be verified by playing the solution, or analysing the run-time trace). Also, making sure that too virtually identical runs (differing only in insignificant parameters) produce identical results.
For performing the test, you can use any tool that can be easily installed on a GNU-based UNIX derivative. I would prefer if the tests were written in a combination of C, Perl and Bash (or plain sh). Still, I will accept tests written in other languages or frameworks, because they are better than no tests at all, and can easily be re-implemented should the need arise.
Converting the Install Procedure to SCons
At the moment, Freecell Solver uses GNU Autoconf, Automake and Libtool as its build and installation system. However, these tools are incredibly idiosyncratic and painful to work with, and have caused many problems in the past. A more modern and superior tool is SCons, and I had a pleasant experience working with it on Latemp.
I believe a switch of the Freecell Solver build system to SCons is in order. The only thing that has to be done previously is to write a rudimentary regression test suite to check the output of several board solutions before and after the switch. (Better safe than sorry.)
Note: Eventually it was decided to convert the Freecell Solver build-system to use CMake instead, and we are happy with this choice.
PySol Integration
PySol by Markus Oberhumer is by far the most feature-rich and complete open-source suite of card Solitaire games. PySol's has its own ad-hoc solving mechanism for all of its supported variants, including those that are supported by Freecell Solver. However, as far as the games supported by Freecell Solver are concerned, it fairs much worse, often leading the player to incorrect solutions.
PySol is written in Python, a high-level cross-platform language. Integrating Freecell Solver into PySol will require creating Python bindings for some of Freecell Solver API (a large part of it can be encapsulated by calls to its internal command line arguments-based configurator), and then creating the appropriate interface within the core PySol code.
As of January 2, 2003, PySol 4.81 is available on its site, and is ready to run and stable. Markus mentions there that he is working on PySol 5, which would be based on wxPython, and include many improvements. Assuming you are interested in integrating it, the choice is yours whether to patch PySol 4.81 or wait for a beta of PySol 5.x to be released.
Note: PySolFC, an enhanced spin-off of PySol now has an extensive integrated support for solving using Freecell Solver for all of the variants that the latter supports. The integration was done by calling the fc-solve command-line solver, and parsing its output, which was not how I thought of doing it, but still is a good way to achieve the integration. The original developer of PySol now recommends PySolFC instead on the PySol homepage, and I have been happy with it as well.
Thanks to the PySolFC developers for making it happen.
Command Line Prefix Tree Handling
At the moment, each flag in the command line is checked by comparing for each of the command line options accepted by Freecell Solver, one after the other. This is sub-optimal because it is possible the relevant command line option will be looked up only at the end, and also because this long process needs to be done for each option that was input on the command line.
To resolve it it would be a good idea to define the command line processing by processing a prefix-tree of command line options, that once accepted will result in a clause being evaluated. (Or if failed, will jump to a common "unknown command line option" handling code.) This should be done by preprocessing the command line evaluation code using a Perl program written for this purpose.
Note: already implemented in freecell-solver-2.12.0.
RCS-like State Storage
RCS is short for Revision Control System, and is an early version control system for UNIX computers, that is still in use today. (Either directly or indirectly). RCS works by storing the original file, and then storing the differences from the original to its subsequent versions, and from each subsequent versions to its subsequent versions etc. To extract a file of version X, it starts from the original version and applies patches 0->1, 1->2 until X-1 -> X.
Nadav Har'El suggested that instead of storing the entire state in memory, Freecell Solver will only store the moves leading to this state from its predecessor. That way, a lot of memory will be conserved, and FCS may even run faster. Freecell Solver already stores the moves to the parent states, because they are required to output the solution as a sequence of individual moves. However, it still requires the bulk board layout to distinguish between similar states.
Your mission, should you choose to accept it, is to tweak the code, so it would be possible to remove the board layouts themselves and get by with the moves alone. Note that the code at the moment, is completely unsuitable for this, and would have to be re-vamped. Also note that I believe one would still need to have a cache of the recently encountered states, to make sure the solver does not spend too much time constructing states from scratch.
This is a relatively speculative feature, which I only want to implement to see how well it run.
Note: Implemented at version 3.4.0 as a compile time option. With RCS states, Freecell Solver runs slower, but, on the other hand, consumes much less RAM, which allows it to scale better to a large number of positions. The older storage method that stores the position's layout itself in memory is still available as a compile-time option and will continue to be maintained.
Porting to Java
Imagine being able to browse to a web-site which will present you with a Java applet implementing Freecell with a built-in solver. At the moment Freecell Solver is written in C, and requires compilation or downloading a binary or a program that integrates it. If it is converted to Java, however, it can be deployed on most modern Internet-connected systems without the need for pre-installation.
Writing an equivalent Java version (perhaps without some of the specific C optimizations that Freecell Solver has), would be a very cool thing. I did not get to do it yet, because I keep having new ideas for improving the C versions. Note that as far as the graphical user-interface is concerned, there should not be too much problem, because there's already an open-source Solitaire Suite written in Java, with Freecell and many other games.
Note that Internet C++ assuming it becomes popular, may eventually eliminate the need for it, since the C compiler gcc can compile code to its virtual machine. However, at the moment, Java is the de-facto technology for making programs run inside a browser.
Note
We now provide a browser-side JavaScript port of Freecell Solver courtesy of the Emscripten compiler, which has proven useful for some people.
Java fell out of fashion as a technology for browser-side applets.
There are some other solvers that were written in Java from the ground up in case there's interest in that.
In the future, it may be possible to compile the Freecell Solver’s C code to Java instead of JavaScript.
As a result of all these points, we mark this task as done.
State Lookups
Currently, in order to find a suitable meta-move, Freecell Solver performs a large number of nested loops, each searching all the columns or freecells for suitable cards or card combinations. However, it is possible that one can speed up such queries by "compiling" the state and forming a lookup table, that will allow the elimination of some loops.
A prospective volunteer for implementing this should study the code and see where such lookups can be made, implement the state compilation (once for each inspected state), and convert the code to using them.
Note: This was implemented to a very limited extent in only three of the move functions in freecell.c
. (As determined by profiling) It should be implemented in other move functions as well, while possibly extending the functionality scope.
Multi-Threading
Freecell Solver can run several scans on the same states collection. However, it can only run a certain scan for a given number of iterations, suspend it with purely high-level mechanisms, and then run a different scan instead. Later on, the original scan can be resumed. However, it is still not possible to run two scans on the same state collection in two different threads simultaneously without risking the integrity of the data and the program as a whole.
The code-base foundation for thread-enabling is already in the code, based on the distinction between soft-threads that encompass a single scan, and hard-threads - a collection of soft-threads that share some resources. Every hard-thread can run only one of its soft-thread at the time, but several hard-threads would be able to run simultaneously, assuming suitable locking mechanisms are in place.
A scheme for Multi-threading Freecell Solver was proposed by Shlomi Fish, but the actual implementation of the locking was not implemented yet. To do so, one should write an abstraction of threading and locking mechanisms (fc_solve_thread_*
), which will either default to doing nothing, or to running the appropriate threading functions of any threading API (be it POSIX threads, the Win32 API, APR or whatever).
Making Freecell Solver thread-enabled is not high on my agenda, because few users have multi-processor machines that can somehow benefit from this scheme. Those with uni-processor machines are better off using several soft-threads within a single hard-thread that are arbitrated by the program.
Rejected: resource sharing multi-threading does not perform too well due to excessive locking. See this book for more info.
A Client/Server Multi-tasking Architecture
Yet another speculative feature that was inspired by a talk I had with Dave Goehrig in which he claimed multi-processing in Linux was more efficient than multi-threading. (a claim I saw elsewhere). I believe the Game AI model gives way to multi-threading better because all scans operating on the same states collection need access to all the states present in it. However, it is possible that a multi-processed model will still work better.
What would be done is that the parent process (the server) will hold the entire state collection and will spawn children process which each will take the responsibility of running a hard thread. The hard threads will query the parent process (through some Inter-Process Communication mechanism, probably an anonymous pipe) about the presence of states there. The server process will answer the queries one by one and will add relevant states to the client processes. Once one of them queries the empty state, it will terminate all the children processes, and reconstruct the graph from there.
This is much easier done on UNIXes or UNIX-like systems where multi-processing is much stronger than on Win32. (<rant />) It also may be worthwhile for each client process to hold a local cache of states, so it won't query the server excessively.
Again, this is something I'm planning to do, after I implement multi-threading, if I do it at all.
Rejected: for similar reasons.