Contents

• 1. Multi-Tasking
  • 1.1. Hard Threads and Soft Threads
  • 1.2. Generating the Best Meta Scan
    • 1.2.1. Naive Approach - Scan Switching
    • 1.2.2. More Sophisticated - Prelude
    • 1.2.3. Optimization Algorithm
• 2. Indirect Stack States Optimizations
  • 2.1. Copy on Write Stacks
  • 2.2. Compact Allocation using Memory Pools
  • 2.3. Result
• 3. Command Line Processing
  • 3.1. Generic Function for CL Processing
  • 3.2. --read-from-file
  • 3.3. Solver Presets
  • 3.4. Recycling Solver Instances
• 4. Freecell Pro Interoperability
  • 4.1. The Problem
  • 4.2. The Solution
• 5. To Parent Links
• 6. The Michael Mann "Fork"
• 7. Future Directions
  • 7.1. To Do
  • 7.2. My Involvement

Copyright

Copyrighted under the Creative Commons Attribution License version 1.0 or greater.

• You wanted it - you got it! Freecell Solver supports multi-tasking since version 2.4.0.
• Run more than one scan on the same states collection.
• My early attempt at introducing multi-tasking when working on MS DevStudio failed to produce a working code.
• The next attempt that was planned more thoroughly and executed using gvim on Linux succeeded with blazing colours.
• (and they claim IDEs are superior)

• 1.1. Hard Threads and Soft Threads
• 1.2. Generating the Best Meta Scan
  • 1.2.1. Naive Approach - Scan Switching
  • 1.2.2. More Sophisticated - Prelude
  • 1.2.3. Optimization Algorithm

• Freecell Solver distinguishes between two levels of tasks:
• 1. Soft Thread - a soft thread is one dedicated scan running on the state collection.
• 2. Hard Thread - a task that should be performed by one system thread with all the dedicated resources that should prevent collisions with other hard threads as much as possible.
• A hard thread switches between several soft threads.
• At the moment, hard threads can not be multi-threaded using the system threads, as no locking mechanisms are in place. But the distinction still exists in the code.

• Now assuming we can multi-task, how can we generate the best (time-wise) meta-scan that consists of several individual scans?

• 1.2.1. Naive Approach - Scan Switching
• 1.2.2. More Sophisticated - Prelude
• 1.2.3. Optimization Algorithm

• Do a circular switch between the scans, allocating a certain quota for each scan.
• Configurable from the command line.
• Such scans were constructed by hand, and gave relatively good results.

• Create a prelude to the scans, in which an initial sequence of scan IDs and their quotas are performed before the continuous circular process.
• The specified prelude can be very long.
• But how to construct such a (pseudo-)optimal prelude?

• I thought of the following greedy, (but not optimal) algorithm to create a pseudo-optimal prelude:
• First we record the number of iterations (= states scanned) it took the scans' to solve a given board for each of a large set of boards. (in our case the Microsoft 32,000).
• Then, we allocate a certain number of iterations, and assign this quota to the scan that solves the most boards within this quota.
• Repeat.
• The configurations generated by this algorithm yield very good performance.

• As you may recall, stacks were allocated in pointers to a common stack collection, instead of the entire contents one after the other.
• This scheme is called indirect stack states.
• In recent versions, it was optimized.

• 2.1. Copy on Write Stacks
• 2.2. Compact Allocation using Memory Pools
• 2.3. Result

• In older versions of FCS, when deriving a state, all the allocated stacks were first allocated to a temporary memory, then modified and then looked up or registered in the stack collection.
• Starting from version 2.6.x, a different, faster scheme was enacted:
• Every stack is marked with its own flag. Once modified, the stack is temporarily allocated and its flag set.
• The non-marked stacks are kept as they are, while the marked stacks are looked up in the stack collection.
• This is a variant of the Copy-on-Write (COW) technique.

• Indirect stacks were originally individually malloc'ed.
• This consumed a lot of overhead memory.
• In recent versions, they were compactly allocated, contiguously, out of a memory pool.

• The indirect stack states became slightly faster than the normal "compact states".
• Thus, they were made the default.

• The command line processing of Freecell Solver has seen some improvements in the versions since the first presentation.
• This section will describe some of the more interesting ones.

• 3.1. Generic Function for CL Processing
• 3.2. --read-from-file
• 3.3. Solver Presets
• 3.4. Recycling Solver Instances

• The command line processing used to occupy a large part of the main() function of Freecell Solver.
• Instead, recent versions of Freecell Solver designated a special function ( in the cmd_line.c module) to configure an instance according to the command line arguments that are passed to it.
• This enabled writing other programs which configure themselves according to this scheme. (as all they needed to do was call this function)
• It also allows for programs that use FCS and for its language bindings, to configure themselves using this one textual interface, instead of a multitude of separate configuration functions.

• The Freecell Solver command lines could get very long.
• To resolve this and allow for a more modular command line, a meta command line argument was created --read-from-file [SKIP],[FILENAME].
• This allowed reading arguments from a text file with a format similar to a Bourne Shell command.
• (The code that tokenizes this file resides in cl_chop.c and is quite hideous. Still it works and doesn't interfere with the rest of the program so I just keep it as it is.)

• In Freecell Solver 2.8.0, a presets feature was introduced.
• It records certain command lines in central configuration files, and allows the user to retrieve them by saying -l [PRESET].
• This way, fc-solve -l cool-jives is a configuration that is usually very fast, and stands for a 1,171 characters command line.

• Starting from Freecell Solver 2.6.0, it can recycle instances so that they will have the same configuration as before, but still would be a candidate for trying to solve another board.
• This involved quite a lot of delicate coding to make sure that everything works perfectly, as the initialization and freeing up of an FCS instance is very complex.

• 4.1. The Problem
• 4.2. The Solution

• Freecell Pro is a feature-rich Freecell implementation for Win32, that integrated its own solver (by Don Woods and further work by others).
• I wanted it to integrate Freecell Solver as well, so I was referred to its developer, Adrian Ettlinger.
• Ettlinger was happy to help me, and so we started working on integrating the two programs.
• After some code was written and about 100 E-mails were exchanged, a problem surfaced.

• Freecell Solver can move any number of cards as a sequence, and moves cards to the foundations when it sees fit.
• Freecell Pro tries to emulate Microsoft Freecell in its behaviour. Namely:
  
  1. Column-to-column moves were identified only by source and destination columns. (not the number of cards.)
  2. Cards that could be safely moved to the foundations, were indeed moved without an explicit move by the player or the solver.
• This behaviour is even present in the internals of Freecell Pro, which made adapting FC-Pro to use FCS even more difficult.
• This brought the following active discussion in the mailing-list.

• Adrian modified FC-Pro to accept sequence moves with a specified number of cards for moves to empty stacks only. (where the number of cards cannot be deduced from the destination.)
• I wrote an interface to process the Freecell Solver solution, and to generate moves that were acceptable to Freecell Pro.
• This involved playing the entire solution move by move, transferring cards to the foundations, and keeping track of such cards.
• This took about a 100 more E-mails between Adrian and I.

End Result

• Integration of Freecell Solver with Freecell Pro is now working, and the "Solver Evaluation Edition" of FC-Pro was released.
• All's well that ends well!

• In later versions of Freecell Solver, each state contains a pointer to its "parent state" - the first state from which it was discovered.
• I eventually realized I could add a move stack of moves that lead from the parent to it, thus enabling FCS to trace the solution of a state by collecting all the moves to the initial state.
• This resulted in shorter solutions, making the optimization scan almost completely unnecessary.

• At one point a certain man named Michael Mann submitted two patches to Freecell Solver, one of which I accepted.
• Then he explained his greater motivation:
• At one point he was interested to write a Freecell solver, but first decided to search if one existed. He found mine in a Google search.
• He saw in my to-do list that I wanted to convert it to Java, so he decided to privately convert it to C++ instead.
• He started at version 1.4, and as I released new versions he incorporated these changes into his C++ version, and so until version 2.2 of Freecell Solver.
• After he "came out of the closet" he submitted his C++ version (which was documented using doxygen), which I placed online for reference.
• This is the single most amazing thing that happened to me in my professional life as a programmer.

• This section will deal with what can possibly be implemented in Freecell Solver in the future.

• 7.1. To Do
• 7.2. My Involvement

• Incorporating Patsolve's logic.
• Thread-enabling (true system threads that can make use of SMP capabilities).
• Writing an automatic testing framework.
• Safety from failed memory allocations. Currently if a malloc/realloc call fails, it can crash the program.
• Converting to Java.
• Others: http://fc-solve.shlomifish.org/to-do.html

• I (= Shlomi Fish) have not seriously worked on Freecell Solver for a long time.
• I feel that it is already rather complete and feature-rich, and does not justify too much further work.
• While there are still some things that could possibly be done, I've lost interest (at least temporarily) in performing more work on the software.
• If someone shows he is interested on continuing the work on Freecell Solver instead, and that he is capable of making meaningful contributions, I'll gladly pass the baton to him or her.