Hi Shlomi,
I guess there's you, me, and a couple of observers. I think I
can address your points, but I'm fuzzy on what you are calling
meta-moves. Even when you count moves that are part of a
flourish, the fanout at that point is just 1 per move.
The real point of this exercise is figuring out (proving) that
many moves are unnecessary and which ones they are, so a
solver doesn't have to investigate them. Everyone who has
written a solver knows that sorting moves is incredibly
important. However, when a solver gets on the wrong
track, it then becomes necessary to effectively prune away
the unnecessary moves, or the solver may never be able
to backtrack out of its difficulty.
>> of FreeCell moves. Fanout needs to be restricted to the
>> minimum of necessary moves at each step. Investigating
>> every possible move is not only unnecessary, but it
>> guarantees that a solver cannot perform an exhaustive
>> search in any practical time.
>
> Well, I'm not if the fanout is so important. If we want to solve a given
> Freecell initial layout, then we may encounter some positions with a large
> fanout, but can you show that it affects the effectiveness of the solver?
>
As I stated above (and later expand upon), if a solver doesn't restrict
fanout in some way, it will run into intractable positions that it can't
solve or render impossible. Most solvers have trouble with game #s
24795893, 53687601, and the cookie game -2. How does your solver
fare on these games?
> Moreover, given that my solver does meta-moves, the number of possible meta-
> moves extending from one position, is theoretically bigger than the number of
> individual moves (including multi-card moves). So counting the individual
> moves may not be so revealing.
>
A multi-card move should be handled as a single move, but it
could be thought of as a series of single card moves done in a
canonical order -- either way, it is a great savings over simple
single-card moves that have the same effect. Now, what are
your meta-moves?
>>
>> Therefore, the purpose of this exercise is to discuss the
>> maximum fanout with the maximum of limitations, i.e.
>> never allowing an unnecessary move. Clearly, at certain
>> points, there are few or zero moves possible. At other
>> points there may be quite a few. However, a possible
>> move may not be a necessary move. For example, if
>> you try moving a card to one of 4 empty free cells, and
>> can't find a solution by doing so, moving it to one of
>> the other free cells does not need to be tried. This 2nd
>> move is unnecessary or redundant. There are many
>> such moves. This is essentially a discussion of them.
>>
>> I can imagine that the proof that a move is redundant
>> could get to be quite complex, indeed.
>>
>> So, again, what is the maximum NECESSARY
>> fanout given some constructed layout, such as the
>> one Shlomi proposes below (or one of your own
>> choosing)? I chose a layout with only one empty
>> free cell and one empty column to produce the
>> maximum of 41 moves that I came up with.
>
> May you tell us which layout this is, so we can learn from it, and try to
> improve upon it?
>
Unfortunately, when I went back and recounted, I
found that I had counted some moves twice, so now
I only come up with 33+ moves. I hope you can
decypher my notation:
A possible scenario (b2=black Two, etc.):
Freecells: b2, b2, b4 (5 moves --> columns)
Home: r2, r2, b3, b5 (4 moves --> home)
Columns: r3, r3, r5, b4, b6, b6, r7
(7 moves -->FC, 10 moves --> EC,
7 moves column --> column)
column -->column moves: 14, 24, 35, 36, 43, 57, 67.
FC=free cell, EC = empty column, home = foundation.
>>
>> By the way, regarding Shlomi's layout below, I
>> calculate that there are zero NECESSARY moves.
>> The layout produces an immediate flourish!
>>
>
> Well, my solver still has to do all the moves of the cards to the foundations
> explicitly. In most configurations, this will be the first thing it tries to
> do, but these are still counted as explicit moves.
>
>> It was a useful example to get the discussion
>> started, however. But no discussion occurred!
>> Is there anybody out there?
>
> Maybe only I. ;-)
>
> Regards,
>
> Shlomi Fish
>
> --
> -----------------------------------------------------------------
> Shlomi Fish http://www.shlomifish.org/
> What Makes Software Apps High Quality - http://xrl.us/bkeuk
>
> God gave us two eyes and ten fingers so we will type five times as much as we
> read.
>
>
>
> ------------------------------------
>
> Yahoo! Groups Links
>
>
>
>
Received on Thu May 14 2009 - 10:37:28 IDT