In a message dated 11/19/01 4:19:50 AM Pacific Standard Time,
aettlinger_at_worldnet.att.net writes:
> Subj: DFS vs. A*
> I had been abysmally ignorant of the theory underlying this kind a
> game-solving. I knew the term DFS from the Don Woods software, but had no
> idea whether this represented one of a dozen possible approaches, or what.
> So it's very new to me that, evidently, there are two primary types of
> applicable strategy, A* or DFS. I'd never heard of A* previously, and I'd
> asked Shlomi if he could explain it, and he referred me to that website.
>
> So I'd like to ask you this. This is from curiosity I've had about
your
> solver, because I must admit that I have been very surprised at the speed
> you've reported. If you don't mind revealing this, is the reason for your
> high speed that you are using A* instead of DFS? Or do you have yet a
third
> approach? Or could one say that between A* and DFS, they are inherently
the
> only two possible types of approach?
I've long hoped this kind of discussion would appear in some freecell forum
somewhere.
There are two fundamental exhaustive searches: Depth-First (DFS) and
Breadth-First (BrFS).
BrFS is guaranteed to find the shortest solution because it examines the game
tree level by level, keeping all positions active. At the starting position
(level 0), all moves to level 1 are recorded. From there all moves to level
2, etc. When it finds a solution at level N, it already knows there was no
solution at level N-1, so the N-move solution is shortest. But this fills up
memory quickly, which makes BrFS impractical for most FC deals. Some
zero-freecell deals can be solved with BrFS because the moves are limited.
I've solved only one 4-freecell game with BrFS - 1941 - and I had to keep the
equivalent of fifteen million (yes, that's 15,000,000) of Woods' positions
active.
DFS' primary advantage is that only one branch of the game tree exists at a
time. saving much space. Woods' solver uses DFS, in which the next position
examined is always downward in the game tree toward the tip of a branch.
Woods has space and time problems because all branches are equally likely to
be explored, so memory fills up with the transposition table, bloated with
positions unlikely to be found in a solution.
A useful variation of DFS is Best-First Search (BFS). Instead of proceeding
down each branch of the game tree with equal probability, at each position a
judgement is made about the moves available from there. The move most likely
to lead to a solution is taken. Fish published his rules for these judgements
a few weeks ago.
I have strong doubts whether A* can be used economically with freecell.
Actually, I suspect that A* cannot be used at all because automoves cannot be
accurately anticipated.
My solver is fast because I've found a dozen ways to save space and time. The
first one was my automove rule "Raymond's Rule" which is bolder than MS' rule
but just as safe. When I worked that out in the summer of 1999, I began to
realize that I could write a quicker solver. Then I discovered that many
positions need not be recorded, and I was off! The two space-saving methods
I'm looking at now may make doable even the most-untractable two-freecell
games.
Bill Raymond
Bill Raymond
Received on Mon Nov 19 2001 - 10:34:25 IST