I'm glad that you agree on the multi-card move calculations. I'm also
glad that you decided to abandon 'f' in favor of 'a' .. 'd'. I have no
suggestion on what notation you'd use beyond 'a' .. 'g' to represent
seven free cells. However, since it's already been determined that only
an extremely small subset of the vast number of FreeCell deals can not
be solved with five free cell, I don't see where you'll have a problem
limiting yourself to seven free cells.
Since there are only 140 distinct moves possible in the 8x4 layout, it
would seem to me that a small array would hold all possible entries you
would ever need for your "ban list" as you descend the tree. You could
simply assign moves to specific integer array elements and then set each
element to zero/one to indicate inactive/active, respectively. However,
you may want to keep track of all entries generated at a given depth in
case you have to back out of that path to try another. Maybe a 2-D array
would work. If you limited your solver to a depth of 200 moves, then
your array would need 28,000 elements. The size of each element is only
limited by your creativity. Heck, it could theoretically be a 2-D array
of one-bit elements.
All of the above applies to auto-moves as well.
I don't know if your specific method of tracking redundant moves has
been done before, but I originally used three (small) two-dimensional
arrays to track moves. With them, I was able to catch most redundant
two-move combinations; e.g. "1a" and (later) "a7" ... when skipping the
first move and replacing the second move with "17" would have been
equally effective. If the resulting move put the card back in its
original position, then I backed out of that path by one level. It did a
modest job of reducing the number of move combinations I needed to
examine, but there were lots of multiple-move redundancies waiting after
that. Not all of which I've adequately resolved.
Good Luck!
HELSER ERIC JOSEPH wrote:
> I think you're right about the 'f' thing. My program has been running
> for about 2 hours now, and it's hanging around 40 moves in. Most of
> which are rundundant moves.
>
> Here's my next idea to reduce stupid moves:
>
> 1. Convert 'f' notation to 'a,b,c,d...'.
> 2. Create another array called the "ban list".
> 3. Whenever a move is made, add its reverse to the ban list. For
> example, if you move '12', then '21' will be an illegal move until
> column 1 is modified.
>
> Working example: MS deal #1
> (current move) ~ ban list
> 1a ~ a1
> 1b ~ b1 (a1 was removed)
> 1c ~ c1 (b1 was removed)
> 61 ~ 16 (rest were removed because '1' was modified)
> 61 ~ 16 (it's already here)
> 6d ~ d6 (16 was removed)
> 67 ~ 76 (d6 was removed)
> a7 ~ 76, 7a (76 was NOT removed)
> 16 ~ 7a...
>
> Good thing I worked that out, because now I actually understand how it
> works. Has this been done before?
>
> Let X = any table or free cell
> Let Y = any table or free cell
> Let Z = any table or free cell
>
> If XY is on the ban list, you may not make move XY until either move
> ZY or YZ is made.
>
> The question that remains is: should I made this a dynamic list,
> created each time the "temporary" table is evaluated, or do I make
> this an addition onto the list of moves made, so I don't have to keep
> recreating the ban list every time I want to determine the legality of
> a potential next move? The quicker way, to make an array, would be
> less time consuming but more memory consuming.
>
> Also, what do I do if I want to utilize more freecells? I can't go "a,
> b, c, d, e, f, g, h..." because 'h' is reserved for 'home'. Maybe if I
> just skipped over it and went to 'i' instead?
>
> Well, this ban list works just peachy for beginning- and mid-game
> tactics, but when there is lots of free space, there would have to be
> scores of banned moves listed... maybe I'll tell it that moving a
> complete stack to another open column is a no-no. Ah, I'll figure it
> out when I get there!
>
> This weekend I thought I couldn't do this, but I've come around a lot.
> This is fun! Lots of revamping to do...
Received on Tue Nov 18 2003 - 23:27:14 IST