- View Source
> > Since BFS by definition finds the shortest path between the

Actually 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... - View 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

complete solution.

Besides, that paragraph is about Graph Theory, not really about practice.

Regards,

Shlomi Fish

>

----------------------------------------------------------------------

> To unsubscribe from this group, send an email to:

> fc-solve-discuss-unsubscribe@yahoogroups.com

>

>

>

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.