The best way to save a large prefix tree

Question

I'm going to write a program that will be an AI for playing a board game against a player. I want to save each game in the prefix tree and look for it for similar games. But I am afraid that the tree may become too large for storage in memory. So the best way to save it. And be able to quickly find it. I don’t think writing it to a file is a good solution. Maybe in some DB king?

Answer 1

What you are looking for is a built-in database, and most of them are written in C ++, but there are some that have C # wrappers. I would recommend Berkeley DB for .NET (which is a wrapper around Oracle Berkeley DB ).

What I would recommend is that you create a unique hash for each prefix tree, where the generated hashes will have a locality that properly represents similar prefix trees: in other words, the hashes for two similar prefix trees should be very close to each other to a friend, The game you are talking about is called Tic-Tac-Toe, so hashing such Tic-Tac-Toe games should be easy, here are some links (I really didn’t read them, I just looked through the “Tic-Tac- hashing” Toe ", and these were the results):

• I think this might be a java example
• Strategic Reduction TicTacToe
• http://cg.scs.carleton.ca/~luc/1997notes/topic14/

The hash is then stored in DB Berkeley, and the prefix tree is stored in an Aux file, or if you want, you can also store it in a value. Since Berkeley DB stores key-value pairs, you can set the hash as a key and value to anything (i.e. the prefix tree or the path to the aux file containing your prefix tree). Then all you do is search for similar hashes and extract the appropriate trees from the aux file.

Berkeley DB stores similar keys in a sequence, so you can rely on it to not move the keys and not break the location of your hashes. Since the terrain will not be broken, you can perform additional optimization and get a large page of key-value pairs, as well as reduce the number of search queries and perform a disk search.