Currently Freecell Solver stores the entire state for every state in
memory. This is a large overhead because a Freecell State is quite large.
During the Freecell Solver lecture, Nadav Har'El suggested that for
every state only the deltas to the originating state would be stored. (in
a similar manner to what source control systems like RCS do)
In order to compare two states for equality we would need to re-create the
state based on the original state. That would be very slow. The way I see
it, we have two ways to minimize it:
1. Make sure the states are accompanied by a very large hash function, to
make sure comparison happens very rarely.
2. Store some of the complete states in a cache (such as a Least-Recently
Used or LRU cache), and make sure one can lookup them at any point of the
trail to the original state.
I'm not sure whether we will see a speed improvement here. Bill, did you
happen to implement such a Scheme for your solver yet? If so, did it
result in a speed improvement?
In any case, I'll probably delay implementing this Scheme to later on as I
only have too many things which I'd like to accomplish for the 2.5.x
branch.
Regards,
Shlomi Fish
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_iglu.org.il
He who re-invents the wheel, understands much better how a wheel works.
Received on Tue Jun 04 2002 - 23:55:41 IDT