Well, another good idea that bit-the-dust, maybe. For sure, the concept runs into trouble with my general solver because I prioritize my moves. This means that the 3S->4D move may be selected over the 8H->9C move. Later, when the 8H->9C move is needed, it's blocked. The only recourse is to backtrack and select the 8H->9C move and work forward from there.
Bottom Line: blocking moves may force unforeseen backtracking that wastes time.
I'm still planning to try the logic in my BFS solver. It never needs to backtrack, and this may still prove to be a successful pruning logic for it.
---In fc-solve-discuss_at_yahoogroups.com, <dannyjones183_at_...> wrote:
> Interesting. Although I don't know how easy it would be to implement.
I added 16 bytes to my Layout structure. For a 64-bit computer (which mine isn't):
/* suit mapping bit array for blocked move */
/* [0] blocks for Club /Diamond source card */
/* [1] blocks for Spade/Heart source card */
unsigned int64 CardBlocked[2];
If 9C bit is set in CardBlocked[1] then move 8H->9C is blocked. The extra software was trivial because of my default solver's design. It will take more effort to implement in my (older) BFS solver.
> You may wish to look at Shirl Hart’s Freecell solver:
> https://github.com/shlomif/shirl-hart-freecell-solver https://github.com/shlomif/shirl-hart-freecell-solver
> He told me it sometimes yielded shorter solutions than the ones on
> freecellgamesolutions.com .
Yes, my default solver can occassionally find a shorter solution than one posted by Yuri Bortnik. However, I'm sure execution time factored into how much effort his solver was allowed to put into solving each of the 1M deals that he posted. I'd hate to force my solver to find equivalent-length solutions for that many deals on my modest computer.
---In fc-solve-discuss_at_yahoogroups.com, <shlomif_at_...> wrote:
Hi Danny,
On 25 Oct 2013 12:07:23 -0700
<dannyjones183_at_... mailto:dannyjones183_at_...> wrote:
> The following is a premature release of information on my latest FreeCell
> project. It involves a pruning operation that's only partially implemented in
> my general solver (because it's easier to implement there). Eventually, I
> hope to implement it in my BFS solver.
>
> Permutations for two disjoint moves can be: move <1> followed by move <2>, or
> move <2> followed by move <1>. However, the results are the same in FreeCell.
> Instead, why not reorganize the logic to: move <1> followed by move <2>, or
> move <2> and block move <1> thereafter.
>
> Consider the following scenario:
>
> You've reached a point where you have two choices for moving a card from
> column-to-occupied_column; e.g. 8H->9C or 3S->4D. You choose 8H->9C and
> proceed. You subsequently include 3S->4D while trying to reach a solution to
> the game. However, you aren't successful and must backtrack to the place
> where you originally chose 8H->9C. At this point, you choose 3S->4D and
> proceed. Do you ever need to include 8H->9C among your subsequent moves???
>
> I've been working under the assumption that the answer to the above question
> is "No" -- unless the 9C is subsequently moved. So far, I've implemented the
> logic in my column-to-occupied_column routine (above scenario) and in my
> freecell-to-occupied_column routine. I've seen a modest reduction in the
> number of layouts examined by my solver. Next, I plan to include this pruning
> operation in my multi-card column-to-occupied_column routine. Hopefully, I'll
> see additional reductions in the layouts examined.
>
Interesting. Although I don't know how easy it would be to implement.
> Unfortunately, I have other routines where I'm (currently) unable to justify
> implementing this pruning operation.
>
>
> History:
>
> Yuri Bortnik created the freecellgamesolutions.com website, which contains
> very short solutions for the solvable first 1M games. Last Spring, he and I
> began discussions on short vs. very short vs. minimal-length solutions. We
> decided to tackle the first 1000 games and see how far each could proceed
> towards finding minimal-length solutions. My efforts produced an average of
> 34.28 moves/deal, but weren't minimal-length overall. Except for a few games
> outside his solver's range, Yuri Bortnik produced minimal-length solutions
> with an average of 33.01 moves/deal. The execution times for our efforts were
> abominable.
You may wish to look at Shirl Hart’s Freecell solver:
https://github.com/shlomif/shirl-hart-freecell-solver https://github.com/shlomif/shirl-hart-freecell-solver
He told me it sometimes yielded shorter solutions than the ones on
freecellgamesolutions.com .
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish
http://www.shlomifish.org/ http://www.shlomifish.org/
Optimising Code for Speed -
http://shlom.in/optimise http://shlom.in/optimise
If you have the same ideas as everybody else, but have them one week earlier
than everyone else — then you will be hailed as a visionary. But if you have
them five years earlier, you will be named a lunatic. ( Barry Jones )
Please reply to list if it's a mailing list post -
http://shlom.in/reply http://shlom.in/reply .
Received on Fri Nov 01 2013 - 18:30:27 IST