Hi!
Stephan Kulow suggested that instead of storing all the encountered states
in memory, Freecell Solver should use an LRU cache that will delete states
that were not used recently. It could be a good idea because it will enable
us to run longer while occupying the same amount of memory. Of course, some
dead end states will be checked again, but there are no free lunches in
programming.
Each state may contain a counter for the number of times it was reached by
the algorithm. And eventually, some of the states with the lowest counters
will be removed.
The problem is that some states cannot be removed from the cache. In the
case of DFS scans such states are those that are found in the current
solution path. In the case of A* they are all the states that are found in
the scan's priority queue (check out Justin HJ's page for more info) as
well as all their parents and forefathers.
Remember that there can be more than one thread in action, so it means we
have to go over all the threads, and mark all of their important states as
un-removable. Then we can remove some of the other states, based on their
popularity with the different active scans.
Naturally, assuming system threads are used, we will have to halt all the
threads before the cleanup is in gear.
I suppose BFS should be treated similiarly to A*, but since a pure BFS scan
makes little sense for Freecell-type games, it should not be a major concern.
Regards,
Shlomi Fish
----------------------------------------------------------------------
Shlomi Fish shlomif_at_techie.com
Home Page:
http://t2.technion.ac.il/~shlomif/
I don't believe in fairies. Oops! A fairy died.
I don't believe in fairies. Oops! Another fairy died.
Received on Wed Feb 28 2001 - 03:03:31 IST