On Tue, 13 Feb 2001, Shlomi Fish wrote:
> > What is your current weight function? I still think that the multi-move
> > approach doesn't go well with A* speed wise. You're right that this
> > helps
> > reducing memory usage, but it also widens your search tree
> >
>
> Hmmm. Well you can try taking Tom's solver and implement A* in it. It
> already implements DFS and BFS. I can also program atomic moves tests.
Speaking of that:
http://members.tripod.com/professor_tom/archives/patsolve-2.2.tgz
(It's a tripod page so you have to left click on the link to get to a
"real" download page -- what the heck it's free).
Note that patsolve only solves Freecell and Seahaven Towers variants, so
it's not as versatile as Freecell Solver. I'm not familiar with the other
games so I don't know if the optimizations I use are useful. Other
differences:
Prioritized queue BFS. I don't know much about A* and so on, but since
BFS grows too quickly, the positions are prioritized via an empirically
determined weighting function and queued, so that less likely positions
can be skipped (unless there are no other choices). That and some simple
prunes takes care of most of the exponential blowup, though several
unsolvable games can still take many megabytes of RAM. Note that since
it's not pure BFS, the solutions are not guaranteed to be optimal, though
I try to make them as short as possible. One other optimization allows
occasional DFS branches (if the number of moves is small or if we can move
a card out, basically a greedy algorithm).
Atomic moves. My favorite patience doesn't allow moving stacks, and
anyway this just seemed simpler to me.
No false negatives. If patsolve says it's unsolvable, it is. Early
versions of Freecell Solver didn't have this property, and Shlomi told me
it wasn't a design goal; recent versions seem not to produce false
negatives, however. This was important to me since I basically only
use the solver to answer the question "is this game solvable?" If it
is I solve it myself. :-)
Dr. Tom Holroyd
"I am, as I said, inspired by the biological phenomena in which
chemical forces are used in repetitious fashion to produce all
kinds of weird effects (one of which is the author)."
-- Richard Feynman, _There's Plenty of Room at the Bottom_
Received on Tue Feb 13 2001 - 16:48:17 IST