Hi everybody. I was mostly inactive for a couple of years because a health
problem put me on the sideline. But I'm ok now and I got a second computer in
May so I'm fired up again.
You've started the most interesting conversation yet. I thrive on these
little details. My solver is fast (~10000000 deals per hour _at_733mHz) not because of
any sophisticated algorithm but because I've experimented endlessly with
every tiny variation and the best order to apply them.
There is a very good and simple reason to move a card from a freecell (FC) to
an empty column (EC). Many games cannot be solved without it. Just CAN'T be
solved without it. To play with 3 freecells instead of four makes about 1% of
the deals unsolvable. To play without FC->EC is a similar handicap, although I
don't know what percentage of games it renders unsolvable. Of all the possible
variations and permutations of all the possible moves - and I've identified
hundreds of them - only one can be permanently discarded; Shlomi mentioned it
in his first letter today: there is no reason for FC->EC unless you intend to
put other cards on it.
Regarding BrFS: it's guaranteed to find the shortest possible solution
(fewest moves) but requires enormous amounts of memory. My solver keeps everything
in RAM (768 mBs) because I'm too impatient to wait for pageing. Of the MS32K
I've solved only a dozen or so with BrFS. One of the easiest deals to solve this
way is 1941 because its tree has far fewer branches, or shorter ones, than
nearly all others.
My solver is quick only when solving a long range of deals using DFS. BrFS
takes forever looking for shortest solutions because all moves must be available
and RAM fills up for almost every deal before failing. A* is not possible for
freecell because the solver must know in advance how many moves will be in
the shortest solution. One can approximate A* with Iterative Deepening, where
one makes a lowball guess, runs until failure, then increases the guess by one
and tries again. Repeat until the shortest solution is found. When I was
searching for short freecell deals I didn't use ID but set the depth at 20 and just
let it run over the MS32K. Averaged 11 deals per hour with 1gH Intel and 2gB
RAM. My children grew up, moved out, married and had children of their own
during the time that needed.
I know a couple of reasons to sort the columns while running, but never had
to do that. Now I suspect that some deals are unmanageable for me because some
(or many, or all) of the positions are repeated but with columns permuted. So
sorting columns is on my to-do list.
Bill Raymond
Received on Mon Nov 24 2003 - 11:02:05 IST