Dealing with a very large tree-like datastructure: OutOfMemoryException

Question

I'm creating a variant of a chess-like program that needs to simultaneously generate and traverse a very large tree-like structure. Each node has 10 bools, an int, 8 ulongs, a short[64] and 2 ulong[64]s. The root node receives some initial parameters, then the valid children nodes are determined programatically (recursively) from there.

Basically, my program continuously grows this tree while the user and the program takes turns traversing from child node to child node. Each time a new child node is 'chosen', it's parent and siblings are no longer needed and are discarded. As the tree reaches (on average) a depth of about 60 (from the initial root node), the number of valid children nodes will naturally begin to dwindle until at about a depth of about 75, the tree resolves into one final node with no further children.

The logic behind this looked fairly straight forward at first, but I'm constantly hitting an OutOfMemoryException that is outright killing any further progress.

The following at some averages for valid children per 'generation':

Generation    New Nodes
1             1    
2             20
3             4,000
4             30,000
5             2,200,000
6             > 50,000,000

In my actual program, I can't even fully expand the fifth generation. When I don't persist the node specific data (I clear a node's data once it's been used to determine it's own children) I can fully expand the 5th generation, but hit a very solid wall partway though the sixth generation.

Ideally, I would like my program to eventually reach and then maintain 8 generations of nodes afer the 'current' node. The more I look at this, the less likely this seems.

I tired running this with an sqlite database, but it wasn't able to grow the tree fast enough.

Does anyone know of any potential alternatives to dealing with a very large tree structure?

Answer 1

Typically you have an evaluation when building the trees, which already gives you a weight on the edges. Use those weights to see which pathes will evaluate a stronger path than others and work on those edges, as soon as you can see which are more valuable. As you already have problems with the fifth generation in your algorithm, you only have choices to go in depth on higher weighed branches, and choose one of those, dismissing numberous other branches. just an idea so... perhaps you could run this on the third generation, choosing which way to go. As far as i know chess, this might run you into making only moves with more movable pawns as they probalby will have more impact on the game, which might not be the best solution as compared to fifth generation moves. very interesting issue!

You should investigate on chess programming: Chess programming wiki

Here is more on engines: Chess programming wiki on Engines

There is a forum also, where different approaches are discussed!

Answer 2

There is no general answer to your question. Im going to assume that this large tree is computed to determine optimal moves for your computer program?

In that case it may be helpful for you to define a utility function of a sequence of moves, that measures the value of making this series of moves in the game. If the objective is to reach a maximum score or something like that, that score is a good utility function.

Sometimes you cannot come up with an accurate utility function, in which case a common approach is to make a heuristic evaluation of the utility. Basically it's an approximation, or a best guess. The better the heuristic the better the adversary.

The reason you would like to have a utility measurement is the perform pruning. On example would be to traverse the tree depth-first a couple of times and compute the minimum and maximum utility. These values can help you prune the full algorithm, meaning you can use these bounds to determine if your tree-traversal algorithm could terminate before completion.

Again, it all depends on your game mechanics and how you traverse the tree, but hopefully this can get you thinking in the right direction.