Not finished yet, but getting there.
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_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_techie.com
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
Received on Thu Nov 01 2001 - 05:45:49 IST