The following is a premature release of information on my latest FreeCell project. It involves a pruning operation that's only partially implemented in my general solver (because it's easier to implement there). Eventually, I hope to implement it in my BFS solver.
Permutations for two disjoint moves can be: move <1> followed by move <2>, or move <2> followed by move <1>. However, the results are the same in FreeCell. Instead, why not reorganize the logic to: move <1> followed by move <2>, or move <2> and block move <1> thereafter.
Consider the following scenario:
You've reached a point where you have two choices for moving a card from column-to-occupied_column; e.g. 8H->9C or 3S->4D. You choose 8H->9C and proceed. You subsequently include 3S->4D while trying to reach a solution to the game. However, you aren't successful and must backtrack to the place where you originally chose 8H->9C. At this point, you choose 3S->4D and proceed. Do you ever need to include 8H->9C among your subsequent moves???
I've been working under the assumption that the answer to the above question is "No" -- unless the 9C is subsequently moved. So far, I've implemented the logic in my column-to-occupied_column routine (above scenario) and in my freecell-to-occupied_column routine. I've seen a modest reduction in the number of layouts examined by my solver. Next, I plan to include this pruning operation in my multi-card column-to-occupied_column routine. Hopefully, I'll see additional reductions in the layouts examined.
Unfortunately, I have other routines where I'm (currently) unable to justify implementing this pruning operation.
History:
Yuri Bortnik created the freecellgamesolutions.com website, which contains very short solutions for the solvable first 1M games. Last Spring, he and I began discussions on short vs. very short vs. minimal-length solutions. We decided to tackle the first 1000 games and see how far each could proceed towards finding minimal-length solutions. My efforts produced an average of 34.28 moves/deal, but weren't minimal-length overall. Except for a few games outside his solver's range, Yuri Bortnik produced minimal-length solutions with an average of 33.01 moves/deal. The execution times for our efforts were abominable.
Recently, I decided to test a new (to me) pruning operation. I'm hoping that it will finally let me accurately determine minimal-length solutions to most games.
Received on Fri Oct 25 2013 - 12:07:23 IDT