Working with a very large tree data structure: OutOfMemoryException

Question

I am creating a variant of a chess program, which should simultaneously generate and cross a very large tree structure. Each node has 10 bools, int, 8 ulongs, short [64] and 2 ulong [64] s. The root node receives some initial parameters, then the correct child nodes are determined programmatically (recursively) from there.

Basically, my program is constantly expanding this tree, while the user and the program take turns intersecting from the child node to the child node. Each time a new child node is selected, its parents and siblings are no longer needed and discarded. Since the tree reaches (on average) a depth of about 60 (from the initial root of the node), the number of allowed child nodes will naturally begin to decrease to about a depth of about 75, the tree resolves to one final node without further children.

At first, the logic of this looked pretty straightforward, but I constantly encounter an OutOfMemoryException, which completely kills further progress.

Below are some average values ​​for valid children for each generation:

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

In my real program, I can’t even completely expand the fifth generation. When I do not save the specific node data (I clear the node data when it was used to define its own children), I can completely expand the fifth generation, but hit the very strong wall on the sixth generation.

Ideally, I would like my program to eventually reach and then support 8 generations of nodes, as well as the “current” node. The more I look at it, the less likely it is.

I am tired of working with sqlite database, but could not quickly grow the tree.

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

Answer 1

Usually you have a rating when building trees that already gives you weight around the edges. Use these weights to see which paths will evaluate a stronger path than others, and work with these edges as soon as you see which ones are more valuable. Since you already have problems with the fifth generation in your algorithm, you only have to choose the depth on the more weighted branches and select one of them, rejecting several other branches. just an idea, so ... maybe you could run this on the third generation by choosing a method. As far as I know chess, this can only force you to make moves with more moving pawns, since they are likely to have a greater impact on the game, which may not be the best solution compared to the fifth generation moves. very interesting problem!

You must explore chess programming: Chess wiki program

More about engines: Chess programming wiki on engines

There is also a forum that discusses various approaches!

Answer 2

There is no general answer to your question. I assume that this large tree is calculated to determine the optimal moves for your computer program?

In this case, it may be useful for you to determine the utility function of the sequence of moves that measures the value of this series of moves in the game. If the goal is to achieve the maximum grade or something like that, that grade is a good utility function.

Sometimes you cannot find the exact utility function, in which case the general approach is to heuristically evaluate the utility. This is mainly an approximation, or a better guess. The better the heuristic, the better the adversary.

The reason you would like to have a utility measurement is to crop. As an example, one could cross the depth of a tree first a couple of times and calculate the minimum and maximum utility. These values ​​can help you trim the complete algorithm, i.e. you can use these boundaries to determine if your tree traversal algorithm can complete before completion.

Again, it all depends on your game mechanics and how you go through the tree, but hopefully this can make you think in the right direction.