Hi all,

Freecell Solver’s version control repository was converted from Subversion
(which is an open-source centralised version control system) to Mercurial
(which is an open-source distributed version control system - see
http://mercurial.selenic.com/ ).

Instructions on checking out the source code with the new repository can be
found here:

http://code.google.com/p/fc-solve/source/checkout

The documentation and the site were also updated for that change.

I’m sorry that it took me so long to announce it here.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Why I Love Perl - http://shlom.in/joy-of-perl

I feel much better, now that I’ve given up hope.
     — Ashleigh Brilliant

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

I recently added the "--show-exceeded-limits" (or "-sel" for short) flag to
fc-solve. What it does is remove ambiguity in the output:

[SHELL]

shlomif[fcs]:$trunk/fc-solve/source$ pi-make-microsoft-freecell-board -t 11982 |
./fc-solve -mi 100000
I could not solve this game.
Total number of states checked is 35265.
This scan generated 35265 states.
shlomif[fcs]:$trunk/fc-solve/source$ pi-make-microsoft-freecell-board -t 9 |
./fc-solve -mi 100000
I could not solve this game.
Total number of states checked is 100000.
This scan generated 100159 states.
shlomif[fcs]:$trunk/fc-solve/source$ pi-make-microsoft-freecell-board -t 11982 |
./fc-solve -sel -mi 100000
I could not solve this game.
Total number of states checked is 35265.
This scan generated 35265 states.
shlomif[fcs]:$trunk/fc-solve/source$ pi-make-microsoft-freecell-board -t 9 |
./fc-solve -sel -mi 100000
Iterations count exceeded.
Total number of states checked is 100000.
This scan generated 100159 states.
shlomif[fcs]:$trunk/fc-solve/source$

[/SHELL]

As one can see with "-sel" on the initial line of report if the iterations were
exceeded is different, which removes ambiguity.

This flag will be part of freecell-solver-3.12.0.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Interview with Ben Collins-Sussman - http://shlom.in/sussman

Trying to block Internet pornography is like climbing a waterfall and trying
to stay dry. (— one of Shlomi Fish’s Internet Friends)

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

in another failed attempt to solve the 2-freecells deal No. 982, I have
implemented a scheme which I've called "Split-BrFS". It was implemented in the
main branch in the repository.

What it does is run a standard Breadth-First-Search
( http://en.wikipedia.org/wiki/Breadth-first_search ) until a certain number of
positions accumulated in the queue, and then dump the queue it has so far to a
file, one position after the other in separate lines. After that, the dump file
is processed for duplicates, and then a different instance of the same solver
loads it again for processing the reached positions one by one, and infer
more BrFS derived positions for them.

The problem I found with this scheme (whose main file can be found at
scripts/982_dbm_total.bash in the distribution) is that it took too long and
built too many states.

However, now that I think about it, I think I can make it faster by making the
states from the previous scans in the current iteration of the solver run, be
kept in the cache so as to prevent them from being traversed again by the
solver when inspecting further boards. I'm going to try that out soon.

Meanwhile, I've began work on a queue implementation that offloads most of the
data to the hard disk in hope of conserving space. I've written a prototype
for it in Perl 5 and tested it and need to translate it to C.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Understand what Open Source is - http://shlom.in/oss-fs

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 .

Hi all.

Great news everybody: we have finally reached a conclusive verdict regarding
the 2-Freecell Microsoft deal No. 982 : it was demonstrated to be impossible
(as I suspected for some time, and naturally barring any bugs in the solver’s
code.)

This conclusion was reached thanks to a worker from Washington State
University ( http://www.wsu.edu/ ; he's BCCed to this message) who was given
permission to deploy the dbm_fc_solver on one of his university’s
high-performance computing (HPC) nodes, which has 512 GB of RAM, and did the
necessary work of deploying it there, with my guidance. I'll also like to
thank Amadiro (also BCCed) who had deployed the solver earlier on a
University of Oslo ( http://www.uio.no/english/ ) HPC computer, with 128 GB of
RAM, which had enabled to solve most of the other intractable 2-freecell deals
and inspired many improvements to the codebase. Some of these improvements were
recent optimisations in RAM consumption (which I'd like to post about in a
separate post.).

Here are the last lines from the log of the solver’s run. A complete log is
available here:
http://fc-solve.shlomifish.org/downloads/dbm-fc-solver/982-fully-traversed.dump.\
xz
and a Perl program to process it and output a Tab-separated value file with
some run-time numbers and statistics, can be found here:
https://github.com/shlomif/fc-solve/blob/master/fc-solve/source/scripts/convert-\
dbm-fc-solver-log-to-tsv.pl

[LOG]

Reached 3095300000 ; States-in-collection: 3095579317 ; Time: 1337732245.947757
>>>Queue Stats: inserted=3095579317 items_in_queue=279317 extracted=3095300000
Reached 3095400000 ; States-in-collection: 3095642846 ; Time: 1337732248.707633
>>>Queue Stats: inserted=3095642846 items_in_queue=242846 extracted=3095400000
Reached 3095500000 ; States-in-collection: 3095691025 ; Time: 1337732250.920092
>>>Queue Stats: inserted=3095691025 items_in_queue=191025 extracted=3095500000
Reached 3095600000 ; States-in-collection: 3095742956 ; Time: 1337732253.286799
>>>Queue Stats: inserted=3095742956 items_in_queue=142956 extracted=3095600000
Reached 3095700000 ; States-in-collection: 3095790607 ; Time: 1337732255.441771
>>>Queue Stats: inserted=3095790607 items_in_queue=90607 extracted=3095700000
Reached 3095800000 ; States-in-collection: 3095838110 ; Time: 1337732257.554776
>>>Queue Stats: inserted=3095838110 items_in_queue=38110 extracted=3095800000
instance_run_solver_thread end
instance_run_all_threads end
handle_and_destroy_instance_solution start
Reached 3095862346 ; States-in-collection: 3095862346 ; Time: 1337732258.708077
>>>Queue Stats: inserted=3095862346 items_in_queue=0 extracted=3095862346
Could not solve successfully.
handle_and_destroy_instance_solution end

[/LOG]

So, the game’s graph spans 3,095,862,346 positions. Note that it excludes some
positions that were pruned using Horne’s play.

I'd like to post a report summarising the conclusion about the statistics of
solving all the 2-Freecell 1-32,000 Microsoft deals, but this will have to yet.
Moreover, it appears that the dbm_fc_solver still consumes much more RAM than it
should, so I'd like to look into the Partial-IDA* scan to see if it
will improve upon it. If anyone can recommend good online (or less preferably
offline) sources that explain it, I would be grateful.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Perl Humour - http://perl-begin.org/humour/

Comedy is simply a funny way of being serious.
     — http://en.wikiquote.org/wiki/Peter_Ustinov

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

this message aims to detail some of the recent optimisations done to reduce
memory consumption in regards to the dbm_fc_solver in the repository tip here:

https://github.com/shlomif/fc-solve

1. The first thing that was done (and it was done quite some time ago) was
switching the balanced binary tree to "avl.c" from libavl, which doesn't use
parent pointers for its tree nodes. This saved an extra pointer - or 8 bytes
per states (because on 64-bit machines, pointers take 8 bytes).

2. Afterwards the queue used by the dbm_fc_solver was converted to an
offloading-to-hard-disk queue. Such a queue splits the data into constant-sized
frames, each assigned a serial index, and offloads the middle frames (i.e:
those not at the head or tail of the queue) to the hard-disk. It was prototyped
in Perl and later on translated to C, and works pretty well. You can find it
here:

https://github.com/shlomif/fc-solve/blob/master/fc-solve/source/offloading_queue\
.h

This saves us from having to store the queue's items in RAM, while we can use
the hard-disk instead, and also since frames are vectors, they waste less space
than a linked list which has a pointer for each item.

3. After that, I decided to store the raw items of the AVL tree directly in the
tree's nodes, instead of allocate them dynamically and store them as pointers
(which was somewhat wasteful). This required extensively patching libavl/avl.c,
but worked pretty well.

3. Then I took a closer look at the way the items were stored in
the binary tree. It looked something like that:

fcs_encoded_state_buffer_t key;
fcs_encoded_state_buffer_t parent_and_move;
signed char avl_balance;

Since fcs_encoded_state_buffer_t take 24 bytes, it is more wasteful than an
8-byte pointer. I don't need parent_and_move - just its pointer (which by
virtue of the tree implementation remains constant throughout the program's
run). So I converted it to a pointer, and placed the move in one of the bytes
of "key", which is 24 bytes for alignment, and never reached more than 18
occupied bytes and so has some bytes to spare.

Similarly, I've also moved avl_balance inside key, so it won't waste
avl_balance's 8 bytes in total for alignment.

4. Afterwards, I realised I can reduce the size of the queue's frames by
keeping only pointers instead of the keys, for similar reasons. This does not
save a lot of RAM, but it does cuts the hard-disk space consumption to a third
of its original value. As a result, it was implemented too.

-------------------------

All these memory consumption optimisations appear to have made the RAM
consumption of the dbm_fc_solver better, but like I said, I'd like to look into
the Partial IDA* scan to improve matters even more.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/

I hope that if it had not been clear before, it isn’t less clear now.
     — One of Shlomi Fish’s Technion Lecturers

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

I'm forwarding a message I sent to Dr. de Bondt about compactly representing
Freecell positions/states. Now that I think of it, I think we don't need to
store the single card move-from-parent-state at all, because we can enumerate
all the moves from the parent to its children and see which one matches the one
in the solution (because we hold a parent state pointer).

Furthermore, I have another scheme in mind that is similar to my original
scheme where we store a bit for whether the cards on the columns or in the
Freecells are (H vs. D) or (C vs. S) and so on, and would like to look into it.
And naturally, I should play with representing the existing encoding more
compactly as one large number.

Regards,

	 Shlomi Fish

Begin forwarded message:

Date: Sat, 26 May 2012 15:56:22 +0300
From: Shlomi Fish <shlomif@...>
To: Michiel de Bondt <MichieldeB@...>, M.deBondt@...
Subject: Re: Freecell states


Hi Michiel,

Since I don't know if the @netscape.net address is still active, I'm CCing this
to your university E-mail, which I found on this paper you have written
http://www.math.ru.nl/onderzoek/reports/rep2004/rep04_18.ps.gz by following
the links on a Google search for your name.

It seems like you are interested in the NP-completeness of Minesweeper, of
which I have heard back when I studied in the Technion, and is also a game
included in Windows 3.x. That's Impressive.

See below for my response.

On Tue, 16 Sep 2003 22:54:37 +0200
Michiel de Bondt <MichieldeB@...> wrote:

> Hello Shlomi,
>
> You made a solver of Freecell. I wish to discuss about how the states
> are stored. I have understood that you represent a state by 8 pointers
> (to the 8 stacks) and some other info, but forgive me if I am wrong. 8
> 16-bit pointers already take 128 bits of memory. I thought out a way to
> store a state with only 128 bits. It works with <= 52 freecells, <= 52
> stacks, and <= 52 cards per stack. Here is how.
>
> For each card, except the aces, the individual state of that card is
> stored, which can take 6 values. Since 216 <= 256, you can store 3 cards
> in a byte, so 48/3 = 16 bytes are needed for the state representant.
>
> The individual state of a card C, say jack of diamonds, represents what
> is below it.
>
> 1 C is the lowest card of a stack.
> 2 C lies on queen of spades.
> 3 C lies on queen of clubs.
> 4 C lies on the carpet (i.e. on ten of diamonds).
> 5 C lies on a free cell.
> 6 C does not satisfy one of the above (i.e. C lies on the card it
> initially lies on).
>

I nearly forgot about that E-mail thread and your suggestion, but I've ran into
it when I was going over my old Freecell Solver-related E-mail and in the
context of having implemented the so-called delta states:

http://fc-solve.shlomifish.org/to-do.html#orig_calc_states

Now this resulted in compactly stored states - varying in size, but never more
than 18 bytes (or 144 bits), which I've placed into 24 bytes for parity (and
also was able to eventually pack more stuff there, like the leading, or the AVL
tree's balance).

Now, your suggestion about storing the states of 3 cards in a byte of 256 values
can be improved by calculating a big 6**52 number and storing it in the number
of necessary bits:

log2(6) * 52 = 134.4180500375 bits (bytes: 17)

That's already an improvement over the potentially long 18 bytes, but we can
do even better. If you remember, the only valid positions for Aces (given
Horne's prune) are in their original position (#6 in your case), or in the
foundation (#4 in your case), so we can have:

log2(6) * 48 + log2(2) * 4 = 128.078200034615 bits (bytes: 17)

In addition, cases #2 and #3 are not possible for kings, so they only have 4
possible cases, so we get:

log2(6) * 44 + log2(2) * 4 + log2(4) * 4 = 125.738350031731 bits (bytes: 16)

That already fits in 16 bytes or 128 bits.

But we can do even better. If we first encode the value of each foundation
(from 0 to King - 14 values in total), we can remove one option (#4 in your
case) from each of the bases and get:

log2(14) * 4 + log2(5) * 44 + log2(1) * 4 + log2(3) * 4 = 123.734105866159 bits
(bytes: 16)

Something else I tried is to encode the length of the cards which remained in
their original position since the start of play, in each of the 8 columns, like
so:

0-1 cards: 0 (because 1 remaining cards is equivalent to none)
2 cards: 1
3 cards: 2
4 cards: 3
5 cards: 4
6 cards: 5
7 cards: 6

Then since there are 4 columns with seven initial cards and 4 columns of six,
we get:

log2(7) * 4 + log2(6) * 4 + log2(14) * 4 + log2(4) * 44 + log2(1) * 4 + log2(2)
* 4 = 128.798689379345 bits (bytes: 17)

As you see it made matters worse, so I guess it's better to use the 123.73 bits
notation.

===========================

I also would like to encode the move-to-the-parent-state as compactly as
possible. Since in the case of the DBM-fc-solver, it is a single card move,
then there are these possibilities:

1. 4 moves to each of the foundation - H, S, C, D (from the appropriate card).

2. Moves from the top of the column to any one of the freecells - 8 in total.

3. Moves from any of the Freecells to at most three options in the columns (two
possible parent cards, and one empty stack) - 4*3 in total.

4. Moves from one column to another (parent #1, parent #2 or an empty column) -
24 in total, for simplicity's sake (probably can be reduced further).

In total we get 48 in total. If we add it to the state representation we get:

log2(48) * 1 + log2(14) * 4 + log2(5) * 44 + log2(1) * 4 + log2(3) * 4 =
129.31906836688 bits (bytes: 17)

So we need 130 bits. However, there are at least 3*2 of them in the low-bits of
the three pointers (left tree child, right tree child and
pointer-to-game-parent-node) in the tree representation (3*3 if these are
64-bit pointers), so we can use those for the two remaining bits (and also the
AVL tree balance or R/B tree node colour), and as a result be able to represent
each key as 16-bytes instead of 24 bytes, and save 8 bytes (or 64-bits) per
state.

So I guess that mission accomplished.

Thanks for the insight!

Best regards,

­— Shlomi Fish

> Suppose you wish to use e.g. 2^n MB for the hash table, with 1 <= n <=
> 9. Cards 0 to 5 are stored in the first 16 bits of the state
> representant. Cards 6 to 8 are stored in the next 8 bits. Cards 9 to 47
> are stored after that.
> Now compute a hash value with XOR arithmetic, such that the individual
> states of the cards are given by the following amount of bits.
>
> Card 0..5: 0 bits
> Card 6..8: 16 bits
> Card 9..47: 15+n bits
>
> You get a hash value of 15+n bits this way. Now XOR this value with the
> first 15+n bits of the state representant. This is the number of the
> bucket where the state representant is stored. But the trick is, that
> only the last 128-(15+n) bits of the state representant need to be
> stored in the bucket.
>
> The remaining 15+n bits are used to point to the next state in the
> bucket. This next state is in another table of 15+n entries: the first
> table only contains "first buckets states". The third and subsequent
> states are also in the second table, each pointed by the remaining 15+n
> bits.
>
> Since each byte of the state representant is redundant, it is no problem
> to reserve the value 0 or -1 in the first word of the table entry for
> "empty". The value 0 in a pointer in either of both tables indicates
> that there is no next entry, i.e., the end of the bucket is reached, so
> the index 0 can not be used for the second table.
>
> Two tables of 2^(15+n) entries of 16 bytes take 2*16*2^15*2^n = 2^n MB
> of memory.
>
> This way of storing seems efficient to me. To move a row of cards to
> another stack, only the lowest card need to be moved in terms of the
> above way of storing. Further, no ordering routines are needed.
>
> If you do not wish to search deep, just discourage your search by the
> amount of cards that have state 6. If no cards have state 6, then you
> have solved the board. So if you demand that the count of state 6 cards
> decreases one every 100 moves, you do not get deeper than 5200 moves.
>
> Best regards, Michiel
>
>



--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
What Makes Software Apps High Quality -  http://shlom.in/sw-quality

Chuck Norris doesn’t make mistakes. (Su‐Shee) He corrects God. (Shlomi Fish)

Please reply to list if it's a mailing list post - http://shlom.in/reply .


--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Best Introductory Programming Language - http://shlom.in/intro-lang

Satan condemned Hitler for a million years of writing XSLT.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

On Sat, 5 May 2012 12:10:17 +0300
Shlomi Fish <shlomif@...> wrote:

> Hi all,
>
> Freecell Solver’s version control repository was converted from Subversion
> (which is an open-source centralised version control system) to Mercurial
> (which is an open-source distributed version control system - see
> http://mercurial.selenic.com/ ).
>
> Instructions on checking out the source code with the new repository can be
> found here:
>
> http://code.google.com/p/fc-solve/source/checkout
>

Well, apparently, the conversion from Subversion to Git to Mercurial was not
flawless, and so I had to restort to using Git instead. You can find the
repository here:

https://github.com/shlomif/fc-solve

I'm contemplating whether to set up a git mirror for the repository on the
Google Code project, or whether to use GitHub's issue tracker instead of Google
Code’s (even though I think I prefer Google Code's issue tracker), or maybe
seek a different solution.

Regards,

	 Shlomi Fish

> The documentation and the site were also updated for that change.
>
> I’m sorry that it took me so long to announce it here.
>
> Regards,
>
>  Shlomi Fish
>



--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/

“We’re not doing it for money… we’re doing it for a shitload of
money!”
     — Spaceballs, http://www.imdb.com/title/tt0094012/

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Does Windows 7 have an accessible location for setting old freecell satistics?
Windows XP and earlier had a location in the registy.

Your help would be appreciated.

Larry

Hi Mr. Hart,

On Sat, 09 Jun 2012 23:48:01 -0000
"Lawrence Hart" <ljhart1961@...> wrote:

> Does Windows 7 have an accessible location for setting old freecell satistics?
Windows XP and earlier had a location in the registy.
>
> Your help would be appreciated.
>

I have no idea about Microsoft Windows FreeCell , so I cannot help with it.
Sorry.

However, please consider downloading one of the quality open-source Freecell
implementations (some of them have integrated Freecell Solver). For more
information see the notice on:

http://fc-solve.shlomifish.org/download.html

And especially see http://pysolfc.sourceforge.net/ which is the most
recommended, and runs very nicely on Windows and other platforms.

For why you should experiment with open-source software, see what I wrote about
it here:

http://teachingopensource.org/index.php/How_to_start_contributing_to_or_using_Op\
en_Source_Software

Best regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
What does "Zionism" mean? - http://shlom.in/def-zionism

CPAN thrives *because* of the unfettered uploading of shit, not in spite of it.
     — Andy Lester

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

Freecell Solver 3.12.0 was released and can be downloaded from its homepage at
http://fc-solve.shlomifish.org/ . Freecell Solver is a reusable and
open-source (MIT/X11-licensed) library, written in mostly portable C
(32-bit/64-bit, UNIX/Linux and MS Windows), that can automatically solve the
Solitaire game Freecell and some similar Solitaire variants.

The Freecell Solver distribution also includes some standalone command-line
programs that make use of the library. Freecell Solver has a very large amount
of features, supports many different run-time heuristics that may yield
different solutions, is a fast solver, and supports the largest number of
Solitaire variants of all other solvers of its kind.

Here is the list of changes since the previous stable release, 3.10.0, from the
NEWS.txt file:

[QUOTE]
Version 3.12.0: (12-Jun-2012)
-----------------------------

1. Add the +--show-exceeded-limits+ / +-sel+ flag that removes some ambiguity
in the output.

2. Fix invoking the solver with +--set-pruning r:tf+ in conjunction
with +-opt+.

3. Add the +-l three-eighty+ preset.

4. Many +dbm_solver.c+ improvements including the implementations of kaztree
and libavl2-derived backends, several major reductions of the memory
consumption, and many code cleanups and bug fixes.

5. Add support for building and testing the distribution in an out-of-tree
build (e.g:
+mkdir build ; cd build ; cmake -DFCS_WITH_SUITE=1 .. ; make ; make test+
).

6. A new experimental +fcc_solver.c+ which aims to reduce memory consumption
in exhaustive scans even further.

7. Removed many #ifdefs from the code by creating common abstractions.

8. Eliminate many GCC warnings with certain GCC compile flags.
[/QUOTE]

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
The Case for File Swapping - http://shlom.in/file-swap

Better be a tail for the lions, than the head of the jackals.
     — Pirkei Avot, 4 15

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

the subject of that post was wrong because I edited an older message and
re-submitted it. The new release is 3.12.0 - not 3.10.0 (which was released
back in January).

Regards,

	 Shlomi Fish

On Tue, 12 Jun 2012 20:48:59 +0300
Shlomi Fish <shlomif@...> wrote:

> Hi all,
>
> Freecell Solver 3.12.0 was released and can be downloaded from its homepage at
> http://fc-solve.shlomifish.org/ . Freecell Solver is a reusable and
> open-source (MIT/X11-licensed) library, written in mostly portable C
> (32-bit/64-bit, UNIX/Linux and MS Windows), that can automatically solve the
> Solitaire game Freecell and some similar Solitaire variants.

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
UNIX Fortune Cookies - http://www.shlomifish.org/humour/fortunes/

If Botticelli were alive today, he’d be working for Vogue.
     — http://en.wikiquote.org/wiki/Peter_Ustinov

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

as I’ve been playing some Baker’s Dozen (see
http://en.wikipedia.org/wiki/Baker%27s_Dozen_%28solitaire%29 ) lately,
I came to a realisation of one way we could prune the moves there, and in
other variants where empty columns cannot be filled by any card, and which I
believe would still guarantee a correct verdict.

What I thought of is that there is no point in moving the last card in a column
to a parent on a different column, because then the column won't be able to be
filled,
and will be left to disuse. Furthermore, after moved to a parent, the card might
block
other cards that can be placed on the parent.

A variation of this prune for variants where only kings can fill empty columns
is that if
there are enough columns to provide hosting for all the kings that are active,
then there
is no point in clearing a column of cards.

Does this sound reasonable to you?

Regards,

	 Shlomi Fish


--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
My Aphorisms - http://www.shlomifish.org/humour.html

Chuck Norris reads all messages posted to LKML (= the Linux Kernel Mailing
List), understands them all, and he kills all gnomes he sees in sight.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

On Sun, 17 Jun 2012 08:30:53 +0300
Shlomi Fish <shlomif@...> wrote:

> Hi all,
>
> as I’ve been playing some Baker’s Dozen (see
> http://en.wikipedia.org/wiki/Baker%27s_Dozen_%28solitaire%29 ) lately,
> I came to a realisation of one way we could prune the moves there, and in
> other variants where empty columns cannot be filled by any card, and which I
> believe would still guarantee a correct verdict.
>
> What I thought of is that there is no point in moving the last card in a
column
> to a parent on a different column, because then the column won't be able to be
filled,
> and will be left to disuse. Furthermore, after moved to a parent, the card
might block
> other cards that can be placed on the parent.
>

OK, so I implemented this prune in commit
7cd599215f83a82241bb10abd97434903e8bf88b in the repository
(titled "Prune for tests__is_filled_by_none().") and bechmarked the first
two-hundred (200) PySolFC Baker’s Dozen deals. The results are that:

1. With the prune it now runs in 742 wallclock seconds instead of 938s (a 26%
improvement).

2. It now solves 127 deals instead of 89.

3. It's not all roses, because some of the previously solved deals are now
intractable.

4. Only one deal was found to be unsolvable in both cases, and it's the same
deal.

---------------

Note that this is with the default Freecell Solver configuration.

So overall I am happy - it did not require a lot of coding work, and it yielded
good results.

Regards,

	 Shlomi Fish

> A variation of this prune for variants where only kings can fill empty columns
is that if
> there are enough columns to provide hosting for all the kings that are active,
then there
> is no point in clearing a column of cards.
>
> Does this sound reasonable to you?
>
> Regards,
>
>  Shlomi Fish
>
>



--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Escape from GNU Autohell - http://www.shlomifish.org/open-source/anti/autohell/

He has a high degree of idealism, a high degree of stubbornness, and an even
higher degree of inability to distiniguish between the two.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

>
> 3. It's not all roses, because some of the previously solved deals are now
intractable.
>

I would consider this highly suspicious, and certainly undesirable. How can
pruning make deals which were solved before suddenly become intractable?  The
logic of your argument (not moving a lone card in a column to an occupied column
in NoFill games) seems sound.  Could there be a bug in the code?

Hi Michael,

thanks for your E-mail.

On Tue, 26 Jun 2012 06:38:30 -0000
"MichaelK" <wgreview@...> wrote:

> >
> > 3. It's not all roses, because some of the previously solved deals are now
intractable.
> >
>
> I would consider this highly suspicious, and certainly undesirable. How can
pruning make deals
> which were solved before suddenly become intractable?  The logic of your
> argument (not moving a lone card in a column to an occupied column in NoFill
> games) seems sound.  Could there be a bug in the code?
>

Well, the problem is that there are many factors at play here as the algorithm
is affected by many things. If we clear a column, then we may opt to choose
different game positions first, and so traverse the game’s graph in different
ways. And this is without starting to consider the random-DFS scan which
randomises the results.

While some bugs may be present, I am hesistant to blame the
newly-unsolved-deals on that, given the complexity of Freecell Solver, and so
far all the tests in the automated test suite are still passing.

I have ran the Baker’s Dozen solver on more deals, and will report about them
soon.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
UNIX Fortune Cookies - http://www.shlomifish.org/humour/fortunes/

The only things worse than XSLT are Excel and Sugar‐Less Tea (XSLT).

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

in continuation to
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1115 ,
I was thinking how to represent Baker’s Dozen positions.

What I came with was:

1. I can use 4 * log2(14) data to represent the foundations.

2. The 13 bottom-most cards will always be either in the foundations or in
their original place (due to the prune at
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1121 ).
We can tell which one is that based on the encodings in #1 - so:
  13 * log2(1)

3. The rest of the cards can be either in their original position or on top of
one of the 4 parents of all suits - H, C, D, S. So 39 * log2(5).

To sum up:

$ perl -MLog2 -e 'plog2(4 => 14, 13 => 1, 39 => 5)'
log2(14) * 4 + log2(1) * 13 + log2(5) * 39 = 105.784615388838 bits (bytes: 14)

so this is even better than Freecell. There may be some complications in trying
to represent games in mid-play where the prune was not completely followed.

For this, there is:

$ perl -MLog2 -e 'plog2(4 => 14, 48 => 5)'
log2(14) * 4 + log2(5) * 48 = 126.681968242824 bits (bytes: 16)

(Because the kings cannot be moved).

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
What does "Zionism" mean? - http://shlom.in/def-zionism

Staring at XSLT code for one minute has a 67% chance of making one permanently
blind.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

On Tue, 3 Jul 2012 14:02:34 +0300
Shlomi Fish <shlomif@...> wrote:

> Hi all,
>
> in continuation to
> http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1115 ,
> I was thinking how to represent Baker’s Dozen positions.
>
> What I came with was:
>
> 1. I can use 4 * log2(14) data to represent the foundations.
>
> 2. The 13 bottom-most cards will always be either in the foundations or in
> their original place (due to the prune at
> http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1121 ).
> We can tell which one is that based on the encodings in #1 - so:
>  13 * log2(1)
>
> 3. The rest of the cards can be either in their original position or on top of
> one of the 4 parents of all suits - H, C, D, S. So 39 * log2(5).
>
> To sum up:
>
> $ perl -MLog2 -e 'plog2(4 => 14, 13 => 1, 39 => 5)'
> log2(14) * 4 + log2(1) * 13 + log2(5) * 39 = 105.784615388838 bits (bytes: 14)
>
> so this is even better than Freecell. There may be some complications in
trying
> to represent games in mid-play where the prune was not completely followed.
>
> For this, there is:
>
> $ perl -MLog2 -e 'plog2(4 => 14, 48 => 5)'
> log2(14) * 4 + log2(5) * 48 = 126.681968242824 bits (bytes: 16)
>
> (Because the kings cannot be moved).

replying to myself I'd like to note that I found a way in which we can improve
on it. At the moment, each card contains the option of {OriginalPlace,
Parent-H, Parent-C, Parent-S, Parent-D}. However, since if we take the
3H/3C/3S/3D, only at most one of them can be on top of the 4H, we can do the
following analysis on a rank by rank basis:

Rank = r | S=0 | S=1 | S=2 | S=3 |

             4! (All Rank = r-1 cards are above their ancestors, no card is
                 in original place.)
			 +
             4 * 4*3*2 (Only one card is in its original place).
			 +
             nCr(4,2) * 4*3 (Two cards are in their original place.)
			 +
             4 * 4 (Three cards are in their original place.)
			 +
             1 (All four cards are in their original place.)

Then we get for the four cards in total:

$ perl -E 'say 4*3*2*1 + 4*4*3*2 + 4*3/2 * 4*3 + 4*4 + 1'
209

This is instead of 5 to the power of 4 (5**4 == 625) for the four cards
individually.

Since we don't need to consider the placement of either Kings or Aces, we get:

$ perl -MLog2 -e 'plog2(4 => 14, 12 => 209)'
log2(14) * 4 + log2(209) * 12 = 107.717729273201 bits (bytes: 14)

Which is lower than the previous attempt. Now to think how to apply this
technique to Freecell where columns are built by alternate colour.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Free (Creative Commons) Music Downloads, Reviews and more - http://jamendo.com/

Mastering ‘cat’ is almost as difficult as herding cats.
     — http://www.shlomifish.org/humour/bits/Mastering-Cat/

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

On Tue, 3 Jul 2012 17:47:49 +0300
Shlomi Fish <shlomif@...> wrote:

> Hi all,
>
> On Tue, 3 Jul 2012 14:02:34 +0300
> Shlomi Fish <shlomif@...> wrote:
>
> > Hi all,
> >
> > in continuation to
> > http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1115 ,
> > I was thinking how to represent Baker’s Dozen positions.
> >
> > What I came with was:
> >
> > 1. I can use 4 * log2(14) data to represent the foundations.
> >
> > 2. The 13 bottom-most cards will always be either in the foundations or in
> > their original place (due to the prune at
> > http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1121 ).
> > We can tell which one is that based on the encodings in #1 - so:
> >  13 * log2(1)
> >
> > 3. The rest of the cards can be either in their original position or on top
of
> > one of the 4 parents of all suits - H, C, D, S. So 39 * log2(5).
> >
> > To sum up:
> >
> > $ perl -MLog2 -e 'plog2(4 => 14, 13 => 1, 39 => 5)'
> > log2(14) * 4 + log2(1) * 13 + log2(5) * 39 = 105.784615388838 bits (bytes:
14)
> >
> > so this is even better than Freecell. There may be some complications in
trying
> > to represent games in mid-play where the prune was not completely followed.
> >
> > For this, there is:
> >
> > $ perl -MLog2 -e 'plog2(4 => 14, 48 => 5)'
> > log2(14) * 4 + log2(5) * 48 = 126.681968242824 bits (bytes: 16)
> >
> > (Because the kings cannot be moved).
>
> replying to myself I'd like to note that I found a way in which we can improve
> on it. At the moment, each card contains the option of {OriginalPlace,
> Parent-H, Parent-C, Parent-S, Parent-D}. However, since if we take the
> 3H/3C/3S/3D, only at most one of them can be on top of the 4H, we can do the
> following analysis on a rank by rank basis:
>
> Rank = r | S=0 | S=1 | S=2 | S=3 |
>
>             4! (All Rank = r-1 cards are above their ancestors, no card is
>                 in original place.)
> 		 +
>             4 * 4*3*2 (Only one card is in its original place).
> 		 +
>             nCr(4,2) * 4*3 (Two cards are in their original place.)
> 		 +
>             4 * 4 (Three cards are in their original place.)
> 		 +
>             1 (All four cards are in their original place.)
>
> Then we get for the four cards in total:
>
> $ perl -E 'say 4*3*2*1 + 4*4*3*2 + 4*3/2 * 4*3 + 4*4 + 1'
> 209
>
> This is instead of 5 to the power of 4 (5**4 == 625) for the four cards
> individually.
>
> Since we don't need to consider the placement of either Kings or Aces, we get:
>
> $ perl -MLog2 -e 'plog2(4 => 14, 12 => 209)'
> log2(14) * 4 + log2(209) * 12 = 107.717729273201 bits (bytes: 14)
>
> Which is lower than the previous attempt. Now to think how to apply this
> technique to Freecell where columns are built by alternate colour.
>

replying to myself again I'd like to note that log2(209) * 12 should have been
log(2) * 11 because there are only 11 ranks excluding Ace and King - not 12, so
we get:

$ perl -MLog2 -e 'plog2(4 => 14, 11 => 209)'
log2(14) * 4 + log2(209) * 11 = 100.01037014112 bits (bytes: 13)

This is really good. We have over 3 bytes to spare to get to 16.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
"Star Trek: We, the Living Dead" - http://shlom.in/st-wtld

Failure is not an option! It’s bundled with the product.
     — Cipher-0 in Freenode’s #perl

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

I ran the solver on the first 1,000 Baker’s Dozen Deals and here are the
results, which can be found here:

https://github.com/shlomif/fc-solve-bakers-dozen-1-to-1K

1. At first I've ran the solver in various configuration on the first 1,000
deals and generated a table (using the "table" command in the ANALYZE.bash file)
of which configurations solved what. An excerpt from it is:

[QUOTE]
1 I S S S S S I I I I I I
2 S S S S I I S S I S I I
3 I I I I S S I I S S I I
4 S S S S I S I I I I S I
5 S S S S S S S S S S S S
6 S S S S S S S S S S S S
7 S S S S I I S S S S I I
8 I I I I S S I I I I S S
9 S S S S I I S S S S I I
10 S S I I S S I I I I S I
11 I I S S S S I I S S S S
12 S S S S I I S S S S I I
[/QUOTE]

"S" is solved, "I" is intractable and "U" is unsolved. There were 926 deals
which were solved in any configuration like that, deal #64 which was reported
as unsolvable by all the scans (and was the only one reported as unsolvable)
and 73 deals which were all intractable. These deals were:

37, 46, 74, 78, 79, 93, 100, 134, 154, 185, 188, 192, 206, 210, 216, 219, 238,
247, 248,
290, 297, 300, 306, 319, 333, 336, 342, 381, 417, 448, 454, 462, 464, 476, 477,
480, 506,
520, 537, 553, 554, 558, 578, 607, 650, 664, 677, 715, 745, 763, 764, 766, 804,
817, 822,
835, 837, 844, 846, 860, 862, 866, 871, 878, 908, 922, 926, 930, 944, 949, 950,
952, 969

2. Next I've ran the go_over_unsolved_indexes function from ANALYZE.bash and it
generated bakers_dozen_unsolved_indexes-2.txt . All the deals from it where
solved except for 4 intractables:

238, 417, 477, 952

3. SCAN3.bash came next. It solved deal No. 952, proved #477 to be impossible
and the
two other deals (#238 and #417) remained intractable. The results are in
bakers_dozen_unsolved_indexes__3.txt .

4. SCAN4.bash was able to solve deal #238 - the results are in
bakers_dozen_unsolved_indexes__4.txt .

5. Deal #417 remains intractable.

--------------

So to sum up:

1) Two (2) deals are provably impossible - #477 and #64.

2) 997 deals were solved.

3) One deal (#417) remains intractable and I suspect it to be impossible as
well.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Chuck Norris/etc. Facts - http://www.shlomifish.org/humour/bits/facts/

A: I’m hungry today.
B: Well, wait until tomorrow. Maybe this feeling will pass.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

can anyone provide a solution for the 2-freecells Freecell Pro/Microsoft
FreeCell deal No. 384243 or prove that it is impossible? For reference, here is
the layout of the board (each line is a column):

3H 9C 5H TS 9H QD JS
TC 8H 9S AC 6S 3D 4D
5S AS 7H 9D 2C KD KC
2S 5C 7S JC 8C 7D AH
AD QC 8S 6H 7C 3S
6D JH JD 2D 4H TD
KH 4C TH 6C 3C QH
QS 2H 5D 8D 4S KS

Best regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
My Favourite FOSS - http://www.shlomifish.org/open-source/favourite/

XSLT is the worst thing since non‐sliced bread.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

On Wed, 11 Jul 2012 06:34:25 -0700
"Gary Campbell" <gary@...> wrote:

> The latest version of my solver is in a state of flux, but I’ll keep it in
mind, and get back to you.
> Prove it impossible?  Probably not.  Solve it, maybe so.  We shall have to
see.     -Gary
>

Thanks!

Regards,

	 Shlomi Fish

> From: Shlomi Fish
> Sent: Wednesday, July 11, 2012 1:51 AM
> To: fc-solve-discuss@yahoogroups.com
> Subject: Can anyone solve the 2-freecells Deal No. 384243 ?
>
>
> Hi all,
>
> can anyone provide a solution for the 2-freecells Freecell Pro/Microsoft
> FreeCell deal No. 384243 or prove that it is impossible? For reference, here
is
> the layout of the board (each line is a column):
>
> 3H 9C 5H TS 9H QD JS
> TC 8H 9S AC 6S 3D 4D
> 5S AS 7H 9D 2C KD KC
> 2S 5C 7S JC 8C 7D AH
> AD QC 8S 6H 7C 3S
> 6D JH JD 2D 4H TD
> KH 4C TH 6C 3C QH
> QS 2H 5D 8D 4S KS
>
> Best regards,
>
> Shlomi Fish
>



--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
http://www.shlomifish.org/humour/ways_to_do_it.html

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 .

Hi all,

just a heads-up that the repository was moved once again - it is still a git
repository, but now it is hosted in bitbucket.org. See:

http://bitbucket.org/shlomif/fc-solve

The reason I chose bitbucket.org was because its issue tracker is somewhat
better than GitHub’s. Otherwise, Bitbucket is very similar to GitHub. So feel
free to fork the repository there and send me pull requests, or file issues.

I am keeping the GitHub copy for the time being in case anyone is interested,
but the master copy will be at Bitbucket.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
What Makes Software Apps High Quality -  http://shlom.in/sw-quality

Tel Aviv, a functional definition: free parking space‐free space.
     — Shachar Shemesh ( http://blog.shemesh.biz/?p=435 )

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

here is a summary of the major things that are new in the version control
repository:

1. I implemented the so-called “DeBondt” compact states encoding:

http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1115

This allows us to represent positions in always less than 16 8-bit bytes
instead of in an encoding scheme that can often contain more (and used 24
bytes for parity).

This was first prototyped in Perl and later on translated to C. After some bugs
were ironed, it appears to be working nicely and to conserve RAM.

2. I implemented some 64-bit-enabling fixes for some limits in the core
libfreecell-solver code. It used to use only ints (which are often 32-bit on
64-bit platforms), and now it supports larger limits. Some API functions were
added to handle this.

3. The TODO.txt file was heavily cleaned up and many items were removed:

*     Add super_method_type.

     * Divide the scan type variable into two variables: super-scan
     (DFS vs BeFS/BFS/Opt) and sub-scan (random_dfs, soft_dfs, etc.), to
     facilitate multiplexing them.

* Inline fc_solve_free_instance()

*
     Remove the "ST Name" trace.

     It is no longer needed.

4. I converted some identifiers that uses the old terminology "card_num"
instead of "rank" to "rank.

5. Added a convenient way to test if an fcs_card_t was empty or not.

6. Got rid of many warnings in the board_gen/ directory and refactored the code
there a little.

7. There's now a separate branch called
“ spqjea_priority_queue_by_peter_sanders__trial ” where we play with Prof.
Peter Sanders’s KNHeap priority queue from this paper:

http://www.mpi-inf.mpg.de/%7Esanders/papers/spqjea.ps.gz

So far it appears to break backwards compatibility (with the exact expected
output), and, while the number of moves is shorter it performs somewhat
lower, appears to take somewhat more time. This may be caused by the fact that
the priority queue's functions are no longer inlined (because they are written
in C++ and use extern "C" wrappers), but it's hard to tell. Finally, compiling
the files emits many compiler warnings.

------------

Best regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
My Aphorisms - http://www.shlomifish.org/humour.html

There is an IGLU Cabal, but its only purpose is to deny the existence of an
IGLU Cabal.
     — Martha Greenberg

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

On Wed, 11 Jul 2012 11:51:48 +0300
Shlomi Fish <shlomif@...> wrote:

> Hi all,
>
> can anyone provide a solution for the 2-freecells Freecell Pro/Microsoft
> FreeCell deal No. 384243 or prove that it is impossible? For reference, here
is
> the layout of the board (each line is a column):
>
> 3H 9C 5H TS 9H QD JS
> TC 8H 9S AC 6S 3D 4D
> 5S AS 7H 9D 2C KD KC
> 2S 5C 7S JC 8C 7D AH
> AD QC 8S 6H 7C 3S
> 6D JH JD 2D 4H TD
> KH 4C TH 6C 3C QH
> QS 2H 5D 8D 4S KS
>

I'd like to note that I'm now running the new dbm_fc_solver (with the DeBondt
state encoding) on it on a High Performance Computing (= HPC) machine. It is
the last 2-freecell deal out of 1-400,000 that we do not know if it's solvable
or impossible, so I hope we can get to the bottom of it now.

If you can still find a solution, then I'll appreciate it.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
My Public Domain Photos - http://www.flickr.com/photos/shlomif/

Microsoft — making it all make sense. Ours.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

yesterday I came up with a scheme for combining some of the best aspects of the
DBM-FC-Solver and the FCC-FC-Solver (Fully connected components). What I had in
mind was that we'll keep an array of states collections+queues for each of the
FCC-depth where the FCC-depth is the number of irreversible moves performed so
far in the trail leading to the game position.

Then, once the solver ascends to a new depth, we recycle all the RAM and other
resources in the previous depth.

However, I found a problem with this scheme: we need the states in the previous
depths for tracing the final solution from the parent pointers. However, I
think I figured out a way to overcome this issue: we can keep a
num_active_children count in each state (which is always in the range 0-255
because there can be no more emerging single-card moves from that) which
is a reference count indicating the number of active derived states, and which
once it becomes 0, one can recycle the position's struct there, and decrement
its parent’s reference count (and so on). Since the reference count is only
one
byte, we should be able to put it in the high bits of the parent's pointer or
something like that.

At first I thought that now we no longer need the split into several levels of
depths, but then I realised that we need to do the sweep of the states from the
depth-specific-collection only when we ascend to a new depth because otherwise
the balanced-binary-tree implementing the collection's integrity will be
harmed.

Do you think this scheme is viable?

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
http://www.shlomifish.org/humour/ways_to_do_it.html

Except for boastfulness, rashness is my only defect!
     — Based on http://www.shlomifish.org/humour/TheEnemy/ .

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hi all,

after I had implemented the scheme I thought of in this post -
http://tech.groups.yahoo.com/group/fc-solve-discuss/message/1135 -
I found out that the new depth_dbm_fc_solver traversed more boards than
the normal dbm_fc_solver for one of the impossible deals. That indicated
that some deals were probably counted twice, so I decided to investigate.

What seems to have been the problem is the fact that some irreversible moves
actually consist of two irreversible moves. I.e: if we move the 2H from its
original
location under a non-parent card to the foundations, then it would be equivalent
to two
irreversible moves, because we may reach this in a different case by first
moving it into
a freecell (one irreversible move) and then moving it to the foundation (another
irreversible move). So I need to account for those in both the calculation of
the
rank of irreversibility of a single move, and the number of irreversible moves
performed
by the Horne's Prune's process.

After I fixed this problem, the number of derived states and their contents was
identical
between the depth_dbm_fc_solver and the dbm_fc_solver.

Regards,

	 Shlomi Fish

--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Interview with Ben Collins-Sussman - http://shlom.in/sussman

If God exists and is the ego‐maniacal, sadistic and helpless creature that is
described in the Old Testament, then we’re in deep trouble.

Please reply to list if it's a mailing list post - http://shlom.in/reply .

Hello,

I'm Danny A. Jones and I've returned from a long absence. I'm reading through
messages from the start of the year, so I may be replying to issues that have
already been solved. If so, then please skip over my replies until I'm curent.

I recently wrote an updated FreCell solver based on a request from Michael
Keller. He refers to your 2-freecell scenario as 8x2e0. Here is my solver's
solution to the two puzzles in question. It uses what I call "WKR" automoves --
5D on 4D in home cell when 3C and 3S present in their home cells. It also uses
full-power supermoves.

#00017760 Attempt: 1 8x2e0 (WKR  Super)  65 moves
64. 56. 37. 2a. 2h. 2h. 21. 2h. ah. 26.
3a. 3b. 36. 35. a6. 53_ 63_ 43_ 2a. 42.
43. 24. b2. 52. 5b. 53. 83. 85. 81. 82.
52. 87. b8. 45_ 42. 48. 75_ 71. 12_ 84_
8b. 17. 18. 17. 15. 12. b7. 47_ 64_ 6b.
16. b1. 41_ 64_ 6b. 3h. 2h. 76_ 53_ 78.
5h. 2h. 82. 62_ 74_
~~~~~

#00017880 Attempt: 1 8x2e0 (WKR  Super)  45 moves
5a. 15. 51_ 54. 2b. 23. 53. 23. 63. 6h.
ah. 7a. 8h. 52. b5. 65. 45_ 6b. 4h. 74.
b6. 76_ 7h. 16_ 47_ 47. 47. a7. 1a. 1b.
15. 16. 45. 17. 46. b7. 31_ 3b. 34. 35.
35. 34. 23_ 81. 8a.
~~~~~


--- In fc-solve-discuss@yahoogroups.com, Shlomi Fish <shlomif@...> wrote:
>
> Hi all,
>
> can anyone give a 2-Freecell solution for the #17760 and #17880 deals? For
> reference, I'm talking about (the game columns are placed in lines):
>
> # MS Freecell Deal No. 17760
> <<<<<<<<<<<<<<<<<<
> QS 5D 4H 8C 3D 9D AC
> 3H JC 3C 8S 4S 3S 4C
> KS JS TH KD 9S 6D 2S
> 5H 9H 9C 6H 8D AD 8H
> 5C 6S QC QH 2C QD
> 2D 2H KH KC AS 7C
> TD AH JH TC 6C 7S
> 7H 5S JD 7D TS 4D
> >>>>>>>>>>>>>>>>>>
>
> # MS Freecell Deal No. 17880
> <<<<<<<<<<<<<<<<<<
> 6S 5C 9H 5H 2D 8H 6H
> 3D 7C 2C 2S TH QD KD
> 3H AD QH 6C 7H KS KC
> 4D 8S 8C 9D JH 4S JD
> 6D AC JC TS 7S 3C
> 2H JS QC 3S AS 9S
> 5S TD 9C TC AH 7D
> QS 4H KH 8D 5D 4C
> >>>>>>>>>>>>>>>>>>
>
> The issue is that Danny A. Jones' solver reported them as solvable, but they
> end up as intractable in all the solvers I tried (fc-solve, my DBM
> Freecell solver, and patsolve claims to run out memory when trying to solve
> #17760 even though it consumed less than 3% of my machine's RAM.). I've tried
to
> solve deal #17760 manually, by patching PySol Fan Club Edition (I intend to
> share the patches), and by getting some help from fc-solve for detecting
> dead-ends moves, but I am unable to solve it.
>
> So any solutions to these deals (or proofs that they cannot be solved)
> would be appreciated.
>
> Regards,
>
>  Shlomi Fish
>
> --
> -----------------------------------------------------------------
> Shlomi Fish       http://www.shlomifish.org/
> Original Riddles - http://www.shlomifish.org/puzzles/
>
> Chuck Norris refactors 10 million lines of Perl code before lunch.
>
> Please reply to list if it's a mailing list post - http://shlom.in/reply .
>

Hi Danny,

I'm glad to have you back. See below for my response.

On Tue, 14 Aug 2012 17:44:20 -0000
"dannyjones183" <dannyjones183@...> wrote:

>
>
> Hello,
>
> I'm Danny A. Jones and I've returned from a long absence. I'm reading
> through messages from the start of the year, so I may be replying to
> issues that have already been solved.

That is the case for this message.

> If so, then please skip over my
> replies until I'm curent.
>
> I recently wrote an updated FreCell solver based on a request from
> Michael Keller. He refers to your 2-freecell scenario as 8x2e0. Here

I realise 8 is the number of columns and 2 is the number of freecells, but what
does e0 mean?

> is my solver's solution to the two puzzles in question. It uses what
> I call "WKR" automoves -- 5D on 4D in home cell when 3C and 3S
> present in their home cells.

Is this the so-called Raymond's prune? According to a previous post by Dr.
Tom Holroyd, this results in some solvable deals that are not solved.

> It also uses full-power supermoves.
>
> #00017760 Attempt: 1 8x2e0 (WKR  Super)  65 moves
> 64. 56. 37. 2a. 2h. 2h. 21. 2h. ah. 26.
> 3a. 3b. 36. 35. a6. 53_ 63_ 43_ 2a. 42.
> 43. 24. b2. 52. 5b. 53. 83. 85. 81. 82.
> 52. 87. b8. 45_ 42. 48. 75_ 71. 12_ 84_
> 8b. 17. 18. 17. 15. 12. b7. 47_ 64_ 6b.
> 16. b1. 41_ 64_ 6b. 3h. 2h. 76_ 53_ 78.
> 5h. 2h. 82. 62_ 74_
> ~~~~~
>
> #00017880 Attempt: 1 8x2e0 (WKR  Super)  45 moves
> 5a. 15. 51_ 54. 2b. 23. 53. 23. 63. 6h.
> ah. 7a. 8h. 52. b5. 65. 45_ 6b. 4h. 74.
> b6. 76_ 7h. 16_ 47_ 47. 47. a7. 1a. 1b.
> 15. 16. 45. 17. 46. b7. 31_ 3b. 34. 35.
> 35. 34. 23_ 81. 8a.
> ~~~~~

Well, I have for a long time expressed my distaste of the so-called "standard
notation" and here apparently, you have added "." and "_" which I'm not getting
to the bottom of.

Anyway, we already have solutions for these two 2-freecell deals.

Regards,

	 Shlomi Fish

>
>
> --- In fc-solve-discuss@yahoogroups.com, Shlomi Fish <shlomif@...>
> wrote:
> >
> > Hi all,
> >
> > can anyone give a 2-Freecell solution for the #17760 and #17880
> > deals? For reference, I'm talking about (the game columns are
> > placed in lines):
> >
> > # MS Freecell Deal No. 17760
> > <<<<<<<<<<<<<<<<<<
> > QS 5D 4H 8C 3D 9D AC
> > 3H JC 3C 8S 4S 3S 4C
> > KS JS TH KD 9S 6D 2S
> > 5H 9H 9C 6H 8D AD 8H
> > 5C 6S QC QH 2C QD
> > 2D 2H KH KC AS 7C
> > TD AH JH TC 6C 7S
> > 7H 5S JD 7D TS 4D
> > >>>>>>>>>>>>>>>>>>
> >
> > # MS Freecell Deal No. 17880
> > <<<<<<<<<<<<<<<<<<
> > 6S 5C 9H 5H 2D 8H 6H
> > 3D 7C 2C 2S TH QD KD
> > 3H AD QH 6C 7H KS KC
> > 4D 8S 8C 9D JH 4S JD
> > 6D AC JC TS 7S 3C
> > 2H JS QC 3S AS 9S
> > 5S TD 9C TC AH 7D
> > QS 4H KH 8D 5D 4C
> > >>>>>>>>>>>>>>>>>>
> >
> > The issue is that Danny A. Jones' solver reported them as solvable,
> > but they end up as intractable in all the solvers I tried
> > (fc-solve, my DBM Freecell solver, and patsolve claims to run out
> > memory when trying to solve #17760 even though it consumed less
> > than 3% of my machine's RAM.). I've tried to solve deal #17760
> > manually, by patching PySol Fan Club Edition (I intend to share the
> > patches), and by getting some help from fc-solve for detecting
> > dead-ends moves, but I am unable to solve it.
> >
> > So any solutions to these deals (or proofs that they cannot be
> > solved) would be appreciated.
> >
> > Regards,
> >
> >  Shlomi Fish
> >
> > --
> > -----------------------------------------------------------------
> > Shlomi Fish       http://www.shlomifish.org/
> > Original Riddles - http://www.shlomifish.org/puzzles/
> >
> > Chuck Norris refactors 10 million lines of Perl code before lunch.
> >
> > Please reply to list if it's a mailing list post -
> > http://shlom.in/reply .
> >
>
>



--
-----------------------------------------------------------------
Shlomi Fish       http://www.shlomifish.org/
Funny Anti-Terrorism Story - http://shlom.in/enemy

The one and only, 100% original, real, actual, and unmatched, Slimy Fish™!

Please reply to list if it's a mailing list post - http://shlom.in/reply .

> > I recently wrote an updated FreCell solver based on a request from
> > Michael Keller. He refers to your 2-freecell scenario as 8x2e0. Here
>
> I realise 8 is the number of columns and 2 is the number of freecells, but
what
> does e0 mean?

Michael Keller is working with a new class of freecell. Since he's not in full
production yet, I'll hold off on the details.

>
> > It uses what
> > I call "WKR" automoves -- 5D on 4D in home cell when 3C and 3S
> > present in their home cells.
>
> Is this the so-called Raymond's prune? According to a previous post by Dr.
> Tom Holroyd, this results in some solvable deals that are not solved.
>

I'll review this logic and get back to you.

> Well, I have for a long time expressed my distaste of the so-called "standard
> notation" and here apparently, you have added "." and "_" which I'm not
getting
> to the bottom of.

My apologies for the additional characters added to the standard notation. I
should have trimmed them before posting. FWIW: my solver appends a period (.) to
single-card moves and an underscore (_) to multiple-card moves. I'll go back
through your posts and see what notation you're now using instead of the
"standard notation".