On Sunday 18 Oct 2009 23:40:49 Gary Campbell wrote:
> I'm not sure why Shlomi Fish or Michael Keller didn't mention
> my solver/player, but it has no difficulty with this game or your
> position within it. Here is the last point where your solution is
> solvable. Beyond that you have made the position impossible.
> Please, people, mention my solver when you need to solve
> something beyond the capability of FCPro and you would like
> to use Windows as a program base. I would appreciate it.
> -Gary Campbell
> (solver available free at http://numin8r.us/programs
>
Indeed, one omission of my email was not mentioning alternative solvers to
Freecell Solver. I apologise for that. The most complete list I know of (and
which I prepared and maintain) is:
http://fc-solve.berlios.de/links.html#other_solvers
I tend to think that my solver is the most powerful, featureful, portable and
most polished one (see for example -
http://fc-solve.berlios.de/features.html
), and on top of it is distributed under the MIT/X11 Licence which is
practically public domain. But naturally, it is possible that a different
solver will supercede it in the future.
Gary, regarding your solver, can you answer the following questions:
1. How many board positions can it handle before it runs out of memory? Using
my Indirect-stack-states scheme (where I store pointers to stacks in the stack
collection instead of storing copies) I was able to scale Freecell Solver to a
million states and more on a 32-bit x86 machine. On a 64-bit machine (Alpha
AXP, x86-64, UltraSPARC, etc.) with enough RAM, it may be more, but naturally
the pointers there are larger.
Your solver seems to be a small 8086/8088 COM object binary and as such can
probably only map 640KB of RAM. So assuming every board position consumes 8-
bits of RAM (which is probably way-too-optimistic), it can only go up to an
optimistic upper limit of 640,000 positions before exhaustion.
I should note that I have an idea for states that are packed bit-by-bit as a
big delta from the original state (I borrowed the idea from the original Don
Woods solver.). This way a column in each state will usually occupy much less
than even 32-bits. This will require some major internal changes in fc-solve
and may make the solution slower due to the packing and unpacking, but it will
conserve a lot of memory.
2. What happens when your solver runs out of memory? Does it crash? Does it
gracefully exit? Does it prune dead ends? Will it continue to run
indefinitely?
I should note that when my solver fails a malloc() it would try to access a
NULL pointer and crash the entire process. My todo list had an item for
implementing a graceful return propagation on a failed memory allocation, but
it's not high on my priority list, for many reasons.
3. Does your solver have an automated test suite? If not, how do you make sure
bugs don't creep in? I should note that you can use this Perl/CPAN module I
created (which is gratis and open-source) to help making sure the solutions
are correct:
http://fc-solve.berlios.de/verify-code/
Regards,
Shlomi Fish
>
> QC TS 9H KS 9D 7H QH 2D AC 2H
> QD 3S 5C 6C 8S 7C KH 6D KD KC JC
> QS JH 2S TC 7D 3D 8H
> 5S 2C 3H AS 6S 9S 4H
> 8C 7S 5D 5H 3C
> 6H TH JD JS
> 4C TD 4D 4S
> 9C
> 8D
> GAME #715037 is solved partially as follows: {15 1 0 0 -2 -2 524 524 2 2 0
> 0 68 68 2000 100} 8h 5d 5c 5b 5a d5 65 65 68 65
> 6d 76 72 a2 6a[76]74 a7 6a 83
> 72 c6 38 7c a7 83 38 6a 83 c6
> 56 7c 38 83 ??
This notation seems strange, incomprehensible and too terse. What does it all
mean?
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
The Case for File Swapping - http://shlom.in/file-swap
Chuck Norris read the entire English Wikipedia in 24 hours. Twice.
Received on Mon Oct 19 2009 - 04:03:33 IST