You already have two excellent replies from Shlomi Fish and Adrian
Ettlinger.
(I just noticed a reply from Bill Raymond pop up as I was completing my
reply.)
I'll just add a coupla personal notes.
As pointed out, "Method 1" is a DFS method that's (conceptually) the
easiest method to implement. However, it's been my experience that too
simplified of an implementation will often result in very long solution
searches that consume lots of time. It's very important that you have a
good algorithm for prioritizing moves as you move from one level to the
next. It's also important that you have a good algorithm for tracking
redundant paths so that you don't waste time on an equivalent path
that's already been rejected.
As pointed out, "Method 2" is a BFS (or BrFS) method that attempts to
track all moves from one level to the next. It requires storing a lot
more information and a very good algorithm for tracking equivalent
paths. Even so, the number of moves at each depth grows exponentially
and you're eventually forced to prune the tree of moves that are
expected to be unproductive. Here, you'll need a good pruning algorithm.
My current solver uses this method because it's the best way that I know
to look for (near-)optimal solutions. Note: the "(near-)" is included
because you could miss an optimal solution through pruning.
Your "off-topic" question is actually a very important topic if you're
using the DFS method. Without freecells, the complexity of a FreeCell
deal drops drastically. As Bill Raymond suggested, getting your solver
to handle solvable 8x0 deals is a great way to check your solver's
column-to-column logic, column-to-home logic, auto-move logic, and
redundant move logic. Once you feel that you can solve 8x0 deals
reasonably fast and effectively, then move on to the complexity of
implementing freecells. If you want them, Bill Raymond and I have
generated a list of the solvable 8x0 deals in the first 1M deals.
Once you implement freecells, then (IMHO) the most important thing to
implement is an algorithm for selecting which card will be moved to a
newly created empty column!!! The next most important thing is to
determine when to move a card to/from a freecell ... and from/to which
column. If you have a perfect column, then moving a card from a freecell
to it is probably a good idea unless there's a card on a non-perfect
column that can be moved to the same destination column. After analyzing
167,670 moves from 3,619 deals solved by my solver, there were only
three times that it moved a card off a perfect column of more than three
cards in length. Most of the other times, it was mimicking multi-card moves.
Once you've done all of the above, then implement multi-card moves.
Bottom Line: No one seems to have come up with the "perfect algorithm".
However, FreeCell Solver and PatSolve are way faster than my solver, so
they must be doing something really right!!! Their implementation into
FcPro26 make it a really nice was to play FreeCell as a game!!!
Good Luck, DAJ
HELSER ERIC JOSEPH wrote:
> For all you FCS veterans out there, which is the faster way to find a
> solution to a hand:
>
> Method 1: (What I'm doing) The program evaluates the solution one move
> at a time until it finds a legal move, then attempts to make another
> move. When no legal move can be made, the program steps back and
> continues searching for another legal move to make. This is VERY time
> consuming, but minimally taxing on the memory.
>
> Method 2: The program evaluates ALL possible "branches" of the tree of
> moves at once. It starts with one set of all possible moves on the
> table: table-table, table-freecell, freecell-table, table-home,
> freecell-home. If a move is not legal or not possible, that "branch"
> is pruned away. After all illegal moves are purged, all remaining
> branches extend second branches for ALL possible moves. Illegal moves
> are pruned away again. Repeat this until one branch provides a
> solution. This is extremely memory-intensive, but does it provide any
> quicker results?
>
> Second off-topic question: Is it a good idea to restrict a solver from
> moving a freecell card to an empty column? My program solved MS#1012
> in 44 moves (~600 move checks, 25 seconds) without being able to move
> anything from freecells to empty columns. When I disabled that rule,
> the program couldn't solve 1012 in a reasonable time. Weird...
Received on Mon Nov 24 2003 - 11:43:03 IST