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

Summary of FCS Lecture - Rev. 2

Expand Messages
  • Shlomi Fish
    Voila. More detailed now in some parts. The other parts will be written in time. Regards, Shlomi Fish ... * There are 8 stacks, 4 freecells, and 4 foundations.
    Message 1 of 3 , Nov 1, 2001
    • 0 Attachment
      Voila. More detailed now in some parts. The other parts will be written in
      time.

      Regards,

      Shlomi Fish

      Freecell's Rules:
      -----------------

      * There are 8 stacks, 4 freecells, and 4 foundations.

      * An atomic move consists of:
      - moving a card from a stack to a freecell.
      - moving a card from a freecell to a parent card on a stack.
      - moving a card from the top of a stack on top of a parent card on a
      different stack
      - moving a card from the top of a stack or from a freecell to the
      foundation.

      * A parent card is such that its rank is higher by 1 and it is of a different
      colour.

      * The foundations build by suit from Ace to King.

      * Each freecell can hold one card.

      Strategies:
      -----------

      * A sequence of more than one card can be moved by moving the top cards to
      the freecells or to unoccupied stacks.

      * Sometimes, it is useful to move cards to the freecells, so the card
      below them can serve as a basis for a sequence.

      The Freecell Solver 0.2 Architecture:
      -------------------------------------

      * A DFS scan:

      Solve-State(state, prev_states, ret)
      if (state == empty_state)
      Push(ret, state)
      return SOLVED
      for each move possible on state
      new_state <- state
      apply(new_state, move)
      if (new_state in prev_states)
      ; Do nothing
      else
      add new_state to prev_states
      if (Solve-State(new_state, prev_states, ret) == SOLVED)
      Push(ret, state)
      return SOLVED
      return UNSOLVED

      Freecell-Solver(init_state)
      if (Solve-State(init_state, Null, ret) == SOLVED)
      print "State was solved"
      while (state <- Pop(ret))
      print state
      else
      print "I could not solve this board";


      * Several tests to get to subsequent moves - give some examples:
      I called them "multi-move" to indicate they may include one or more
      moves or "supermoves". By coding them I tried to emulate the kind of
      moves a human player would try to do.

      Examples:
      ---------

      * Put top stacks cards in the foundations.
      * Put Freecell cards in the foundations.
      * Put non-top stack cards in the foundations. (by moving cards above them
      to freecells or vacant stacks).
      * Move stack cards to different stacks.
      * Move sequences of cards onto free stacks.
      * etc.

      I later improved some of these moves and added an extra one.

      Due to their multi-moves heuristic nature, it is possible that some boards
      are solveable, yet cannot be solved by FCS.

      * Once the program finds a solution it outputs the intermediate boards to
      the screen.

      * Each state was represented as a relatively large data structure containing
      other data structures.
      - A card was { short, short}
      - A stack was { int, card[] },
      - A state was { stack[] }.

      * The State collection was implemented as a sorted vector of whole state data
      structures.
      - It had a sort margin, so not every new element would require moving
      many states aside.
      - After several elements were collected the array and its sort margin
      were qsort()ed.

      The State Collection Representation Improvements:
      -------------------------------------------------

      B-search based merge to add the sort margin instead of qsort:
      -------------------------------------------------------------

      * The sort margin is kept outside the main array.

      * It is added to the main array by using a binary search-based merge.

      - The reason why it was preferred over a normal linear merge
      was because there are usually much more elements in the main
      array so a lot of time would be spent on comparisons.

      * The merge was done from end to start, so there was not any need in
      allocating an extra space.

      Pointers to structs instead of a vector of whole structs:
      ---------------------------------------------------------

      * I converted the vector to be a vector of pointer to structs, instead
      of vector of whole structs.

      * There was a great speed improvements, because only pointers were
      manipulated and not entire structs, whose movement in memory requires
      a lot of time.

      A balanced binary tree:
      -----------------------

      * I don't really know how to program my own balanced binary tree
      implementation, but I found some on the Net:

      1. libavl - contains implementations of AVL and Red-Black trees.
      2. libredblack - contains an implementation of a Red-Black tree.
      3. glib - contains an implementation of a balanced binary tree.

      There are others, but I decided to stick to those three.

      * By using a balanced binary tree I managed to increase the brute speed
      by %33. (and the net speed times 2 or so).

      A hash table:
      -------------


      - Using a 4-byte wide XOR as the hash function.
      - Using MD5 as the hash function.

      The State Representation:
      -------------------------

      * Chars and half-chars instead of shorts and ints.

      * Pointers to stacks instead of a vector of stacks.
      - A cache of stacks.

      * Remember the original stack and freecell locations using the
      "Indexes out of Bounds of Main Data Structure"<tm> - anti-patent
      pending technology.

      Abstracting the Game:
      ---------------------

      * Variable number of Freecells and Stacks.
      * The game play options:
      - Empty stacks filled by any card/kings only/none,
      - Sequences are built by suit/alternate colour/rank
      the is_parent_card() macro.
      - Unlimited sequence move.

      * Presets: setting those settings automatically by selecting a preset.

      Scans:
      ------

      * The original Hard-DFS scan.

      * A*

      * Soft-DFS rev. 1.

      * Soft-DFS rev. 2.

      * The BFS optimization scan.

      Move Stacks:
      ------------

      * In the beginning, the user had to deduce what had happened between two
      subsequent states.

      * That was:
      A. Not comfortable.
      B. Even harder for a Freecell implementation to do on its own.

      * I created the concept of move stacks, which each test loaded with the moves
      that were it performed.

      * Those stacks were later collected into one stack, to get the total move
      stack from the initial board to the final solution.



      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      If:
      1. A is A
      2. A is not not-A
      does it imply that
      1. B is B
      2. B is not not-B
    • Nadav Har'El
      ... I think for an ignorant like me (who played various versions of Solitaire but never heard of freecell), you ll need to be a little more specific (maybe
      Message 2 of 3 , Nov 1, 2001
      • 0 Attachment
        On Thu, Nov 01, 2001, Shlomi Fish wrote about "[hackers-il] Summary of FCS Lecture - Rev. 2":
        > * There are 8 stacks, 4 freecells, and 4 foundations.
        >
        > * An atomic move consists of:
        > - moving a card from a stack to a freecell.
        > - moving a card from a freecell to a parent card on a stack.
        > - moving a card from the top of a stack on top of a parent card on a
        > different stack
        > - moving a card from the top of a stack or from a freecell to the
        > foundation.
        >
        > * A parent card is such that its rank is higher by 1 and it is of a different
        > colour.
        >
        > * The foundations build by suit from Ace to King.
        >
        > * Each freecell can hold one card.

        I think for an ignorant like me (who played various versions of Solitaire but
        never heard of freecell), you'll need to be a little more specific (maybe
        it's easier to do it interactively than via email - you can even play a demo
        on the computer, if you use one in the presentation :)), because from this
        explanation I had to do a lot of deduction and guessing to figure out how
        this game is played.

        What is a "stack" (I guess a stack of cards)? How many cards does it start
        with (after all, you can't divide evenly 52 cards into 8 stacks)? From how
        many decks of cards (I guess one 52-card deck)? are the cards in the stack
        visible to the player or not (or only the topmost card is visible)? Do
        "freecells" and "foundations" start empty (I'd guess yes)?

        The visibility question is obviously very important, because it (I think)
        completely changes your ability to solve the problem (if only the topmost
        card is visible on every stack, you can't walk the tree of all possibilties,
        and need to make guesses that you can't undo, and come up with a probabilistic
        solution, e.g., an algorithm which only solves 20% of the games). I think,
        by the way, that these probabilistic and invisibility issues are what make
        a solitaire game fun and interesting, rather than a very hard riddle.

        Please define "parent card" before you first use it.

        What is the goal of the game? My guess: to build 4 piles, each of a different
        suite, from ace to king, and I guess you called these the "foundations"?

        Is there no additional large pile of cards like I know from other solitare
        games - just the "stacks" that start off with all the cards?

        --
        Nadav Har'El | Thursday, Nov 1 2001, 15 Heshvan 5762
        nyh@... |-----------------------------------------
        Phone: +972-53-245868, ICQ 13349191 |Disclaimer: The opinions expressed above
        http://nadav.harel.org.il |are not my own.
      • Shlomi Fish
        ... At the beginning of the game yes, but Freecell Solver was adapted to solve boards in the midst of play. ... In Freecell all cards are visible at the
        Message 3 of 3 , Nov 1, 2001
        • 0 Attachment
          On Thu, 1 Nov 2001, Nadav Har'El wrote:

          > On Thu, Nov 01, 2001, Shlomi Fish wrote about "[hackers-il] Summary of FCS Lecture - Rev. 2":
          > > * There are 8 stacks, 4 freecells, and 4 foundations.
          > >
          > > * An atomic move consists of:
          > > - moving a card from a stack to a freecell.
          > > - moving a card from a freecell to a parent card on a stack.
          > > - moving a card from the top of a stack on top of a parent card on a
          > > different stack
          > > - moving a card from the top of a stack or from a freecell to the
          > > foundation.
          > >
          > > * A parent card is such that its rank is higher by 1 and it is of a different
          > > colour.
          > >
          > > * The foundations build by suit from Ace to King.
          > >
          > > * Each freecell can hold one card.
          >
          > I think for an ignorant like me (who played various versions of Solitaire but
          > never heard of freecell), you'll need to be a little more specific (maybe
          > it's easier to do it interactively than via email - you can even play a demo
          > on the computer, if you use one in the presentation :)), because from this
          > explanation I had to do a lot of deduction and guessing to figure out how
          > this game is played.
          >
          > What is a "stack" (I guess a stack of cards)? How many cards does it start
          > with (after all, you can't divide evenly 52 cards into 8 stacks)? From how
          > many decks of cards (I guess one 52-card deck)? are the cards in the stack
          > visible to the player or not (or only the topmost card is visible)? Do
          > "freecells" and "foundations" start empty (I'd guess yes)?
          >

          At the beginning of the game yes, but Freecell Solver was adapted to solve
          boards in the midst of play.

          > The visibility question is obviously very important, because it (I think)
          > completely changes your ability to solve the problem (if only the topmost
          > card is visible on every stack, you can't walk the tree of all possibilties,
          > and need to make guesses that you can't undo, and come up with a probabilistic
          > solution, e.g., an algorithm which only solves 20% of the games). I think,
          > by the way, that these probabilistic and invisibility issues are what make
          > a solitaire game fun and interesting, rather than a very hard riddle.
          >

          In Freecell all cards are visible at the beginning of play. In any case, I
          don't find the fact that all cards are revealed in Freecell, to lessen its
          fun factor.

          > Please define "parent card" before you first use it.
          >
          > What is the goal of the game? My guess: to build 4 piles, each of a different
          > suite, from ace to king, and I guess you called these the "foundations"?
          >

          There are 4 special piles called foundations, to which all the cards need
          to be moved. (from ace to king).

          > Is there no additional large pile of cards like I know from other solitare
          > games - just the "stacks" that start off with all the cards?
          >

          There is no Talon in Freecell, because all the cards are dealt to the
          piles. (I decided to call those piles "stacks" because they behave much
          like programming stacks).

          I guess I'll have to refine my description a bit...

          Regards,

          Shlomi Fish

          > --
          > Nadav Har'El | Thursday, Nov 1 2001, 15 Heshvan 5762
          > nyh@... |-----------------------------------------
          > Phone: +972-53-245868, ICQ 13349191 |Disclaimer: The opinions expressed above
          > http://nadav.harel.org.il |are not my own.
          >
          >
          > To unsubscribe from this group, send an email to:
          > hackers-il-unsubscribe@egroups.com
          >
          >
          >
          > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
          >
          >



          ----------------------------------------------------------------------
          Shlomi Fish shlomif@...
          Home Page: http://t2.technion.ac.il/~shlomif/
          Home E-mail: shlomif@...

          If:
          1. A is A
          2. A is not not-A
          does it imply that
          1. B is B
          2. B is not not-B
        Your message has been successfully submitted and would be delivered to recipients shortly.