I am building an agent for a board game that can have a relatively lot of time to think. Therefore, memory management should be efficient.

I am using a transposition table, where the nodes are stored in a list for each hash index.

There are 2 options that I came across:

  • the first is to limit the length of the lists per hash index and replace old items with new ones (there are different replacement schemes, TwoDeep is a popular one for minimax).

  • The second one is node recycling, which basically stores leaf nodes in a FIFO and discards the ones that were visited a long time ago.

I have a few questions

  1. Which one would be better for my case (or any other methods I am not aware of, not necessarily these)? It would also help if I could have pros/cons for each to drive me towards the right direction.

  2. How should we choose the replacement scheme for the first option (TwoDeep is more suitable for minimax, I would expect visit count or UCT value to be more applicable for MCTS)

  3. Would it be a good idea to combine the FIFO from node recycling with a list that stores the nodes per depth?

We could safely remove nodes from the table with a depth smaller than the depth of the current root, and then remove others from the FIFO.

Let me know if anything is not clear!

  • $\begingroup$ I made some changes to your post. In particular, I change the title. Make sure the current version of this post is consistent with what you were asking. If not, feel free to edit it again. To be honest, I don't understand what your main question is here: Can you clarify what your MAIN SPECIFIC question is here? $\endgroup$ – nbro Mar 8 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.