On Tue, 13 Feb 2001, Markus F.X.J. Oberhumer wrote:
> Shlomi,
>
> below you will find my final python bindings, ready for inclusion
> in 1.4.2. I'd still ask you to have a look - esp. the result
> from fcs_move_get_num_cards_in_seq() looks suspicious.
>
Pay attention to the move type. It is move type
FCS_MOVE_TYPE_STACK_TO_FREECELL in which this field is irrelevant because
only one card can be moved at a time.
Would it be possible for the bindings to return an array of all the moves
that should be made till the solution, instead of just one? It would be a
waste of resources to call it each time the user requires a hint.
And here are some other thoughts:
1. The bindings should use Soft-DFS as it is much more resume friendly
than DFS.
2. The bindings should be compiled with INDIRECT_STACK_STATES. That
generally consumes much less memory and can scale well even on games of
Der Katzenschwanz (excuse my poor German) and Die Schlange. BTW, I suggest
that Die Schlange will be treated as Der Katz because Freecell Solver
excpects games to be as close to Freecell as possible.
3. You should supply an initialization option to initialize the tests
order, because it is a very useful option (see below).
> The second file is an unrelated patch against the 1.4.1 source
> tree - mainly fixing spelling errors and constifying some fields.
>
Applied.
> The next step would be speeding up your algorithm ;-) I've had
> a quick look but didn't get too far - what are you using,
> brute force or some sort of alpha/beta pruning ?
>
Freecell Solver solves game using logical multi-moves (i.e: several
supermoves that it thinks _might_ make sense). It can do it using either
hard DFS, Soft (i.e: without procedural recursion) DFS, A*, or BFS. BFS
does not work well because the number of possible states of distance N is
too large to be effective, at least for multi-moves. A* gives mixed
results.
I have 1000 test boards at home and while limiting them to 150000
iterations, I get that the linear average of A* is about 2 times of DFS.
My main problem is finding a good weight function.
In order to improve the algorithm, Dr. Tom Holroyd (who is
subscribed to fc-solve-discuss) suggested using threads that will
operate on the same state collection. Each thread will have a different
tests order, or a different weight function, which will increase the
chance that one of them will work.
This can be implemented not only using system threads, but also with
soft-threading, which means that the program will switch-task between them
by limiting them to a certain number of iterations.
I'm planning to implement it in the 1.7.x tree, which hopefully will lead
to Freecell Solver 2.0.x.
Regards,
Shlomi Fish
> Markus
>
> On 11-Feb-2001 Shlomi Fish wrote:
> >
> > I found a bug in Freecell Solver which became apparent in the python
> > bindings which Markus wrote. In any case, I fixed it (it's a two line
> > patch that involves setting two members of instance to NULL).
> >
> > Now, the python program works perfectly, but then again, it only runs
> > three boards. I suggest making a combo of my make_pysol_freecell_board.py
> > and it, so we can check it on a sequence of games. I can do that, but I
> > have some other stuff on my head now, including some tests.
> >
> > Anyway, you can download it from the site.
> >
> > Markus, let me know when the bindings are going to be released under the
> > public domain, so I can put it on the Freecell Solver sites.
> >
> > Regards,
> >
> > Shlomi Fish
> >
> >
>
>
> ---- Markus F.X.J. Oberhumer _at_ http://www.oberhumer.com ----
> ---- 5E CB 5C 85 DE AF 9E BF E9 DA 7E 6A 39 F8 CC 67 ----
>
> 3 WARPS TO URANUS
>
>
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_techie.com
The prefix "God Said" has the extraordinary logical property of
converting any statement that follows it into a true one.
Received on Tue Feb 13 2001 - 01:57:29 IST