Eric, your mailer does not cut long lines. Please configure it that it
would. (<sigh />
On Mon, 24 Nov 2003, 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.
>
This is called Depth-First Search (or DFS) in CS speak. It should not be
too time consuming for most hands.
> 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?
>
This is called Breadth-First Search (BrFS) in CS Speak. Not only it is
exteremely memory intensive but in Freecell it usually will take a long
time for a solution to be reached.
OK, here's the deal. Freecell Solver can theoretically be configured at
run-time to use either DFS, BrFS or Best-First-Search (BeFS - see below) scans.
In practice, the best heuristics that were found so far, involved
intermediately multi-tasking among several scans to produce a fast
meta-scan. If you read the Freecell Solver USAGE file and looked at the
presets in its directory, you should know how to implement similar things.
Just be warned that it will take a while and is way out of a scope of a
rudimentary or proof-of-concept solver.
Dr. Tom Holroyd's Patsolve used to use a mixture of BrFS and DFS, but now
uses a mixture of both as well as a priority queue scan. I don't fully
understand it, but it's also very fast. I started working on integrating
the functionality of Patsolve into Freecell Solver, but lost interest, at
least momentarily.
Danny A. Jones' solver is an either pure-BrFS one or such that involves a
lesser Breadth-First-Search. Both of them are usually substantially slower
than either Freecell Solver or Patsolve, but they produce optimal or
near-optimal results. (which was Jones' intention).
If you want to know what kind of heuristics Bill Raymond's solver uses,
ask him and he'll tell you if he'd like. As it is, the solver was not
released to the public yet in source or binary form, but based on Bill's
description it should be quite sophisticated.
Other possible heuristics: for this you can consult a good Games AI book.
But off the top of my head:
1. Best-First-Search: first check the states that best first a certain
scalar criteria. Implemented using a priority queue.
2. A* (pronounced A-star) - a sort of hybrid between BeFS and DFS. Justin
Heyes Jones has a good tutorial on it on his homepage. Don't ask me how to
implement it for Freecell, albeit it's possible that the new version of
FCS has implemented it in a way.
Except for what my experience in Freecell Solver (and to a lesser extent
LM-Solve) taught me, I'm not really a games AI expert, as I'm mostly
unknowledgable in the theory and research conducted so far. If you wish to
write a Freecell solver that works, in the shortest time, then my
suggestion to you is to use atomic moves and DFS. This is usually enough
to solve most games quickly.
If you want to somehow build a more sophisticated solver than what is
present at the moment, then it would probably be a better idea to start
from an existing one. The existing solvers are complex from a reason, and
they incoroporate a lot of wisdom that was acquired throughout their
development. Freecell Solver still has room for some improvement, and I
could make use of some clueful compotent contributors.
> 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...
>
First of all your questions are not off-topic. They are right on-topic and
that's why this mailing list was formed in the first place.
I can find several possible explanations:
1. Do you keep track of all the possible encountered states?
2. Do you keep track of states with the same columns only with a different
order?
You should do both. Other than that, I think that logically there is no
reason to move a card from a freecell to an empty stack, unless you want
to put some cards above it. Pruning it without resorting to meta-moves is
an entirely different issue, which I cannot really answer right now.
Regards,
Shlomi Fish
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
An apple a day will keep a doctor away. Two apples a day will keep two
doctors away.
Falk Fish
Received on Mon Nov 24 2003 - 03:17:48 IST