On Tuesday 31 March 2009 01:59:30 Gary Campbell wrote:
> Just for comparison, the statistics and descriptions mentioned below are
> for my released solver (anyone can download it and verify them).
>
> > Which hard games are you interested in? And I should note that FCS has
> > many possible run-time configurations, each one potentially performing
> > better on some games than others. I've constructed some aggregate scans,
> > that on average perform better than others. See the "-l" flag for more
> > details.
>
> I have tried to build in multiple attacks on difficult games so that no
> run-time configuration is necessary. I have tried to tinker with solving
> parameters so that the user doesn't have to.
>
Well, my solver is configurable at run times, but configuring it to behave in
a generally optimal way is not hard - just add "-l gi" to the command line.
I'd rather not make it the default, because I still want to keep the present
and future customisability of FCS open to further improvements. So by
specifying different -l ("load") configurations one can potentially have
improved behaviour in the future, without breaking existing behaviour.
> >> its average solution
> >> length,
> >
> > I haven't measured this, though I can easily. The question is with which
> > preset are you interested. Would "-l gi" - good-intentions be good enough
> > for you?
>
> I just ran my solver on the 1st 1000 games and it got solution lengths of
> fewer than 64 moves on all games (34 of them < 48 steps). Of course this
> doesn't count automove steps, and all "supermoves" are counted as single
> steps. I think it is important to use standard move notation and layout
> description.
FCS also counts supermoves (or moving any sequence of cards) as a single move.
But it doesn't limit itself to the playing conventions of MS-Freecell, and so
is incompatible with it. If you're interested in the number of moves in that
regard, I'll need to re-use the ext-ifaces code I pointed to.
>
> > I should note that Freecell Solvers's solutions explicitly includes many
> > moves that are implicit in MS-Freecell/Freecell-Pro. As a result, the
> > solution may be artificially longer than a strictly FC-Pro compatible
> > solver that automatically moves some cards into the foundations. Which of
> > the two options are you interested in?
> >
> >> its speed over a range of games,
> >
> > To quote http://tech.groups.yahoo.com/group/fc-solve-discuss/message/887
> > :
> >
> > {{{{{{{{{{{{{{{{{
> > Added the FCS_FREECELL_ONLY compile-time flag to hard-code the settings
> > for Freecell and thus allow faster run-time. On a Pentium 4-2.4GHz
> > machine running Mandriva Linux Cooker, this allows to solve the Microsoft
> > 32,000 in 194.56353 seconds ( 164 deals / second ) instead of
> > 228.84 seconds for the generic version ( 140 deals / second ).
> > }}}}}}}}}}}}}}}}}
> >
> > I only tested it against the first 32,000 deals.
>
> I just ran my solver on the 1st 32000 games and on a 1.73 GHz Pentium with
> a 794 MHz RAM, it solved all the games (except 11982, of course) in 145 s.
> This is 220 games/second. Of course, in this small set, there were no
> False Negatives or intractables.
>
I see.
> >> and its
> >> percentage of false negatives or intractables.
> >
> > Freecell Solver supports atomic moves, so assuming there are no bugs in
> > the code, solving configurations that end up using atomic moves, will
> > have no false negatives.
> >
> > I'm a bit more hazy about intractables. Freecell Solver has an arbitrary
> > (~2**32) limit on its resources so it may go on searching forever given
> > enough time and resources. If you want me to determine the number of
> > intractables for a certain iterations' limit - that would be doable,
> > though may be somewhat time consuming.
>
> I pretty much consider a game or layout intractable when it takes over five
> minutes and doesn't get a result. My released solver rarely encounters
> such a layout, but it does occasionally (game 10916159 is such a game).
>
> How does your solver handle Game# -2 (the artificial Microsoft layout)?
> My released version also finds this one intractable.
I haven't tried yet.
>
> My current research and development is aimed at reducing or eliminating
> intractables without introducing any false negatives. This is like walking
> a tightrope. But, I'm getting closer all the time.
>
> My solver is aimed at standard freecell, but I expect my next version to
> handle 0-4 free cells, instead of exactly 4. It also handles the full
> eight billion games of the standard random number generator, not just the
> four billion that are determined by the 32-bit datatype. However, you have
> to run FCELL standalone to get them. When using its front end, it is
> limited to the standard four billion games (plus an infinite number of
> layouts that you might input as text files).
Freecell Solver also accepts any arbitrary layout for input as a text file,
including ones at mid-play. What I meant by 2**32 is that it stores some
resources as 32-bit-integers and so won't be able to handle more than 2**32
(or even 2**31) such resources. If you do get to this stage, then an overflow
may occur and Bad Things will happen. On 64-bit systems with enough RAM, it
should be able to manage more positions in the scans, but it is still limited
by the ANSI C "int" datatype.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Stop Using MSIE - http://www.shlomifish.org/no-ie/
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Tue Mar 31 2009 - 03:05:59 IDT