This is a forward of an old email sent by Michael Mann (creator of the
C++/doxygen spin-off of Freecell Solver -
http://fc-solve.berlios.de/michael_mann/ ) which gives some information about
an extra move he had created for the Simple Simon solver.
It is forwarded here with his permissions.
Regards,
Shlomi Fish
---------- Forwarded Message ----------
Subject: Re: more on simple solving algorithms
Date: Thursday 31 October 2002
From: Michael Mann <mmann78_at_adelphia.net>
To: shlomif_at_vipe.stud.technion.ac.il
Sorry about replying to the wrong email address. It was the email
address I saw from your last response and I thought it would be better
to use it. I was mistaken.
As far as Public Domain, my theory is your work/code was free, so should
mine. Place it under Public Domain. This also goes for any more work I
submit to you.
Actually, my "solving algorithm" for each board was try a-star for 10000
iterations, if it can't be solved, try dfs for 10000 iterations, and if
that can't be solved, try a-star again with 500000 iterations. I
probably could have used resume, but I would restart the board from
scratch. I picked this algorithm up from trying to solve freecell
boards. I noticed that in boards where dfs had a high number of
iterations, a-star sometimes didn't and vice versa. The reason behind
it is probably has something to do with dfs and a-star having different
weights (only in dfs you can't change them except by changing the test
order).
I first tried BFS with freecell without a iteration limit and didn't get
very far. It ate up a lot of memory and didn't get really far (I would
run out of virtual memory only to find it only got about 8/9 deep). I
thought it may be more useful for freecell boards in the middle of a
game, or some of the other card games. I haven't done much with
soft-dfs, but I'll look into it.
The difference between
freecell_solver_sfs_simple_simon_move_whole_stack_sequence_to_false_parent
and freecell_solver_sfs_simple_simon_move_sequence_to_false_parent
is that the old test requires the entire stack to be a sequence. The
new test will move any sequence, whether it takes up the whole stack or
not. This is why I thought move_false_parent could replace
move_whole_s_s_to_false_parent, but in the little testing I did, boards
needed to go through significantly more iterations. I think the main
reason more boards were solved is that it will move single cards to
their false parent. This is why I started creating the test. I saw a
few boards that only went through a few iterations, and in looking at
it, I saw moves it could do, but didn't, mostly centered around moving a
single card to its false parent.
You used "suit" and "card_num" to save the suit and card number of a
particular card on the stack. Why not just represent it as a whole
card? In compact and indirect states, it will only take up a char of
space. I also think that amount of work the code needs to get a suit
and card number (finding the suit/card within the bits of a char) isn't
outwieghted by the number of times you copy a new cards to save. Look
for "next_card" and "saved_card" in the code. These are the variables
that I replaced "suit" and "card_num" with.
What generated you change log before? It looked to me like it was
manually entered.
I'll look into the bug and get back to you.
Mike
-------------------------------------------------------
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
http://www.shlomifish.org/humour/ways_to_do_it.html
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Sat May 30 2009 - 08:29:24 IDT