On Thursday 14 May 2009 16:27:41 Gary Campbell wrote:
> 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.
A meta-move is a move that consists of several single or multiple card moves
done at once. For example, my solver may opt to move a card that's covered by
several cards to the foundations, by first moving the cards on top of it to
free freecells, or to free stacks. I have a move function that attempts to do
this, and as far as the solver is concerned, it moves from the original state
to the derived state with the card already placed in the foundations in one
step.
I should note that FCS still keeps track of the individual moves that are
conducted by this move, so it can later replay the solution step-by-step.
>
> 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.
OK.
>
> >> 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?
Well, on game No. 24,795,893 my solver (with its "-l gi" configuration) has
done 11,414,822 iterations and consumed over 50% of my memory (2.5 GB RAM + 1
GB swap) before I gave up and killed it.
With game No. 53,687,601 my solver (with its "-l gi" configuration) has done
13,593,338 iterations and consumed over 50% of my memory, before I gave up and
killed it.
With the Cookie game #2:
{{{{{{{{{{{{{{{{{{
AS KS QS JS TS 9S 8S
AH KH QH JH TH 9H 8H
AD KD QD JD TD 9D 8D
AC KC QC JC TC 9C 8C
7S 6S 5S 4S 3S 2S
7H 6H 5H 4H 3H 2H
7D 6D 5D 4D 3D 2D
7C 6C 5C 4C 3C 2C
}}}}}}}}}}}}}}}}}}
I'm getting:
{{{
I could not solve this game.
Total number of states checked is 1158165.
This scan generated 642361 states.
}}}
How does your solver fare on those?
>
> > 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?
Reading from the USAGE file:
{{{{{{{{{{{{{{{{{{
-to [Test's Order]
--tests-order [Test's Order]
This option specifies the order in which Freecell Solver will try the
different types of moves that it can perform. Each move is specified by
one character, and they are performed in the order in which they appear
in the parameter string. You can omit tests by not including their
corresponding characters in the string.
The tests along with their characters are:
Freecell Tests:
'0' - put top stack cards in the foundations.
'1' - put freecell cards in the foundations.
'2' - put freecell cards on top of stacks.
'3' - put non-top stack cards in the foundations.
'4' - move stack cards to different stacks.
'5' - move stack cards to a parent card on the same stack.
'6' - move sequences of cards onto free stacks.
'7' - put freecell cards on empty stacks.
'8' - move cards to a different parent.
'9' - empty an entire stack into the freecells.
Atomic Freecell Tests:
'A' - move a stack card to an empty stack.
'B' - move a stack card to a parent on a different stack.
'C' - move a stack card to a freecell.
'D' - move a freecell card to a parent.
'E' - move a freecell card to an empty stack.
}}}}}}}}}}}}}}}}}}
>
> >> 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.
>
I see. Interesting. I don't see an obvious way to improve upon it.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
The Case for File Swapping - http://xrl.us/bjn7i
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Thu May 14 2009 - 14:22:05 IDT