Subject: Summary of FCS Lecture - Rev. 2

From: Shlomi Fish <[email-masked]>
Date: Thu, 1 Nov 2001 15:57:02 +0200 (IST)

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        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

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

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 1 Nov 2001 16:24:41 +0200

> * 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
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Disclaimer: The opinions expressed above
http://nadav.harel.org.il           |are not my own.

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 1 Nov 2001 19:56:57 +0200 (IST)

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

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

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

> 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

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

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