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

Re: [hackers-il] FCS Lecture Summary - Finalized (Rev. 4)

Expand Messages
  • mulix
    ... this is an interesting point. did you consider to there may be a brute force method which might be able to solve all boards? is such a brute force method
    Message 1 of 3 , Nov 3, 2001
    • 0 Attachment
      On Sat, 3 Nov 2001, Shlomi Fish wrote:

      >
      > Enjoy, and flame away!
      >
      > Regards,
      >
      > Shlomi Fish
      >
      > Freecell's Rules:
      > -----------------
      >
      > * There are 8 stacks of cards, 4 freecells, and 4 foundations. The game
      > is played with one deck.
      >
      > * At the beginning of play, the cards are dealt to the stacks (4*7+4*6).
      > The faces of all the cards are visible at the beginning of play.
      >
      > * A freecell can hold one _single_ card.
      >
      > * The foundations are built from ace to king and the object of the
      > game is to move all the cards to the foundations.
      >
      > * A card can be placed on top of a card that is of the opposite colour,
      > and is higher in rank by 1, assuming that the latter is at the top of a
      > stack.
      >
      > * An empty stack may be filled with any card.
      >
      > * 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
      > foundations.
      >
      > Strategies:
      > -----------
      >
      > * A sequence of more than one card can be moved by moving the top cards to
      > the freecells or to unoccupied stacks. The later is commonly called a
      > "supermove"
      >
      > * 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.

      this is an interesting point. did you consider to there may be a brute
      force method which might be able to solve all boards? is such a brute
      force method feasible, in terms or time/space complexity?

      > * 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 no 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:
      > -------------
      >
      > Description: What is a Hash Table?
      > ----------------------------------
      >
      > * A hash table is a vector of linked lists. Each linked list contains
      > a set of keys (or key-value pairs).

      that's not what a hash table is. that's what an *implementation* of a
      hash table might look like.

      you might be interested in checking out the lecture notes for the
      technion's cs department's 'data structures one' class. they have very
      good lectures on avl, b trees and hash tables. (note - last year they
      also had quite a few small but annoyiing mistakes in the slides - i hope
      they are better this year). the slides are here:
      http://www.cs.technion.ac.il/~dang/courseDS/

      > * The index of the list in which the key is placed is determined by
      > a hash function. Usually, the hash function generates an integer
      > in a very large range, and the index is taken as its modulo with the
      > number of elements in the hash table.

      again, that's one specific implementation, not necessarily the best.

      > Rehashing:
      > ----------
      >
      > Sometimes, when a hash becomes two crowded, the number of elements
      > in it is increased and all of its existing elements are placed in
      > their new place.
      >
      >
      > * I first tried using glib's hash implementation with a 4-byte wide XOR as
      > the hash function. This generated very awful results.
      >
      > * Then I tried using the MD5 hash function, and got excellent results,
      > similar to what I encountered when using a balanced binary tree.
      >
      > * I coded my own stripped-down hash implementation in my attempt to figure
      > out what went wrong with using a hash. It turned out to be a bit faster
      > than glib's hash.

      this is not suprising: you replaced a general version with a private
      version tailored for your needs.

      >
      > Hash Optimizations:
      > -------------------
      >
      > * Storing the hash values along with the keys. That way, the hash
      > values can be first compared before comparing the entire keys.

      that's a very nice trick, but why did you need to store the hash value
      explicitly? isn't the hash value the index of the cell in the array? (i
      suspect you use 'hash value' here to refer to the very large number,
      before you did the modulu, correct?)

      > * Moving elements that were hit to the start of their chains.

      why?

      > * When re-hashing, using the same malloc'ed elements, only re-linking
      > them to their new siblings.

      of course.

      you might wish to explain in a few words how you *profiled* your code,
      before optimizing it (i hope you profiled it...)

      [snipped the rest as i didnt have any comments]

      --
      mulix

      http://www.pointer.co.il/~mulix/
      http://syscalltrack.sf.net/
    • Shlomi Fish
      ... Several people wrote atomic moves-based Freecell solvers and they do not work too bad. I decided to use multi-moves in the first place, because I thought
      Message 2 of 3 , Nov 3, 2001
      • 0 Attachment
        On Sat, 3 Nov 2001, mulix wrote:

        > > 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.
        >
        > this is an interesting point. did you consider to there may be a brute
        > force method which might be able to solve all boards? is such a brute
        > force method feasible, in terms or time/space complexity?
        >

        Several people wrote atomic moves-based Freecell solvers and they do not
        work too bad. I decided to use multi-moves in the first place, because I
        thought they would yield better results.

        > > The State Collection Representation Improvements:
        > > -------------------------------------------------
        > >
        [ Snipped the B-search, sort-margin and balanced binary tree stuff ]
        > > A Hash Table:
        > > -------------
        > >
        > > Description: What is a Hash Table?
        > > ----------------------------------
        > >
        > > * A hash table is a vector of linked lists. Each linked list contains
        > > a set of keys (or key-value pairs).
        >
        > that's not what a hash table is. that's what an *implementation* of a
        > hash table might look like.
        >

        Well, AFAIK a hash is an implementation of the dictionary abstract data
        type (ADT). Naturally, hashes comes in many forms and sizes. I realize it
        is also possible to use open addressing for a hash. However, I do not want
        to cover the entire theory of hashing in the lecture.

        > you might be interested in checking out the lecture notes for the
        > technion's cs department's 'data structures one' class. they have very
        > good lectures on avl, b trees and hash tables. (note - last year they
        > also had quite a few small but annoyiing mistakes in the slides - i hope
        > they are better this year). the slides are here:
        > http://www.cs.technion.ac.il/~dang/courseDS/
        >

        I took the EE equivalent course (or at least half of the two equivalent EE
        courses).

        > > * The index of the list in which the key is placed is determined by
        > > a hash function. Usually, the hash function generates an integer
        > > in a very large range, and the index is taken as its modulo with the
        > > number of elements in the hash table.
        >
        > again, that's one specific implementation, not necessarily the best.
        >

        I'm not saying it is.

        > > Rehashing:
        > > ----------
        > >
        > > Sometimes, when a hash becomes two crowded, the number of elements
        > > in it is increased and all of its existing elements are placed in
        > > their new place.
        > >
        > >
        > > * I first tried using glib's hash implementation with a 4-byte wide XOR as
        > > the hash function. This generated very awful results.
        > >
        > > * Then I tried using the MD5 hash function, and got excellent results,
        > > similar to what I encountered when using a balanced binary tree.
        > >
        > > * I coded my own stripped-down hash implementation in my attempt to figure
        > > out what went wrong with using a hash. It turned out to be a bit faster
        > > than glib's hash.
        >
        > this is not suprising: you replaced a general version with a private
        > version tailored for your needs.
        >

        Perhaps, but it is also possible mine is written better.

        > >
        > > Hash Optimizations:
        > > -------------------
        > >
        > > * Storing the hash values along with the keys. That way, the hash
        > > values can be first compared before comparing the entire keys.
        >
        > that's a very nice trick, but why did you need to store the hash value
        > explicitly? isn't the hash value the index of the cell in the array? (i
        > suspect you use 'hash value' here to refer to the very large number,
        > before you did the modulu, correct?)
        >

        That's right. The hash value is the value before the modulo is taken.

        > > * Moving elements that were hit to the start of their chains.
        >
        > why?
        >

        My assumption is that elements that were hit a lot are likely to be hit
        again often. That's why I wish them to be closer to the start of the list
        as possible so that redunant images would be eliminated soon.

        > > * When re-hashing, using the same malloc'ed elements, only re-linking
        > > them to their new siblings.
        >
        > of course.
        >
        > you might wish to explain in a few words how you *profiled* your code,
        > before optimizing it (i hope you profiled it...)
        >

        Actually, many times I implemented such optimizations out of necessity, or
        because I thought they would generate good results. Then, after I compared
        them with the previous results, I realized they were better in time or in
        memory.

        Regards,

        Shlomi Fish

        > [snipped the rest as i didnt have any comments]
        >
        > --
        > mulix
        >
        > http://www.pointer.co.il/~mulix/
        > http://syscalltrack.sf.net/
        >
        >
        >
        >
        > 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.