Hi all,
yesterday I came up with a scheme for combining some of the best aspects of the
DBM-FC-Solver and the FCC-FC-Solver (Fully connected components). What I had in
mind was that we'll keep an array of states collections+queues for each of the
FCC-depth where the FCC-depth is the number of irreversible moves performed so
far in the trail leading to the game position.
Then, once the solver ascends to a new depth, we recycle all the RAM and other
resources in the previous depth.
However, I found a problem with this scheme: we need the states in the previous
depths for tracing the final solution from the parent pointers. However, I
think I figured out a way to overcome this issue: we can keep a
num_active_children count in each state (which is always in the range 0-255
because there can be no more emerging single-card moves from that) which
is a reference count indicating the number of active derived states, and which
once it becomes 0, one can recycle the position's struct there, and decrement
its parent’s reference count (and so on). Since the reference count is only one
byte, we should be able to put it in the high bits of the parent's pointer or
something like that.
At first I thought that now we no longer need the split into several levels of
depths, but then I realised that we need to do the sweep of the states from the
depth-specific-collection only when we ascend to a new depth because otherwise
the balanced-binary-tree implementing the collection's integrity will be
harmed.
Do you think this scheme is viable?
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
http://www.shlomifish.org/humour/ways_to_do_it.html
Except for boastfulness, rashness is my only defect!
— Based on http://www.shlomifish.org/humour/TheEnemy/ .
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Thu Jul 26 2012 - 04:36:42 IDT