> > Since BFS by definition finds the shortest path between the
> > source and the
> > destination...
Actually patsolve doesn't use pure BFS since that suffers from exponential
blowup. The hybrid prioritized BFS/DFS strategy doesn't always find the
shortest solution, and it (empirically) is very sensitive to things like
pile order and so on.
I think you just have to keep a "current solution" that you regenerate
when the user deviates from it. One problem I just realized with that is
that it's quite possible for the user to get into a position that is
unsolvable, and the only hint is "undo". Maybe that's not such a problem,
since unsolvable positions are usually detected pretty quickly, especially
mid-game, and then you just suggest "undo" as the hint, which takes you
back to some precomputed solution... You just have to keep restarting the
solver when the user makes an unexpected move, which for patsolve means
rerunning the program (it was never designed to be restartable, because of
the way the position hash-store works).
A really clever hinter would not only generate "the" solution, but also
side solutions, so that the "expected move" would be two or more instead
of just one. But it starts to become a completely different algorithm,
since the solvers need to do a "self-avoiding walk" of the game tree,
which precludes consideration of most side solutions...
Received on Thu Feb 15 2001 - 02:11:00 IST