... Actually patsolve doesn t use pure BFS since that suffers from exponential blowup. The hybrid prioritized BFS/DFS strategy doesn t always find theMessage 1 of 9 , Feb 15, 2001View Source
> > Since BFS by definition finds the shortest path between theActually patsolve doesn't use pure BFS since that suffers from exponential
> > source and the
> > destination...
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...
... Then, in that case the solver will give a completely different solution. If you follow the hints all along you will eventually get to a complete solution.Message 1 of 9 , Feb 15, 2001View SourceOn Thu, 15 Feb 2001, Chen Shapira wrote:
> >Then, in that case the solver will give a completely different solution.
> > Actually, when using BFS it can be proved that such thing is
> > not possible.
> > Since BFS by definition finds the shortest path between the
> > source and the
> > destination than if a BFS on node A suggested a movement to
> > node B and if
> > the BFS on node B suggested a move to node A, then we could
> > have saved two
> > moves by staying at B, which contradicts the definition of BFS.
> But he talked about a case when a user moves NOT according to the hint.
If you follow the hints all along you will eventually get to a
Besides, that paragraph is about Graph Theory, not really about practice.
> To unsubscribe from this group, send an email to:
Shlomi Fish shlomif@...
Home Page: http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif@...
The prefix "God Said" has the extraordinary logical property of
converting any statement that follows it into a true one.