Loading ...
Sorry, an error occurred while loading the content.

RE: hinting

Expand Messages
  • Tom Holroyd
    ... Actually patsolve doesn t use pure BFS since that suffers from exponential blowup. The hybrid prioritized BFS/DFS strategy doesn t always find the
    Message 1 of 9 , Feb 15, 2001
    View Source
    • 0 Attachment
      > > 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...
    • Shlomi Fish
      ... 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 2 of 9 , Feb 15, 2001
      View Source
      • 0 Attachment
        On Thu, 15 Feb 2001, Chen Shapira wrote:

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

        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.

        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.
      Your message has been successfully submitted and would be delivered to recipients shortly.