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

Fwd: Re: more on simple solving algorithms

Expand Messages
  • Shlomi Fish
    This is a forward of an old email sent by Michael Mann (creator of the C++/doxygen spin-off of Freecell Solver - http://fc-solve.berlios.de/michael_mann/ )
    Message 1 of 1 , May 30, 2009
    View Source
    • 0 Attachment
      This is a forward of an old email sent by Michael Mann (creator of the
      C++/doxygen spin-off of Freecell Solver -
      http://fc-solve.berlios.de/michael_mann/ ) which gives some information about
      an extra move he had created for the Simple Simon solver.

      It is forwarded here with his permissions.

      Regards,

      Shlomi Fish

      ---------- Forwarded Message ----------

      Subject: Re: more on simple solving algorithms
      Date: Thursday 31 October 2002
      From: Michael Mann <mmann78@...>
      To: shlomif@...

      Sorry about replying to the wrong email address. It was the email
      address I saw from your last response and I thought it would be better
      to use it. I was mistaken.

      As far as Public Domain, my theory is your work/code was free, so should
      mine. Place it under Public Domain. This also goes for any more work I
      submit to you.
      Actually, my "solving algorithm" for each board was try a-star for 10000
      iterations, if it can't be solved, try dfs for 10000 iterations, and if
      that can't be solved, try a-star again with 500000 iterations. I
      probably could have used resume, but I would restart the board from
      scratch. I picked this algorithm up from trying to solve freecell
      boards. I noticed that in boards where dfs had a high number of
      iterations, a-star sometimes didn't and vice versa. The reason behind
      it is probably has something to do with dfs and a-star having different
      weights (only in dfs you can't change them except by changing the test
      order).
      I first tried BFS with freecell without a iteration limit and didn't get
      very far. It ate up a lot of memory and didn't get really far (I would
      run out of virtual memory only to find it only got about 8/9 deep). I
      thought it may be more useful for freecell boards in the middle of a
      game, or some of the other card games. I haven't done much with
      soft-dfs, but I'll look into it.
      The difference between
      freecell_solver_sfs_simple_simon_move_whole_stack_sequence_to_false_parent
      and freecell_solver_sfs_simple_simon_move_sequence_to_false_parent
      is that the old test requires the entire stack to be a sequence. The
      new test will move any sequence, whether it takes up the whole stack or
      not. This is why I thought move_false_parent could replace
      move_whole_s_s_to_false_parent, but in the little testing I did, boards
      needed to go through significantly more iterations. I think the main
      reason more boards were solved is that it will move single cards to
      their false parent. This is why I started creating the test. I saw a
      few boards that only went through a few iterations, and in looking at
      it, I saw moves it could do, but didn't, mostly centered around moving a
      single card to its false parent.
      You used "suit" and "card_num" to save the suit and card number of a
      particular card on the stack. Why not just represent it as a whole
      card? In compact and indirect states, it will only take up a char of
      space. I also think that amount of work the code needs to get a suit
      and card number (finding the suit/card within the bits of a char) isn't
      outwieghted by the number of times you copy a new cards to save. Look
      for "next_card" and "saved_card" in the code. These are the variables
      that I replaced "suit" and "card_num" with.
      What generated you change log before? It looked to me like it was
      manually entered.

      I'll look into the bug and get back to you.

      Mike



      -------------------------------------------------------
      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      http://www.shlomifish.org/humour/ways_to_do_it.html

      God gave us two eyes and ten fingers so we will type five times as much as we
      read.
    Your message has been successfully submitted and would be delivered to recipients shortly.