## Summary of FCS Lecture - Rev. 2

Expand Messages
• 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
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:
-------------------------------------------------

-------------------------------------------------------------

* 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 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
• ... 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
• ... 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@...