Subject: Summary of my "Freecell Solver" lecture

From: Shlomi Fish <[email-masked]>
Date: Wed, 31 Oct 2001 19:24:56 +0200 (IST)

This is a summary for a lecture I'm planning to give on the changes and
re-factoring I made in Freecell Solver.

Note that it still only contains mostly bullets, and will be filled with
more info as time goes by. I depreciated a previos summary on which I
focused on too many minor points and organized the material chronlogically
instead of logically.

In any case, comments, suggestions, flames are welcome. Please post them
to the list.

Regards,

	Shlomi Fish

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

* A DFS scan - give pseudo-code.

* Several tests to get to subsequent moves - give some examples.

* Outputs the intermediate boards to the screen.

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

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

* Pointers to structs instead of a vector of whole structs.

* A balanced binary tree.

* 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: guy keren <[email-masked]>
Date: Thu, 1 Nov 2001 10:48:50 +0200 (EET)

> In any case, comments, suggestions, flames are welcome. Please post them

i'd like to make 2 general points.

1. you assume the listeners know what 'freecel' is and what 'freecel
   solving' is about. you should either explain that, or prepare some
   material that people should read before the lecture.

2. you seem to assume familiarity with a former version of freecel solver,
   which is most likely not the case. not sure how you should deal with
   that. perhaps avoid the 'comparison part' all-together, and just
   describe what you got now, explaining architectural decisions along the
   way (you already seem to do that partially).

3. it seems too long. note sure if/how this could be broken into more then
   a single lecture perhaps you should chose specific aspects of the
   architecture, and only delve into few of them - only the interesting
   parts. for example, you could skip detailing the memory usage
   optimizations you made, and instead just give a one-line summary of how
   much memory (approx.) was saved due to reducing data types in general.
   i think the algorithmic part should 'control' the better part of the
   presentation, while only describing the data structures where it is
   required to understand the algorithm(s), or for things you find
   particularly interesting (if you find everything to be particularly
   interesting, sort it by order of 'interesting attribute', and only
   discuss the top 2-3 aspects).

--
guy

"For world domination - press 1,
 or dial 0, and please hold, for the creator." -- nob o. dy

---

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

>    material that people should read before the lecture.

Actually, I am going to introduce them to the game in the first slide or
two. It was not included in that revision of the summary but it is there.

>    way (you already seem to do that partially).

Again, my mistake. The next revision includes a brief description of the
architecture of Freecell Solver 0.2.

And it is my strategical decision to explain the _changes_ I made, rather
than focus on the current architecture as it is.

>    discuss the top 2-3 aspects).

I already removed most of the minor changes I made to the program, and
kept only those that were interesting on my part. (i.e: made me realize
something important about programming).

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

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